Система функций алгебры логики F ={ f 1, f 2,…, fs,…}Í P 2 называется полной или функционально полной, если любая функция алгебры логики может быть записана в виде формулы через функции этой системы (или, как говорят, выражена формулой над F).
В соответствии с этим определением системы функций {Ø,&,Ú}, {Ø,&}, {Ø,Ú}, {Ø,®}, а также {¯} и {½} являются функционально полными.
Имеются и другие полные системы функций. Определить полноту некоторой системы функций можно с помощью следующей теоремы.
Теорема. О полных системах функций алгебры логики
Пусть имеются две системы функций алгебры логики: F ={ f 1, f 2,…, fp,…} и G ={ g 1, g 2,…, gr,…}, относительно которых известно, что система F полна и каждая её функция может быть выражена формулой через функции системы G. Тогда система функций G – является полной.
Пример: покажем функциональную полноту следующих систем: (1) G 1={º,Ú,0}, (2) G 2={Å,&,º} и (3) G 3={1,·,Å}, где «·» – это обычное умножение.
(1) Известно, что система функций {Ø,Ú} является полной. Поскольку «Ú» имеется в G 1, а «Ø» выражается формулой , то G 1 тоже полна.
|
|
(2) Известно, что система функций {Ø,&} является полной. Поскольку «&» имеется в G 2, а «Ø» выражается формулой , то G 2 тоже полна.
(3) Т.к. система {Ø,&} является полной и х · у = х & у, а , то G 3 – полная система функций. Система G 3 играет особую роль в алгебре логики, т.к. формула, сконструированная из функций {1,·,Å} и скобок, после раскрытия скобок и несложных алгебраических преобразований переходит в полином Жегалкина(СПНФ).
Другой важный критерий полноты системы функций алгебры логики связан с понятием замыкания и замкнутого класса.
Пусть М Í Р 2 – некоторое подмножество множества всех функций алгебры логики. Замыканием М называется множество тех истинностных функций, которые могут быть выражены формулой над М.
Замыкание М обозначается [ M ].
Класс функций М называется функционально замкнутым или просто замкнутым, если его замыкание совпадает с ним самим, т.е. [ M ] = М.
Определение полной системы функций можно сформулировать в терминах замыканий: система функций М является функционально полной, если её замыкание совпадает с множеством всех функций алгебры логики, т.е. [ M ]= P 2.