4.4. Булева алгебра.

Основные свойства элементарных логических функций

Булевой алгеброй логических функций называется алгебра (Р₂; Ú, Ù,` ), основным множеством которой является все множество логических функций, а операциями – дизъюнкция, конъюнкция и отрицание. Операции булевой алгебры часто называют булевыми операциями, а представления логических функций рассматриваются как суперпозиции функций И, ИЛИ, НЕ.

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

1. Свойства констант:

2. Свойство двойного отрицания:

(4.2)

3. Идемпотентность (отсутствие степеней и множителей):

а) х Ù х = х; б) х Ú х = х. (4.3)

4. Закон противоречия:

х Ù`х = 0. (4.4)

5. Закон «исключенного третьего»:

х Ú`х = 1. (4.5)

6. Ассоциативность:

а) х₁ Ù (х₂ Ù х₃) = (х₁ Ù х₂) Ù х₃; б) х₁ Ú (х₂ Ú х₃) = (х₁ Ú х₂) Ú х₃. (4.6)

7. Коммутативность:

а) х₁ Ù х₂ = х₂ Ù х₁; б) х₁ Ú х₂ = х₂ Ú х₁. (4.7)

8. Дистрибутивность конъюнкции относительно дизъюнкции:

х₁ Ù (х₂ Ú х₃) = (х₁ Ù х₂) Ú (х₁ Ù х₃). (4.8)

9. Дистрибутивность дизъюнкции относительно конъюнкции:

х₁ Ú (х₂ Ù х₃) = (х₁ Ú х₂) Ù (х₁ Ú х₃). (4.9)

10. Правила де Моргана:

а) б) (4.10)

Приведенные выше десять основных свойств булевых операций можно проверить указанным ранее стандартным способом – вычислением обеих частей равенств на всех наборах значений переменных. Результат вычислений не зависит от того, как получены значения переменных, входящих в эти равенства, т.е. от того, являются ли эти переменные независимыми или, в свою очередь, получены в результате каких-то других вычислений. Поэтому эти свойства остаются справедливыми при подстановке вместо переменных любых логических функций и, следовательно, любых формул, представляющих эти функции. Важно лишь соблюдать правило подстановки формулы вместо переменной: при подстановке формулы F вместо переменной х все вхождения переменной х в исходное соотношение должны быть заменены формулой F. Это правило подстановки позволяет получать из соотношений (4.1 – 4.10) новые эквивалентные соотношения.

Во всякой алгебре (в том числе и в булевой алгебре функций) равенство F₁ = F₂ означает, что формулы F₁ и F₂ описывают один и тот же элемент алгебры, в данном случае одну и ту же логическую функцию f₁. Следовательно, если какая-либо формула F содержит F₁ в качестве подформулы, то замена F₁ на F₂ не изменяет элемента булевой алгебры f, над которым производятся операции в формуле F; поэтому F', полученная из F такой заменой, эквивалентна F. Это утверждение представляет собой правило замены подформул, которое позволяет, используя эквивалентные соотношения, получать формулы, эквивалентные данной.

Подчеркнем разницу между правилами подстановки и замены. При подстановке переменная заменяется на формулу; формула может быть любой, но требуется одновременная ее подстановка вместо всех вхождений переменной. При замене подформул может быть заменена любая подформула, однако не на любую другую, а только на эквивалентную ей. При этом замена всех вхождений исходной подформулы не обязательна. Пусть имеется эквивалентность F₁ = F₂, где F₁ и F₂ содержат переменную х. Если вместо всех вхождений х в F₁ и F₂ подставить произвольную формулу F, то получаются новые формулы F’₁ и F’₂, причем не обязательно F₁ = F’₁, F₂ = F’₂, однако между собой новые формулы будут эквивалентны: F’₁ = F’₂. Если же в F₁ какую-либо подформулу заменить на эквивалентную ей, то получится новая формула F’₁, эквивалентная F₁.

Пример 4.1.

В выражение, описывающее правила де Моргана (4.10, а) подставим
(`х₁ Ù х₃) вместо х₁. Получим две формулы, неэквивалентные исходным,

,

но эквивалентные между собой. Если же в правой части нового соотношения заменить формулу ,эквивалентной ей  в силу правила (4.10), а в полученной подформуле заменить  на эквивалентную ей в силу правила (4.2) формулу х₁, то все формулы в построенной цепи преобразований эквивалентны.

.

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

Рассмотрим некоторые основные эквивалентные преобразования в булевой алгебре и новые соотношения, получаемые с их помощью из правил
(4.1 – 4.10), приводящие к упрощению формул (т. е. получение эквивалентных формул, содержащих меньшее число символов).

1. Поглощение:

Доказательство:

2. Склеивание:

Доказательство:

3. Обобщенное склеивание:

Доказывается с помощью расщепления, т.е. применения правила склеивания (4.12) в обратную сторону и правила поглощения (4.11):

4. Обобщением равенств (4.11 а) и (4.14) является равенство: