Полнота

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

Из представления любой логической функции булевой формулой следует, что система {Ú, Ù, Ø}функционально полна, причем является функционально избыточной. Функционально полной будет и любая система, через функции которой можно выразить дизъюнкцию, конъюнкцию и отрицание.

1. Система {Ù, Ø}- функционально полная. Действительно, из закона де Моргана = Ù следует, что Ú и, следовательно данная система функционально полна.

2. Система {Ú, Ø}- функционально полная. Это вытекает из следующих формул: = Ú , Ù .

Пример 8.1. Выразить функцию Ú ( Ú ) в системе {Ù, Ø}.

Ú ( Ú ) .

Пример 8.2. Запишем формулу из примера 9.1 в системе {Ú, Ø}.

Ú ( Ú ) .

3. Система {|}- штрих Шеффера функционально полная. Ранее было установлено, что | = Ú , тогда | = . При = = x последняя формула примет вид x | x = , получаем:

= = ( | )|( | ).

Следовательно, система {Ù, Ø} может быть представлена формулами над {|}. Откуда и следует полнота {|}.

4. Система {¯}- стрелка Пирса функционально полная. Известно, что

¯ = . Отсюда легко получить: = x ¯ x, Ú =

=( ¯ )( ¯ ). Система {¯}- функционально полная.

5. Система {Ù, Å, 1} -функционально полная, т.к. , и следовательно любая функция полной системы {Ù, Ø} может быть представлена формулами над .