![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Тема: ТЕОРЕМЫ В ТЕОРИЯХ ПЕРВОГО ПОРЯДКА
Основные вопросы, рассматриваемые на лекции:
1. Теорема о тавтологии
2. Теорема о тавтологическом следствии
3. Теорема редукции
4. Теорема подстановки для квантора $
5. Производныое правила: введения $, обобщения, подстановки
Краткое содержание лекционного материала
Пусть P – тавтология с пропозициональными переменными p 1,…, pn, а A – формула, полученная из P заменой каждого вхождения переменой pi формулой Bi для всех i =1,…, n (B 1,…, Bn – формулы теории первого порядка). Формула A называется частным случаем тавтологии P.
Поскольку теории первого порядка содержат аксиомы A 1- A 3 и правило MP, то из исчисления высказываний можно перенести следующую теорему.
Теорема о тавтологии. Пусть формула A теории T является частным случаем некоторой тавтологии. Тогда A – теорема T.
Если формула A 1Þ…Þ An Þ B теории T – частный случай тавтологии, то формула B называется тавтологическим следствием формул A 1- An.
Из теоремы о тавтологии следует
Теорема о тавтологическом следствии. Пусть формула B является тавтологическим следствием теорем A 1- An. Тогда B – тоже теорема T.
Формула A *=" x 1…" xnA, где x 1,…, xn – все свободные переменные формулы A, называется замыканием формулы A.
Теорема редукции. Формула A теории T является теоремой теории T тогда и только тогда, когда теория T [Ø A *] будет противоречивой.
Аксиома (A 4) называется аксиомой подстановки для квантора ". Докажем теорему подстановки для квантора $:
(T 1) |¾ Ax [ t ]Þ$ xA.
Доказательство построим в виде вывода:
1. " x Ø A ÞØ Ax [ t ] (A 4)
2. Ax [ t ]ÞØ" x Ø A тавтологическое следствие
3. Ax [ 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 1) A |¾" xA.
Доказательство построим в виде вывода:
1. A гипотеза
2. Ø" xA Þ A тавтологическое следствие
3. Ø" xA Þ" xA правило (")
4. " xA тавтологическое следствие
Следующее правило называется правилом подстановки:
(P 2) A |¾ Ax [ t ].
Доказательство построим в виде вывода:
1. A гипотеза
2. " xA (P 1)
3. " xA Þ Ax [ t ] (A 4)
4. Ax [ t ] (MP)
Формула A *=" x 1…" xnA называется замыканием формулы A, если x 1,…, xn – все переменные, свободные в A. Из определения истинностного значения формулы – обобщения следует, что формула A и ее замыкание A * логически эквивалентны: A º A *.
Теорема о замыкании. |¾ A *Û|¾ A.
Доказательство. 1) Пусть |¾ A. Тогда n раз применим правило обобщения (P 1), и получим, что |¾ A *.
2) Пусть |¾ A *. Тогда запишем n аксиом подстановки (A 4):
" x 1" x 2" x 3…" xn -1" xnA Þ" x 2" x 3…" xn -1" xnA;
" x 2" x 3…" xn -1" xnA Þ" x 3…" xn -1" xnA;
……………………………………..
" xn -1" xnA Þ" xnA;
" xnA Þ A.
Применим n раз правило (MP), и получим, что |¾ A.
Формула без свободных вхождений переменных называется замкнутой. В частности, замыкание формулы является замкнутой формулой.
(T 2) |¾" x (A Þ B)Þ(A Þ" xB),
где переменная x не свободна в A.
Доказательство построим в виде вывода:
1. " x (A Þ B)Þ(A Þ B) (A 4)
2. (" x (A Þ B)Ù A)Þ B)) тавтологическое следствие
3. (" x (A Þ B)Ù A)Þ" xB)) (")
4. " x (A Þ B)Þ(A Þ" xB) тавтологическое следствие
Дата публикования: 2015-03-26; Прочитано: 312 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!