Материал: discrete_mathematics

Теоремою теорії першого порядку T називають формулу, яка виводиться із аксіом за допомогою скінченної кількостi застосувань правил виведення. Множину теорем теорії T позначатиме-

мо Th(T).

Те, що формула A − теорема, позначатимемо T A A, або A A,

якщо T мається на увазі.

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

Сигнатурою теорії першого порядку називають сигнатуру мови цієї теорії. Формулу мови теорії називатимемо також формулою теорії.

Розглянемо кілька прикладів теорій першого порядку.

Приклад 6.9.

1.Теорію першого порядку, що не містить власних аксіом,

називають численням предикатів першого порядку (скорочено ЧП-1).

2.Особливе місце серед формальних теорій займає теорія на-

туральних чисел − формальна арифметика. Таку теорію позна-

Ar7) Ax [0] & x(A→Ax [x+1])→ xA − аксiоми iндукцiї.

Кожна власна аксіома формальної арифметики є IАФ. ◄

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

кожна теорема ЧП 1 є всюди істинною формулою.

Моделлю теорії першого порядку T називають інтерпретацію

мови теорії, на якій істинні всі власні аксіоми теорії T.

Приклад 6.10.

1.Моделлю ЧП-1 є кожна інтерпретація його мови.

2.Моделлю формальної арифметики Ar є N − стандартна

iнтерпретацiя Lar. Таку модель називають стандартною модел лю формальної арифметики.

241

Формулу Φ називають iстинною в теорії T, якщо Φ істинна на кожній моделi теорії T.

Справедливі такі твердження:

Кожна теорема теорії першого порядку T iстинна в T

(тeорeма iстинностi).

Кожна тавтологiя єтеоремою (теорема тавтології).

У наведених нижче прикладах використаємо теорему тавто-

логії (ТТ).

Приклад 6.11. 1. |− xA → А.

(Ах2) A ¬ A → x ¬ A, звідки за ТТ A ¬ x ¬ A → A, тобто

AxA → А.

2.(правило -ввeдeння). Якщо A A → B та x не вільне в A, то

A A → xB.

Якщо AA→ B, то A ¬ B → ¬ A за TT, звiдки A x ¬ B→ ¬ A за П5. Тодi A ¬ ¬ A→ ¬ x ¬ B за ТТ, отже, A A → xB.

3. (правилa -дистрибутивності та -дистрибутивності). Якщо A A → B, то маємо A xA → xB та A xA → xB.

Маємо A A→B (умова) та A B → xB (аксіома Ах2), звiдки за TT A A → xB, тому за П5 дістаємо A xA → xB.

Із умови маємо A ¬ B → ¬ A за TT, отже A ¬ A→ x ¬ A (Ах2), звiдки за ТТ A ¬ B → x ¬ A.

За П5 A x ¬ B → x ¬ A, тому за TT A ¬ x ¬ A → ¬ x ¬ B, тобто A xA → xB.

Наведені приклади дають змогу ввести похідні правила виведення:

−правило вв: A → B A A→ xB, якщо x не вiльне в A;

−правило -дис: A→B A хA → xB;

−правило дис: A→B A xA → xB.

4. (правило уособлення). Якщо A xA, то A A.

За п. 1 A xA → A. Звідси та з умови A xА за МР A A.

5. (правило узагальнення). Якщо A A, то A xA.

242

Якщо A A, то за П1 A xA A, звідки за TT A ← A → хA. Тоді A x ← A → xA за П5, тобто A xA xA.

Тепер A xA за П2.

6. A х уA ↔ у xА.

Із аксіоми Ах2 A A → хA за -дис маємо A уA → у xА, далі за П5 A х уA → у xА.

Аналогічно A у xА → х уA, тому за ТТ A х уA ↔ у xА. 7. A х уA → у xА. Маємо A A → хA (Ах2), звідки

AуA → у xА за -дис. За П5 маємо A х уA → у xА.

8.A х(A В) → xА хВ. Маємо

A A → хA (Ах2) та A В → хВ (Ах2),

звідки за ТТ маємо A A В → xА хВ. Тепер за П5 A х(A В) → xА хВ.

9.A xА хВ→ х(A В). ЗаТТмаємоAА→ A ВтаAВ→ A В, звідки A xА → х(A В) та A xВ → х(A В) за -дис.

Тепер A xА хВ → х(A В) за ТТ.

10.A х(A → B) → (A → хB) за умови х не вільне в А.

Маємо A х(A → B) → (A→B) (п. 1), звідки за ТТ дістаємо

A х(A → B) & A → B.

За правилом -введення A х(A → B) & A → хB, звідки за

TTA х(A → B) → (A → хB).

11.(правило симетрії). Для довільних термів a та b

A a = b ↔ b = a.

Маємо A x = y → x = x → x = x → y = x,

аксіома рівностi для ПС =

звідки A x = x → x = x → y = x → y = x за ТТ. Однак A x = x (Ах3), тому послідовно за MP

A x = x → y = x → y = x та A x = y → y = x.

Аналогiчно A y = x → x = y, тому A x = y ↔ y = x за ТТ. Звідси за ПП A a = b ↔ b = a.

243

12 (правило транзитивності). Для довільних термів a, b та c

A a = b → b = c → a = c. Маємо A y = x → y = z → y = y → x = z,

аксіома рівності для предикатного символу =

звідки A y = y → y = x → y = z → x = z за ТТ.

Однак A y = y (Ах3), тому за MP A y = x → y = z → x = z. Згідно із правилом симетрії A x = y → y = x, тому

A x = y → y = z → x = z за ТТ. За ПП A a = b → b = c → a = c. ◄

Нехай T − довiльна теорія першого порядку із множиною власних аксiом Ax, Γ − деяка множина формул. Розширення теорії T із множиною власних аксiом Ax Γ позначають T[Γ]. Теорію, отриману із T додаванням A як нової аксіоми, позначимо T[A].

Тeорeма дeдукції. Нехай A − замкнена формула. Тоді для довiльної формули B маємо:

T A A → B T[A] A B.

Теорію першого порядку T називають нeсупeрeчливою, якщо нe існує формули Φ такої, що T A Φ та T A ¬Φ.

Нeсупeрeчливу теорію першого порядку T називають макси мальною (інколи кажуть повною), якщо для кожної замкненої

формули Φ маємо або T A Φ, або T A ¬Φ.

Приклад 6.12. Позначимо S замкнену формулу

x y(x = y),

істинну тільки на 1-eлeмeнтних iнтeрпрeтаціях. Тодi ¬ S істинна на всіх n-eлeмeнтних інтeрпрeтаціях, дe п > 1. Якщо A S, то B S,

що нeможливо; якщо ж A ¬ S, то B ¬ S, що також нeможливо.

Із наведеного прикладу маємо, що числення предикатів першого порядку не є максимальним (є неповним).

Завдання для самостійної роботи

1. Побудувати виведення в численні предикатів: 1) A¬ xB ↔ x ¬ B та A ¬ xB ↔ x ¬ B;

244

2) A хA ↔ x ← ← A; 3) A х уA ↔ у xА;

4) A хA xВ → x(А В); 5) A хA& xВ ↔ x(А & В); 6) A х(A & В) → xА & хВ;

7)A х(A & B) → хA & B;

8)A xА B ↔ x(А В), якщо x нe вільна у В;

9)A xА В ↔ x(А В), якщо x нe вільна у В;

10)A xA & B ↔ x(A & B) за умови х не вільне у В;

11)A хA & B ↔ x(А & В) за умови х не вільне у В;

12)A (A → хB) → ( хA → B);

13)A x(А → В) → ( хА → xВ);

14)A x(А → В) → ( хА → xВ);

15)A ( хА →xВ) → x(A → B);

16)A ( хА → xВ) → x(A → B).

2.Чи є істотною умова замкненості формули А в теоремі дедукції?

3.Доведіть, що теорія першого порядку T супeрeчлива тоді й

тільки тоді, коли T A А для кожної формули А мови теорії T. 4. Нехай А - замкнена формула. Доведіть таке твердження:

–якщо неправильно T AА, то T [A] несуперечлива;

–T A А тоді й тільки тоді, коли T [←A] суперечлива.

245