Читать «Teopeмa Гёделя» онлайн - страница 24

А вот такая же таблица для второй аксиомы:

p q p˅q рﬤ(р˅q)

K ₁ K ₁ K ₁ K ₁

K ₁ K ₂ K ₁ K ₁

K ₂ K ₁ K ₁ K ₁

K ₂ K ₂ K ₂ K ₁

В первых двух столбцах таблицы указаны все возможные распределения двух элементарных компонент аксиомы по двум классам, в третьем — соответствующие значения ее неэлементарной компоненты (согласно условию (1)), в четвертом — значения самой аксиомы. И здесь из рассмотрения последнего столбца таблицы сразу видно, что аксиома является тавтологией. Точно так же устанавливается тавтологичность остальных двух аксиом.

Докажем теперь, что свойство «быть тавтологией» наследственно относительно применений правила modus ponens. (Доказательство его наследственности относительно правила подстановки предоставляется читателю.) Пусть формулы S₁ и S₁ ﬤ S₂ — тавтологии; нам надо доказать, что тогда и формула S₂ есть тавтология. Допустим, что S₂ не является тавтологией. В таком случае для хотя бы одного распределения элементарных компонент этой формулы по классам K₁ и K₂ она принадлежит классу K₂. Но, по предположению, S₁ является тавтологией, т. е. принадлежит классу Ki при любых распределениях своих элементарных компонент, в том числе и при том, при котором S₂ принадлежит K₂. Но тогда при этом распределении формула S₁ ﬤ S₂ должна (в силу второго условия) принадлежать классу K₂, что, однако, противоречит предположению о тавтологичности S₁ ﬤ S₂. Противоречие показывает, что S₂ должна быть тавтологией. Таким образом, тавтологичность формулы есть свойство наследственное, т. е. передаваемое от посылок правила modus ponens к его заключению.

Теперь нам остается указать пример формулы нашего исчисления, не являющейся тавтологией. Такова, например, формула «p ˅ q», принадлежащая классу K₂, если обе ее компоненты («p» и «q») принадлежат этому классу. (В переводе на содержательный язык: высказывание «„p“ или q“» ложно, если ложны оба входящие в его состав высказывания «p» и «q».)

Наша цель достигнута. Мы нашли формулу, не являющуюся теоремой нашей системы. Но в случае противоречивости выбранной нами системы аксиом такой формулы в нашем исчислении не нашлось бы. Таким образом, из аксиом исчисления высказываний нельзя вывести никакой формулы одновременно с ее отрицанием. Этим и завершается абсолютное доказательство непротиворечивости исчисления высказываний.