<<
>>

1.9.1. Система функций {}

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

Доказательство.

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

Пример.

x y f(x,y)
0 0 1
0 1 1
1 0 0
1 1 1

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

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

<< | >>
Источник: Викентьева О. Л.. Математическая логика и теория алгоритмов. Конспект лекций для студентов специальностей АСУ, ЭВТ, КЗИ. Пермь, 2007г.. 2007

Еще по теме 1.9.1. Система функций {}: