Мінімізація ДДНФ за допомогою карт Карно

Завдання. Зведіть формулу до попередньої форми і складіть для неї таблицю істинності :

Будь-яку формулу, для компактності запису, можна звести до мінімальної форми(вигляд формули, спростити який неможливо), знайшовши спочатку ДДНФ і скориставшись методом склеювання – методом спрощення двох і більше диз’юнкцій елементарних кон’юнкцій, які відрізняються лише однією змінною, наприклад або ).

Завдання. Знайдіть мінімальну форму для формули .

Таблиця істинності останньої формули на три змінних займає чимале місце, легко бачити, що таблиця істинності формули на чотири змінних буде в два рази більшою. Існує інший – більш компактний запис таблиці істинності, який називається “карта Карно” або “діаграма Карно-Вейча”. За допомогою карт Карно можна легко спрощувати формули до їх мінімальної форми.

Вигляд карти Карно на три змінних:

Якщо придивитися, то можна побачити, що два верхні рядки схожі на таблицю істинності від двох змінних, тільки переставлені місцями два рядки.

B A
A
B

У карті Карно перший рядок відповідає значенням змінної А, другий рядок – значенням змінної В, другий стовпчик – значенням змінної С.

Отже, для того, щоб скласти карту Карно будь-якої логічної формули потрібно: звести формулу до ДНФ або ДДНФ і заповнити таблицю згідно елементарних кон’юнкцій, які отримані. Після зведення останньої формули до ДДНФ отримуємо: .

Отримана ДДНФ – це диз’юнкція чотирьох констатуент одиниці. Кожна з них запишеться у карті Карно як одиниця у відповідному місці. Розглянемо перший доданок – він буде істинним, якщо одночасно істинні всі три змінні A, B, C, тобто коли всі вони приймають значення одиниці. Знаходимо у таблиці клітинку яка знаходиться на перетині трьох одиниць і ставимо там одиницю.

Розглянемо другу констатуенту одиниці . Вона істинна тоді і тільки тоді, коли змінні А і С – істинні, а В – хибна. Отже, знаходимо у першому рядку одиниці(їх дві) у другому нулі(їх теж два), але стовпчик, у якому у першому рядку одиниця, а у другому нуль лише один, тому саме четвертий стовпчик той, який нам потрібний. А рядок беремо той, у якому змінна С приймає значення один, тобто останній.

Аналогічно заносимо у таблицю і одиниці відповідні ; у таблиці буде чотири одиниці, а на порожні клітинки поставимо нулі і таблиця матиме вигляд:

Як зазначалося вище, ДДНФ можна спростити за допомогою склеювання. Але це інколи є досить складно – не завжди вдається помітити всі можливості склеювання – наприклад, для ДДНФ на чотири змінних з десяти-дванадцяти констатуент одиниці, вибрати всі доданки, які можна склеїти вже не так просто. Тому для мінімізації використовують карти Карно, які дозволяють максимально мінімізувати будь-яку ДДНФ. Для цього в таблиці потрібно виділити всі пари одиниць, що знаходяться поруч(зазначимо, що пару у п’ятому стовпчику можна не виділяти, бо всі одиниці вже задіяні, але одну і ту ж одиницю можна включати до різних пар).

Розглянемо пару одиниць у першому рядку. Їй відповідає для змінної C – нуль, для B – одиниця(бо у другому рядку цієї змінної нашій парі відповідають саме одиниці), а от у змінної А виділеній парі відповідають і одиниця і нуль, тобто змінні В і С – фіксовані, а змінна А – ні. Це означає, що даній парі відповідає елементарна кон’юнкція ,. Так дві констатуенти одиниці можна замінити однією кон’юнкцією . Аналогічно діємо з другою парою – їй відповідає для змінної С – одиниця, для А – теж одиниця, а для В і одиниця і нуль – знову фіксованими є лише дві змінні А і С – тому замість можна написати АС. Отже – ліва частина тотожності є мінімальною формою.

Завдання.