Мінімізація булевых функцій

Задачі

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

Виконати графічну мінімізацію заданих у задачі 2 булєвих функцій, вважаючи виділені вершини конституентами нуля.

Виконати графічну мінімізацію заданих за допомогою формул:

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₂ùx₃ùx₄;

x₁(x₂+ùx₄)ùx₂(x₁+ùx₃);

ùx₂(x₁+ùx₂+x₃+x₄)ùx₁ùx₃(ùx₂+x₄)₂x₃(x₁+x₂)(ùx₃+x₄).

a b

с d

Рис. 3.2. Графічне завдання булевых функцій

Виконати мінімізацію заданих булєвих функцій від трьох перемінних для ДНФ і КНФ за допомогою карт Карно:

a

Таблиця 3.2

x1,x2 x3

b

Таблиця 3.3

x1,x2 x3

c

Таблиця 3.4

x1,x2 x3

d

Таблиця 3.5

x1,x2 x3

Виконати мінімізацію булєвих функцій від чотирьох перемінних, для ДНФ і КНФ за допомогою карт Карно:

a

Таблиця 3.6

x1,x2 x3x4

b

Таблиця 3.7

x1,x2 x3x4

c

Таблиця 3.8

x1,x2 x3x4

d

Таблиця 3.9

x1,x2 x3x4

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

Ú(0, 2, 3, 6, 7, 10, 11, 12, 13, 15);

Ú(0, 2, 4, 5, 6, 8, 9, 10, 12, 14, 15);

Ú(2, 3, 5, 7, 8, 10, 11, 12, 13);

Ú(0, 2, 5, 7, 8, 10, 11, 13, 14, 15);

Ú(0, 2, 4, 5, 6, 7, 8, 9, 13).

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

Ù(1, 4, 5, 8, 9, 14);

Ù(1, 3, 7, 11, 13);

Ù(0, 1, 4, 6, 9, 14, 15);

Ù(1, 3, 4, 6, 9, 12);

Ù(1, 3, 10, 11, 12, 14, 15).

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

Виконати мінімізацію заданих у задачі 6 булєвих функцій методом Блейка-Порецького для ДНФ.

Виконати мінімізацію заданих у задачі 7 булєвих функцій методом Блейка-Порецького для КНФ.

Порівняти ціни по Квайну МДНФ і МКНФ, отриманих у задачах 6 і 7 (чи 9 і 10, тому що результати повинні бути тотожні). Виконати аналітичне перетворення МДНФ у МКНФ і навпаки, переконавши в тотожності формул і правильності виконання мінімізації.

Виконати графічну мінімізацію заданих на рис. 3.3. частково визначених булєвих функцій від трьох перемінних, вважаючи світлі виділені вершини відповідними конституентам одиниці, а темні виділені вершини – байдужним наборам.

a b

Рис. 3.3. Графічне завдання частково визначених булєвих функцій

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

Виконати мінімізацію заданих часткових булєвих функцій від чотирьох перемінних за допомогою карт Карно:

a

Таблиця 3.10

x1,x2 x3x4
	х			х
		Х		Х

b

Таблиця 3.11

x1,x2 x3x4
				х
		Х		Х
				Х
	Х

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

Ú(0, 2, 3, 6, 7, 10, 11, 12, 13), ´(8, 14, 15);

Ú(0, 2, 4, 5, 6, 8, 9, 10, 12, 14), ´(7, 11, 15);

Ú(2, 3, 5, 8, 10, 11, 12, 13), ´(1, 7, 9);

Ú(2, 5, 8, 10, 11, 14, 15), ´(0, 7, 13).

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

Ù(1, 4, 5, 9), ´(8, 14, 15);

Ù(1, 3, 13), ´(7, 11, 15);

Ù(0, 4, 6, 14, 15), ´(1, 7, 9);

Ù(1, 3, 4, 6, 9, 12), ´(0, 7, 13).

Виконати мінімізацію заданих у задачі 15 часткових булєвих функцій методом Блейка-Порецького для ДНФ.

Виконати мінімізацію заданих у задачі 16 часткових булєвих функцій методом Блейка-Порецького для КНФ.

Порівняти ціни по Квайну для МДНФ і МКНФ, отриманих у задачах 15 і 16 (чи 17 і 18, тому що результати повинні бути тотожні). Виконати аналітичне перетворення МДНФ у МКНФ і навпаки, переконавши в необов'язковій тотожності формул, пояснити причину нетотожності.