Теорема Поста
[предыдущая глава]  [оглавление]  [следующая глава]

Вы уже знаете, что операцию можно выразить через & и ~. Значит, любую булеву функцию можно выразить через эти операции, получив сначала СДНФ или СКНФ, а потом избавившись от операции .

Аналогично можно выразить любую булеву функцию через две операции: и ~, или даже через одну операцию: штрих Шеффера или стрелку Пирса. Все эти варианты в математике не находят большого применения, так как получаются слишком громоздкие формулы. Зато в электронике бывает полезна возможность реализовать любую логическую функцию через правильно соединенные одинаковые логические элементы, реализующие либо штрих Шеффера, либо стрелку Пирса. В электронике эти операции обычно называют "И-НЕ" и "ИЛИ-НЕ".

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

Теорема Поста.

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


Ниже приведена таблица, в которой отмечены все функции от 1 и 2 переменных и классы, которым они принадлежат. Символ "#" означает непринадлежность к классу. Для того, чтобы узнать, годится ли некоторый набор из этих функций для того, чтобы выразить произвольную логическую функцию, необходимо и достаточно убедиться, что в этом наборе есть хотя бы по одному "#" в каждой строке.

Класс x|yxyx<yx>yxyxy~x~y xyxy0 x&yxy1 yx
Сохраняет 0 # # # # # # # #
Сохраняет 1 # # # # # # # #
Линейная # # # # # # # #
Монотонная # # # # # # # # # #
Самодвойственная# # # # # # # # # # # #

Из этой таблицы, например, можно увидеть, что любую функцию можно выразить через операцию и константу 0.