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

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

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

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

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

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

«p», «~ p», «(р) ﬤ (q)», «((q) ˅ (r)) ﬤ (p)».

Однако выражения «(p)(~ q)» или «((р)ﬤ(q))˅» формулами не являются, так как они не удовлетворяют приведенному здесь определению формулы.

Правил преобразования имеется два. Первое из них — правило подстановки (вместо пропозициональных переменных) — гласит, что из произвольной формулы можно вывести другую формулу посредством одновременной подстановки некоторой формулы вместо некоторой входящей в исходную формулу пропозициональной переменной, причем такая подстановка (одна и та же) должна производиться вместо каждого вхождения выбранной переменной. Например, из формулы «p ﬤ p» можно, подставив вместо переменной «p» переменную (а тем самым — формулу) «q», вывести формулу «q ﬤ q»; подставив в ту же исходную формулу вместо «p» формулу «p ˅ q», мы выведем формулу «(p ˅ q) ﬤ (p ˅ q)» и т. п. Или, если интерпретировать «p» и «q» как некоторые русские предложения, то из «p ﬤ p» можно, например, получить предложения «Лягушки квакают ﬤ лягушки квакают», «(Летучие мыши слепы ˅ летучие мыши едят мышей) ﬤ (летучие мыши слепы ˅ летучие мыши едят мышей)» и т. п. Второе правило преобразования — это так называемое правило отделения (или modus ponens). Согласно этому правилу из любых двух формул, имеющих соответственно вид «S₁» и «S₁ ﬤ S₂», можно вывести и формулу «S₂». Например, из формул «p ˅ ~ p» и «(p ˅ ~ p) ﬤ (p ﬤ p) мы можем вывести «p ﬤ p».