Teopeмa Гёделя
Шрифт:
Алфавит логики высказываний (называемой часто «пропозициональным исчислением») очень несложен. Он состоит из переменных и констант. Переменные, поскольку вместо них можно подставлять предложения (sentences) системы, называют сентенциональными (чаще — пропозициональными) переменными. В качестве переменных мы будем использовать буквы «p», «q», «r», …, «p1», «p2» …, «q1», «q2» ….
Постоянные символы (константы) — это «пропозициональные» связки и знаки препинания. Мы будем употреблять следующие пропозициональные связки: «~» читается как «не»; — «или»; «» — «если…, то…»; «·» — «и»; знаки препинания: «(» — «левая скобка», «)» — «правая скобка».
Действительно, перечисленные связки возникли как сокращенные обозначения для указанных в скобках выражений; более того, при устном чтении формул исчисления высказываний этими выражениями часто называют соответствующие формальные символы (скажем, формула «~ p q» читается как «не p или q» и т. п.). Следует, однако, твердо помнить, что эти «названия» связок не нужны для описания исчисления (неинтерпретированного!) как такового; они относятся к его метатеории, и, скажем, электронно-вычислительная машина, производящая операции с формулами исчисления высказываний как с таковыми, в такого рода «названиях» не нуждается. — Прим. перев.
Правила образования указывают, какие именно комбинации элементарных символов алфавита мы будем считать формулами нашего исчисления. Прежде всего формулой, по определению, является каждая пропозициональная переменная. Далее, если «S» обозначает некоторую формулу [2] , то ее «формальное отрицание» «~ (S)» также есть формула. Аналогично, если «S1» и «S2»суть обозначения некоторых формул, то выражения «(S1) (S2)», «(S1) (S2)» и «(S1)·(S2)» также суть формулы.
2
Именно обозначает, но не является формулой (является именем формулы); S, не принадлежащая алфавиту описываемого исчисления, относится к его метаязыку. — Прим. перев.
Примеры формул:
«p», «~ p», «(р) (q)», «((q) (r)) (p)».
Однако выражения «(p)(~ q)» или «((р)(q))» формулами не являются, так как они не удовлетворяют приведенному здесь определению формулы [3] .
Правил преобразования имеется два. Первое из них — правило подстановки (вместо пропозициональных переменных) — гласит, что из произвольной формулы можно вывести другую формулу посредством одновременной подстановки некоторой формулы вместо некоторой входящей в исходную формулу пропозициональной переменной, причем такая подстановка (одна и та же) должна производиться вместо каждого вхождения выбранной переменной. Например, из формулы «p p» можно, подставив вместо переменной «p» переменную (а тем самым — формулу) «q», вывести формулу «q q»; подставив в ту же исходную формулу вместо «p» формулу «p q», мы выведем формулу «(p q) (p q)» и т. п. Или, если интерпретировать «p» и «q» как некоторые русские предложения, то из «p p» можно, например, получить предложения «Лягушки квакают лягушки квакают», «(Летучие мыши слепы летучие мыши едят мышей) (летучие мыши слепы летучие мыши едят мышей)» и т. п. Второе правило преобразования — это так называемое правило отделения (или modus ponens). Согласно этому правилу из любых двух формул, имеющих соответственно вид «S1» и «S1 S2», можно вывести и формулу «S2». Например, из формул «p ~ p» и «(p ~ p) (p p) мы можем вывести «p p».
3
В тех случаях, когда нечего опасаться недоразумений, часть скобок в записях формулы опускают.
Наконец, аксиомами нашего исчисления (по существу теми же, что в Principia Mathematica [4] являются следующие четыре формулы [5] ;
1. (p p) p
[если p или p, то p];
2. p (p q)
[если p, то p или q];
4
В Principia была еще аксиома «(p (q r)) (q (p r))» выводимая, однако, как установил П. Бернайс (1926), из остальных четырех аксиом. — Прим. перев.
5
Начиная отсюда, мы будем, как обычно, опускать кавычки при записях формул, напечатанных в отдельную строку. Нам, ведь, нужны не сами по себе кавычки, а уверенность в том, что не возникнет недоразумений (ср. с названием книги Рассела и Уайтхеда, всюду в настоящей книжке выделяемым не кавычками, а курсивом). — Прим. перев.
3. (p q) (q p)
[если p или q, то q или p];
4. (p q) ((r р) (r q))
[если p влечет q, то (r или p) влечет (r или q)].
Здесь вначале приведены аксиомы, а в квадратных скобках указаны их «переводы» на обычный язык [6] .
Каждая из приведенных аксиом представляется довольно-таки «очевидной» и тривиальной.
Если, конечно, иметь в виду некоторые «естественные переводы» (т. е. интерпретации!) аксиом, самих по себе никакого «смысла» не имеющих. Аналогичное замечание следует иметь в виду при чтении следующей фразы текста и всюду в аналогичных случаях далее. — Прим. перев.
6
«Переводы» эти, разумеется, к самому исчислению не относятся. — Прим. перев.
Тем не менее из них с помощью сформулированных выше двух правил преобразования можно вывести бесконечное множество теорем, многие из которых трудно назвать очевидными или тривиальными. К числу таких теорем относится, скажем, формула
((p q) ((r s) t)) ((u ((r s) t)) ((p u) (s t))).
В данный момент нас, однако, не интересует вывод теорем из аксиом. Цель наша состоит в том, чтобы показать непротиворечивость этой системы аксиом, т. е. дать «абсолютное» доказательство невозможностивывода из данных аксиом с помощью правил преобразования никакой формулы S одновременно с ее формальным отрицанием ~S.
Оказывается, что к числу теорем нашего исчисления относится формула «p (~ p q)» (выражаемая словесно следующим образом: «если p, то не p влечет q»). (Мы примем этот результат к сведению, не проводя фактического его доказательства.) Допустим, что некоторая формула S, так же как и ее отрицание ~ S, выводима из аксиом. Подставляя тогда S вместо переменной «p» в только что упомянутую теорему (пользуясь правилом подстановки) и применяя затем дважды modus ponens, мы получим, что теоремой является и формула «q».
Подставляя S вместо (p) в «p (~ p q)», мы получим сначала «S (~ S q)». Беря затем эту формулу и формулу S в качестве посылок modus ponens, получим «~ S ~ q». Наконец, из последней формулы и ~ S также по modus ponens получим формулу «q».