Колмогоров, Драгалин - Введение в математическую логику, страница 12

По определению Ехр«= Етп«()Тт,. б. Индуктивный характер определения множества Ещ» предполагает возможность использовать следующий способ рассуждения — индукцию по построению множества формул (языжа (1). А именно если мы желаем доказать, что некото- рое свойство Х выполняется для всех формул языка й, то достаточно установить, что: А. каждая атомарная формула языка ьз обладает' свой- ствам Х; ' Б.

если формула А и В обладают свойством Х, то фор- мулы (АЛВ), (А~/В), (А:эВ), )А также обладают свой- ством Х; В. если формула А обладает свойством Х, то свойством обладают и формулы у' хА, ~ хА. Если факты А, Б, В установлены, то можно быть уве- ренным, что свойство Х имеет место для любой формулы языка. Докажем, например, что всякая формула языка содер- жит одинаковое количество вхождений левых и правых скобок. В самом деле: А. атомарная формула Р((ь...,( ) такова, так как каж- дый терм с; содержит одинаковое число вхождений левых и правых скобок; Б. если формулы А, В содержат одинаковое количество левых и правых скобок, то, очевидно, таковы же и формулы (А/~В), (АЧВ), (А:зВ), 1А; В.

если формула А содержит одинаковое 'количество ле- вых и правых скобок, то, очевидно, таковы же формулы )УхА, ДхА. Аналогично, индуктивный характер определения Гт, да- ет возможность задавать функции, определенные на множе- стве Рщ, индукцией по определению множества Рт, (за- давать функции рекурсией (примитивной рекурсией) по по- строению множества Ггп,). А именно:, А.

пусть с каждой атомарной А формулой- языка ьз мы связали некоторый объект Р(А); Б. пусть задано правило, в соответствии с которым, ес- 58 Ячй Л)( 1 )) П'ормулу ( р х (Р (х, у) ~ ( у' хЯ (г) ЛЙ) ) ~/Я (х) ) сокращенно запишем в виде 1у х(Р(х, у) »1у хЯ(г) Л)() ~/Я(х). лп формулам А и В уже приписаны некоторые значения Р(А) н Р(В),- можно отыскать и объекты Р(АЛВ), Р(А\/В), Р(А~В), Р("1А); В. пусть задано правило, в соответствии с которым, если формуле А уже приписан объект Р(А), для любой пе,еменной х можно отыскать объекты Р((у хА) и Р(ЗхА).

В такой ситуации для всякой формулы А языка (г определен объект Р(А). 6. Свяжем, например, с каждой формулой А~Гш«натуральное число 1(А), называемое логической сложностью формулы А, следующим образом: 1) Е(А) =О, если А — атомарна; 2) 1(АЬВ) =ЦА)+1(В)+1; 1( ~ А) =ЦА) +1; 3) 1(ЯхА) =1(А) +1. Упражнение. Проверьте, что Ц'ухД г((РЦ(х, у))Л ~ х(г (х, г) ) ~ Д уЯ(х, у) ) ) =6. Упражнение. Индукцией по построению множества формул докажите, что 1(А) равно количеству вхождений логических символов в А.

7. Практически записывая формулы„удобно экономить скобки, пользуясь некоторыми традициями и приемами. Этц «экономные» записи следует. рассматривать как неформальные обозначения для формул в нашей записи.. Вся точная тсорня у нас будет относиться лишь к формулам в точном определении.

Прежде всего, мы опускаем внешние скобки. Кроме того, ниже мы расположим связки и кванторы в определенном порядке, считая, что те символы, которые в этом порядке находятся правее, «связывают сильнее», т. е. их следует выполнять «в первую очередь»: Ч- Ч л'~ ~ Таким образом, дизъюнкция и конъюнкция связывают сильнее, чем имллнкации, а сами они равноправны в отношении связывания. Аналогично, равноправны и кванторы. Онн связывают сильнее, чем любые логические связки. Так, формулу (Р=з(ЯУЮ=з( )й=»1Р))) можно сокращенно записать в виде Р~ ~:э Р Дальнейшая экономия скобок достигается употреблен ем точки.

Если внутри скобок выполняется несколько о породных (по силе связывания) логических символов, точкой мы отмечаем тот логический символ, который .выло няется в последнюю очередь в пределах своих скобок. Ра смотрим примеры: 1) формулу Р-~(Я~/Я~( ~й~ 1Р)) можно записать в виде Р= (аней . И= 1Р); 2) формулу (((Р ® й) (Р (О= )т))) можно записать в виде (Р.:зЯ.

~Я) ~ (Р~.4~:зй); 3) формулу (Р: (Я:»Я)) ((Р: Я) (Р= В).) можно записать в виде Р~ (Я-оЯ) ~. (Р:~Я) ~ (Р~Я) или в виде (Р-з.Я~Я) ~ (Р~Я. зРой); 4) формулу (((Р Е Ю/Р) ) можно записать в виде (Р~Я~Я)\/Р:зЯ; 5) формулу Рз)/хЯ(х)~/Я (х)) можно записать в виде Р=~~/х.Я(х) ~/В(х). 8. В формулах вида у'хА, ~хА выражение ух или 3 называется кванторной приставкой, х — переменной кван торной приставки, а формула А — областью действия кван торной приставки. Каждое вхождение переменной в формулу мы будем на зывать свободным или связанным. А именно, вхождение пе ременной х в формулу А называется связанным, если в А входит формула вида ЯхВ, причем рассматриваемое вхождение х,в А является вхождением х в эту формулу ЯхВ.

Кратко говорят, что вхождение х в А связано, если оно,по падает в область действия квантора по х или в саму кван- ео горную приставку с переменной х. Вхождение переменной, пе являющееся связанным, называется свободным. Таким образом, каждое связанное вхождение переменной происходит из-за некоторой кванторной приставки, которая «связывает» переменную. В примерах, приводимых ниже, мы указываем,:какие переменные являются связанными и от каких кванторсв это происходит (стрелками отмечены свободные вхождения переменных): ('! 'у' х (Р (~ (х)) Л ~ хЯ (х, г) ~ Д х)с (х, х)) ~~ Я (г, х), ! ! ! ! ! ! Чг(Р(У(г)) ЛЗхЯ(х, г) ~Зу)т(г, у))Ч Ю(г.

х), ! ' ! !' ~1' ! ! ! ! 'у'х(РД(х)) Л ~хЯ(х, г) ~~у)с(х, у))')Я(г, у). ! ! 1'1 Заметим, что одна и та же переменная может иметь и свободные и связанные вхождения в одну и ту же формулу.' Вхождение переменной может быть связано во всей формуле и в то же время свободно в некоторой ее подформуле. Здесь подформулой мы называем вхождение формулы в данную формулу, т. е. часть формулы, которая сама является формулой. В аналогичном смысле используется термин подтсрм и т.,п.

В атомарную формулу всякая переменная по определе. нию входит свободно. Удобно также считать по определению, что все переменные, входящие в терм, входят в него свободно. 9. Выше мы дали явное определение свободных и связанных вхождений переменных в формулу, но нетрудно дать и индуктивный рецепт, позволяющий отыскать свободные и связанные вхождения переменных. А.

Если рассматриваемая формула атомарна, то всякая переменная, входящая в нее, свободна. Б, Если формула имеет вид (АЬВ), то следует посмотРеть, ~куда именно входит переменная х, в А или в В. Допустим, например, что в А. Тогда х свободна (связана) в (АЛВ)«=»х свободна (связана) в А. Кратко это правило можно выразить так; логические связки переменных «не связывают».

В. Еспн формула, имеет вид ЯуА, и мы интересуемся вхождением, переменной х в эту формулу, то следует -разобРать два случая. 1) у сонцадает с х. Тогда х автоматцчески входит свя ванно в ЯуА. 2) у отлично от х. Тогда х свободна (связана) в ЯуА -~=»х свободна (связана) в А.' 10. Переменная х называется свободной переменной фор мулы А, или параметром А, если х входит (хотя бы оди раз) свободно в А. Разумеется, при этом х может входит в А и связанно. Множество всех параметров А обозначим через Рч(А) Это — конечное множество, переменных, может быть, и пу стое. Формулу, не содержащую параметров, назовем зам кнутой формулой, или предложением.

Множество всех пред ложений языка И-обозначим через Я,. Например, следующая формула есть 'предложение: ')ух.Р(х)Л~хЯ(х, х)~~ уй(х, у). Аналогично, параметром терма назовем всякую перемен ную, в него входящую. Терм назовем замкнутым, если он н содержит переменных (т. е. построя, ~исходя лишь из кон- стант языка Й).

Нетрудно дать и индуктивный рецепт для вычисления множества Рч(А): А. Рч(Р((ь ..., Ь»)) Рч(11)Ц...()Рч(1»); Б. Рч(ААВ) =Рч(А)УРч(В); Рч( ~А) =Рч(А); В. Рч(ЯхА) =Рч(А) '~(х). Здесь Ц обозначает объединение множеств, ". обозна- чает разность множеств и (х) — одноэлементное множество, единственным элементом которого является переменная х.

11. Роль формул в языке состоит в том, чтобы описы- вать высказывания и высказывательные формы в языке. При этом высказывательная форма зависит от перемен- ных —,параметров формулы (а не от связанных ~перемен- ных формулы). Каждая высказывательная форма, в свою очередь, задает некоторый предикат от своих параметров. Под предикатом мы понимаем функцию от переменных, про- бегающих некоторую область, причем эта функция прини- мает лишь два значения: 1 — «нстнна» н 0 — «ложь». Например, в некотором языке атомарная формула Р(х, у, х) может выражать высказывательную формух+у=а, где х, у, г обозначают натуральные числа О, 1, 2, 3„...

Та- ким образом, Р(х, у, з) задает трехместную функцию = предикат: Р(3,5,3)=0, Р(3 5,8)=1, Р(0,4,2)=0,... Формула й ур(х, у, з) задает уже предикат лишь от двух переменных х и з. Переменная у оказывается связанной. Например й уР(2, у, 3) =1, Д уР(0, у, О) =1, ~ уР(5, у, 2) =О. Нетрудно понять, что формула ЗуР(х, у, г) задает форму х~х.

На этом примере можно понять, почему свободные и связанные переменные играют различную. роль в формуле. Во-первых, вместо связанной переменной нельзя .подставить ~конкретное значение — получится бессмысленное выражение. Так, например, 3уР(0, у, 3) — вполне осмысленное, истинное утверждение, а ДЗР(2, 3, 3) не имеет разум. ного смысла. Во-вторых, связанная переменная не имеет самостоятельного значения, ее можно заменить на другую переменную и смысл формулы от этого не изменится.

Все формулы ~ уР(х, у, г), ~ иР(х, и, х), ~ иР(х, о, г) выражают один и тот же предвкат, одну и ту же функцию от х, г. Такая операция называется переименованием связанной переменной. При переименовании -связанной .переменной смысл формулы ие меняется, если при этом соблюдать одну существенную предосторожность: никакая .свободная переменная в любой подформуле' данной формулы не должна после переименования оказаться связанной.