Изменения

Названия булевых функций от одной переменной:

!Обозначение

!Название

|3-ИЛИ, максимум

|}

=== Тождественность и двойственность ===

Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так:<br />

<math>f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)</math>

Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.

{{main|Теорема Поста о полной системе функций}}

=== Дизъюнктивная нормальная форма (ДНФ) ===

''Простой конъюнкцией'' или ''конъюнктом'' называется конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза. ''Дизъюнктивной нормальной формой'' или ''ДНФ'' называется дизъюнкция простых конъюнкций.

Элементарная конъюнкция

=== Конъюнктивная нормальная форма (КНФ) ===

''Конъюнктивная нормальная форма'' (КНФ) определяется двойственно к ДНФ. ''Простой дизъюнкцией'' или ''дизъюнктом'' называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкций.

{{main|Полином Жегалкина}}

{{main|Реализация булевой функции схемой из функциональных элементов}}