Теория алгоритмов. Зюзысов В.М. - 32 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

3. В последней интерпретации символ R понимается снова по-другому.
• R интерпретируется как символ «≥».
Указанная интерпретация теореме xPyRz ставит в соответствие истинное
утверждение о целых положительных числах «x+y≥z», и поэтому данная интерпретация
является моделью системы PR1. Но мы сейчас имеем существенное отличие от
предыдущей интерпретации: не все
истинные утверждения вида x+y≥z являются
теоремами в PR1. Так, например, формула ––P–R– имеет истинную интерпретацию 2+1 ≥
1, но это не теорема.
3.3 Исчисление высказываний
Классическое определение исчисления высказываний
Исчислением высказываний называется формальная теория с языком логики
высказываний, со схемами аксиом
A1) A⊃(B⊃A);
A2) (A⊃(B⊃C)) ⊃ ((A⊃B) ⊃ (A⊃C));
A3) (¬B⊃¬A) ⊃ ((¬B⊃A) ⊃B)
и правилом вывода MP (Modus Ponens – обычно переводится как правило отделения):
MP
B
BAA ⊃,
Здесь A, B и C – любые формулы. Таким образом, множество аксиом исчисления
высказываний бесконечно, хотя задано тремя схемами аксиом. Множество правил вывода
также бесконечно, хотя оно задано только одной схемой.
Пример. Для любой формулы A построим вывод формулы A⊃A, т. е.
A⊃A – теорема.
Подставляем в схему аксиом A2 вместо B формулу
A⊃A и вместо C формулу A, получаем
аксиому
(A⊃((A⊃A)⊃A))⊃((A⊃(A⊃A))⊃(A⊃A)). (1)
Подставляем в A1 вместо формулы B формулу A⊃A, получаем аксиому
A⊃((A⊃A)⊃A). (2)
Из формул (1) и (2) по правилу MP получаем
(A⊃(A⊃A))⊃(A
⊃A). (3)
Подставляем в A1 вместо формулы B формулу A, получаем аксиому
A⊃(A⊃A). (4)
Из формул (3) и (4) по правилу MP получаем A⊃A.
Теорема 10. Если Γ|–A⊃B и Γ|–A, то Γ|–B.
Доказательство. Пусть A
1
, A
2
,..., A
n
– вывод формулы A из Γ, где A
n
совпадает с A.
Пусть B
1
, B
2
,..., B
m
– вывод формулы A⊃B из Γ, где B
n
совпадает с A⊃B. Тогда A
1
, A
2
,..., A
n
,
B
1
, B
2
,..., B
m
, B – вывод формулы B из Γ. Последняя формула в этом выводе получена
применением правила MP к формулам A
n
и B
m
.
В исчислении высказываний импликация очень тесно связана с выводимостью.
Теорема 11 (о дедукции). Если Γ, A|–B, то Γ|–A⊃B и наоборот.
Следствие.
1. A⊃B, B⊃C |–A⊃C.
2. A⊃(B⊃C), B |–A⊃C.
Полнота, разрешимость и непротиворечивость исчисления
высказываний
В исчислении высказываний у нас есть два понятия, касающиеся формул: теорема
и тавтология. Аксиомы и правило вывода придуманы так, что эти два понятия совпадают.

Страницы