Полные системы функций. Система функций {}

Теорема. Всякая булева функция порождается некоторой формулой, в которой есть только операции .

Доказательство. Пусть некоторая булева функция. Для нее можно поострить таблицу истинности, в которой будет 2n строк. Каждую строку можно представить в виде конъюнкции переменных х1,…хn, куда входит либо , либо . Если значение конъюнкции будет равно 1, то всю функцию можно представить в виде дизъюнкции этих конъюнкций.

Пример.

x

y

f(x,y)

0

0

1

0

1

1

1

0

0

1

1

1

Получим СДНФ, используя таблицу истинности.

 

Возникает вопрос: Существуют ли другие системы булевых функций, с помощью которых можно выразить все другие функции?

 

Логика - доступно для всех