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

UptoLike

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

Рубрика:

§6. Полнота и непротиворечивость

1. Непротиворечивость и корректность

Мы рассмотрели один пример формальной теории — исчисление

высказываний. Наша цель теперь — показать, что доказуемость (` A) и

общезначимость (|= A) равносильны. Тогда мы будем уверены, что два

метода — вывод и таблицы истинности — в исчислении высказываний

всегда приводят к одним и тем же результатам.

Пусть S — некоторое свойство формул. Говорят, что формаль-

ная теория корректна (или непротиворечива) относительно свойства

S, если все теоремы теории обладают свойством S; формальная теория

полна относительно свойства S, если все формулы теории, обладающие

свойством S, суть теоремы. Обычно корректность и полнота рассмат-

риваются относительно свойства общезначимости (тождественной ис-

тинности). В этом случае свойство корректности формулируется так:

если ` A, то |= A, а свойство полноты — если |= A, то ` A.

Теорема 1. (Теорема о корректности). Всякая доказуемая фор-

мула исчисления высказываний общезначима.

/ Все аксиомы исчисления высказываний — общезначимые фор-

мулы. Это доказывается путем построения таблиц истинности или

какими-либо другими способами, рассмотренными ранее. Например,

покажем тождественную истинность аксиомы 1: A ⇒ (B ⇒ A).

A B B ⇒ A A ⇒ (B ⇒ A)

0 0 1 1

0 1 0 1

1 0 1 1

1 1 1 1

Вместо построения таблицы истинности можно было произвести

эквивалентные преобразования:

A ⇒ (B ⇒ A) ∼ ¬A ∨ (¬B ∨ A) ∼ 1 .

Общезначимость всех остальных аксиом доказывается аналогично. Та-

ким образом, для любой аксиомы A имеет место |= A.

По теореме 2 из § 1, если |= A и |= A ⇒ C, то |= C. Отсюда сле-

дует, что если из общезначимых формул A и B по правилу отделения