Лекция №16

Тема: ТЕОРЕМЫ В ТЕОРИЯХ ПЕРВОГО ПОРЯДКА

Основные вопросы, рассматриваемые на лекции:

1. Теорема о тавтологии

2. Теорема о тавтологическом следствии

3. Теорема редукции

4. Теорема подстановки для квантора $

5. Производныое правила: введения $, обобщения, подстановки

Краткое содержание лекционного материала

Пусть P – тавтология с пропозициональными переменными p ₁,…, p_n, а A – формула, полученная из P заменой каждого вхождения переменой p_i формулой B_i для всех i =1,…, n (B ₁,…, B_n – формулы теории первого порядка). Формула A называется частным случаем тавтологии P.

Поскольку теории первого порядка содержат аксиомы A ₁- A ₃ и правило MP, то из исчисления высказываний можно перенести следующую теорему.

Теорема о тавтологии. Пусть формула A теории T является частным случаем некоторой тавтологии. Тогда A – теорема T.

Если формула A ₁Þ…Þ A_n Þ B теории T – частный случай тавтологии, то формула B называется тавтологическим следствием формул A ₁- A_n.

Из теоремы о тавтологии следует

Теорема о тавтологическом следствии. Пусть формула B является тавтологическим следствием теорем A ₁- A_n. Тогда B – тоже теорема T.

Формула A *=" x ₁…" x_nA, где x ₁,…, x_n – все свободные переменные формулы A, называется замыканием формулы A.

Теорема редукции. Формула A теории T является теоремой теории T тогда и только тогда, когда теория T [Ø A *] будет противоречивой.

Аксиома (A ₄) называется аксиомой подстановки для квантора ". Докажем теорему подстановки для квантора $:

(T ₁) |¾ A_x [ t ]Þ$ xA.

Доказательство построим в виде вывода:

1. " x Ø A ÞØ A_x [ t ] (A ₄)

2. A_x [ t ]ÞØ" x Ø A тавтологическое следствие

3. A_x [ t ]Þ$ xA определение квантора $

Правило (") называется правилом введения квантора ". Докажем правило введения квантора $:

($) A Þ B |¾$ xA Þ B,

где переменная x не свободна в B. Доказательство построим в виде вывода:

1. A Þ B гипотеза

2. Ø B ÞØ A тавтологическое следствие

3. Ø B Þ" x Ø A правило (")

4. Ø" x Ø A Þ B тавтологическое следствие

5. $ xA Þ B определение квантора $

Следующее правило называется правилом обобщения:

(P ₁) A |¾" xA.

Доказательство построим в виде вывода:

1. A гипотеза

2. Ø" xA Þ A тавтологическое следствие

3. Ø" xA Þ" xA правило (")

4. " xA тавтологическое следствие

Следующее правило называется правилом подстановки:

(P ₂) A |¾ A_x [ t ].

Доказательство построим в виде вывода:

1. A гипотеза

2. " xA (P ₁)

3. " xA Þ A_x [ t ] (A ₄)

4. A_x [ t ] (MP)

Формула A ^*=" x ₁…" x_nA называется замыканием формулы A, если x ₁,…, x_n – все переменные, свободные в A. Из определения истинностного значения формулы – обобщения следует, что формула A и ее замыкание A ^* логически эквивалентны: A º A ^*.

Теорема о замыкании. |¾ A ^*Û|¾ A.

Доказательство. 1) Пусть |¾ A. Тогда n раз применим правило обобщения (P ₁), и получим, что |¾ A ^*.

2) Пусть |¾ A ^*. Тогда запишем n аксиом подстановки (A ₄):

" x ₁" x ₂" x ₃…" x_{n -1}" x_nA Þ" x ₂" x ₃…" x_{n -1}" x_nA;

" x ₂" x ₃…" x_{n -1}" x_nA Þ" x ₃…" x_{n -1}" x_nA;

……………………………………..

" x_{n -1}" x_nA Þ" x_nA;

" x_nA Þ A.

Применим n раз правило (MP), и получим, что |¾ A. 

Формула без свободных вхождений переменных называется замкнутой. В частности, замыкание формулы является замкнутой формулой.

(T ₂) |¾" x (A Þ B)Þ(A Þ" xB),

где переменная x не свободна в A.

Доказательство построим в виде вывода:

1. " x (A Þ B)Þ(A Þ B) (A ₄)

2. (" x (A Þ B)Ù A)Þ B)) тавтологическое следствие

3. (" x (A Þ B)Ù A)Þ" xB)) (")

4. " x (A Þ B)Þ(A Þ" xB) тавтологическое следствие