Метод Квайна

Повний процес спрощення

Алгоритм дій, якимслід керуватися при спрощенні булевих виразів.

Етап 1. Побудувати карту Карно і помістите одиниці в ті комірки, які відповідають одиницям в таблиці істинності. Решту всіх комірок заповнити нулями.

Етап 2. Проаналізувати карту, знайти області прилеглих одиниць і виділити ті одиниці, які не прилягають до інших одиниць. Вони називаються ізольованими одиницями.

Етап 3. Знайти одиниці, які прилягають тільки до ще однієї одиниці. Згрупувати в пари дві будь-які прилеглі одиниці.

Етап 4. Згрупувати всі октети, навіть якщо вони містять одиниці, які вже були згруповані.

Етап 5. Згрупувати всі квартети, що містять одну або декілька одиниць, які ще не були згруповані. При цьому переконайтеся, що використовується мінімальна кількість груп.

Етап 6. Згрупувати будь-які пари, які необхідні, щоб включити ті одиниці, які ще не були згруповані. Переконайтеся, що використовується мінімальна кількість груп.

Етап 7. Підсумувати всі члени, що описанняються кожною групою.

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

Метод отримання скороченої диз’юктивної нормальної форми логічної функції називається методом Квайна.

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

Fxi Fxi = F

Теорема Квайна. Якщо в удосконаленій диз’юнктивній нормальній формі логічної функції провести всі операції неповного склеювання і потім всі операції поглинання, тоді в результаті отримується скорочена диз’юнктивна нормальна форма цієї функції, тобто диз’юнкція всіх її простиx імплікант.

Для знаходження логічної функції за таблицею істинності використовують метод Квайна. Цей метод представлено у вигляді послідовності таких дій:

1. У таблиці істинності виділяють рядки, в яких вихідна змінна має значення 1.

2. Для кожного рядка, де Y=1 складають кон'юнкцію всіх вхідних змінних цього рядка, причому записують співмножник Х _i, якщо змінна приймає значення 1, інакше записують . Таким чином, встановлюється стільки складових функції, скільки є рядків з Y=1.

3. Далі записують логічну суму всіх знайдених складових кон'юнкції, яка представляє шукану функцію.

Приклад 1 Скласти комбінаційну схему для наступної умови. Є два вимикача. При включені одного з них загорається лампа (світлодіод). Скласти таблицю роботи.

Рішення:

1. Складаємо таблицю 1 роботи:

Таблиця 1 – Таблиця роботи схеми

Х1	Х2	У

2. У відповідності з таблицею 1 знайдемо функцію:

3. Комбінаційна схема має вигляд:

Приклад 2 Скласти комбінаційну схему для наступної таблиці станів:

Таблиця 2 – Таблиця станів

Строчка	Х1	Х2	Х3	У

Рішення:

Для третього рядка кон’юнкція:

Для п’ятого рядка кон’юнкція:

Для сьомого рядка кон’юнкція:

Вихідна функція:

Використовуючи закони Булевої алгебри, отримуємо:

Дата добавления: 2014-01-07