Вы уже знаете, что операцию можно выразить через & и ~.
Значит, любую булеву функцию можно выразить через эти операции,
получив сначала СДНФ или СКНФ, а потом избавившись от операции
.
Аналогично можно выразить любую булеву функцию через две операции:
и ~, или даже через одну операцию: штрих Шеффера или стрелку
Пирса. Все эти варианты в математике не находят большого применения,
так как получаются слишком громоздкие формулы. Зато в электронике
бывает полезна возможность реализовать любую логическую функцию
через правильно соединенные одинаковые логические элементы,
реализующие либо штрих Шеффера, либо стрелку Пирса. В электронике
эти операции обычно называют "И-НЕ" и "ИЛИ-НЕ".
Оказывается, можно заранее сказать, какой набор функций годится для выражения всех остальных функций, а какой не годится. На этот вопрос отвечает теорема Поста.
Все остальные логические функции можно составить из набора логических функций, среди которых есть:
Класс | x|y | x![]() | x<y | x>y | x![]() | x![]() | ~x | ~y | x![]() | x![]() | 0 | x&y | x![]() | 1 | y | x |
Сохраняет 0 | # | # | # | # | # | # | # | # | ||||||||
Сохраняет 1 | # | # | # | # | # | # | # | # | ||||||||
Линейная | # | # | # | # | # | # | # | # | ||||||||
Монотонная | # | # | # | # | # | # | # | # | # | # | ||||||
Самодвойственная | # | # | # | # | # | # | # | # | # | # | # | # |
Из этой таблицы, например, можно увидеть, что любую функцию можно выразить через операцию и константу 0.