6.2 Лабораторна робота №5

Тема. Логіка предикатів 1-го порядку.

Мета. Засвоїти основні поняття (Поняття n-місного предикату. Квантори загальності та існування. Вільні та зв'язані змінні. Алфавіт та формули логіки предикатів . Інтерпретація формул логіки предикатів . Загальнозначимі формули логіки предикатів . Рівносильні перетворення формул з кванторами. Нормальні форми формул логіки предикатів 1-го порядку).

Завдання.

1 Нехай (x) А₁²(f₁¹(x), n)  (x) А₂²(f₂¹(x), n) формула логіки предикатів 1-го порядку(де n порядковий номер студента в журналі). Розглянути 2 інтерпретації формули. В 1-й інтерпретації значення формули повинно бути "істина", а в 2-й інтерпретації - "хибність"

2 Розглянути формулу, яка є запереченням .формули із 1-го завдання, та її інтерпретацію із значенням "хибність"

3 Формулу із 2-го завдання перетворити у таку рівносильну їй формулу в заданій інтерпретації, яка не містила б операцій заперечення.

4 Побудувати попередню нормальну форму для формули із 1-го завдання.

Приклад виконання завдання

1 Нехай (x) А₁²(f₁¹(x), а₁)  (x) А₂²(f₂¹(x), а₁) формула логіки предикатів 1-го порядку . Розглянемо 2 інтерпретації формули. В 1-й інтерпретації значення формули повинно бути "істина", а в 2-й інтерпретації - "хибність"

Перша інтерпретація D = R; а₁=37, f₁¹(x)= х +37,

А₁²(f¹(x), а₁) =" f₁¹(x)  а₁".

f₂¹(x)=x² , А₂²(f₂¹(x), а₁) =" f₂¹(x)= а₁"

Отримане висловлення (x) (  х +37 37)  (x) (x² =37) є істинним.

Друга інтерпретація D = N; a₁=37, f₁¹(x)=sinx,

А₁²(f₁¹(x), а₁) = " f₁¹(x) > а₁".

f₂¹(x)=x , А₂²(f₂¹(x), а₁) =" f₂¹(x)= а₁"

Отримане висловлення (x) ( sinx >37)  (x) (x =37) є хибним.

2 Розглянемо формулу, яка є запереченням .формули із 1-го завдання, та її інтерпретацію із значенням "хибність"

((x) А₁²(f₁¹(x), а₁)  (x) А₂²(f₂¹(x), а₁)) 

(x) А₁²(f₁¹(x), а₁)  (x) А₂²(f₂¹(x), а₁)

Інтерпретація D = R; а₁=37, f₁¹(x)=cosх,

А₁²(f¹(x), а₁) = " f₁¹(x) > а₁".

f₂¹(x)=x, А₂²(f₂¹(x), а₁) =" f₂¹(x)= а₁"

Отримане висловлення (існує х, для якого не виконується нерівність cosх  37, або для будь-якого х не виконується рівність х=37) є хибним.

3 Формулу із 2-го завдання перетворимо у таку рівносильну їй формулу в заданій інтерпретації, яка не містила б операцій заперечення.

Отримане висловлення (існує х, для якого виконується нерівність cosх  37, або для будь-якого х виконується нерівність х37)є хибним.

4 Побудуємо попередню нормальну форму для формули із 1-го завдання.

(x) А₁²(f₁¹(x), а₁)  (x) А₂²(f₂¹(x), а₁) 

(x) А₁²(f₁¹(x), а₁)  (y) А₂²(f₂¹(y), а₁) 

(x) (y)(А₁²(f₁¹(x), а₁)  А₂²(f₂¹(y), а₁)).

6.3 Контрольні питання

1 Логіка предикатів .

2. Поняття n-місного предикату.

3. Квантори загальності та існування. Вільні та зв'язані змінні.

4. Алфавіт логіки предикатів .

5. Формули логіки предикатів .

6. Інтерпретація формул логіки предикатів .

7. Загальнозначимі формули логіки предикатів .

8. Рівносильні перетворення формул з кванторами.

9. Правило побудови заперечення формул з кванторами.

10. Нормальні форми формул логіки предикатів 1-го порядку.

11. Аксіоми та правила виведення числення (логіки) предикатів 1-го порядку.

12. Виведення формул в численні предикатів 1-го порядку на прикладі.

13. Основні властивості числення предикатів 1-го порядку.

14. Несуперечність числення предикатів 1-го порядку.

15. Теорема дедукції для числення предикатів 1-го порядку.

16 Зв'язок між тавтологіями числення висловлювань та загальнозначимими формулами числення предикатів 1-го порядку.

Додаток 1 Тотожно істинні формули логіки висловлень

1 А ~ А закон тотожності

2

закон суперечності- протиріччя (невірно, що А і не А )

3 закон виключеного третього. Або А –істинне, або не А,

третього не дано.

4  А

Закони тавтології

5  А

6~А Закон подвійного заперечення

7. 

Комутативні закони

8 

9 

Дистрибутивні закони

10

11

Асоциативні закони

12





13

14





15





16





17

18

19







20









21

2









2

23









24



2











5

















26

27

28

29

30

31

32

33

3





4