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

Начнем с определения термов языка зг. Это определение индуктивное и содержит три пункта. Первые два пункта являются базисом индукции: в них непосредственно указа- но, какие из объектов языка следует считать термами. Тре- тий пункт представляет собой шаг индукции — он задает порождающие правила: если уже построены некоторые тер- мы, то разрещается построить из них новый терм по ука- занному правилу.

Каждый терм имеет либо вид, указанный з первых двух пунктах определения, либо получен,по по- рождающему правилу третьего пункта из термов, построен- ных на более раннем этапе. Каждому терму в силу определения будет однозначно приписан некоторый сорт языка — сорт данного герма (в ' другой терминологии — сорт значений данного терма). Итак, приведем индуктивное определение терма данного сорта языка И: 1) каждая переменная х сорта и языка й есть терм сор- та и; 2) константа с сорта и языка й есть терм сорта гц 3) если 1 — фУнкциональный символ .вила (пь ..., и» н) языка й и 1, — терм сорта пь 㻠— терм сорта пм ...„ »» — терм сорта и„, то выражение )((ь ..., 1») есть'терм сор- та и; коротко этот пункт запишем в виде правила вывода 6»,г», ...,г» 1(й, ...,ц) ' Множество всех термов сорта и языка й обозначим через.

Тш"„множество всех терман всевозможных сортов — че- рез Тт,. Таким образом, каждый терм имеет одни и только один 'из следующих двух видов. А. Константа или переменная языйа й; Б. 1(гь ..., 1»), где 1 — функциональный символ языка й и 1ь ..., г» суть термы соответствующих сортов. Например, термом некоторого языка может быть выра- жение д(й(с, х),д(х, Ь(с, у))), где у и й — двумерные функциональные символы, с — кон- станта, х и у — переменные. При этом сорта выражений должны быть надлежащим образом согласованы. Роль термов в языке состоит в том, чтобы описывать именные формы и .имена предметов.

Так, в некотором язы- ке переменные могут рассматриваться как пробегающие множество О, 1, 2,... натуральных чисел, у(х, у) описывает сумму х+у, а й(х. у) — произведение х у натуральных чи- сел. Константа с обозначает натуральное число О. Тогда вышеприведенный терм задает именную форму О х+(х+О у). Подчеркнем, однако„что сами по себе термы — суть. просто строчки символов и ничего не выражают. Чтобы уз- нать, какую именную форму задает терм, необходимо до- полнительно объяснить, что обозначают символы„встречаю- щиеся в терме, т.

е., как говорят логики, задать семантику языка, задать интерпретацию языка. Одной из наших даль- нейп»их задач и будет точное оформление этой идеи. Индуктивный характер определения множества Тша предполагает возможность использовать следующий способ рассуждения: принцип индукции по построению множества термов (языка й). А именно пусть мы желаем доказать, что некоторое свойство Х выполняется для всех термов языка й. С этой целью достаточно установить', что: 1) каждая переменная языка й обладает свойством Х, 2) каждая константа языка (г обладает свойством Х, 3) если 1,, ..., 1 суть термы, обладающие свойством Х, н 1(1ь ..., 1 ) — терм, то 1(1ь ..., 1 ) также обладает свой-.

ством Х. В таКой ситуации в силу индуктивного определения множества Тш, можно быть уверенным, что всякий терм языка () обладает свойством Х. Зтот при~нцип индукции естественно обобщает известный школьный принцип полной математической индукции. Действительно, натуральные числа можно трактовать как индуктивно порождаемые объекты: они порождаются из объекта О последовательным применением операции прибавления единицы. Поэтому если мы установим, что: 1) О обладает свойством Х, 2) если п есть натуральное число, обладающее свойством Х, то а+1 также обладает свойством Х, то можно быть уверенным, что всякое натуральное число обладает свойством Х.

С этой точки зрения множество термов образует арифметику со многими операциями следования, которые могут быть и многоместными. Подобные индуктивные определения играют важную роль в математической логике. Докажем, например, что всякий терм языка содержит одинаковое количество вхождений левых и правых скобок. В самом деле, это верно по отношению к переменным и константам языка (ни те, ни другие вовсе не содержат скобок). Далее, если термы (ь ..., 1 та~новы, что каждый терм й содержит одинаковое количество левых и правых скобок, то терм )(1ь ..., 1 ), очевидно, тоже таков (в нем добавилось ровно одно вхождение левой скобки и одно вхождение правой скобки).

Наше утверждение следует теперь из принципа индукции по построению термов языка. Упражнение, Индукцией по построению термов докажите, что количество запятых в терме равно т — й, где т— сумма арностей всех вхождений функциональных символов, а й —,количество вхождений функциональных символов в терм. Аналогично, индуктивный характер определения Тщ„ дает возможность задавать функции, определенные на множестве Тгп, индукцией по построению множества термов языка 11 (иногда в таких случаях говорят о возможности задавать функции рекурсией (примитивной рекурсией) по построению множества термов). А именно: 1) пусть с каждой переменной х языка 12 мы связали некоторый объект Р(х), 2) с каждой константой с языка Й мы связали некоторый объект Р(с), 3) нусть задано правило, в,соответствии с которым ес- лн термам 1ь ..., 1 уже приписаны объекты Р(1~), ..., Р(1 ), то правило позволяет отыскать объект РЩ(ь ..., 1 )) для терма 1(1ь ..., 1 ).

В такой ситуации для всякого терма 1 языка однозначно определен объект Р(1). Определим, например, функцию 1 на множестве всех термов языка»з рекурсией: 1) если х — переменная языка, то положим 1(х) =О, 2) если с — константа языка, то,положим Цс) =О, 3) если терм имеет вид ~(1ь ..., 1»), то определим, Ц)'(1ь ..., 1») ) =Ц1,) +.,+ Ц1»)+1. На последнее равенство следует смотреть ка~к на прави.ло, в силу которого мбжнр вычислить Ц1(1ь ..., 1»)), если уже известны значения 1(Я, ..., Ц1»). Указанное определение дает рецепт для вычисления 1 от любого терма. Например 1(Ду(х, у), с, г, х) ) =2. Значение Ц1) называется функциональной сложностью терма 1.

У п р а ж н е н и е. Индукцией по построению термов до- ' кажите, что для всякого терма 1 значение Ц1) равно количеству вхождений функциональных символов в терм 1. Таким образом, можно было,бы дать и не .индуктивное, явное определение функции 1. Оба определения математически эквивалентны: приняв одно из них, второе можно доказать как математическую теорему. Такая ситуация еще не раз у нас встретится. Заметим, что множество Тшл, всегда бесконечно, так как содержит переменные сорта н (даже если в языке отсутствуют функциональные символы и константы).

3. Атомарные формулы языка »1 (в другой терминологии — элементарные формулы языка ьз) определяются следующим образом.' Если Р— предикатный символ языка И вида (пь ..., н»), а 1ь ..., 1» суть термы, причем терм 1~ имеет сорт нь то выражение Р(1ь ..., 1») есть атомарная формула. В частности, если Р— пропозициональная буква (т. е. нульместная буква), то Р сама по себе является атомарной формулой. Множества всех атомарных формул языка Й обозначи м через А1 Гт,. 4. Формулы языка ь) определяются нндуктивно с помощью следующих ниже семи пунктов.

Первый пункт представ:: -. собой базис индукции, а остальные шесть цунк тов суть порождающие правила, позволяющие строить но- вые формулы из уже построенных. Прн построении формул используются новые символы, которые называются логическими символами, Они делятся на две категории — логические связки и кванторы. Мы употребляем следующие четыре логические связки: Л вЂ” конъюнкция, «и», Ч вЂ” дизъюнкция, «или», :э — импликация, «если, то», «влачет», 1 — отрицание, «не». Мы используем .два ивантора: у' — всеобщность (генерализация), «для всех», и' — существование (экзистенция), «существует». Итак, приведем индуктивное определение формулы язы- ка Й: 1) каждая атомарная формула есть формула; 2) — ', т.

е. если уже построены формулы А и В, то А,В (АЛВ) ' разрешается построить новую формулу (АЛВ); подобным образом следует трактовать и следующие три пункта: 3) — ' А,в (А)/В) 4) — ' А;В (А~В) 5) —; А )А' 6) — ', т. е. если уже построена формула А и х — про- А,х нкА извольная переменная языка ь), то разрешается построить новую формулу )/ хА; подобным образом следует трактовать и следующий пункт: 7) — ' А,х йкА Множество всех формул языка Я обозначим через Еш,.

Таким образом, каждая формула имеет один и только один иэ следующих трех видов: А. атомарная формула языка ().„ Б. (АЛВ), где А, В суть формулы языка ьг, а Ь— логическая связка, один из символов Л, ~/, ~ или А, где А формула языка (); В. ЯхА, где А — формула языка й, х — переменная языка Й и я — квантор, один из символов )/, 3.

4 за«. 478 57 Например, формулой некоторого языка может быть вы- ражение Ч З ((Ра , у))ИЭ е(», )) З у(1( ° у)). Читая логические связки и кванторы, мы можем «про- честь» ету формулу: «для всякого х существует г, такое, что если РЦ(х, у)) и существует х, для которого Я(х, г), то существует у, для которого Я(х, у)». Выражением зайка й мы назовем формулу языка й или терм языка Р. Множество всех выражений языка»« обозначим Ехр,.