Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою.

Доведення. Достатньо впевнитися в тому, що аксіоми АП1‒ АП5 – загальнозначущі формули, і показати, що застосування правил виведення АП1‒ АП3 до загальнозначущих формул приводить до одержання тільки загальнозначущих формул.

Загальнозначущість аксіом АП1‒ АП3 (вони ж А1‒ А3) було розглянуто в 2.1, 2.2. Покажемо загальнозначущість формули x А (х) → А (у) (аксіома АП4). Припустимо, що ця формула загальнозначуща, тоді одержимо, що у задовільній предметній області є такий набір значень предметних змінних, при якому x А (х) =I, а А (у) = X. Але оскільки є значення предметних змінних, при яких формула А набуває хибного значення X, тоді згідно з квантором загальності формула x А (х) також повинна набувати значення X. Виникла суперечність і доводить загальнозначущість формули х А (х) → А (у), звідки випливає і загальнозначущість аксіоми АП4. При доведенні аксіоми АП5 припустимо, що формула xi (А → В) → (А → xi В) незагальнозначуща. Тоді при деякій інтерпретації формула А → xi В набуде значення X, а xi (А → В) – значення I. Якщо А → xi В = X, то А = I, а xi В = X. Оскільки xi (А → В) = I, то для будь-якого xi при В = X повинне виконуватися А = I. Із суперечності для істинного значення формули А випливає справедливість загальнозначущості аксіоми АП5, що й необхідно було довести.

Теорема 3.6.2. Числення предикатів першого порядку ПL є несуперечною теорією.

Доведення. Припустимо, що для деякої формули А в теорії ПL є дві теореми А і А. Із факту загальнозначущості будь-якої із цих теорем отримаємо, що А= I і А= I, але одночасно цього не може бути, що й потрібно було довести.

Теорема 3.6.3. Якщо формула В не залежить від формули А при доведенні Г, А ├ В, то Г ├ В.

Доведення. Доведення виконаємо індукцією за довжиною виведення , , …, = В. При n = 1 маємо = = B і B або належить Г {A}, або є аксіомою. Але В не може збігатися з А внаслідок незалежності В від А. Отже,

Г ├ В.

Нехай теорема справедлива для всіх формул В, довжина виведення яких менша n. Якщо В Г або В – аксіома, то Г ├ В. Якщо ж В – безпосередній наслідок деяких формул із , , …, (однієї або двох) і оскільки В не залежить від А, то від А не залежить жодна із цих формул. Але тоді за припущенням індукції, із Г виводяться формули (одна або дві), а разом з ними – і формула В, що й по-трібно було довести.

Теорема 3.6.4 (теорема дедукції). Нехай Г, А ├ В і при цьому нехай існує таке виведення В із Г, А, в якому жодне застосування правила узагальнення до формул, які залежать від А в цьому виведенні, не зв’язується квантором загальності формули А. Тоді Г ├ А → В.

Доведення. Доведення проводиться індукцією за довжиною виведення , , …, = В. При n = 1 існують дві можливості:

а) Г або є аксіомою;

б) = А.

У першому випадку а) А → В, оскільки це випливає з аксіоми АП1, → (А → ) за правилом МР.

У випадку б), коли А = , то Г ├ → , оскільки А → А – тавтологія.

Нехай тепер теорема справедлива для всіх і < n. Припустимо, що існують індекси k і j, менші і, і що = → ® . Тоді за припущенням індукції Г ├ А → і Г ├ А → ® ( → ). Але за аксіомою АП2 маємо А→( → ) → → ((А → ) → (А → )) і за правилом МР отримаємо, що Г ├ А → .

Припустимо, що існує такий індекс j < i, що = = xk B. Тоді за припущенням індукції Г ├ А → і або не залежить від А, або xk не є вільною змінною формули А. Якщо не залежить від А, то за теоремою 7.2.1

Г ├ і, застосовуючи правило узагальнення, отримаємо Г ├ хk . За схемою аксіоми АП1 знаходимо, що → ® (А → ) і А → ‒ за правилом МР. За припущенням індукції Г├ А→ , за правилом узагальнення Г├ xk А → ® В і, нарешті, за правилом МР отримаємо Г ├ А → xk , тобто Г ├ А → , що й потрібно було довести.

Наслідок 3.6.1. Якщо Г, А ├ В й існує виведення В без застосування правила узагальнення до вільних змінних формули А, то Г ├ А → В.

Наслідок 3.6.2. Якщо формула А замкнена і Г,А├ В, то Г ├ А → В.

Приклад 3.6.1. Довести, що ├ х у А → х у А.

Розв’язання. Застосуємо предикатні аксіоми, правило МР та узагальнення:

а) х у А – гіпотеза;

б) х у А → у А – аксіома АП4;

в) у А – МР із а), б);

г) у А → А – аксіома АП4;

д) А – МР із в), г);

е) х А – правило узагальнення із д);

є) у х А – правило узагальнення із е).

Теорема 3.6.5. Якщо формули А (х) і А (у) подібні, то ├ х А (х) у А (у).

Доведення. Використовуючи аксіому АП4, маємо

├ х А (х) → А (у). Виходячи з умови теореми 3.6.5 і скориставшись правилом узагальнення, отримаємо

├ у ( х А (х) → А (у)). За схемою аксіоми АП5 маємо

├ х А(х)→ у А (у). Аналогічно доводять і формулу

├ у А (у) → х А (х). Для цього необхідно скористатися тавтологією А → ( В → (А → В) А→(В→

→ АÙ B), унаслідок чого отримаємо х А(х) у А(у).

Теорема 3.6.6 (теорема еквівалентності). Якщо формула В є підформулою А і формула отримана з формули А заміною яких-небудь (можливо, жодного) входжень В формулою С і якщо будь-яка змінна формули В або формули С, що є одночасно пов’язаною змінною формули А, зустрічаються у списку , ,…, , то

├ у₁ у₂… у_k (В С) → (А ).

Доведення. Доведення виконаємо індукцією за числом зв’язок і кванторів у А. Зауважимо, що якщо жодне входження В насправді не змінюється, то А збігається з і формула, яку потрібно вивести, є окремим випадком тавтології В → (А А). Якщо В збігається з А і це єдине входження замінюється на С, то формула, яку необхідно вивести, виводиться із аксіоми АП4. Отже, необхідно вважати, що В є власна підформула формули А і принаймні одне входження В замінюється.

Тепер припустимо, що теорема справедлива для будь-якої формули з меншим числом кванторів і логічних зв’язків, ніж у А.

Випадок 1. А – елементарна формула. Тоді В не може бути власною підформулою формули А.

Випадок 2. А має вигляд D. Тоді нехай A^/ є . За припущенням індукції ├ у₁ у₂… у_k(В С)®(D Û ). Звідси за допомогою тавтології А В → ( А → → В) отримаємо

├ у₁ у₂… у_k (В С) → (А ).

Випадок 3. А має вигляд D → E. Нехай = → . За припущенням індукції

├ у₁ у₂… у_k (В С) → (D ) і ├ у₁ у₂… у_k (В С) → (Е ). Застосовуючи тавтологію ((А В) (C D)) → ((A → C) (B → D)),

отримаємо ├ … (В С) → (А Û ).

Випадок 4. А має вигляд x D. Тоді є x . За припущенням індукції ├"y₁"y₂…"у_k (В С)→(D ). Змінна х не є вільною змінною формули

├ у₁ у₂… у_k (В С). Якщо припустимо, що це так, то х входила б вільно в В або С, і оскільки х пов’язана в А, то х входила б до переліку , ,…, і була б пов’яза-ною змінною в у₁ у₂… у_k (В С), а це суперечить умові. Застосовуючи тепер аксіому АП5, отримаємо

у₁ у₂ … у_k (В С) → (D ). Використовуючи х (А D) → ( х А х D), маємо х (D )→ → ( хD х ). Користуючись транзитивністю імплікації, остаточно отримаємо

у₁ у₂… у_k (В С) → ( хD х ) або у₁ у₂ … у_k (В С) → (А ), що й потрібно було довести.

Теорема 3.6.7 (теорема про заміну). Нехай формули А, , В і С задовольняють умови теореми еквівалентності. Тоді якщо ├ В С, то ├ А , а якщо ├ В С і ├ А, то ├ . Ця теорема є простим наслідком теореми еквівалентності.

Теорема 3.6.8 (теорема перейменування пов’язаних змінних). Якщо х В (х) є підформулою формули А, формула В (у) подібна формулі В(х) і отримана з А заміною хоча б одного входження х В(х) у А на у В(у), то ├ А .

Доведення. Доведення випливає з теорем 3.6.5 і 3.6.7.

 

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

1. Які додаткові нові логічні поняття введені в логіку предикатів і з якою метою?

2. Дайте визначення поняття «предикат».

3. Що називають п -місним предикатом?

4. Що називають порядком предиката?

5. Що називають нульмісним предикатом?

6. Наведіть приклади функціональних символів.

7. Який функціональний символ називають п -місним?

8. Дайте визначення поняття «терма».

9. Що розуміють під предметною областю?

10. Дайте визначення понять «предметна константа» і «предметна змінна».

11. Дайте визначення квантора загальності.

12. Що розуміють під квантором існування?

13. Як позначають квантори загальності та існування?

14. Які змінні називають зв’язаними, а які – вільними?

15. Як залежить значення предиката від зв’язаних або вільних змінних?

16. Поясніть призначення зв’язаних змінних.

17. До яких наслідків призводить застосування квантора за однією із змінних тримісного предиката?

18. Коли предикат у Р (х,у) набуває значення ” Істина ”?

19. Коли предикат х Р (х,у) набуває значення ” Істина ”?

20. Що називають формулою у логіці предикатів?

21. Яку формулу називають атомарною?

22. Що розуміють під областю дії квантора?

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

24. Запишіть правила, згідно з якими формула логіки предикатів може набути істинного або хибного значення.

25. Порівняйте поняття інтерпретації у логіці висловлювань і логіці предикатів.

26. Що таке рівносильність формул логіки предикатів?

27. Як впливає область інтерпретації на рівносильність формул логіки предикатів?

28. Як впливають на рівносильність вільні й зв’язані змінні у формулах логіки предикатів?

29. До якого наслідку призводить перенесення квантора на початок формули?

30. Які додаткові закони й тотожності існують у логіці предикатів порівняно з логікою висловлювань?

31. Поясніть суть заміни зв’язаної змінної.

32. Сформулюйте комутативні властивості кванторів.

33. Сформулюйте дистрибутивні властивості кванторів.

34. Яким чином можна обійти обмеження дистрибутивних властивостей кванторів?

35. Запишіть формули закону де Моргана для кванторів.

36. Яке числення називають численням предикатів першого порядку?

37. Які властивості числення предикатів першого порядку ви знаєте?

38. Довести, що будь-яке числення предикатів першого порядку є несуперечною теорією.

39. Сформулюйте умови теореми еквівалентності формул у численні предикатів першого порядку.