1 of 34

МІНІМІЗАЦІЯ булевих функцій. Метод Квайна і Квайна-Мак-Класки

ЛЕКЦІЇ 6

​

1

ДИСКРЕТНА МАТЕМАТИКА

Булева алгебра

Харьковский национальный университет радиоэлектроники,

кафедра АПВТ, тел. 7021 326, е-mail: ri@kture.kharkov.ua

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

2 of 34

мета лекції - вивчити методи Квайна і Квайна-Мак-Класки для мінімізації булевих функцій, що описують комбінаційні підсхеми цифрових проектів

2

Зміст:

  • Сенс процесу мінімізації
  • Поняття імпліканти
  • Етапи методу Квайна
  • Недоліки методу Квайна
  • Метод Квайна-Мак-Класки
  • Приклади

Тема: Мінімізація булевих функцій. � Методи Квайна і Квайна-Мак-Класки

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

3 of 34

Базові поняття:

    • Булева змінна
    • Булева функція
    • Двійкова система

числення

    • Числове уявлення ФАЛ
    • Кубічне уявлення ФАЛ
    • ДДНФ і ДКНФ

​

​

3

Терміни

Ключові слова:

​

    • мінімізація
    • імпліканта
    • суттєві імпліканти
    • мінімальне покриття

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

4 of 34

4

Сенс процесу мінімізації

  • Різні вираження однієї і тієї ж булевої функції описують різні схеми
  • приклад

№

х1

х2

х3

f (x1, x2, x3)

№

х1

х2

х3

f (x1, x2, x3)

0

0

0

0

1

4

1

0

0

0

1

0

0

1

0

5

1

0

1

1

2

0

1

0

0

6

1

1

0

1

3

0

1

1

1

7

1

1

1

0

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

5 of 34

5

Сенс процесу мінімізації

  • Перетворимо ДДНФ до вигляду:

​

​

  • Схемотехнічне уявлення формул дає схеми з 12 і 10 контактів відповідно:

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

6 of 34

6

Визначення

  • Вихідна функція задана в ДДНФ
  • Def: імпліканта функції - це деяка логічна функція, що має значення одиниця на тому ж наборі змінних, на якому дорівнює одиниці сама функція
  • Будь-який кон'юнктивний терм або група термів, з'єднаних знаками диз'юнкції, що входять до ДДНФ, є імплікантами вихідної функції
  • Def: первинна імпліканта функції - це імпліканта типу елементарної кон'юнкції, ніяка частина якої вже не є імплікантою

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

7 of 34

7

Історична довідка

Куайн Віллард ван Онрман

  • американський математик
  • професор Гарвардського університету
  • читав лекції в Сан-Пауло (Бразилія), Оксфорді (Англія), Токіо, Парижі, Упсалі (Швеція)
  • найбільший фахівець в області математичної логіки і основ математики
  • Член Американської Академії наук і мистецтв у Бостоні

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

8 of 34

8

Мінімізація методом Квайна

  • Складається в попарному порівнянні всіх імплікант, що входять в ДДНФ, з метою виявлення можливості поглинання якоїсь змінної на основі закону склеювання

​

  • Вдається знизити ранг термів
  • Процедура проводиться до тих пір, поки не залишиться жодного члена, що допускає поглинання з іншим термом
  • Терми, які зазнали поглинання, відмічаються
  • Невідмічені терми є первинними імплікантами
  • Отриманий логічний вираз не завжди виявляється мінімальним

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

9 of 34

9

Мінімізації методом Квайна

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

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

10 of 34

10

Етапи методу Квайна

  • Визначення первинних імплікант
  • Розстановка міток
  • Знаходження суттєвих імплікант
  • Визначення та видалення зайвих стовпців
  • Визначення та видалення зайвих первинних імплікант
  • Вибір мінімального покриття
  • Складання мінімальної форми вихідної функції

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

11 of 34

11

Приклад мінімізації по методу Квайна

  • Потрібно мінімізувати функцію:
  • Функцію у вигляді ДДНФ

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

12 of 34

12

  • 1. Визначення первинних імплікант
  • Складається таблиця вихідних термів

номери стовпців

1

2

3

4

5

6

7

8

двійкові

набори

0011

0100

0101

0111

1 001

1011

1100

1101

вихідні

терми

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

1

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

13 of 34

13

  • 1. Визначення первинних імплікант
  • Ранг термів знижується

номери стовпців

1

2

3

4

5

6

7

8

9

первинні імпліканти

3-го рангу

​

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

​

1

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

1

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

14 of 34

14

  • 2. Розстановка міток

номери стовпців

1

2

3

4

5

6

7

8

Набори

0011

0100

0101

0111

1 001

1011

1100

1101

імпліканти

3-го і 2-го рангу

​

​

​

​

​

​

​

​

​

*

​

​

*

​

​

​

​

​

*

​

​

​

​

*

​

​

​

​

​

*

*

​

​

​

​

​

​

​

​

​

*

*

​

​

​

​

​

​

​

*

​

​

*

​

​

*

*

​

​

​

*

*

* Ставиться на перетині рядка і стовпця, якщо імпліканта входить в будь-який вихідний терм

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

15 of 34

15

  • 3. Знаходження суттєвих импликант

номери стовпців

1

2

3

4

5

6

7

8

НАборе

0011

0100

0101

0111

1 001

1011

1100

тисяча сто один

імпліканти

3-го і 2-го рангу

​

​

​

​

​

​

​

​

​

*

​

​

*

​

​

​

​

​

*

​

​

​

​

*

​

​

​

​

​

*

*

​

​

​

​

​

​

​

​

​

*

*

​

​

​

​

​

​

​

*

​

​

*

​

​

*

*

​

​

​

*

*

Cуттєвою є імпліканта, навпроти якої в стовпці стоїть єдина *

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

16 of 34

16

  • 4. Видалення зайвих стовпців

номери стовпців

1

2

3

4

5

6

7

8

Набори

0011

0100

0101

0111

1 001

1011

1100

1101

імпліканти

3-го і 2-го рангу

​

​

​

​

​

​

​

​

​

*

​

​

*

​

​

​

​

​

*

​

​

​

​

*

​

​

​

​

​

*

*

​

​

​

​

​

​

​

​

​

*

*

​

​

​

​

​

​

​

*

​

​

*

​

​

*

*

​

​

​

*

*

Виділяються стовпці, в яких * стоїть навпроти суттєвої імпліканти

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

17 of 34

17

  • 4. Видалення зайвих стовпців

номери стовпців

1

2

3

4

5

6

7

8

Набори

0011

0100

0101

0111

1 001

1011

1100

1101

імпліканти

3-го і 2-го рангу

​

​

​

​

​

​

​

​

​

*

​

​

*

​

​

​

​

​

*

​

​

​

​

*

​

​

​

​

​

*

*

​

​

​

​

​

​

​

​

​

*

*

​

​

​

​

​

​

​

*

​

​

*

​

​

*

*

​

​

​

*

*

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

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

18 of 34

18

  • 5. Викреслювання зайвих первинних імплікант

номери стовпців

1

4

5

6

Набори

0011

0111

1 001

1011

імпліканти

3-го і 2-го рангу

​

​

​

​

​

*

*

​

​

​

*

​

​

*

​

​

*

​

​

​

​

​

*

*

​

​

​

*

​

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

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

19 of 34

19

  • 6. Вибір мінімального покриття
  • 7. Складання мінімальної форми вихідної функції
  • Мінімальна форма складається з суми суттєвих імплікант, визначених у п.3 і первинних імплікант, що покривають залишилися минтермов, визначених у п.6: і :

перевагу

віддається покриттю

з мінімальним

сумарною кількістю

букв в імплікантах

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

20 of 34

20

Недолік методу Квайна

  • Необхідність попарного порівняння всіх термів на першому етапі при знаходженні первинних імплікант
  • З ростом числа вихідних термів збільшується кількість попарних порівнянь, що ускладнює розв’язування
  • Вихід: модифікація методу

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

21 of 34

21

  • Метод Квайна-Мак-Класки - модифікація методу Квайна
  • Грунтується на числовому і кубічному поданні термів ДНФ
  • Числове уявлення ФАЛ - спрощення процедури знаходження первинних імплікант на першому етапі
  • Початкове задання функції визначається для зручності десятковими кодами довічних кубів, відповідних ДНФ
  • Куби попередньо розбиваються на підгрупи, що визначаються однаковою кількістю одиниць
  • Розбиття дає можливість порівнювати куби тільки сусідніх по числу одиниць груп для зменшення кількості переборовши

Модифікація методу Квайна - метод Квайна-Мак-Класки 1

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

22 of 34

22

Модифікація методу Квайна - метод Квайна-Мак-Класки 2

  • Вихідні терми записуються у вигляді їх довічних номерів
  • Всі номери розбиваються на непересічні групи за кількістю одиниць
  • Умова освіти r-куб - наявність розбіжності в (r-1) -куб тільки по одній координаті в одному двійковому розряді і наявність загальних незалежних координат
  • В i-группу включають всі номери наборів, що мають в своєму записі i одиниць
  • Попарне порівняння проводиться тільки між сусідніми по номеру групами

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

23 of 34

23

Приклад мінмізаціі за методом Квайна-Мак-Класки 1

  • мінімізувати

функцію:

№

х1

х2

х3

х4

f (x1, x2, x3, х4)

№

х1

х2

х3

х4

f (x1, x2, x3, х4)

0

0

0

0

0

0

8

1

0

0

0

0

1

0

0

0

1

0

9

1

0

0

1

1

2

0

0

1

0

0

10

1

0

1

0

0

3

0

0

1

1

1

11

1

0

1

1

1

4

0

1

0

0

1

12

1

1

0

0

1

5

0

1

0

1

1

13

1

1

0

1

1

6

0

1

1

0

0

14

1

1

1

0

0

7

0

1

1

1

1

15

1

1

1

1

0

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

24 of 34

24

Приклад мінмізаціі за методом Квайна-Мак-Класки 2

  • випишемо всі 0-куби (Точки) у вигляді комплексу K0:

​

​

​

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

25 of 34

25

Приклад мінмізаціі за методом Квайна-Мак-Класки 3

  • розіб'ємо комплекс K0 на групи за кількістю одиниць в кожному двійковому наборі. Таких груп буде три:

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

26 of 34

26

Приклад мінмізаціі за методом Квайна-Мак-Класки 4

1. Визначення первинних импликант:

а) порівнюємо сусідні по номеру групи кубів:

​

склеювання кубів

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

27 of 34

27

Приклад мінмізаціі за методом Квайна-Мак-Класки 5

За результатами склеювання складаємо K123 куб:

склеювання кубів

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

28 of 34

28

Приклад мінмізаціі за методом Квайна-Мак-Класки 6

б) розбиваємо все 1-куби на групи в залежності від положення незалежних координат Х:

Нижній індекс відповідає порядковому номеру розташування незалежної координати Х

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

29 of 34

29

Приклад мінмізаціі за методом Квайна-Мак-Класки 7

Порівнюємо куби всередині кожної групи з метою отримання K2-куб:

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

30 of 34

30

Приклад мінмізаціі за методом Квайна-Мак-Класки 8

номери стовпців

1

2

3

4

5

6

7

8

НАборе

0011

0100

0101

0111

1 001

1011

1100

тисяча сто один

0X11

*

​

​

*

​

​

​

​

X011

*

​

​

​

​

*

​

​

01X1

​

​

*

*

​

​

​

​

10X1

​

​

​

​

*

*

​

​

1X01

​

​

​

​

*

​

​

*

X10X

​

*

*

​

​

​

*

*

2. Складання таблиці та розстановка міток.Складаємо таблицю вихідних термів і тих импликант, які не брали участь в склеюванні. Якщо в початковий терм входить якась первинна импликанта, то на перетині відповідного рядка і стовпця вказується мітка*

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

31 of 34

31

3. Знаходження істотних импликант.Істотна імплітанта визначається єдиною міткою в будь-якому стовпці таблиці. Суттєвою импликантой другого рангу є терм, відповідний 2-кубу Х10Х. Виділяємо стовпці відповідні суттєвої импликанте.

Приклад мінмізаціі за методом Квайна-Мак-Класки 9

​

номери стовпців

1

2

3

4

5

6

7

8

​

НАборе

0011

0100

0101

0111

1 001

1011

1100

тисяча сто один

A

0X11

*

​

​

*

​

​

​

​

B

X011

*

​

​

​

​

*

​

​

C

01X1

​

​

*

*

​

​

​

​

D

10X1

​

​

​

​

*

*

​

​

E

1X01

​

​

​

​

*

​

​

*

​

X10X

​

*

*

​

​

​

*

*

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

32 of 34

32

Приклад мінмізаціі за методом Квайна-Мак-Класки 9

​

номери стовпців

1

4

5

6

​

НАборе

0011

0111

1 001

1011

A

0X11

*

*

​

​

B

X011

*

​

​

*

C

01X1

​

*

​

​

D

10X1

​

​

*

*

E

1X01

​

​

*

​

A ν D

З урахуванням отриманої суттєвої імпліканти виписуємо остаточне уявлення функції:

4. Мінімальне покриття.Складаємо таблицю для решти невиділених термів і импликант. Вирішуємо задачу покриття рядків стовпцями.

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

33 of 34

висновки

  • Методи мінімізації булевих функцій використовуються у всіх програмних додатках, пов'язаних з синтезом обчислювальних пристроїв
  • Вони дозволяють в середньому на 20-30% отримати більш економічний проект з позиції витрат апаратури
  • Найбільш практично орієнтованим є метод Квайна-Мак-Класки, який оперує кубічним поданням булевих функцій
  • Недоліком обох методів є застосування импликантной таблиці для вирішення задачі знаходження мінімального покриття, яке вимагає великого обсягу пам'яті для реальних об'єктів

33

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua

34 of 34

Тест-питання

1. Вказати, які куби склеюються:

  • а) Х00, Х10;
  • б) 011, 100;
  • в) 10Х, 01Х;
  • г) жодна пара не склеюється.

2. Склеювання кубів 010 і 011 дає:

  • а) Х00; б) 0ХХ;
  • в) 101; г) 01Х.

3. Куб ХХ1 є

  • а) 1-кубом; б) 2-кубом;
  • в) 0-кубом.

4. Куб 00х є

  • а) 1-кубом;
  • б) 2-кубом;
  • в) 0-кубом.

34

5.Куб 011 є

  • а) 1-кубом;
  • б) 2-кубом;
  • в) 0-кубом.

6. Кожна импликанта в СДНФ відповідає

а) нульового значення функції;

б) значенням функції, рівному одиниці.

7. Кожна импликанта в СКНФ відповідає

а) нульового значення функції;

б) значенням функції, рівному одиниці.

Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки 2011

ХНУРЭ, факультет КИУ, кафедра АПВТ,

тел. 7021 326, e-mail: ri@kture.kharkov.ua