Juk_Ilyenko_Moklyachuk_Orlovskiy_DM_praktikum

= =

{( , , , )| ( , , , )=1}

= ( 0 0 0 0) ( 0 0 0 1) ( 0 0 1 1) ( 0 1 0 0)

( 0 1 1 0 ) ( 1 0 0 0) ( 0 0 0 1)

( 1 0 1 1) ( 1 1 0 0) ( 1 1 0 1) =

= ( ) ( ) ( ) ( )

( ) ( ) ( )

( ) ( ) ( ).

Для знаходження ДКНФ даної функцiї, оберемо тi значення змiнних, для яких функцiя приймає значення 0. Складемо для всiх таких комбiнацiй змiнних диз’юнкцiї, ставлячи заперечення над змiнною, якщо та рiвна 0. Кон’юнкцiя всiх таких диз’юнкцiй i буде ДДНФ функцiї.

= =

{( , , , )| ( , , , )=0}

= ( 1 1 0 1) ( 1 0 1 0) ( 1 0 0 0)

140

( 0 1 0 1) ( 0 0 0 1) ( 0 0 0 0) =

= ( ) ( ) ( )

( ) ( ) ( )

Знайдемо тепер скорочени ДНФ iз ЗДНФ методом Квайна. Для зручностi, замiсть символiв змiнних будемо працювати лише з показниками їх степенiв. Наприклад, замiсть будемо писати 0 − 1−. Тодi ЗДНФ функцiї буде вiдповiдати множинi всiх її одиничних наборiв.

Випишемо одиничнi набори даної булевої функцiї в таблицю, розбивши її на группи по кiлькостi одиниць. Тодi для застосування формули неповного склеювання достатньо розглянути усi можливi пари наборiв, якi входять в сусiднi групи. Наприклад, склеювання 0000 та 0001 дасть в результатi 000−, адже вони вiдрiзняються лише в однiй позицiї. А склеїти 1100 та 0001 не вдасться, адже вони вiдрiзняютсья бiльш нiж в однiй позицiї. Результати склеювання наборiв з першої полоси розмiстимо у другiй полосi, а набори, якi брали участь у склеюванi, позначимо хрестиком.

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

По завершеннi процедури всi простi iмплiканти попадуть в таблицю i не будуть вiдмiченi хрестиком. Вiдмiченi кон’юнкцiї зникнуть пiсля застосування формули поглинання.

141

Скорочена ДНФ даної булевої функцiї буде мати вигляд ( ) ( ) ( ) ( ) ( ).

№ 14.2. Для булевої функцiї з попереднього прикладу та її скороченої ДНФ побудувати матрицю Квайна та вказати ядровi iмплiканти. За допомогою побудованої матрицi найти мiнiмальну ДНФ та вказати її складнiсть.

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

142

Ядровими iмплiкантами будуть 1, 4 та 5, адже для кожної з них знайдеться такий одиничний набiр, при якому лише одна дана iмплiканта буде iстинною.

Знайдемо тепер мiнiмальну ДНФ функцiї. Оберемо найменьше число таких стовпцiв, щоб для кожного рядка даної таблицi i хоча б одної одиницi в цьому рядку знайшовся хоча б один стовпець iз числа обраний, що її мiстить. Тодi диз’юнкцiя членiв, якi вiдповiдають обраним стовпцям, i буде мiнiмальною ДНФ.

143

Для вибору найменьшого числа таких стовпцiв складемо символьний вираз: (2 3) (2 4) 4 (1 3) 1 (12 3 5) (2 4 5) 4 (5 3) 5. Спростимо даний вираз до ДНФ за допомогою дистрибутивного закону та формули поглинання. Отримаємо (2 3) 4 1 5 = 1 4 1 5 1 3 4 5.

В нашому прикладi символiчнiй кон’юнкцiї 1 2 4 5 вiдповiдає ДНФ

( ) ( ) ( ) ( ), а символiчнiй кон’юнкцiї 1 3 4 5 - ДНФ

( ) ( ) ( ) ( ). Кожна з цих ДНФ має в свому наборi по 9 символiв, вiдповiдно складнiсть обох ДНФ буде рiвна 9. Отже, обидвi ДНФ є мiнiмальними для даної булевої функцiї.

№ 14.3. Для функцiї ( , , ) =1011 1100 знайти мiнiмальну ДНФ та мiнiмальну КНФ за допомогою кар Карно i вказати складнiсть мiнiмальної ДНФ.

Зобразимо карту Карно для функцiї . Згрупуємо нулi та одиницi в найбiльшi можливi прямокутнi групи, в яких кiлькiсть комiрок є степенем двiйки. Вважаємо, що карта "наклеєна"на цилiндр, тобто проходячи нижню межу карти, ми опинимося на верхньому рядку.

144

її складнiсть.

1.( , , , ) = 1111 0101 0011 1101

2.( , , , ) = 1101 1110 1010 1110

3.( , , , ) = 0111 0001 1111 1101

4.( , , , ) = 1100 1110 1111 1011

5.( , , , ) = 1011 1111 1110 0010

6.( , , , ) = 0100 1110 1101 1111

7.( , , , ) = 1111 1110 0111 1100

8.( , , , ) = 1110 0110 1111 1100

9.( , , , ) = 1111 0110 1110 1110

10.( , , , ) = 1011 1111 0001 1111

№14.5. Для заданої функцiї знайти мiнiмальну ДНФ та мiнiмальну КНФ за допомогою карт Карно i вказати складнiсть мiнiмальної ДНФ.

1.( , , ) = 1011 1100

2.( , , ) = 0111 1010

3.( , , ) = 1001 1001

4.( , , ) = 1110 1110

5.( , , ) = 0110 1111

6.( , , , ) = 1110 1110 1111 0001

146

7.( , , , ) = 1111 0010 1111 0111

8.( , , , ) = 1101 1001 1111 0011

9.( , , , ) = 1011 1010 1111 1110

10.( , , , ) = 1101 1100 1111 1101

11.( , , , , ) = 1011 1110 1100 1111 1111 0001 0101 1100

12.( , , , , ) = 1100 1011 1011 1110 1110 1011 0111 1111

13.( , , , , ) = 1011 1111 0011 0001 0110 1101 1011 1110

14.( , , , , ) = 1100 1100 1110 1111 1000 1111 1011 1111

15.( , , , , ) = 1101 0011 1111 1101 1110 1101 0111 1100

147

ЗАНЯТТЯ 15

Основи теорiї графiв

Навчальнi задачi

№ 15.1. Побудувати матрицi сумiжностi та iнцидентностi для графу

Розв’язок. Позначимо вершини та ребра графа.

Складемо матрицю сумiжностi. Для цього ми будуємо матрицю ×, де - кiлькiсть вершин. Кожен елемент вiдповiдає двом вершинам, номери яких вiдповiдають номеру рядку i номеру стовпця, та рiвний 1, коли вершини з’єднанi, та 0, коли нi.

148