Juk_Ilyenko_Moklyachuk_Orlovskiy_DM_praktikum

ЗАНЯТТЯ 12

Булевi функцiї. Досконалi форми

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

№ 12.1. Знайти всi iстотнi та фiктивнi змiннi функцiї , а також рiвносильну їй функцiю, що не мiстить фiктивних змiнних.

( 1, 2, 3) ≡ (( 1 2) 1) 3

Розв’язок. Перевiримо по черзi всi змiннi, пiдставляючи 0 та 1. Для

1 отримаємо

(0, 2, 3) ≡ ((0 2) 0) 3 ≡ 0 3 ≡ 0;

(1, 2, 3) ≡ ((1 2) 1) 3 ≡ 1 3 ≡ 3.

Отже, 1 - iстотна змiнна.

Перевiряємо 2.

( 1, 0, 2) ≡ (( 1 0) 1) 3 ≡ 1 3;

( 1, 1, 2) ≡ (( 1 1) 1) 3 ≡ ( 1 1) 3 ≡ 1 3.

Залишилось перевiрити 3.

( 1, 2, 0) ≡ (( 1 2) 1) 0 ≡ 0;

( 1, 2, 1) ≡ (( 1 1) 1) 1 ≡ ( 1 2) 1.

120

≡ ( ) ( ) ( ) ( ) ( ) ( )

( ) ( ) ( ) ( ) ( ) ( ).

Так як за законом iдемпотентностi ≡ , то залишаємо однаковi елементарнi диз’юнкцiї по одному разу. Виконавши таку операцiю, отримаємо ДДНФ формули .

( ) ( ) ( ) ( ) ( ) ( ) ( ).

№12.3. Знайти ДКНФ для формули

= ( ( )) → (( ) )

Розв’язок. Приведемо до КНФ. Запишемо допомiжний полiном.

( ( )) → (( ) ) ≡ ( ( )) (( ) ) ≡

≡ ( ( )) (( ) ).

Запишемо допомiжний полiном та перетворимо його.

( + )(( + ) ) = ( + )( + ) = 2 + + 2 + 2 2.

Повернувшись до логiчних операцiй та використавши закони iдемпотентностi, будемо мати

( ) ( ) ( )( ) ≡

≡ ( ) ( ) ( ) ( ) ≡

≡ ( ) ( ) ( ).

Тепер додаємо змiннi, яких не вистачає. Для цього скористаємось законами виключення третього ( ≡ 0), дистрибутивностi ( ( ) ≡

122

( ) ( )) та тотожнiстю з константою ( 0 ≡ ). Дiї проводяться аналогiчно випадку з ДДНФ. Другий елемент КНФ уже мiстить усi необхiднi змiннi, тому оперуємо лише першим та третiм елементами. Маємо

( ) ≡ ( ) ( );

( ) ≡ ( ) ( ).

Пiдставляючи отриманi вирази у КНФ, будемо мати

( ) ( ) ( ) ≡ ( ) ( ) ( ) ( ) ( ).

Записавши однаковi елементарнi диз’юнкцiї по одному разу, отримаємо ДКНФ формули .

( ) ( ) ( )

Задачi для аудиторної та домашньої роботи

№ 12.4. Знайти всi iстотнi та фiктивнi змiннi , а також рiвносильну їй функцiю, що не мiстить фiктивних змiнних.

1.( 1, 2, 3) = ( 1 2) ( 2 3);

2.( 1, 2, 3) = ( 1 → ( 2 → 3)) → (( 1 → 2) → ( 1 → 3));

3.( 1, 2, 3) = (( 1 2) 1) → 3;

4.( 1, 2, 3) = ((( 1 2) → 2) → 3) → 2;

5.( 1, 2, 3) = ((( 1 2) 1) → 3) → 1;

6.( 1, 2, 3) = (( 1 2) → 3) → 1;

123

7.( 1, 2, 3) = (( 1 2) → 3) 3;

8.( 1, 2, 3) = (( 1 2) 1) → ( 3 3);

9.( 1, 2, 3) = ( 1 2) 1) → ( 3 3);

10.( 1, 2, 3) = ( 1 2) → ( 3 3);

11.( 1, 2, 3) = ( 1 1) → ( 2 → 3);

12.( 1, 2, 3) = (( 1 2) → ( 3 → 3)) → 1;

13.( 1, 2, 3) = (( 1 2) → 1) → ( 3 → 3);

14.( 1, 2, 3) = ( 1 → ( 1 2)) 3;

15.( 1, 2, 3) = ( 1 → ( 1 2)) 3;

16.( 1, 2, 3) = ( 1 → ( 1 2)) → ( 2 3);

17.( 1, 2, 3) = ( 2 → ( 1 2)) → ( 1 3);

18.( 1, 2, 3) = ( 3 → ( 1 2)) → ( 1 2);

19.( 1, 2, 3) = ( 1 3) → ( 2 → ( 2 3));

20.( 1, 2, 3) = (( 1 2) → 1) → ( 1 3);

21.( 1, 2, 3) = (( 1 2) → 1) ( 1 3);

22.( 1, 2, 3) = ( 1 → ( 2 2)) → ( 3 3);

23.( 1, 2, 3) = ( 2 ( 1 → 1)) → ( 2 3);

24.( 1, 2, 3) = (( 1 2) → ( 2 3)) → ( 1 3);

124

25.( 1, 2, 3) = (( 1 2) → ( 2 3)) → ( 1 3);

26.( 1, 2, 3) = (( 1 2) → ( 1 2)) → ( 3 → 1);

27.( 1, 2, 3) = (( 1 3) → ( 2 → ( 1 2))) → 3;

28.( 1, 2, 3) = (( 1 3) → ( 2 → ( 1 3))) → 3;

29.( 1, 2, 3) = (( 1 2) → ( 3 ( 1 3))) 1.

№12.5. Побудувати таблицю значень булевих функцiй, заданих формулами:

1.(( ) ( )) → ( );

2.(( | ) → ( )) → ;

3.(( → ( )) → ) ( );

4.( ( )) → ( );

5.(( ) ↓ ) → ( → );

6.( | ) → ( );

7.(( ) → ( ↓ )) → ;

8.( ) ( | )) → ;

9.(( | ) ( )) → ;

10.(( → ) ( → )) → ( );

11.(( ( )) ) → ( );

12.(( ) ( → )) → ;

125

13.(( ) → ( )) → ;

14.( ↓ ) ( );

15.(( ) ) → ( | );

16.( ↓ ) ( );

17.(( ↓ ) ( )) → ;

18.(( ) ( )) → ;

19.(( ) ( )) ( | );

20.(( ) → ( ) ↓ ;

21.(( ) ( )) → ;

22.( → ( )) ( );

23.( ( | )) → ( );

24.( ( )) ( → );

25.(( → ) ) → ( | );

26.( ↓ ) ( → ( ));

27.( ↓ ) ( → ( ));

28.(( | ) → ( )) → ( );

29.(( ) ( )) → ( );

30.(( ) ( | )) → ( ).

№12.6. Знайти ДДНФ для формули:

126

127

128

ЗАНЯТТЯ 13

Повнi системи булевих функцiй

№ 13.1. Знайти таблицю значень булевої функцiї ( , ) = ( , , ( , , )), де ( , , ) = (01101000), ( , , ) = (10010100)

Розв’язок. Запишемо таблицю значень функцiй ( , , ) та ( , , )

Тепер складемо таблицю значень функцiї ( , ). Для зручностi випишемо пiд символами функцiй їх значення, що вiдповiдають наборам значень функцiї. Спочатку записуємо значення змiнних та ; потiм виписуємо операнди функцiй i самi функцiї зправа налiво.

129