Функционально полные системы.

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

Из теоремы 8.2 следует, что система является функционально полной. Равным образом, функционально полна любая система , через функции которой можно выразить конъюнкцию, дизъюнкцию и отрицание. Действительно, для любой логической функции из такой системы следует составить булеву формулу (а она обязательно существует согласно теореме 8.2) и потом выразить в ней конъюнкцию, дизъюнкцию и отрицание через функции системы . Аналогично обосновывается более общее утверждение.

Теорема 11.1. Если все функции функционально полной системы представимы формулами над системой , то система также функционально полна.

Пример 1.

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

.

С точки зрения функциональной полноты систему следует считать избыточной: она сохраняет свойство полноты и при удалении из неё конъюнкции или дизъюнкции. Однако легко видеть из приведённого примера, что, хотя системы и не являются избыточными, зато формулы в них получаются гораздо длиннее: замена одной операции на другую вносит в формулу сразу три лишних отрицания.

б) Системы (штрих Шеффера) и (стрелка Пирса) являются функционально полными.

.

Таким образом, система сводится к системе , а система - к системе .

в) Система ( умножение по модулю 2, сложение по модулю 2 – см. пункт 1 лекции № 8)) является функционально полной. Поскольку , данная система сводится к .

На свойствах этой системы остановимся подробнее.