Page 16 - 6733

2.3. Основні теоретичні відомості

2.3.1. Мінімізація (спрощення) логічних виразів

Логічний вираз – це вираз, складений із логічних змінних і логічних
операцій. Логічні операції позначають таким чином:
Інверсія Логічне АБО  або +

Логічне І  або знак Виключне АБО 
множення
Існує кілька способів мінімізації логічних виразів (методом безпосередніх
перетворень, за допомогою карт Карно і Вейча, методом Квайна). Всі ці способи
ґрунтуються на основних законах алгебри логіки (табл.. 2.2).

Таблиця 2.2 - Основні закони алгебри логіки
Для диз’юнкції Для кон’юнкції
Комутативність X  Y  Y  X X  Y  Y  X
Асоціативність ( X  Y ) Z  X  ( Y  Z ) X  Y  Z ( X  Y ) Z  X  ( Y  Z ) X  Y  Z
Дистрибутивність ( X  Y ) Z  X  Z  Y  Z X  Y  Z  (X  ) Z  (Y  ) Z
Ідемпотентність
(тавтологія) X  X  X X  X  X
Операції з
X  0  X , X  1 1 X  0  0, X 1  X
константами
Властивості X  X  1 X  X  0
інверсії X  X

Правила де
X  Y  X  Y X  Y  X  Y
Моргана
Поглинання X  X  Y  X X  ( X  Y ) X
Склеювання X  Y  X  Y  X ( X  Y  () X  Y ) X

Мінімізація логічних виразів шляхом безпосередніх перетворень
здійснюється послідовним застосуванням законів алгебри логіки до складових
логічного виразу. Найбільш ефективним при цьому є застосування правил де
Моргана і законів поглинання і склеювання.

Приклад. Заданий логічний вираз: ( X  X  Y ) Y  Z  X  Y

1) за законом дистрибутивності X  X  Y  (X  X )  (X  Y )
2) із властивостей операцій з константами і інверсією випливає
(X  X )  (X  )Y   (1 X  Y ) X  Y

3) за правилом де Моргана X  Y  X  Y
4) за правилом де Моргана X  Y  Y  Z  X  Y  Y  Z

5) за правилом склеювання X  Y  X  Y  X

16