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

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

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

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

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

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

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

• хотя бы одна не линейная;
• хотя бы одна не монотонная;
• хотя бы одна не самодвойственная;
• хотя бы одна не сохраняющая 0;
• хотя бы одна не сохраняющая 1.

---

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

Класс

x|y

xy

x<y

x>y

xy

xy

~x

~y

xy

xy

0

x&y

xy

1

y

x

Сохраняет 0

#

#

#

#

#

#

#

#

Сохраняет 1

#

#

#

#

#

#

#

#

Линейная

#

#

#

#

#

#

#

#

Монотонная

#

#

#

#

#

#

#

#

#

#

Самодвойственная

#

#

#

#

#

#

#

#

#

#

#

#

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