Элементы математической логики. Фролов И.С. - 45 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

получается формула C, то C также общезначима. Действительно, что-
бы правило отделения было применимо, формула B должна иметь вид
A ⇒ C.
Рассмотрим формальное доказательство B
1
, B
2
, . . . , B
n
формулы
B = B
n
. В нем каждая формула B
i
— либо аксиома, либо получается по
правилу отделения из предыдущих. В обоих случаях |= B
i
; в частности,
|= B, т.е. теорема B общезначима.
Упражнение 1. Докажите тождественную истинность всех аксиом исчисле-
ния высказываний.
Следствие. (Абсолютная непротиворечивость). Не существует
формулы B такой, что доказуемы формулы B и ¬B.
Пусть для некоторой формулы B одновременно справедливы се-
квенции ` B и ` ¬B. По теореме 1 тогда |= B и |= ¬B, т.е. при любой
интерпретации I значения |B| = |¬B| = 1. Но это невозможно, так как
если B имеет значение 1, то ¬B должно иметь значение 0.
Абсолютно непротиворечивой называется формальная теория, в
которой не все формулы доказуемы, т.е. не все формулы суть теоремы.
Следствие теоремы 1 как раз утверждает это для исчисления высказы-
ваний. Можно привести конкретный пример: поскольку известно, что
A ⇒ A — теорема (теорема 1 § 5), то ¬(A ⇒ A) не есть теорема. Вообще
говоря, в абсолютно непротиворечивой теории отношение доказуемости
разбивает множество всех формул теории на два класса: теоремы и не-
теоремы. Согласно свойству корректности, все теоремы общезначимы.
Существуют ли общезначимые формулы, не являющиеся теоремами?
2. Правила введения и удаления логических
связок
Использование дополнительных свойств выводимости, а также
известных теорем облегчает процесс построения вывода, как мы уже
могли убедиться в предыдущем параграфе. Добавим еще ряд произ-
водных правил вывода — ими можно пользоваться наравне с правилом
отделения, но их предварительно нужно обосновать. Производное пра-
вило 1-го рода записывается как F
1
, F
2
` G и означает, что из формул
F
1
и F
2
выводится формула G. Производное правило 2-го рода записы-
вается как
S
1
; S
2
S
и означает, что из справедливости секвенций S
1
и S
2
вытекает справедливость секвенции S.
Теорема 2. Для любых формул A, B, C и списка формул Γ имеют
место следующие правила вывода
1
:
44

Страницы