![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Построим исчисление высказываний ИВ1 без правила подстановки, более удобное для исследования. Формальные символы и формулы ИВ1 совпадают с аналогичными понятиями в ИВ. Пусть А,В,С - произвольные формулы в ИВ. Введем следующие схемы аксиом.
Al) A ® (В ® А).
А2) (А ® (В ® С)) ® ((А ® В) ® (А ® С)).
A3) А & В ® А.
А4) А & В ® В.
А5) (А ® В) ® ((А ® С) ® (А ® В & С)).
А6) А ® А V В.
А7) В ® А V В.
А8) (А ® С) ® ((В ® С) ® (А V В ® С)).
А9) (А ® В) ® (ù В ® ù А).
А10) А ® ù ù А.
А11) ù ù А ® А.
Единственным правилом вывода является правило заключения.
Теорема. Классы формул, доказуемых в ИВ и в ИВ1, совпадают.
Доказательство. Покажем, что класс формул, доказуемых в ИВ1, содержится в классе формул, доказуемых в ИВ. В самом деле, пусть ├ 1 А (т.е. формула А доказуема в ИВ1) и A1,A2,...,Ak (=A) есть доказательство формулы А в ИВ1. Так как все Аi тождественно истинны, то ├ Аi. Каждое вхождение формулы Аi в доказательстве формулы А в ИВ1 заменим на доказательство формулы Аi в ИВ. Полученная последовательность формул будет доказательством формулы А в ИВ.
Покажем теперь индукцией по длине k доказательства формулы в ИВ, что класс формул, доказуемых в ИВ, содержится в классе формул, доказуемых в ИВ1.
БАЗИС. k = 1. Всякая аксиома в ИВ (только аксиомы имеют длину доказательства 1) доказуема в ИВ1, ибо всякая аксиома в ИВ является аксиомой и в ИВ1.
ПРЕДПОЛОЖЕНИЕ ИНДУКЦИИ. Пусть все доказуемые в ИВ формулы с длиной доказательства меньше k доказуемы в ИВ1.
ШАГ ИНДУКЦИИ. Покажем, что все доказуемые в ИВ формулы с длиной доказательства k доказуемы в ИВ1. Пусть ├ А и А1, А2,..., Аk (=А) есть доказательство длины k формулы А в ИВ. Возможны следующие случаи.
1. Аk есть аксиома в ИВ. Тогда Аk - аксиома в ИВ1 и потому ├ 1 Аk.
2. Аk получена подстановкой формулы С в формулу Аi(р) в доказательстве A1,А2,...,Аi(р),...,Аk, т.е. Аk = Аi(С). Так как длина доказательства формулы Аi(р) в ИВ меньше k, то по предположению индукции формула ├ 1 Аi(р). В доказа-тельстве B1, В2,...,Вm(р) (=Аi(р)) формулы Аi(р) в ИВ1 заменим все вхождения р на формулу С. Полученная последовательность будет доказательством формулы А в ИВ1.
3. Формула Аk получена из формул Аi и Аi ® Аk в доказательстве A1,...,Аi,...,Аi ® Аk,..., Аk с помощью правила заключения. Так как длины доказательств A1,...,Ai и A1,..., Аi,...,Аi ® Аk формул Аi и Аi ® Аkв ИВ меньше k, то по предположению индукции ├ 1 Аi и ├ 1 Аi ® Аk; откуда по правилу заключения ├ 1 Аk.
Теорема доказана.
Дата публикования: 2015-01-23; Прочитано: 265 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!