double arrow

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

Система функций алгебры логики 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.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: