Упрощение булевых выражений

1. Закон двойного отрицания (двойное отрицание исключает отрицание):

А = .

2. Переместительный (коммутативный) закон:

o для логического сложения: А + B = B + A;

o для логического умножения: A & B = B & A.

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

3. Сочетательный (ассоциативный) закон:

o для логического сложения: (А + B) + C = A + (B + C);

o для логического умножения: (A & B) & C = A & (B & C).

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

4. Распределительный (дистрибутивный) закон:

o для логического сложения: (А + B) & C = (A & C) + (B & C);

o для логического умножения: (A & B) + C = (A + C) & (B + C).

Закон определяет правило выноса общего высказывания за скобку.

5. Закон общей инверсии (законы де Моргана):

o для логического сложения: = & ;

o для логического умножения: = +

6. Закон идемпотентности (от латинских слов idem — тот же самый и potens — сильный; дословно — равносильный):

o для логического сложения: А + A = A;

o для логического умножения: A & A = A .

Закон означает отсутствие показателей степени.

7. Законы исключения констант:

o для логического сложения: А + 1 = 1, А + 0 = A;

o для логического умножения: A & 1 = A, A & 0 = 0.

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

o A & = 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

9. Закон исключения третьего:

o A + = 1.

Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано.

10. Закон поглощения:

o для логического сложения: А + (A & B) = A;

o для логического умножения: A & (A + B) = A.

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

Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), другие - основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).

Нарушения законов логики приводят к логическим ошибкам и вытекающим из них противоречиям.

Упрощение формул.

Пример 1. Упростить формулу (А + В) & (А + С).

Решение:

1. Раскроем скобки: (А  В) & (А  С) = A & A  A & C  B & A  B & C;

2. По закону идемпотентности A & A =A, следовательно,
A & A  A & C  B & A  B & C = A  A & C  B & A  B & C;

3. В высказываниях А и А & C вынесем за скобки А и используя свойство А + 1= 1, получим
A  A & C  B & A  B & C = A & (1  C)  B & A  B & C = A  B & A  B & C;

4. Аналогично предыдущему пункту вынесем за скобки высказывание А.
A  B & A  B & C = A & (1  B)  B & C = A  B & C.

Таким образом, мы доказали закон дистрибутивности.

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

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

Решение:

 Карта Карно

Если число логических переменных не превышает 6, то минимизацию логических уравнений удобно производить с помощью карт Карно или диаграмм Вейча. Минимизацию производят объединением наборов (термов) на карте Карно. Объединяемые наборы должны иметь одинаковые значения функции (все 0 или все 1). Рассмотрим пример: пусть требуется найти логическое выражение для мажоритарной функции F_m трех переменных X, Y, Z, которая описывается следующей таблицей истинности (таблица 2.5):

Таблица 2.5 - Таблица истинности мажоритарной функция

Составим карту Карно. Она представляет собой нечто похожее на таблицу, в которой наименования столбцов и строк представляют собой значения переменных, причем переменные располагаются в таком порядке, чтобы при переходе к соседнему столбцу или строке изменялось значение только одной переменной. Например, в строке XY таблицы 12.3 значения переменных XY могут быть представлены следующими последовательностями: 00, 01, 11, 10 и 00, 10, 11, 01. Таблицу заполняют значениями функции, соответствующими комбинациям значений переменных. Полученная таким образом таблица выглядит, как показано ниже (таблица 2.6).

Таблица 2.6 — Карта Карно мажоритарной функции

На карте Карно отмечаем группы, состоящие из 2ⁿ ячеек (2, 4, 8,...) и содержащие 1, так как такие группы описываются простыми логическими выражениями. Три прямоугольника в таблице определяют логические выражения XY, XZ, YZ. Каждый прямоугольник, объединяющий две ячейки, соответствует логическим преобразованиям:

,

,

.

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

F_m = XY + XZ + YZ.                                            (1)

Для реализации функции мажоритарной логики трех логических переменных необходимо реализовать схему, которая при подаче на ее входы трех сигналов формировала бы на выходе сигнал, равный сигналу на большинстве входов (2 из 3 или 3 из 3). Эта схема полезна для восстановления истинного значения сигналов, поступающих на 3 входа, если возможен отказ на одном из входов. Для реализации функции на элементах 2И-НЕ запишем формулу (1) при помощи операций логического умножения и инверсии:

                                 (2)

Соответствующая формуле (2) схемная реализация функции F_m приведена на рисунке 2.1.

Рисунок 2.1 — Схемная реализация функции F_m на элементах 2И-НЕ