RSS   мы в социальных сетях

Суперпозиция политики

Оцените материал
(0 голосов)
Конъюнкция, дизъюнкция и отрицание являются полным набором (в этом убедились в разд. 5), но не являются базисом, так как это набор избыточен, поскольку с помощью правил де Моргана можно удалить конъюнкцию или дизъюнкцию. Любую функцию можно представить в виде полинома Жегалкина (разд. 6). Ясно, что функции конъюнкция, сложение по модулю 2 и константы 0 и 1 являются полным набором, но эти четыре функции также не являются базисом, поскольку 1+1=0, и поэтому константу 0 можно исключить из полного набора (для построения полиномов Жегалкина константа 0 необходима, поскольку выражение “1+1” не является полиномом Жегалкина). Легко видеть, что одним из способов проверки полноты какого-то набора К является проверка того, что через функции из этого набора выражаются функции другого полного набора (можно проверить, что через функции из К можно выразить конъюнкцию и отрицание или дизъюнкцию и отрицание. Существуют такие функции, что одна такая функция сама является базисом (здесь достаточно проверить только полноту, неизбыточность очевидна). Такие функции называются шефферовскими функциями. Это название связано с тем, что штрих Шеффера является базисом. Заметим, что вычислительное устройство чаще всего базируется на полном наборе функций (часто на базисах). Если в основе устройства лежат конъюнкция, дизъюнкция и отрицание, то для этих устройств важна проблема минимизации ДНФ; если в основе устройства лежат другие функции, то полезно уметь алгоритмически минимизировать выражения через эти функции.
Последнее изменение Воскресенье, 09 Февраля 2014 18:10
0
РосУкрИнформ

РосУкрИнформ

Информационное агентство

Госсовет Крыма сегодня принял Конституцию РК

11 Апреля 2014

Госсовет Крыма сегодня принял Конституцию РК

На заседании Государственного Совета Крыма сегодня была принята Конституция Республики Крым, состоящая из 10 глав и 95 статей. Основные положения схожи со статьями Конституции РФ.... ДАЛЕЕ

Чем закончится противостояние в Киеве?
Янукович станет украинским Лукашенко - 2.7%
Оппозиция возьмет власть в руки - 12.1%
Украина расколется на несколько частей - 23.9%
Федерализация и мир во всем мире - 11.2%
США и Россия разделят Украину по Днепру - 22%
Ничего не изменится: воровали и будут воровать - 28.1%

Результаты: 636
Голосование на этот опрос закончилось в: 03 2014-03-03 2014
РОСУКРИНФОРМ | ИНФОРМАЦИОННОЕ АГЕНТСТВО | ВСЕ ПРАВА ЗАЩИЩЕНЫ.