Juk_Ilyenko_Moklyachuk_Orlovskiy_DM_praktikum

№ 10.7. Знайти загальний розв’язок рекурентного спiввiдношення 5 по-

5.+4 + 4 +3 + 5 +2 + 2 +1 − 12 = 0;

6.+4 − 5 +3 − 2 +2 + 14 +1 − 20 = 0;

8.+4 − 4 +3 − 27 +2 − 6 +1 + 36 = 0;

9.+4 + +3 − 30 +2 + 42 +1 − 36 = 0;

11.+4 − 4 +3 + +2 − 6 +1 + 36 = 0;

12.+4 + +3 − 22 +2 + 42 +1 − 36 = 0;

14.+4 − 7 +3 + 8 +1 − 56 = 0;

15.+4 − 6 +3 − 23 +2 − 34 +1 − 18 = 0.

№10.8. Знайти загальний розв’язок рекурентного спiввiдношення 5 порядку при заданих початкових умовах.

110

1.( + 4) = 5 ( + 3) − ( + 2) − 21 ( + 1) + 18 ( ), (0) = 3,

(1) = 8, (2) = 8, (3) = 38;

2.( + 4) = − ( + 3) + 7 ( + 2) + 13 ( + 1) + 6 ( ), (0) = 1,

(1) = 6, (2) = 1, (3) = 44;

3.( + 4) = −6 ( + 3) + 22 ( + 1) − 15 ( ), (0) = 5, (1) = −4,

(2) = 19, (3) = −54;

4.( + 4) = 3 ( + 3) + 3 ( + 2) − 7 ( + 1) − 6 ( ), (0) = 3,

(1) = −3, (2) = 12, (3) = −3;

5.( + 4) = 7 ( + 3) − 12 ( + 2) − 4 ( + 1) + 16 ( ), (0) = 4,

(1) = −3, (2) = −1, (3) = −19;

6.( + 4) = ( + 3) + 7 ( + 2) − 13 ( + 1) + 6 ( ), (0) = 3,

(1) = 3, (2) = 4, (3) = 7;

7.( + 4) = 4 ( + 3) − 3 ( + 2) − 4 ( + 1) + 4 ( ), (0) = 0,

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

8.( + 4) = 5 ( + 3) + 3 ( + 2) − 13 ( + 1) − 10 ( ), (0) = 3,

(1) = 3, (2) = 0, (3) = 15;

9.( + 4) = 11 ( + 3) − 39 ( + 2) + 49 ( + 1) − 20 ( ), (0) = 2,

(1) = 0, (2) = −11, (3) = −58;

10.( + 4) = 6 ( + 3) − 8 ( + 2) − 6 ( + 1) + 9 ( ), (0) = 1,

(1) = 3, (2) = 17, (3) = 51;

11.( + 4) = 3 ( + 3) + 2 ( + 2) − 12 ( + 1) + 8 ( ), (0) = 6,

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

111

12.( + 4) = 9 ( + 2) + 4 ( + 1) − 12 ( ), (0) = 5, (1) = −3,

(2) = 19, (3) = −37;

13.( + 4) = − ( + 3) + 12 ( + 2) + 28 ( + 1) + 16 ( ), (0) = −2,

(1) = −1, (2) = 9, (3) = −29;

14.( + 4) = −7 ( + 3) − 13 ( + 2) + 3 ( + 1) + 18 ( ), (0) = 2,

(1) = 1, (2) = 7, (3) = −17;

15.( + 4) = 2 ( + 3) + 12 ( + 2) − 18 ( + 1) − 27 ( ), (0) = 4,

(1) = 2, (2) = 4, (3) = 50.

112

ЗАНЯТТЯ 11

Алгебра логiки. Нормальнi форми

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

№11.1. Чи будуть наступнi вирази формулами:

1.( 1 2) → ( 3);

2.1 2 → 3;

3.( 1 2) → 3;

4.(( 1 2) → 3).

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

Вираз 4 є формулою.

№ 11.2. Довести, що кожна формула алгебри логiки рiвносильна формулi, що мiстить лише логiчнi символи , , ¬.

Розв’язок. Твердження задачi випливає з рiвносильностей → ≡, ≡ ( ) ( ) та правила пiдстановки.

№ 11.3. Для формули = ( → ( )) ( ) знайти двоїсту.

113

Розв’язок. Перетворимо формулу в рiвносильну з логiчними символами , , ¬. Маємо

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

Замiнивши логiчнi символи на двоїстi, маємо

* = ( ( )) (( ) ( )).

№11.4. Знайти ДНФ формули

= (( ) → ( )) ( ).

Розв’язок. Перейдемо до логчних символiв ¬, , та побудуємо формулу з тiсними запереченнями (кожне заперечення вiдноситься лише до змiнних).

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

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

Розкриємо дужки у формулi . Це зручно зробити, розглянувши допомiжний алгебраїчний полiном, в якому в формулi замiнити операцiю

на множення, а операцiю на додавання. Маємо

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

Скориставшись тим, що ≡ 0 та ≡ 0, будемо мати

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

Так як ≡ та ≡ 0, отримаємо

+ + + = + + .

114

Переходячи вiд множення та додавання назад до логiчних операцiй, отримаємо ДНФ формули :

( ) ( ) ( ).

№11.5. Знайти КНФ формули

= (( → ) → ( → )) → ( → ).

Розв’язок. Аналогiчно попереднiй задачi, перейдемо до логчних символiв ¬, , та побудуємо формулу з тiсними запереченнями.

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

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

≡(( ) ( )) = .

Розкриємо дужки у формулi , замiнивши операцiю на множення, а операцiю на додавання. Отримаємо

(( ) + ) = + .

Скориставшись тим, що ≡ та ≡ 1, другий доданок останньої формули можна вiдкинути. Переходячи назад до логiчних операцiй, отримаємо необхiдну ДНФ:

( ).

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

№11.6. Визначити, чи будуть наступнi вирази формулами:

1.( 1 2) 3 4;

115

2.( 1 2) → 3;

3.(( 1 → 1) 3);

4.((( 1 → 2) (( 2 3))).

№11.7. Розставити дужки в наступних виразах так, щоб отримати формулу:

1.1 → 2 2 3;

2.1 → 2 → 3 1 → 2

№11.8. Довести, що кожна з формул алгебри логiки рiвносильна формулi з тiсними запереченнями. Вказiвка: використати задачу 11.2 та закони двоїстостi.

№11.9. Знайти двоїстi для наступних формул:

1.(( ) → ) → ( );

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

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

4.((( ) → ( )) → ( )) → ;

5.(( ) → ( )) ;

6.(( ) ( )) → ;

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

8.(( ) → ( )) → ;

9.(( ) → ( )) → ( ).

116

№11.10. Знайти двоїстi до даних рiвносильностей:

1.≡ ;

2.0 ≡ ;

3.≡ ;

4.( ) ≡ ( );

5.≡ ;

6.( ) ≡ ;

7.( ) ≡ ;

8.( ) ≡ ;

9.( ) ≡ ;

10.( → ) ≡ ;

11.( ) ( ) ( ) ( ) ≡ ( ) ( );

12.( ) ( ) ≡ ( ) ( );

13.( ) ( ) ≡ ;

14.( ) (( ) ( )) ≡ ;

15.( ) ≡ .

№11.11. Знайти ДНФ та КНФ формул:

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

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

117

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

4.(( ) → ) → (( ) → );

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

6.(( ) ) (( → ) → );

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

8.(( ) → ) → ( );

9.(( ) → ) → ( → );

10.((( ) ) → ) → ;

11.((( ) ) → ) → ;

12.(( ( )) → ) → ;

13.(( ( )) ) → ;

14.( → ( )) → ( );

15.(( → ( )) ) → ;

16.(( ) ) → ( → );

17.((( ) → ) ) → ;

18.((( ) ) ) → ;

19.((( ) ) ) → ;

20.((( ) ) ) → ( );

118

21.(( ) ) → ( → );

22.(( → ( )) → ) → ( );

23.( → ) → (( ) ( ));

24.(( ) ) → ( → );

25.((( ) → ) ) → ;

26.((( ) ) ) → ;

27.(( ) ) → ( → );

28.(( ) ) → ( );

29.(( → ) ) ( → );

30.((( ) ) ) → ;

31.(( → ) ( → ( )));

32.((( ) ) ) → ;

33.((( ) ) ) → .

№11.12. Довести, що якщо є тотожно iстинною КНФ, то для довiльної елементарної диз’юнкцiї формули iснує така змiнна , що та

входять в цю диз’юнкцiю.

№ 11.13. Довести, що якщо є тотожно хибною ДНФ, то для довiльної елементарної кон’юнкцiї формули iснує така змiнна , що та входять в цю кон’юнкцiю.

119