Материал: discrete_mathematics

Формулу Φ називають 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

Список літератури

3.Єжов І. І. Елементи комбінаторики / І. І. Єжов, А. В. Скороход, М. Й. Ядренко. – К. : Вища шк., 1972.

4.Калужнин Л. А. Введение в общую алгебру / Л. А. Калужин.

–М.: Наука,1973.

5.Калужнiн Л. А. Алгоритми i математичнi машини /Л. А. Калужнiн, В. С. Королюк. – К. :Вища шк., 1964.

6. Кривий С. Л. Дискретна математика : вибрані питання

/С. Л. Кривий. – К.: Вид. дім "Києво-Могилянська акад.",2007.

7.Кривий С. Л. Збірник задач з дискретної математики : вибрані питання /С. Л.Кривий, О. М. Ходзинський. – К. : Бізнесполіг-

раф, 2008.

8.Кук Д. Компьютерная математика / Д. Кук, Д. Бейз. – М. :

Наука, 1990.

9. Нікітченко М. С. Прикладна логіка / М. С. Нікітченко, С. С. Шкільняк. – К. : ВПЦ "Київ. ун-т", 2013.

10. Нікітченко М. С. Математична логіка та теорія алгоритмів

/М. С. Нікітченко, С. С. Шкільняк. – К. : ВПЦ "Київ. ун-т", 2008.

11.Кузнецов О. П. Дискретная математика для инженера

/О. П. Кузнецов, Г. М. Адельсон-Вельский. – 2-е изд., перераб. и доп.

– М. : Энергоатомиздат, 1988.

12.ТрохимчукР. М. Дискретна математика /Р. М. Трохимчук. – К.:Вид.дім"Персонал", 2010.

13.ТрохимчукР. М. Збірник задач і вправ з дискретної математики /Р. М. Трохимчук.– К. : ВПЦ "Київ. ун-т", 2008.

14.ТрохимчукР. М. Збірник задач і вправ з теорії множин i відношень : навч. посіб. /Р. М. Трохимчук.–К. : ВПЦ"Київ. ун-т", 2012.

15.Хромой Я. В. Математична логіка /Я.В.Хромой. – К.: Вища шк.,1983.

16.Хромой Я. В. Збірник задач і вправ з математичної логіки

/Я.В.Хромой.– К. : Вища шк., 1978.

246