Приклади розв’язання типових задач

3 4 5 6 7 8 9

Задача 1. Звести формулу до диз’юнктивної нормальної форми (ДНФ) та досконалої диз’юнктивної нормальної форми (ДДНФ).

Розв’язання. Використовуючи означення операцій “стрілка Пірса” та “штрих Шеффера”, маємо

Для того, щоб побудувати ДДНФ застосуємо формулу розщеплення:

Задача 2. Використовуючи теорему про диз’юнктивний розклад булевої функції, розкласти функцію за змінними та .

Розв’язання. За теоремою про диз’юнктивний розклад маємо:

Обчислимо:

;

Підставивши отримані значення у формулу диз’юнктивного розкладу, маємо

Задача 3. Нехай булева функція задана таблицею

Побудувати ДДНФ та досконалу кон’юнктивну нормальну форму (ДКНФ) даної функції.

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

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

Задача 4. Скільки існує самодвоїстих функцій від змінних?

Розв’язання. Множина наборів, значення на яких визначають самодвоїсту функцію, містить елементів (половина всіх можливих наборів). Оскільки булева функція на кожному наборі може приймати два значення 0 та 1, то існує самодвоїстих функцій від змінних.

Задача 5. Довести, що на протилежних наборах самодвоїста функція приймає протилежні значення.

Розв’язання. Нехай – самодвоїста функція, тобто

Маємо

Задача 6. Побудувати булеву функцію , двоїсту до функції .

Розв’язання. Замінимо в даній функції всі знаки на (двічі), на та 0 на 1. Використавши дужки для того, щоб порядок виконання операцій залишився тим же, маємо

Задача 7. Мінімізувати за допомогою методу Квайна булеву функцію

За допомогою методу Петрика виписати всі тупикові ДНФ та вибрати серед них мінімальні.

Розв’язання. Виконавши всі можливі операції склеювання, отримаємо диз’юнкцію всіх можливих імплікант функції (скорочену ДНФ):

Очевидно, що операція поглинання не може бути застосованою до отриманої формули. Будуємо імплікантну таблицю.


•	•
•					•
	•	•
		•	•
			•	•
				•	•

У таблиці відміченими є ті клітинки, для яких проста імпліканта, що маркує рядок, є власною частиною повної елементарної кон’юнкції, що маркує стовпчик (імпліканта поглинає відповідну повну елементарну кон’юнкцію). Сформуємо набори покриттів і випишемо мінімальні тупикові ДНФ.

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

ТДНФ ; ТДНФ .

Ці тупикові форми і будуть мінімальними.

Для того, щоб за допомогою методу Петрика виписати всі тупикові форми, поставимо у відповідність кожній простій імпліканті даної функції деяку літеру (ідентифікатор) – перший стовпчик таблиці. Кожному стовпчику приписується диз’юнкція літер, які відповідають тим рядкам, в яких у даному стовпчику стоїть значок “•” – останній рядок таблиці. Далі утворюємо кон’юнкцію цих диз’юнкцій:

Це і буде формула покриття конституент одиниці простими імплікантами.

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

( поглинає та ). Кожна елементарна кон’юнкція утвореної ДНФ відповідає одній тупиковій формі даної функції, тобто

ТДНФ ;

ТДНФ .

Очевидно, що перші дві тупикові форми і будуть мінімальними.

1. На інтерпретаціях № 2 та № 5 знайти істинносне значення функції .

2. Чи буде функція тотожно дорівнювати 0 чи 1?

3. Нехай задана функція .

a) Який порядковий номер цієї функції?

b) Застосовуючи тотожні перетворення, спростити формулу, яка задає .

c) Розкласти функцію за змінною .

d) Побудувати ДКНФ функції .

e) Побудувати . Чи буде функція самодвоїстою?

4. Застосовуючи тотожні перетворення, привести функцію до виду ДНФ, а потім ДДНФ.

5. Функція від трьох змінних набуває значень 1 на наборах № 1, 2, 4, 7. Побудувати ДДНФ і ДКНФ. З’ясувати, чи буде ця функція самодвоїстою.

6. З’ясувати, чи будуть повними системи функцій:

a) ; b) .

7. З’ясувати, які з елементарних кон’юнкцій, складених з двох змінних та , є імплікантами функції . Чи будуть вказані імпліканти простими? Вказати прості імпліканти.

8. За допомогою карт Карно мінімізувати булеві функції:

a) ;

b) .

9. Функція приймає значення 1 на наборах: 010, 011, 100, 101 та 111. За допомогою методу Петрика знайти тупикові ДНФ та вибрати серед них мінімальні форми.

10. Привести булеву функцію до ДДНФ та мінімізувати її аналітичним методом.