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

Повторим последний вывод п. 2.3.1 (с учетом сделанного там замечания):

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

aïa = (НЕ),

(И),

(aïa)ï(bïb) = = a b (ИЛИ).

Здесь мы привели один из способов доказательства полноты системы логических функций:

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

Таким образом, одна функция штрих Шеффера является функционально полной системой функций.

Заметим: Система НЕ, И, ИЛИ излишне полна, т.е. в ней имеются «лишние» функции.

Действительно, если имеем НЕ и И, то ИЛИ можно получить следующим образом

Если имеем НЕ и ИЛИ, то И можно получить так

.

Неизлишне полная система логических функций (система, из которой нельзя исключить никакую функцию без потери полноты) называется минимальным базисом.

2. Стрелка Пирса

f = a↓b= ,

a↓a = = (НЕ),

(ИЛИ),

= (И).

Значит, функция стрелка Пирса является функционально полной системой функций.

3. Импликация и «0»

f = a→b = b,

a→0 = 0 = (НЕ),

→b = b = a b (ИЛИ),

(И).

Следовательно, система {→ и «0»} является функционально полной системой функций.

Другой способ доказательства полноты системы логических функций вытекает из теоремы Поста–Яблонского.