Главная | Обратная связь

Основні способи мінімізації логічних функцій

Карти Карно. В 1953 році Моріс Карно опублікував статтю про розроблену ним систему графічного подання і спрощення функцій перемикання. Карта Карно показана на рисунку 1.2. Тут і надалі приймемо позначення: A, B, C, D – вхідні змінні (аргументи), заперечення А позначається як А′.

Рисунок 1.2 - Позначення квадратів на карті Карно
Чотири квадрати (1, 2, 3, 4) відповідають чотирьом можливим комбінаціям A і B в таблиці істинності функції з двома змінними. При такому зображенні квадрат 1 відповідає добутку А′ B′, квадрат 2 - А′ B і т.д. Для заданої функції складають таблицю, кожна клiтинка якої вiдповiдає однiй з можливих комбiнацiй її аргументiв. У клiтинках, що вiдповiдають комбiнацiям значень аргументiв, при яких функцiя дорiвнює одиницi, проставленi вiдповiдно одиницi, нулю - нулi або нiчого не проставлено, невизначена - перекресленi нулi або буква d.
До послідовності нумерації рядкiв i стовпців у картi Карно є така вимога:

номери двох сумiжних рядкiв чи стовпців повиннi вiдрiзнятись тiльки в одному з розрядiв. Ця вимога виконується i для крайнiх рядкiв i стовпців, тому вони також є сумiжними.Ця вимога є прямим наслідком правила алгебри логіки, на якому грунтується розглядуваний метод карт Карно або, як тут прийнято, К - метод, а саме:
RX+RX'=R, (1)

R – будь-яка комбiнацiя булевих змiнних.

Враховуючи прийняті вкарті Карно позначення аргументів (табл.1), наступну задану функцію можна подати так:

F = S(1,3,4,(5),6,7,(11),(15)) = A'B'C'D + A'B'CD + A'BC'D' + (A'BC'D) + A'BCD' + A'BCD + (AB'CD) + (ABCD) (2)
У цій функції члени, що відповідають її невизначеним значенням, взяті в дужки.
Правило (1) застосовують так:
1) Сумiжнi клiтинки з однаковими значеннями функції об'єднують в прямокутник, кожна сторона якого має одну або парну кiлькiсть клiтинок. Прямокутником бажано охопити якомога бiльше клiтинок. Об'єднуючи клiтинки з одиницями, шукають мiнiмiзоване значення функції, а при об'єднаннi клiтинок з нулями - її доповнення. Клiтинка з невизначеним значенням функції може бути зарахована як до одиниць, так i до нулiв, а може залишатись i незанятою.
2) Мiнiмiзований вираз має стiльки складових, скiльки утворено прямокутникiв, плюс одна складова на кожну одиницю (нуль), що не увiйшла в жоден iз прямокутникiв.
Кожна складова є кон'юнкцiєю всiх аргументiв, що залишаються незмiнними в межах кожної сторони прямокутника, яка охоплює одиниці (нулі) в межах таблиці істинності.
Звiдси очевидний висновок, що потрiбно намагатись збiльшити розмiри вищеназваних прямокутникiв.
У табл. 2 показано можливi способи мiнiмiзації функції F та її доповнення F', в результатi чого отримано
F = A' B + A' D і F' = A + B'D'. (3)
Із прикладiв зрозуміло, що внаслідок сумiжностi крайнiх рядкiв i стовпчикiв сумiжними є також кутовi клiтинки, утворюючи окремий квадрат.

При мiнiмiзації функції п'ятьох змiнних останню розділять на суми двох функцiй чотирьох змiнних у такий спосіб.

F(A,B,C,D,E)=F1(A,B,C,D)×E`+F2(A,B,C,D)×E. (4)

Функції F1 i F2 мiнiмiзують так, як це показано вище. Однойменнi елементи в їх таблицях є сумiжними, що дає змогу створювати сумiснi уявнi прямокутники i визначати мiнiмiзованi складовi для функції п'ятьох змiнних. Проте це потребує певних навикiв. Тому часто подальшу мiнiмiзацiю пiсля отримання мiнiмiзованих функцiй F1 i F2 виконують аналiтично.

Мiнiмiзацiю функції шiстьох змiнних можна проводити на основi очевидного спiввiдношення:
F (A, B, C, D, E, F ) =F1(A, B, C, D)×E`F`+F2(A, B, C, D)×E`F+
+F3(A, B, C, D)×EF`+F4(A, B, C, D)×EF. (5)
Але зрозуміло, що це буде тiльки часткова мiнiмiзацiя, яка потребуватиме наступного етапу.
Карти Карно для мiнiмiзації функцiй двох, i трьох змiнних будують з такими розмiщенням змiнних на сторонах таблиці:
А\B - для функції двох змiнних, А\BC - для функції трьох змiнних (табл..3).