Функционально полные системы булевых функций

Система (совокупность) булевых функций {Т. F-2…, F_n} называется функционально полной, если любая булева функция может быть записана в виде формул через функции этой системы. Одним из способов получения полных систем является использование некоторых существующих, ранее выявленных полных систем.

Пример 4.5. Известно, что система So = {A, V, ->} — полная система функций (И, ИЛИ, НЕ). Это вытекает из того факта, что любую булеву функцию можно представить в дизъюнктивно и конъюнктивно нормальной формах. Являются ли системы S = {А, ->} и = {V, -«} полными?

Решение. Для доказательства полноты системы Si нужно установить, что недостающая относительно So операция дизъюнкции может быть выражена через остальные, т. е. для доказательства достаточно выразить каждую функцию из полной системы через функции проверяемой системы. Такое подтверждение дает правило дс Моргана и двойного отрицания:

Для доказательства полноты системы S₂ нужно установить, что недостающая относительно So операция конъюнкции может быть выражена через остальные, т. е. для доказательства достаточно выразить каждую функцию из полной системы через функции проверяемой системы. Такое подтверждение дает правило де Моргана и двойного отрицания:

Итак, системы Si, S₂ являются полными. ?

Пример 4.6. Известно, что система Si = {Л,->} — полная система функций (И, НЕ). Является ли система S3 = {Л, 0,1} полной?

Решение. Является, так как отрицание в Si может быть выражено через операции S₃ следу юн Ц1 м образом:

Проверка осуществляется по таблице истинности. ?

В качестве других функционально полных систем можно отнести системы {0},.

{$Д};