Тождественно истинные и доказуемые формулы

Пусть А(p₁p₂,…,p_n) - формула в ИВ и p₁p₂,…,p_n - полный список ее переменных; а = (a₁,a₂,…,a_n) - набор из 0 и 1 длины n; Р_a(А) означает значение формулы А на наборе а. Определим это понятие индукцией по построению формулы.

1. Если А есть переменная р_i, то

.

2. Если А есть формула В * С (где * есть один из знаков &, V, ®) или же формула ù В, то

Р_a (В * С) = Р_a (В) * Р_a (С); Р_a (ù В) = ù P_a (В).

Примем обозначения р¹ = р; р⁰ = ù р.

Лемма (о доказуемости формулы по значению на наборе).

Доказательство. Индукция по построению формулы.
Пусть совокупность формул Г =
БАЗИС. Формула А есть переменная р_i. Тогда Р_a (р_i) = а _i.

a) a _i = 1. Тогда = р_i = А; откуда Г ├ А.

b) а _i = 0. Тогда = ù р_i = ù А; откуда Г ├ ù A.

ПРЕДПОЛОЖЕНИЕ ИНДУКЦИИ. Предположим, что лемма справедлива для всех формул глубины построения меньше k.

ШАГ ИНДУКЦИИ. Покажем, что лемма справедлива для формул глубины построения k. Возможны следующие случаи.

а) А есть В & С. Возможны следующие подслучаи.

1. Р_а (А) = 1. Покажем, что Г ├ А. Так как Р_а (А) = Р_a (В & С) = Р_а(В) & Р_а(С) = 1, то Р_а(В) = 1, Р_а(С) = 1. Так как глубина построения формулы В и формулы С меньше k, то по предположению индукции имеем

Г ├ В, Г ├ С, откуда Г ├ В & С, ПВ2.

2. Р_a (А) = 0. Покажем, что Г ├ ù А. Так как Р_a (А) = Р_а (В&С) = Р_а (В) & Р_а (С) = 0, то Р_а (В) = 0 или Р_а (С) = 0. Пусть для определенности Р_а (В) = 0. Так как глубина построения формулы В меньше k, то по предположению индукции

(1) Г ├ ù В. Далее получаем

(2) ├ В & С ® В,

(3) ├ ù В ® ù (В & С), ПВ5(2), контрапозиция;

(4) Г ├ ù (В & С), П3(1,3), т.е. Г ├ ù A.

b) А есть В V С. Возможны следующие подслучаи.

1. Р_а (А) = 1. Покажем, что Г ├ А. Так как Р_а (А) = Р_a (В V С) = Р_а(В) V Р_а(С) = 1, то Р_а(В) = 1 или Р_а(С) = 1. Пусть для определенности имеем Р_а (В) = 1. Так как глубина построения формулы В меньше k, то по предположению индукции

(1) Г ├ В. Далее получаем

(2) ├ В ® В V С,

(3) Г ├ В V С, П3(1,2), т.е. Г ├ А.

2. Р_а (А) = 0. Покажем, что Г ├ ù А. Так как Р_а (А) = Р_а (В&С) = Р_а (В) V Р_а (С) = 0, то Р_а (В) = 0, Р_a (С) = 0. Так как глубина построения формулы В и формулы С меньше k, то по предположению индукции

(1) Г ├ ù В;

(2) Г ├ ù C. Далее получаем

(3) Г ├ ù В & ù C, ПВ2(1,2);

(4) ├ ù В & ù C ® ù (В V С),

(5) Г ├ ù (В V С), П3(3,4), т.е. Г ├ ù A.

c) А есть В ® С. Возможны следующие подслучаи.

1. Р_а (А) = 1. Покажем, что Г ├ А. Так как Р_а (А) = Р_а (В ® С) = Р_а (В) ® Р_a (С) = 1, то Р_a (В) = 0 или Р_а (С) = 1.

Пусть Р_a(В) = 0. Так как глубина построения формулы В меньше k, то по предположению индукции

(1) Г ├ ù В. Далее

(2) Г ├ В & ù B ®C,

(3) Г ├ В ® (ù В ® С), ПВ14(2), разъединение посылок;

(4) Г ├ ù В ® (В ® С), ПВ13(3), перестановка посылок;

(5) Г ├ В ® С, П3(1,4), т.е. Г ├ А.

Пусть Р_а (С) = 1. Так как глубина построения формулы С меньше k, то по предположению индукции

(1) Г ├ С. Далее

(2) ├ С ® (В ® С),

(3) Г ├ В ® С, П3(1,2), т.е. Г ├ А.

2. Р_а (А) = 0. Покажем, что Г ├ ù А. Так как Р_а (А) = Р_а (В ® С) = Р_а(В) ® Р_а(С) = 0, то Р_а(В) = 1, Р_а(С) = 0. Так как глубина построения формулы В и формулы С меньше k, то по предположению индукции

(1) Г ├ В;

(2) Г ├ ù C. Далее

(3) Г ├ ((В ® С) ® С) ® (ù C ® ù (В ® С)),

(4) ├ (В ® С) ® (В ® С),

(5) ├ В ® ((В ® С) ® С), ПВ13(4), перестановка посылок;

(6) Г ├ (В ® С) ® С, П3(1,5);

(7) Г ├ ù С ® ù (В ® С), ПВ5(6), контрапозиция;

(8) Г ├ ù (В ® С), П3(1,7), т.е. Г ├ ù А.

d) А есть ù В. Возможны следующие случаи.

1. Р_а(А) = 1. Покажем, что Г ├ А. Так как Р_a (А) = Р_а (ù В) = ù Р_а (В) = 1, то
Р_a(В) = 0. Так как глубина построения формулы В меньше k, то по предположению индукции Г ├ ù В, т.е. Г ├ А.

2. Р_а (А) = 0. Покажем, что Г ├ ù А. Как и выше, Р_а (В) = 1. По предположению индукции

(1) Г ├ В. Далее

(2) ├ В ® ù ù В,

(3) Г ├ ù ù В, т.е. Г ├ ù А.

Лемма доказана.

Теорема. Всякая тождественно истинная формула доказуема в ИВ.

├

Доказательство. Пусть А(p₁,p₂,…,p_n) есть тождественно истин­ная формула и p₁,p₂,…,p_n - полный список ее переменных; а = (a₁,a₂,…,a_n) - произвольный набор из 0 и 1 длины п. Так как Р _a(А) = 1 для любого набора а, в том числе и для наборов (a ₁,…, a _n-1,1) и (a ₁,…, a _n-1,0), то по доказанной выше лемме

(1)

(2) Далее

(3)

├

ТД(1);

(4)

├ ù

ТД(2);

(5)

├ V ù

ПВ17(3,4), введение V;

(6) ├ p_n V ù p_n,

(7)

├

ПЗ(5,6).

Повторяя предыдущие рассуждения, получим

После конечного числа подобных рассуждений получим ├ А.

Теорема. Всякая доказуемая в ИВ формула общезначима.

Доказательство. Индукция по длине k доказательства.

БАЗИС. k = 1. Непосредственной проверкой убеждаемся, что все аксиомы (только они имеют длину доказательства k =l) тождественно истинны.

ПРЕДПОЛОЖЕНИЕ ИНДУКЦИИ. Допустим, что все доказуемые фор­мулы с длиной доказательства меньше k тождественно истинны.

ШАГ ИНДУКЦИИ. Покажем, что все доказуемые в ИВ формулы с длиной доказательства k тождественно истинны. Пусть формула А доказуема в ИВ и ее доказательство А₁,А₂,...,А_k (=А) имеет длину k. Возможны следующие случаи.

1. А есть аксиома. Тогда А тождественно истинна.

2. Формула А_k (=А) есть (А_i(р)), т.е. получена из формулы А_i(р) в доказательстве А₁,А₂,...,А_i(р),... ,A_k с помощью подстановки. Так как длина доказательства А₁,А₂,...,А_i(р) формулы А_i(р) меньше k, то по предположению индукции формула А_i(р), а вместе с ней и формула А = А_i(С), тождественно истинна.

3. Формула А_k получена из формул А_i и А_i ® А_k в доказательстве А₁,...,А_i,.., А_i ® A_k,...,A_k (=А) с помощью правила заключения.