Розв'язувач карт Карно (K-Map)

Спрощення булевої функції за допомогою карти Карно

Карта Карно (K-Map) розміщує комбінації входів так, щоб сусідні комірки відрізнялися лише однією змінною. Це допомагає побачити, які змінні можна прибрати зі спрощеного виразу.

Solver підтримує функції з 2, 3, 4 і 5 змінними. Почати можна з карти Карно, таблиці істинності, булевого виразу, мінтермів або макстермів.

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

Що означають 0, 1 та X?

Комірка K-Map може містити:

• 1 — функція істинна для цієї комбінації;
• 0 — функція хибна;
• X — значення виходу для цієї комбінації не має значення.

X — це стан don't-care. Його можна використати, якщо він допомагає створити більшу групу та спростити вираз. Якщо користі немає, його можна не включати.

Від таблиці істинності до K-Map

Таблиця істинності показує всі можливі комбінації входів і відповідні виходи.

Карта Карно використовує ті самі дані, але розміщує їх у порядку коду Грея. Завдяки цьому сусідні комірки відрізняються тільки однією змінною.

Наприклад:

A'B'

A'B

Тут змінюється лише B.

Обидва терми можна об'єднати у:

A'

Змінна, яка змінюється всередині групи, зникає зі спрощеного терма.

Той самий принцип працює для більших груп.

Мінтерми, макстерми та булеві вирази

Якщо в умові вже наведено індекси мінтермів, немає потреби заповнювати кожну комірку вручну.

Наприклад:

Σm(1,3,5,7)

визначає мінтерми, для яких вихід функції дорівнює 1.

А:

ΠM(0,2,4,6)

визначає макстерми, що відповідають виходу 0.

Можна також ввести булевий вираз безпосередньо.

Solver обчислить його для всіх комбінацій входів і створить відповідні таблицю істинності, K-Map, мінтерми та макстерми.

Це дозволяє легко порівняти різні способи запису тієї самої булевої функції.

Як працюють групи K-Map

Кількість комірок у правильній групі має бути степенем двійки:

1, 2, 4, 8, 16

Зазвичай більша допустима група означає менше літералів у кінцевому термі.

Протилежні краї карти Карно логічно суміжні.

Комірки на лівому краї можуть утворювати групу з комірками на правому. Верхній та нижній краї працюють так само.

Тому чотири кутові комірки також можуть утворити одну групу.

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

Solver показує використані групи безпосередньо на K-Map.

SOP і POS

У формі SOP (Sum of Products) спрощення головним чином базується на комірках з виходом 1.

Наприклад:

A'B + BC

У POS (Product of Sums) використовуються комбінації, де вихід дорівнює 0.

Наприклад:

(A + B')(B + C)

SOP не завжди буде коротшим.

Для однієї функції простішою може бути SOP-форма, а для іншої — POS.

Якщо завдання не вимагає конкретної форми, можна порівняти обидва результати.

Quine-McCluskey та Petrick's Method

У невеликій карті Карно вдалі групи часто легко знайти візуально.

Для функцій з 4 або 5 змінними може існувати кілька допустимих покриттів.

Solver використовує Quine-McCluskey, щоб систематично визначати implicant.

Implicant, який уже не можна розширити, є prime implicant.

Деякі prime implicant є необхідними, тому що вони покривають мінтерм, який не покриває жоден інший prime implicant.

Якщо після цього залишається кілька способів завершити покриття, Petrick's Method допомагає проаналізувати решту варіантів.

Такий підхід корисний у випадках, коли найкращий набір груп не очевидний лише з вигляду K-Map.

K-Map для 2–5 змінних

K-Map для 2 змінних має 4 комірки.

Для 3 змінних є 8 комірок, і стає помітнішою суміжність протилежних країв.

4-змінна карта Карно має 16 комірок і часто використовується в задачах цифрової логіки.

Для 5 змінних існує 32 комбінації входів. Ручна перевірка стає складнішою, особливо за наявності don't-care або кількох prime implicant.

Solver синхронізує K-Map, таблицю істинності, вираз, мінтерми та макстерми для всіх підтримуваних розмірів.

Логічна схема та PDF

Після спрощення вираз можна переглянути як логічну схему.

Це показує, як SOP або POS реалізується за допомогою елементів AND, OR і NOT.

У результатах також можна побачити кількість термів, літералів і логічних елементів.

Повне рішення можна експортувати у PDF разом із K-Map, групами, етапами спрощення та схемою.