Визначення належності функції F4 до п’яти чудових класів

1. Дана функція зберігає нуль, так як F(0000)=0.

2. Дана функція зберігає одиницю, так як F(1111)=1.

3. Дана функція несамодвоїста, так як F(0001) = F(1110)=1.

4.Дана функція немонотонна, так як F(1101)=0 < F(1100)=1, хоча набори 1101 і 1100 порівняні і 1101>1100.

5. Дана форма нелінійна, так як канонічна форма алгебри Жегалкіна, що отримана у підрозділі 3.3 є не лінійним поліномом.

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

 

Мінімізація функції F4 методом невизначених коефіцієнтів

Ідея цього методу полягає у відшуканні ненульових коефіцієнтів при кожній імпліканті. Рівняння для знаходження коефіцієнтів представимо таблицею (таблиця 3.7.1). Виконаємо викреслення тих рядків на яких функція приймає нульові значення. Викреслимо вже знайдені нульові коефіцієнти в тих рядках таблиці, що залишилися імпліканти, які залишилися після виконання попередніх дій поглинають ті імпліканти, що розташовані зправа від них.

 

X4

X3

X2

X1

X4X3

X4X2

X4X1

X3X2

X3X1

X2X1

X4X3X2

X4X3X1

X4X2X1

X3X2X1

X4X3X2X1

F4

001*

001*

001*

0001*

0010*

001*

011*

011*

0011*

011*

001*

0101*

011*

011*

111*

0111*

1000*

101*

001*

1001*

101*

111*

011*

1011*

1100*

1110*

111*

111*

111*

1111*

 

 

Таблиця 3.7.1 – таблиця невизначених коефіцієнтів

 

 

За таблиці маємо F4 СДНФ функції:

Розглянувши таблицю як таблицю покриттів маємо МДНФ F4:

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

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

Виконаємо cклеювання термів(рисунок 3.8.1):

 

 

 

0001 00X1

0010 0X01

0011 X001

0101 001X

0111 0X11 0XX1

1000 X011 X0X1

1001 01X1 0XX1

1011 X111 XX11

1100 100X X0X1

1110 1X00 XX11

1111 10X1

1X11

11X0

111X

 

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

 

 

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

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

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

	X3
X4	1
1		1		X2
F4	X1

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

 

Реалізуємо функцію F4 на елементах І/АБО. Реалізація функцій в заданому елементному базисі представлена на рисунку 3.9.2.

Рисунок 3.10.3 – схема функції F4.

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

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

Виконаємо мінімізацію системи функцій F1, F2, F3, заданих таблицею істинності (технічного завдання ІАЛЦ.463626.002 ТЗ) методом Квайна-Мак-класкі. Мінімізуємо за одиницями, тому довизначимо невизначені набори функцій одиницями. Звідси виконаемо склеювання (рисунок 3.10.1):

000X(1,2)

00X0(1,2,3)

0000(1,2,3) 0X00(1,3)

0001(1,2) X000(1,2,3) X11X(1,2)

0010(1,2,3) 0X10(1,2,3) 11XX(1,2)

0100(1,3) 01X0(1,3) 0XX0(1,3)

0110(1,2,3) X100(1,3) X1X0(1)

0111(1,2,3) 011X(1,2,3) 11XX(1,2)

1000(1,2,3) X110(1,2) 0XX0(1,3)

1011(1) X111(1,2,3) XX00(1,3)

1100(1,2,3) 1X00(1,2,3) XX00(1,3)

1101(1,2) 1X11(1) X1X0(1)

1110(1,2) 110X(1,2) X11X(1,2)

1111(1,2,3) 11X0(1,2)

11X1(1,2)

111X(1,2)

 

Рисунок 3.10.1 - Склеювання для мінімізації системи функцій F1,F2,F3
Теперь складемо таблицю покриттів функцій f1,f2,f3 для отримання СДНФ, а потім

і МДНФ (рисунок 3.10.2).

F1

F2

F3

X11X(1,2)

V

V

V

V

V

X1X0(1)

V

V

V

XX00(1,3)

V

V

V

V

V

V

V

0XX0(1,3)

V

V

V

V

V

V

11XX(1,2)

V

V

V

V

V

V

V

1X11(1)

V

V

1X00(1,2,3)

V

V

V

V

V

X111(1,2,3)

V

V

V

V

011X(1,2,3)

V

V

0X10(1,2,3)

V

V

V

V

X000(1,2,3)

V

V

V

V

V

V

00X0(1,2,3)

V

V

V

V

V

V

000X(1,2)

V

V

V

V

 

Рисунок 3.10.2 – Таблиця покриття функцій F1,F2,F3

 

 

З таблиці покриття отримаємо СДНФ, а потім і МДНФ:

І/АБО

І-НЕ/І-НЕ

 

 

 

АБО/І-НЕ

АБО-НЕ/АБО

 

Реалізуємо системи функцій F1, F2, F3 на елементах І/АБО. Реалізація функцій в заданому елементному базисі представлена на рисунку 3.10.3.

 

Рисунок 3.10.3 – схема системи функцій F1, F2, F3.

 

Спільна мінімізація заперечень функцій F1, F2, F3

Виконаємо мінімізацію заперечень невизначених систем функцій F1, F2, F3, заданих таблицею істинності (технічного завдання ІАЛЦ.463626.002 ТЗ) методом Квайна-Мак-класкі. Мінімізуємо за нулями, тому до визначимо невизначені набори функцій нулями. Звідси виконаємо склеювання (рисунок 3.11.1):

00X1(3)

0X01(3)

0001(3) X001(3)

0011(1,2,3) 0X11(1,2)

0100(1,2) X011(2,3)

0101(1,2,3) 010X(1,2) 01XX(2)

0110(2,3) 01X0(2) 01XX(2)

0111(1,2) X100(2) X0X1(3)

1001(1,2,3) 01X1(1,2) XX01(3)

1010(1,2,3) X101(3) X0X1(3)

1011(2,3) 011X(2) XX01(3)

1100(2) X110(3)

1101(3) 10X1(2,3)

1110(3) 1X01(3)

101X(2,3)

1X10(3)

Рисунок 3.11.1 - Склеювання для мінімізації системи функцій F1,F2,F3

 

 

 

 

Тепер складемо таблицю покриттів системи заперечь функцій F1,F2,F3

(рисунок 3.11.2) для отримання СДНФ, а потім і МДНФ.

F1

F2

F3

XX01(3)

V

V

V

V

X0X1(3)

V

V

V

V

01XX(2)

V

V

1X10(3)

V

V

101X(2,3)

V

V

V

V

10X1(2,3)

V

V

V

V

X110(3)

V

01X1(1,2)

V

V

X100(2)

V

010X(1,2)

V

V

V

X011(2,3)

V

V

V

V

0X11(1,2)

V

V

1010(1,2,3)

V

V

V

1001(1,2,3)

V

V

V

0101(1,2,3)

V

V

V

0011(1,2,3)

V

V

V

Рисунок 3.11.2 – Таблиця покриттів функцій F1, F2, F3

 

З таблиці покриттів маємо МДНФ функцій-заперечень:

 

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

І/АБО-НЕ

І-НЕ/І

АБО/І

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

Реалізуємо системи функцій F1, F2, F3 на елементах І/АБО-НЕ. Реалізація функцій в заданому елементному базисі представлена на рисунку 3.11.3.

Рисунок 3.11.3 - схема системи заперечень функцій F1, F2, F3