Зависимость между булевыми функциями

Из таблицы 9.1 видно, что между функциями имеется зависимость:

Из этих зависимостей следует, что любая функция двух перемен­ных (включая константы) выражается в аналитической форме через совокупность шести функций, содержащей отрицание и любую из каждой пары функций , , , , . Например, такой совокупностью могут служить функции: константа 0, отрицание , конъюнкция , дизъюнкция , эквиваленция и импликация . Эта совокупность функций используется в исчислении высказываний.

Выбранная таким способом совокупность шести функций явля­ется избыточной. Можно показать, что импликация и эквиваленция выражаются через остальные функции этой совокупности:

Для этого достаточно построить таблицу соответствия и срав­нить ее с табл. 9.1:

Таким образом, комплект элементарных функций сокращается до четырех: константа 0, отрицание , конъюнкция , дизъюнкция . Этот комплект обладает существенными удобствами и часто применяется на практике, но и он может быть сокращен. Далее будет показано, что любые булевы функции могут быть выражены через отри­цание и конъюнкцию или через отрицание и дизъюнкцию.

Более того, для записи любой булевой функции достаточно только одной из двух элементарных функций - стрелки Пирса или штриха Шеффера. Это вытекает из следующих соотношений (их доказатель­ство приводится аналогично с помощью таблиц соответствия):

Дата добавления: 2014-01-13