2.3. ФУНКЦИОНАЛЬНАЯ ПОЛНОТА

Как видно из табл. 2.1, все функции попарно связаны между собой посредством отрицания, т. е. .

Отсюда следуют зависимости для функции одной переменной (двойное отрицание) и для функций двух переменных:

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

При этом отрицанию соответствует связка не, конъюнкции — и, дизъюнкции — или, импликации — если, то и эквиваленцни — если и только если.

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

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

Система функций, суперпозицией которых может быть представлена любая функция из некоторого множества логических функций, называется функционально полной. Если в такой системе допускаются константы 0 и 1, то ее называют ослабленпо функционально полной. Система функций является минимально полной, если удаление из нее любой функции превращает эту систему в неполную. Необходимое и достаточное условие функциональной полноты состоит в том, что выбранные функции должны в совокупности обладать всеми свойствами, приведенными в табл. 2.2 (звездочкой отмечены свойства, которыми обладает данная функция).

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

Таблица 2.2