) системы, называют сентенциональными (чаще — пропозициональными) переменными. В качестве переменных мы будем использовать буквы «p», «q», «r», …, «p>1», «p>2» …, «q>1», «q>2» ….
Постоянные символы (константы) — это «пропозициональные» связки и знаки препинания. Мы будем употреблять следующие пропозициональные связки: «~» читается как «не»; ˅ — «или»; «ﬤ» — «если…, то…»; «·» — «и»; знаки препинания: «(» — «левая скобка», «)» — «правая скобка».
>Действительно, перечисленные связки возникли как сокращенные обозначения для указанных в скобках выражений; более того, при устном чтении формул исчисления высказываний этими выражениями часто называют соответствующие формальные символы (скажем, формула «~ p ˅ q» читается как «не p или q» и т. п.). Следует, однако, твердо помнить, что эти «названия» связок не нужны для описания исчисления (неинтерпретированного!) как такового; они относятся к его метатеории, и, скажем, электронно-вычислительная машина, производящая операции с формулами исчисления высказываний как с таковыми, в такого рода «названиях» не нуждается. — Прим. перев.
Правила образования указывают, какие именно комбинации элементарных символов алфавита мы будем считать формулами нашего исчисления. Прежде всего формулой, по определению, является каждая пропозициональная переменная. Далее, если «S» обозначает некоторую формулу[2], то ее «формальное отрицание» «~ (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)» и т. п. Или, если интерпретировать «
