Аналогично, индуктивный характер определения Тто дает возможность задавать функции, определенные на множестве TmQ индукцией по построению множества термов языка Q (иногда в таких случаях говорят о возможности задавать функции рекурсией (примитивной рекурсией) по построению множества термов). В такой ситуации для всякого терма t языка однозначно! определен объект F(t). Указанное определение дает рецепт для вычисления / от любого терма. Значение l(t) называется функциональной сложностью терма t. Упражнение. Индукцией по построению термов докажите, что для всякого терма t значение /(/) равно количеству вхождений функциональных символов в терм L Таким образом, можно было ;бы дать и не индуктивное, явное определение функции I. Оба определения математически эквивалентны: приняв одно из них, второе можно доказать как математическую теорему. Такая ситуация еще не раз у нас встретится. Атомарные формулы языка Q (в другой терминологии — элементарные формулы языка Q) определяются следующим образом. Если Р — предикатный символ языка Q вида (ль . В частности, если Р — пропозициональная буква (т. Формулы языка Q определяются индуктивно с помо-| щью следующих ниже семи пунктов. При построении формул используются новые символы, которые называются логическими символами. Они делятся на две категории — логические связки и кванторы. Множество всех формул языка Q обозначим через FmQ. Таким образом, каждая формула имеет один и только один из следующих трех видов: A. Выражением языка Q мы назовем формулу языка или терм языка Q. Множество всех выражений языка обозначим Ехра. По определению Ехра = FmaUTma. Индуктивный характер определения множества Fr предполагает возможность использовать следующий спосс рассуждения — индукцию по построению множества форм{, (языка Q). А именно если мы желаем доказать, что некот(| рое свойство X выполняется для всех формул языка Q, достаточно установить, что: A. Если факты А, Б, В установлены, то можно быть уве ренным, что свойство X имеет место для любой формул! языка. Докажем, например, что всякая формула языка соде{ жит одинаковое количество вхождений левых и правы| скобок. Аналогично, индуктивный характер определения Fma да-] ет возможность задавать функции, определенные на множе| стве Fma индукцией по определению множества Fma (за давать функции рекурсией (примитивной рекурсией) по по строению множества Fma). В такой ситуации для всякой формулы А языка Q определен объект F. Упражнение. Индукцией по построению множества формул докажите, что 1(А) равно количеству вхождений логических символов в Л. Практически записывая формулы,, удобно экономить скобки, пользуясь некоторыми традициями и 'приемами. Вся точная теория у нас будет относиться лишь к формулам в точном определении. Прежде бсего, мы опускаем внешние скобки. Кроме того, ниже мы расположим связки и кванторы в определенном порядке, считая, что те символы, которые в этом порядке находятся правее, «связывают сильнее, . Аналогично, равноправны и кванторы. Они связывают сильнее, чем любые логические связки. Если внутри скобок выполняется несколько од нородных (по силе связывания) логических символов, ъ точкой мы отмечаем тот логический символ, который выпол няется в последнюю очередь в пределах своих скобок. Каждое вхождение переменной в формулу мы будем называть свободным или связанным. А именно, вхождение переменной х в формулу А называется связанным, если в А входит формула вида QxB, причем рассматриваемое вхож-' дение х в А является вхождением х в эту формулу QxB. Кратко говорят, что вхождение х в А связано, если оно попадает в область действия квантора по х или в саму кван- 60 торную приставку с переменной х. Вхождение переменной, не являющееся связанным, называется свободным. Таким образом, каждое связанное вхождение переменной происхо-'г дит из-за некоторой кванторной приставки, которая «связывает» переменную. Здесь подформулой мы называем вхождение формулы в данную формулу, т. В аналогичном смысле используется термин подтерм и т. В атомарную формулу всякая переменная по определению входит свободно. Удобно также считать по определению, что все переменные, входящие в терм, входят в него свободно. Выше мы дали явное определение свободных и связанных вхождений переменных в формулу, но нетрудно дать и индуктивный рецепт, позволяющий отыскать свободные и связанные вхождения переменных. Если рассматриваемая формула атомарна, то всякая переменная, входящая в нее, свободна. Кратко это правило можно выразить так: логические связки переменных «не связывают». Если формула имеет вид QyA, и мы интересуемся вхождением переменной х в эту формулу, то следует -разобрать два случая. Тогда х автоматически входит свя| занно в QyA. Переменная х называется свободной переменной фор\ мулы А, или параметром А, если л;. Разумеется, при этом х может входить в А и связанно. Множество всех пред** ложений языка Q обозначим через St0. Аналогично, параметром терма назовем всякую переменную, в него входящую. Терм назовем замкнутым, если он не содержит переменных (т. Роль формул в языке состоит в том, чтобы описывать высказывания и высказывательные формы в языке. ТОМ высказывательная форма зависит от перемен-; ных — . Каждая высказывательная форма, в свою очередь, задает (некоторый предикат от своих 'параметров. Под предикатом мы понимаем функцию от переменных, пробегающих некоторую область, причем эта функция принимает лишь два значения: 1 — «истина» и 0 — «ложь». Переменная у оказывается связанной. На этом пр^имере можно вгонять, почему свободные и связанные переменные играют различную, роль в формуле. Во-первых, вместо связанной переменной нельзя подставить конкретное значение — 'получится бессмысленное выражение. Такая операция называется переименованием связанной переменной. Причина неприятности -состоит в том, что после неудачного переименования связанной переменной у первое вхождение переменной х, которое раньше (было свободным, стало связанным.