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

Виходячи з таблиці істинності функції, запишемо стовпчик ДДНФ, відсортувавши терми за кількістю одиниць. Проводимо попарне склеювання між сусідніми групами. Подальше склеювання неможливе.

Виконаємо поглинання термів (рисунок 3.8.1).

0001	0x01	xx01
0010	x001	x1x1
0101	x010	1xx1
1001	01x1	1x1x
1010	x101	11xx
1100	10x1
0111	101x
1011	1x10
1101	110x
1110	11x0
1111	x111
	1x11
	11x1
	111x

Рисунок 3.8.1 – Поглинання термів

Як можна побачити, ми одержали тіж самі імпліканти, що і при мінімізації методом невизначених коефіцієнтів. Тому результат буде той самий:

3.9 Мінімізація функції методом діаграм Вейча

Виконаємо мінімізацію функції методом Вейча (рисунок 3.9.2). Графічні методи призначені для ручної мінімізації. Наочність даного методу зберігається за невеликої кількості аргументів. Кожна клітинка відповідає конституанті. Прямокутник, що містить клітинок, відповідає імпліканті. Прямокутник максимального розміру відповідає простій імпліканті. Правило заповнення діаграм Вейча, на якому цифри в клітинках відповідають значенню функцію на наборі з таким порядковим номером, можна побачити нижче(рисунок 3.9.1).

Рисунок 3.9.1 – Правило заповнення діаграм Вейча

Рисунок 3.9.2 - Мінімізація функції методом Вейча

Як можна побачити, то ми отримали результат, який відрізняється від двох попередніх методів мінімізації:

3.10 Спільна мінімізація функцій

Щоб одержати схеми з мінімальними параметрами необхідно виконати сумісну мінімізацію системи функцій та їх заперечень. Виконаємо мінімізацію системи функцій заданих таблицею істинності (технічного завдання ІАЛЦ.462214.002 ТЗ) методом Квайна-Макласкі.

Виконаємо поглинання термів (рисунок 3.10.1)

0000 (1,2,3)	000X (1,2)	0XX0 (1,3)
0001 (1,2)	00X0 (1,2,3)	0XX0 (1,3)
0010 (1,2,3)	0X00 (1,3)	XX00 (1)
0100 (1,3)	X000 (1)	XX00 (1)
1000 (1)	0X10 (1,2,3)	X1X0 (1)
1100 (1,2,3)	X010 (3)	X1X0 (1)
0110 (1,2,3)	01X0 (1,3)	X11X (1,2)
1001 (3)	X100 (1,3)	X11X (1,2)
1010 (3)	1X00 (1)	11XX (1,2)
1011 (1)	X110 (1,2)	11XX (1,2)
0111 (1,2,3)	11X0 (1,2)
1101 (1,2)	011X (1,2,3)
1110 (1,2)	110X (1,2)
1111 (1,2,3)	1X11 (1)
	X111 (1,2,3)
	11X1 (1,2)
	111X (1,2)

Рисунок 3.10.1 – Поглинання термів

Побудуємо таблицю покриття

Таблиця 3.10.1 – Таблиця покриття ДДНФ

0000

0001

0010

0110

1000

1011

1110

1101

1110

1111

0000

0001

0010

1101

1110

1111

0000

0010

0100

0111

1001

1010

1100

1111

1001 {3}

V

1100 {1,2,3}

V

V

000X {1,2}

V

V

V

V

00X0 {1,2,3}

V

V

V

V

V

V

0X10 {1,2,3}

V

V

V

V

X010 {3}

V

V

X100 {1,3}

V

V

V

011X {1,2,3}

V

V

X111 {1,2,3}

V

V

V

1X11 {1}

V

V

0XX0 {1,3}

V

V

V

V

V

V

XX00 {1}

V

V

V

X1X0 {1}

V

V

V

X11X {1,2}

V

V

V

V

V

11XX {1}

V

V

V

V

V

V

V

Виведемо нормальні формі:

І/АБО

І-НЕ/І-НЕ

АБО/І-НЕ

АБО-НЕ/АБО

Виконаемо мінімізацію заперечення системи функцій

Склеювання і поглинання імплікант:

0001 (3)	00X1 (3)	01XX (2)
0011 (1,2,3)	0X01 (3)	01XX (2)
0100 (1,2)	0X11 (1,2)	10XX (2)
0101 (1,2,3)	X011 (2,3)	10XX (2)
0110 (2,3)	010X (1,2)
0111 (1,2)	01X0 (2)
1000 (2,3)	X100 (2)
1001 (1,2)	01X1 (1,2)
1010 (1,2)	X101 (3)
1011 (2,3)	011X (2)
1100 (2)	X110 (3)
1101 (3)	100X (2)
1110 (3)	10X0 (2)
	1X00 (2)
	10X1 (2)
	101X (2)

Рисунок 3.10.2 – Поглинання термів заперечення

Таблиця 3.10.2 – Таблиця покриття заперечення

0011

0101

1001

1010

0011

0100

0101

1000

1001

1010

1011

0001

0011

0101

1000

1011

1101

1110

0011 {1,2,3}

V

V

0101 {1,2,3}

V

V

0110 {2,3}

1000 {2,3}

V

V

1001 {1,2}

V

V

1010 {1,2}

V

V

00X1 {3}

V

V

0X01 {3}

V

V

0X11{1,2}

V

V

X011 {2,3}

V

V

V

010X {1,2}

V

V

V

X100 {2}

V

01X1 {1,2}

V

V

X101 {3}

V

V

X110 {3}

V

1X00 {2}

V

01XX {2}

V

V

10XX {2}

V

V

V

V

Виведемо нормальні форми:

АБО/І

АБО-НЕ/АБО-НЕ

І/АБО-НЕ

І-НЕ/І