Теорема. Всякая булева функция порождается некоторой формулой, в которой есть только операции .
Доказательство. Пусть некоторая булева функция. Для нее можно поострить таблицу истинности, в которой будет 2n строк. Каждую строку можно представить в виде конъюнкции переменных х1,…хn, куда входит либо , либо . Если значение конъюнкции будет равно 1, то всю функцию можно представить в виде дизъюнкции этих конъюнкций.
Пример.
|
x |
y |
f(x,y) |
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
Получим СДНФ, используя таблицу истинности.
Возникает вопрос: Существуют ли другие системы булевых функций, с помощью которых можно выразить все другие функции?