Полные системы функций алгебры логики

Система функций алгебры логики F={f₁, f₂,…, f_s,…}Í P₂ называется полной или функционально полной, если любая функция алгебры логики может быть записана в виде формулы через функции этой системы (или, как говорят, выражена формулой над F).

В соответствии с этим определением системы функций {Ø,&,Ú}, {Ø,&}, {Ø,Ú}, {Ø,®}, а также {¯} и {½} являются функционально полными.

Имеются и другие полные системы функций. Определить полноту некоторой системы функций можно с помощью следующей теоремы.

Теорема. О полных системах функций алгебры логики

Пусть имеются две системы функций алгебры логики: F={f₁, f₂,…, f_p,…} и G={g₁, g₂,…, g_r,…}, относительно которых известно, что система F полна и каждая её функция может быть выражена формулой через функции системы G. Тогда система функций G – является полной.

Пример: покажем функциональную полноту следующих систем: (1) G₁={º,Ú,0}, (2) G₂={Å,&,º} и (3) G₃={1,·,Å}, где «·» – это обычное умножение.

(1) Известно, что система функций {Ø,Ú} является полной. Поскольку «Ú» имеется в G₁, а «Ø» выражается формулой , то G₁ тоже полна.

(2) Известно, что система функций {Ø,&} является полной. Поскольку «&» имеется в G₂, а «Ø» выражается формулой , то G₂ тоже полна.

(3) Т.к. система {Ø,&} является полной и х·у = х&у, а , то G₃ – полная система функций. Система G₃ играет особую роль в алгебре логики, т.к. формула, сконструированная из функций {1,·,Å} и скобок, после раскрытия скобок и несложных алгебраических преобразований переходит в полином Жегалкина(СПНФ).

Другой важный критерий полноты системы функций алгебры логики связан с понятием замыкания и замкнутого класса.

Пусть М Í Р₂ – некоторое подмножество множества всех функций алгебры логики. Замыканием М называется множество тех истинностных функций, которые могут быть выражены формулой над М.

Замыкание М обозначается [M].

Класс функций М называется функционально замкнутым или просто замкнутым, если его замыкание совпадает с ним самим, т.е. [M] = М.

Определение полной системы функций можно сформулировать в терминах замыканий: система функций М является функционально полной, если её замыкание совпадает с множеством всех функций алгебры логики, т.е. [M]=P₂.