Упрощение булевых функций
Упрощение с использованием алгебраических функций
В этом подходе одно булево выражение минимизируется в эквивалентное выражение путем применения булевых тождеств.
Проблема 1
Минимизируйте следующее логическое выражение, используя логические тождества -
$$ F (A, B, C) = A'B + BC '+ BC + AB'C' $$
Решение
Учитывая, $ F (A, B, C) = A'B + BC '+ BC + AB'C' $
Или $ F (A, B, C) = A'B + (BC '+ BC') + BC + AB'C '$
[По идемпотентному закону, BC '= BC' + BC ']
Или $ F (A, B, C) = A'B + (BC '+ BC) + (BC' + AB'C ') $
Или $ F (A, B, C) = A'B + B (C '+ C) + C' (B + AB ') $
[По распределительным законам]
Или $ F (A, B, C) = A'B + B.1 + C '(B + A) $
[(C '+ C) = 1 и закон поглощения (B + AB') = (B + A)]
Или $ F (A, B, C) = A'B + B + C '(B + A) $
[B.1 = B]
Или $ F (A, B, C) = B (A '+ 1) + C' (B + A) $
Или $ F (A, B, C) = B.1 + C '(B + A) $
[(A '+ 1) = 1]
Или $ F (A, B, C) = B + C '(B + A) $
[As, B.1 = B]
Или $ F (A, B, C) = B + BC '+ AC' $
Или $ F (A, B, C) = B (1 + C ') + AC' $
Или $ F (A, B, C) = B.1 + AC '$
[As, (1 + C ') = 1]
Или $ F (A, B, C) = B + AC '$
[As, B.1 = B]
Итак, $ F (A, B, C) = B + AC '$ является минимизированной формой.
Проблема 2
Минимизируйте следующее логическое выражение, используя логические тождества -
$$ F (A, B, C) = (A + B) (A + C) $$
Решение
Учитывая, $ F (A, B, C) = (A + B) (A + C) $
Или $ F (A, B, C) = AA + AC + BA + BC $ [Применение дистрибутивного правила]
Или $ F (A, B, C) = A + AC + BA + BC $ [Применение закона Идемпотента]
Или $ F (A, B, C) = A (1 + C) + BA + BC $ [Применение закона распределения]
Или $ F (A, B, C) = A + BA + BC $ [Применение закона доминирования]
Или $ F (A, B, C) = (A + 1) .A + BC $ [Применение закона распределения]
Или $ F (A, B, C) = 1.A + BC $ [Применение закона доминирования]
Или $ F (A, B, C) = A + BC $ [Применение закона доминирования]
Итак, $ F (A, B, C) = A + BC $ - это минимизированная форма.
Карты Карно
Карта Карно (K – map), представленная Морисом Карнофином в 1953 году, представляет собой сетчатое представление таблицы истинности, которая используется для упрощения выражений булевой алгебры. Карта Карно имеет ноль и одну запись в разных позициях. Он обеспечивает группировку логических выражений с общими факторами и исключает нежелательные переменные из выражения. На K-карте пересечение вертикальной или горизонтальной границы ячейки всегда является изменением только одной переменной.
Пример 1
Произвольная таблица истинности взята ниже -
В | Операция Б | |
---|---|---|
0 | 0 | вес |
0 | 1 | Икс |
1 | 0 | Y |
1 | 1 | Z |
Теперь мы сделаем k-карту для приведенной выше таблицы истинности -

Пример 2
Теперь мы сделаем K-карту для выражения - AB + A'B '

Упрощение с использованием K-карты
K-map использует некоторые правила для упрощения логических выражений, объединяя смежные ячейки в один термин. Правила описаны ниже -
Правило 1 - Любая ячейка, содержащая ноль, не может быть сгруппирована.

Неправильная группировка
Правило 2 - Группы должны содержать 2n ячеек (n, начиная с 1).

Неправильная группировка
Правило 3 - Группировка должна быть горизонтальной или вертикальной, но не должна быть диагональной.

Неправильная диагональная группировка

Правильная вертикальная группировка

Правильная горизонтальная группировка
Правило 4 - Группы должны быть охвачены как можно шире.

Недостаточная группировка

Правильная группировка
Правило 5 - Если 1 из любой ячейки не может быть сгруппирована с какой-либо другой ячейкой, она будет действовать как сама группа.

Правильная группировка
Правило 6 - Группы могут перекрываться, но должно быть как можно меньше групп.

Правильная группировка
Правило 7 - Самая левая ячейка / ячейки могут быть сгруппированы с самой правой ячейкой / ячейками, а самая верхняя ячейка / ячейки может быть сгруппирована с самой нижней ячейкой / ячейками.

Правильная группировка
проблема
Минимизируйте следующее логическое выражение, используя K-map -
$$ F (A, B, C) = A'BC + A'BC '+ AB'C' + AB'C $$
Решение
Каждый термин помещается в k-карту, и мы получаем следующее -

K-карта для F (A, B, C)
Теперь мы сгруппируем ячейки 1 согласно правилам, изложенным выше -

K-карта для F (A, B, C)
У нас есть две группы, которые называются $ A'B $ и $ AB '$. Следовательно, $ F (A, B, C) = A'B + AB '= A \ oplus B $. Это минимизированная форма.