Лекція 3 Алгебра логіки Терновой Максим Юрійович к т. н., с н. с., доцент кафедри інформаційно

• Название: Лекція 3 Алгебра логіки Терновой Максим Юрійович к т. н., с н. с., доцент кафедри інформаційно
• Дата: 18.05.2019
• Размер: 1.3 Mb.
• Имя файла: L_3.pdf
• Тип: Лекція; #77617
• страница: 4 из 4

Метод Квайна. 1 етап. Початкове
скорочення формули.Приклад
Скоротимо функцію, яку подано в вигляді ДДНФ:
)
(
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
F









Кон’юнкціями 4-го рангу є ( див. табл.1.23 ):
4 3
2 1
x
x
x
x
4 2
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x

Метод Квайна. 1 етап. Початкове
скорочення формули.Приклад
Таблиця 1.23
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
1 4
3 1
x
x
x
4 3
2
x
x
x
4 3
2 1
x
x
x
x
1 3
2 1
x
x
x
4 3
2
x
x
x
4 3
2 1
x
x
x
x
3 2
1
x
x
x
1 4
2 1
x
x
x
4 3
2
x
x
x
4 3
2 1
x
x
x
x
4 3
1
x
x
x
4 2
1
x
x
x
1 4
3 2
1
x
x
x
x
1 4
2 1
x
x
x
4 3
1
x
x
x
4 3
2 1
x
x
x
x
4 3
2
x
x
x
4 2
1
x
x
x
1 4
3 2
1
x
x
x
x
4 3
2
x
x
x
1 3
2 1
x
x
x
4 3
2 1
x
x
x
x
4 3
2
x
x
x
4 3
1
x
x
x
3 2
1
x
x
x
1

Метод Квайна. 1 етап. Початкове
скорочення формули.Приклад
Проведення всіх можливих склеювань за однією змінною наведено в табл.1.23, в результаті отримаємо кон’юнкції 3-го рангу:
4 3
1
x
x
x
3 2
1
x
x
x
4 3
2
x
x
x
4 2
1
x
x
x
4 2
1
x
x
x
4 3
2
x
x
x
4 3
2
x
x
x
3 2
1
x
x
x
4 3
1
x
x
x
Виконання операцій склеювання та поглинання приводить до вилучення всіх кон’юнкцій четвертого рангу.
Кон’юнкції 3-го рангу залишаються.

Метод Квайна. 1 етап. Початкове
скорочення формули.Приклад
Проведення всіх можливих склеювань кон’юнкцій 3-го рангу наведено в табл.1.24. В результаті отримаємо кон’юнкцію 2-го рангу
3 2
x
x
Виконання операцій поглинання приводить до вилучення кон’юнкцій 3-го рангу
3 2
1
x
x
x
,
4 3
2
x
x
x
,
4 3
2
x
x
x
,
3 2
1
x
x
x
Залишаються кон’юнкції
3-го рангу
,
,
,
,
4 3
1 4
3 2
4 2
1 4
2 1
4 3
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Для єдиної кон’юнкції 2-го рангу
3 2
x
x
виконати операції склеювання неможливо.

Метод Квайна. 1 етап. Початкове
скорочення формули.Приклад
Таблиця 1.24
4 3
1
x
x
x
3 2
1
x
x
x
4 3
2
x
x
x
4 2
1
x
x
x
4 2
1
x
x
x
4 3
2
x
x
x
4 3
2
x
x
x
3 2
1
x
x
x
4 3
1
x
x
x
4 3
1
x
x
x
1 3
2 1
x
x
x
1 3
2
x
x
4 3
2
x
x
x
1 3
2
x
x
4 2
1
x
x
x
1 4
2 1
x
x
x
1 4
3 2
x
x
x
1 4
3 2
x
x
x
3 2
x
x
1 3
2 1
x
x
x
3 2
x
x
1 4
3 1
x
x
x
1

Метод Квайна. 1 етап. Початкове
скорочення формули.Приклад
Оскільки подальше склеювання неможливе, то етап початкового скорочення закінчений. Ми утворили ДНФ. Її доданками є елементарні кон’юнкції:
4 3
1
x
x
x
,
4 2
1
x
x
x
,
4 2
1
x
x
x
,
4 3
2
x
x
x
,
4 3
1
x
x
x
,
3 2
x
x
Але на цьому процес скорочення формули за методом
Квайна не закінчено. Ми скоротили ДДНФ до доданків рангом не більше за три.

Метод Квайна.
2 етап.
Розставляння міток.
На етапі розставляння міток складається таблиця,
число рядків якої дорівнює числу отриманих кон’юнкцій
функції.
Число стовпців співпадає з числом кон’юнкцій ДДНФ.
Якщо в деяку кон’юнкцію ДДНФ входить яка-небудь із
кон’юнкцій отриманої ДНФ, то на перерізі відповідного
стовпця й рядка ставиться мітка (див. таблицю 1.25).

Метод Квайна.
2 етап.
Розставляння міток. Приклад
Таблиця 1.25
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
1
x
x
x


4 2
1
x
x
x


4 2
1
x
x
x


4 3
2
x
x
x


4 3
1
x x
x


3 2
x
x





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

Метод Квайна.
3 етап.
Знаходження суттєвих доданків.
Суттєва кон’юнкція не може бути вилучена з правої частини початкового рівняння, оскільки без неї не буде
отримане покриття всієї множині доданків даної функції.
Тому з таблиці міток виключаються рядки, відповідні
суттєвим кон’юнкціям, і стовпці кон’юнкцій ДДНФ, що покриваються цими суттєвими кон’юнкціями.
Всі суттєві кон’юнкції увійдуть в кінцеву скорочену
ДНФ.

Метод Квайна.
3 етап.
Розставляння міток. Приклад
Для нашої функції суттєвою кон’юнкцією є:
3 2
x x
. Вона покриває доданки ДДНФ
4 3
2 1
x
x
x
x
,
4 3
2 1
x
x
x
x
,
4 3
2 1
x
x
x
x
,
4 3
2 1
x
x
x
x
(тобто поглинає їх). При переході до наступного етапу вони мають бути викреслені.
Таблиця 1.25_1
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
1
x
x
x


4 2
1
x
x
x


4 2
1
x
x
x


4 3
2
x
x
x


4 3
1
x x
x


3 2
x
x





Метод Квайна.
4 етап.
Викреслювання зайвих стовпців.
Досліджується таблиця, отримана після 3-го етапу. (у нашому прикладі таблиця 1.26) Якщо в ній існують 2
стовпці, в яких існують мітки в однакових рядках, то один
із них викреслюється.
У даному прикладі однакових стовпців немає.
Таблиця 1.26
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
1
x
x
x


4 3
2
x
x
x


4 2
1
x
x
x

4 2
1
x
x
x


4 3
1
x
x
x


Метод Квайна.
5 етап. Викреслювання
зайвих кон’юнкцій скороченої ДНФ.
Якщо після викидання деяких зайвих стовпців на 4-ому етапі в таблиці з’являються рядки, в яких немає жодної
мітки, то дані кон’юнкції, відповідні цим рядкам,
виключаються з подальших розглядів.
В нашому прикладі таких рядків немає.

Метод Квайна.
6 етап. Вибір
мінімального покриття.
Досліджується отримана таблиця.
Вибирається така сукупність кон’юнкцій ДНФ, яка
включає мітки у всіх стовпцях (принаймні одну мітку в кожному стовпці).
При декількох можливих варіантах такого вибору віддається перевага варіанту покриття з мінімальним
сумарним числом літер у кон’юнкціях ДНФ.

Метод Квайна.
6 етап. Вибір
мінімального покриття.
Приклад
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
1
x
x
x


4 3
2
x
x
x


4 2
1
x
x
x

4 2
1
x
x
x


4 3
1
x
x
x

Вибираємо покриття з кон’юнкцій
4 3
1
x
x
x
і
4 2
1
x
x
x
, оскільки вони спільно покривають всі ті терми, що залишилися після 4-го етапу. Додаємо суттєву кон’юнкцію
3 2
х
х
Скорочена ДНФ для цієї функції має кінцевий вигляд:
3 2
4 2
1 4
3 1
4 3
2 1
)
(
x
x
x
x
x
x
x
x
x
x
x
x
f




Питання, що були розглянуті
1.
Логічні (булеві) функції.
2.
Алгебра логіки.
3.
Повні набори функцій
4.
Канонічні форми булевих функцій.
5.
Спрощення формул. Утворення скороченої ДНФ
методом Квайна

Дякую за увагу!!!
ПИТАННЯ?