П. 2.4. Полные системы булевых функций

Определение 2.10. Система булевых функций называется полной, если произвольная булева функция может быть выражена через функции .

Теорема 2.6. Полной является система функций .

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

Согласно теореме 2.4. любая булева функция представима в виде СДНФ либо СКНФ, в выражении каждой из которых используется только данная функция .

Полноту других систем можно доказать с помощью следующей теоремы.

Теорема 2.7. Пусть система – полна и любая из функций может быть выражена через функции , тогда система также полна.

Например: Доказать, что система функций является полной.

Решение:

Пусть , , , , . Выразим через : , , .

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

Определение 2.11. Логическая функция штрих Шеффера (и – не) обозначается и задается следующей таблицей истинности:

Функция штрих Шеффера является полной.

; ; ; ; .

Определение 2.12. Логическая функция стрелка Пирса (или – не) обозначается и задается следующей таблицей истинности:

Вопросы и задания.

1. Сколько существует логических функций одной переменной, двух, трех?

2. Привести к дизъюнктивной нормальной форме (ДНФ):

а) ;

б) ;

в) ;

г) ;

д) .

3. Привести к конъюнктивной нормальной форме (КНФ):

а) ;

б) ;

в) ;

г) ;

д) .

4. Приведите примеры нескольких формул системы , представляющих собой СДНФ.

5. Приведите примеры нескольких формул системы , представляющих собой СКНФ.

6. Приведением к нормальным формам установить, является ли формула тождественно истинной, тождественно ложной и выполнимой.

а) ;

б) ;

в) ;

г) ;

д) .

7. Привести к совершенной нормальной дизъюнктивной функции (СДНФ), используя равносильные преобразования:

а) ;

б) ;

в) ;

г) ;

д) .

8. Привести к совершенной нормальной конъюнктивной функции (СКНФ), используя равносильные преобразования:

а) ;

б) ;

в) ;

г) ;

д) .

9. Для каждой из следующих формул найдите СДНФ с помощью таблицы истинности:

а) ;

б) ;

в) ;

г) ;

д) .

10. Для каждой из следующих формул найдите СДНФ с помощью таблицы истинности:

а) ;

б) ;

в) ;
г) ;
д) .

11. Используя СДНФ, найдите формулу, принимающую значения 1 на следующих наборах значений переменных, и только на них.

а) ;

б) ;

в) ;
г) ;
д) .

12. Используя СКНФ, найдите формулу, принимающую значения 0 на следующих наборах значений переменных, и только на них.

а) ;

б) ;

в) ;
г) ;
д) .

13. Найти формулу, определяющую функцию по данной таблице истинности:

x	y	z

14. Докажите, что система полна.

15. Выразите и через и –, доказав тем самым полноту системы .

16. Выразите функции через стрелку Пирса.

Дата добавления: 2014-01-07