Математическая логика и теория алгоритмов. Галуев Г.А. - 28 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 28 из 64
© 2003 Галуев Геннадий Анатольевич
↔∃∀↔ )))(()(( zzQVxPx
по (5.1.)
)()( zVQxzPx∃∀↔ по (5.1)
Последняя формула и есть предваренная нормальная форма исходной формулы.
Основным применением исчисления предикатов также как и исчисления выска-
зываний является доказательство теорем. Рассмотрим этот вопрос.
Лекция №6.
Доказательство теорем в исчислении предикатов.
Скулемовские стандартные формы.
Литеры, дизъюнкты. Эрбрановский универсум и базис.
Семантическое дерево.
В исчислении высказываний мы показали, что теоремы являются тавтологиски-
ми, т.е.
общезначимыми формами и каждая тавтология исчисления высказываний является
теоремой. Для исчисления предикатов мы также показали, что для исчисления пре-
дикатов первого порядка (а именно его мы и рассматриваем) множество его теорем
совпадает с множеством логически общезначимых формул
. Теорема о дедукции (см
стр.11) исчисления высказываний сводит задачу о выводимости некоторой формулы
A
из множества формул
{}
n
AA ...,
1
=Γ к доказательству справедливости выражения:
├
)...)((...(
21
AAAA
n
→→→→ )(∗
Теоремы о непротиворечивости (cм. стр.13) и о полноте (стр.14) исчисления
высказываний говорят о том, что формула
A
есть теорема тогда и только тогда, когда
эта формула является тавтологией. С помощью закона из (2.10), а именно
BABA ∨¬↔→ нетрудно показать, что
))...)(...((
21
AAAA
n
→→→
эквивалентно
VAAVVAVA
n
⎤⎤⎤ ...
21
поэтому вместо теоремы (*) можно доказать теорему
├
VAAVVAVA
n
⎤⎤⎤ ...
21
(**)
Из определения операции
¬ следует, что если (**) теорема, то
VAAVVAVA
n
⎤⎤⎤ ...
21
есть тавтология , тождественно истинное или эквивалентное ему выражение
AAAA
n
⎤&&...&&
2
есть противоречие. Этот факт и положен в основу доказательства теорем в исчисле-
нии высказываний.
Этот же результат справедлив и для исчисления предикатов первого порядка.
Однако, в отличие от исчисления высказываний, здесь (в исчислении предикатов)
количество возможных интерпретаций бесконечно и доказать общезначимость (т.е.
формула эта тавтология) или противоречивость (т.е
. формула это противоречие)
формулы путем перебора всех интерпретаций невозможно.
Эрбраном в 1930 г. показано, что существуют интерпретации (Н-
интерпретации) такие, что если формула истинна (ложна) в этих интерпретациях, то
она логически общезначима (противоречива). Формула при этом представляется в так
называемой скулемовской стандартной форме.

Страницы