Эрнст Нагель - Teopeма Гёделя

Алфавит логики высказываний (называемой часто «пропозициональным исчислением») очень несложен. Он состоит из переменных и констант. Переменные, поскольку вместо них можно подставлять предложения ( sentences ) системы, называют сентенциональными (чаще — пропозициональными) переменными. В качестве переменных мы будем использовать буквы « p », « q », « r », …, « p 1», « p 2» …, « q 1», « q 2» ….

Постоянные символы (константы) — это «пропозициональные» связки и знаки препинания. Мы будем употреблять следующие пропозициональные связки: «~» читается как «не»; ˅ — «или»; «ﬤ» — «если…, то…»; «·» — «и»; знаки препинания: «(» — «левая скобка», «)» — «правая скобка».

Действительно, перечисленные связки возникли как сокращенные обозначения для указанных в скобках выражений; более того, при устном чтении формул исчисления высказываний этими выражениями часто называют соответствующие формальные символы (скажем, формула «~ p ˅ q » читается как «не p или q » и т. п.). Следует, однако, твердо помнить, что эти «названия» связок не нужны для описания исчисления (неинтерпретированного!) как такового; они относятся к его метатеории, и, скажем, электронно-вычислительная машина, производящая операции с формулами исчисления высказываний как с таковыми, в такого рода «названиях» не нуждается. — Прим. перев.

Правила образования указывают, какие именно комбинации элементарных символов алфавита мы будем считать формулами нашего исчисления. Прежде всего формулой, по определению, является каждая пропозициональная переменная. Далее, если «S» обозначает некоторую формулу [2] Именно обозначает , но не является формулой (является именем формулы); S, не принадлежащая алфавиту описываемого исчисления, относится к его метаязыку. — Прим. перев. , то ее «формальное отрицание» «~ ( S )» также есть формула. Аналогично, если « S 1» и « S 2»суть обозначения некоторых формул, то выражения «( S 1) ˅ ( S 2)», «( S 1) ﬤ ( S 2)» и «( S 1)·( S 2)» также суть формулы.

Примеры формул:

« 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 ). Согласно этому правилу из любых двух формул, имеющих соответственно вид « S 1» и « S 1 ﬤ S 2», можно вывести и формулу « S 2». Например, из формул « p ˅ ~ p » и «( p ˅ ~ p ) ﬤ (p ﬤ p ) мы можем вывести « p ﬤ p ».

Наконец, аксиомами нашего исчисления (по существу теми же, что в Principia Mathematica [4] В Principia была еще аксиома «( p ˅ ( q ˅ r )) ˅ ( q ˅ ( p ˅ r ))» выводимая, однако, как установил П. Бернайс (1926), из остальных четырех аксиом. — Прим. перев. являются следующие четыре формулы [5] Начиная отсюда, мы будем, как обычно, опускать кавычки при записях формул, напечатанных в отдельную строку. Нам, ведь, нужны не сами по себе кавычки, а уверенность в том, что не возникнет недоразумений (ср. с названием книги Рассела и Уайтхеда, всюду в настоящей книжке выделяемым не кавычками, а курсивом ) . — Прим. перев. ;

1. ( p ˅ p ) ﬤ p