+102. [р É [q É p].

и бесконечное число переменных:

p, q, r, s, p₁, q₁, r₁, s₁, p₂, q₂, r₂, s₂ …

(указанный здесь порядок называется алфавитным порядком переменных). Переменные и исходная константа называются собственными символами.

В дальнейшем мы будем употреблять следующие сокращения: «пп» вместо «правильно построенная», «ппф» и «пп-формула» вместо «правильно построенная формула».

Правилами построения исчисления P₁ являются:

10 i. Стоящая отдельно исходная константа есть ппф.

10 ii. Отдельно стоящая переменная есть ппф.

10 iii. Если G и D суть ппф, то [G É D] есть ппф.

Для того чтобы завершить определение пп-формул и исчисления Р₁, мы добавляем, что формула является пп-формулой тогда и только тогда, когда это следует из приведенных трех правил построения. Другими словами, класс пп-формул исчисления Р₁ — это наименьший класс формул, содержащий все формулы, описанные в 10i и 10ii, и замкнутый относительно правила 10iii.

Из правил построения вытекает эффективный метод проверки правильности построения, хотя в явном виде этот метод в них и не сформулирован. Если длина некоторой формулы не слишком велика, то часто правильность ее построения может быть обнаружена с первого взгляда. В противном случае мы можем применить некоторый метод подсчета. Если формула состоит из более чем одного символа, то она может быть пп-формулой только в том случае, когда она оканчивается на ] и начинается с [. Поэтому мы можем вести подсчет скобок слева направо и, считая каждую левую скобку [ за + 1 и каждую правую скобку ] за—1, складывать эти числа. Если этот подсчет впервые дает сумму, равную 1, на правой скобке или же на левой скобке, за которой непосредственно следует собственный символ, то в случае, когда формула есть ппф, следующим символом должен быть знак импликации É. Этот знак называется главным знаком импликации данной формулы. Часть формулы, заключенная между начальной левой скобкой и главным знаком импликации, называется антецедентом, а часть формулы, заключенная между главным знаком импликации и конечной правой скобкой, называется консеквентом. Поэтому данная формула является правильно построенной тогда и только тогда, когда как антецедент, так и консеквент суть пп-формулы. Таким образом, вопрос о правильности построения данной формулы сведен к тому же вопросу относительно двух более коротких формул — антецедента и консеквента. Теперь к антецеденту и консеквенту следует применить ту же процедуру, которая была применена к данной нам формуле. После конечного числа повторений либо мы придем к выводу, что данная формула не есть ппф, так как нарушено одно из требуемых условий (или так как, проведя просчет какой-либо формулы, мы дошли до ее конца, не найдя в ней главного знака импликации), либо же вопрос о правильности построения данной формулы сведется к аналогичному вопросу относительно конечного числа формул, состоящих из не более чем одного символа каждая. Формула, число символов в которой равно нулю — так называемая пустая формула, — не является, конечно, ппф. Формула же, состоящая из точно одного символа, будет ппф тогда и только тогда, когда этот символ является собственным символом.

В дальнейшем мы будем говорить о главном знаке импликации, об антецеденте и консеквенте только по отношению к пп-формулам, так как нам в действительности редко придется иметь дело с формулами, которые не будут правильно построенными. Если формула является правильно построенной и состоит из более чем одного символа, то ее единственным образом можно представить в виде [А É В]. При этом А является антецедентом, В — консеквентом, а знак É между А и В — главным знаком импликации.

Под конверсией ппф [А É В] мы будем понимать ппф [В É А].

В P₁ все вхождения всякой переменной во всякую пп-формулу суть свободные вхождения; ппф является п-арной формой, если она содержит (свободные) вхождения точно п различных переменных, и константой, если она не содержит (свободных) вхождений ни одной переменной; все формы являются пропозициональными формами, а все константы — пропозициональными константами, или предложениями (ср. примечание 117).

Для того чтобы сформулировать правила вывода исчисления P₁, мы введем знак „ S | " для обозначения операции подстановки, так что S ^b/_BA | есть формула, являющаяся результатом подстановки формулы В вместо каждого вхождения переменной b в А. Этот знак мы будем часто использовать как в этой, так и в последующих главах. Он, конечно, является знаком не системы P₁ (и не какой-либо другой системы, рассматриваемой в этой книге), а относится к языку синтаксиса, так же точно, как и аппарат синтаксических переменных: используя русские фразы, содержащие слова „подставлять", „подстановка" и т. д., можно во всех случаях избежать его применения, хотя это и связано с некоторыми неудобствами.

Правилами вывода являются следующие два:

*100. Из [ A É В ] и А следует В (правило модус поненс)

*101. Если b — переменная, то из А следует S ^b/_BA | (правило подстановки)

В правиле модус поненс (*100) посылка [ A É В ] называется большой посылкой, а А — малой посылкой. Заметим, что антецедент большой посылки должен совпадать с малой посылкой; заключением тогда является консеквент большой посылки.

Аксиомами системы P₁ являются три следующие:

+102. [р É [q É p].

⇐ Предыдущая 123 4 5 6 7 8 Следующая ⇒