Сведение к
нескольким операциям

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

Приведем еще несколько примеров сведения булевых функций к небольшому числу операций.

После того, как получена СДНФ, мы можем избавиться от операции "" с помощью закона Де Моргана:

x y = ~(~x & ~y)

Таким образом появятся новые скобки, формула внешне усложнится (по количеству символов), но все сведется к двум операциям: "&" и "~".

После того, как получена СКНФ, мы можем избавиться от операции "&" с помощью другого закона Де Моргана:

x & y = ~(~x ~y)

Таким образом появятся новые скобки, формула внешне усложнится, но все сведется к двум операциям: "" и "~".

Также можно свести любую булеву функцию к операциям "" и "~". Для этого сначала сводим ее к операциям "~" и "", а затем избавляемся от операции "" с помощью формулы:

(x y) y = x y

После этого можно избавиться от операции "~" с помощью формулы:

~x = x false

Тем самым все сведется к одной операции "" и константе false (от которой уже не удастся избавиться).

Уникальными в своем роде являются операции "" и "|". Через любую из них можно выразить любую булеву функцию, даже не применяя констант true или false. Таким образом, эти операции могут служить универсальными элементарными строительными блоками для создания микросхем. В схемотехнике они обычно называются "элементом И-НЕ" и "элементом ИЛИ-НЕ".

Для сведения любой булевой функции к штриху Шеффера достаточно свести ее к операциям "" и "~", а потом применить правила:

~x = x | x

x y = (x | x) | (y | y)

Для сведения любой булевой функции к стрелке Пирса достаточно свести ее к операциям "&" и "~", а потом применить правила:

~x = x x

x & y = (x x) (y y)

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

1. &, , ~
2. &, ~
3. , ~
4. &, , true
5. , false
6. , ~

Это - далеко не исчерпывающий список. Универсальный ответ на подобные вопросы дает "теорема Поста", которая позволяет сказать насчет произвольной группы булевых функций, операций и констант - можно ли через них выразить любую другую булеву функцию или нет. Причем, теорема Поста позволяет рассматривать в качестве "строительных блоков" не только операции с одной-двумя переменными, но и произвольные булевы функции. Если интересно, то формулировку теоремы Поста можно найти в справочнике. Предварительно следует ознакомиться с классификацией булевых функций здесь. Учтите, что в справочнике вместо констант false и true используются обозначнения 0 и 1 соответственно. Такая практика обычна для "околокомпьютерной" литературы. Также часто используют обозначения "f" и "t" или "F" и "T".