ячейки которой могут находиться в состояниях, условно обозначаемых символами А, В.

Последовательность ячеек, занятых некоторыйш буквами, называется словом. Словом в данном алфавите называется каждое слово, все буквы которого принадлежат этому алфавиту. Например, если алфавит состоит из букв А, В, С, то слова

А, ВАА, С А, СС, АСВАВ (1)

будут словаьш в этом алфавите. В то же время первые два из них будут словами и в алфавите А, В.

Длиной слова называется число входящих в него символов (т. е. число занятых им ячеек). Так, длинами написанных выше слов (1) являются соответственно числа 1, 3, 2, 2, 5. Два слова называются (графически) равнылш, если они имеют одинаковые длины и на соответствующих местах в них находятся равные буквы.

Пусть символы а, Ь обозначают слова, записанные в алфавите, не содерзкащем самих символов а, Ь. Тогда через йЬ обозначается слово, пол5гчающееся, если сначала выписать слово а, а затем приписать справа к нему слово Ь. Например, если а означает слово aba, а Ь - слово ас, то аЬ будет обозначать слово аЬаас. Слово лЬ называется композицией (иногда произведением) слов й и Ь. Операция композиции слов, очевидно, ассоциативна, но не коммутативна.

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

Слово й называется подсловом стова Ь, если Ь можно представить в виде

Ь = СйЬ, (2)

где с, b - подходящие (возможно пустые) слова. Если й - подслово слова Ь, то говорят также, что й входит в Ь.

При заданных словах Ь, й разложений вида (2) может быть несколько. Например, для слов

Ь = ababab, й = ab

стцествуют следующие разложенпя указанного вида:

6 = a-abab = ab-a-ab = abab-й.

Если в разложении вида (2) слово с имеет наименьшую возможную длину, то говорят о первом вхождении слова а в Ь. Аналогичным образом можно говорить о втором вхождении слова й в слово Ь и т. д. Если слово й есть просто буква, то говорят кратко о вхождениях буквы й в слово Ь.

Пусть разложение (2) соответствует первому (вообще /с-Л1у) вхождению слова й в слово Ь и пусть ш - какое-нибудь слово. Тогда слово сотЬ называют словом, полученным заменой в слове 6 первого [к-то) вхождения слова й словом т. В этом случае говорят также о подстановке в слово Ь слова m вместо соответствующего вхождения слова й. Например, производя подстановку слова ас в слово ababab вместо второго вхождения в него слова аЬ, получим слово abacab. Подставляя в то же слово вместо первого вхождения слова аЬ пустое слово, получим слово аЪаЬ.

1.2. Функции. Термы. Пусть А, В - какие-либо множества, например, совокупности всех слов в подходящих алфавитах. Совокупность всех пар вида <а, 6>, где а (: А, b В, называется декартовым произведением Л па В и обозначается через А х В. Аналогично, если А, А, . . . . . ., Am - некоторые множества, взятые в определенной последовательности, то совокупность {{{Ai X Л2) X X Лд) X . . . x Am) называется декартовым произведением указанных множеств и обозначается кратко через 1 X 2 X ... X Am- Если все множества А, . . ., Am совпадают друг с другом, то их декартово произведение называется декартовой 7п-й степенью множества А.

Если некоторым элементам множества X поставлены в соответствие однозначно определенные элементы множества У, то говорят, что задана частичная функция пз X в Y. Совокупность тех элементов множества X, у которых есть соответствующие в Y, называется областью определения функции, а совокупность тех элементов множества У, которые соответствтот некоторым элементам множества X, называется совокупностью значений функции. Если пбласть определения функции шг X в Y совпадает с множеством X, "то функция называется всюду определен-пой.

Ес.лп функция / ставпт в соответствие эледгенту х (: X элемент у У, то у называется значением функции / в точке X. Функции / и g из Z в У называются равными, ес-лп они имеют одну и ту же область определения и значения их совладают в кан%доп точке области определения. .

Наряду с частичными функциями имеющими непустую область определения, во многих слаях бывает необходимо рассматривать и функцию, нигде не определенную.

Частичные функции из X x X x . . . x X = в Y называются частичными функциями от п переменных или и-местными функциялш из Z в У. Частичная функция из в X называется ге-Д1естной частичной операцией

на X.

Для записи функций и изучения их свойств пользуются особым формальным языком. Алфавит этого языка состоит из символов, разбитых на три группы. Символы первой грзтшы называются предметными символами. В качестве таких символов обычно употребляются буквы а, Ь, X, у, . . . или те же буквы с индексами: а, а-, х, г/о, г/1, • • .

Символы второй группы называются функциональными. Это будут буквы с верхними и, возможно, нижнилш индексами: g, fl, fb Буква с верхним индексом ге (и > 1) будет называться ге-местньш функциональным символом. Иногда верхние индексы не пишут, но непременно указывают число мест для данных функциональных символов.

Наконец, символы третьей группы - это символы левой, правой скобок и запятой: (,) ,,.

Слова особого вида, записанные в этом функциональном алфавите, называются термами. Определение их следующее. Термами длины 1 называются однобуквенные слова из букв, являющихся предметными переменными. Далее пользуемся индукцией. Пусть для некоторого s > 1 термы длины, меньшей s, определены. Тогда слово длины s называется термом, если оно имеет вид / (й, . . ., й„), где . . ., й„ - некоторые терлш меньшей длины, а / - и-членный функциональный символ. Например, если а, X - предметные символы, а f, g - соответственно одноместный и двухместный функциональные символы, то слова

Z, f (а), g {х, а), g (/ {х), g (а, х))

являются терма1ш длины соответственно!, 4, 6, 14.

Введем теперь понятие значения терма при заданных значениях предметных и функциональных символов. По определению задать значение предметного символа - это значит указать некоторое непустое множество, называемое основным лдаожеством, и сопоставить с рассматривае-

мым символом некоторый элемент этого множества. Этот элемент и называется значением данного символа.

Задать значение и-местного функционального символа - это значит сопоставить с ним какуто-нибудь частичную ге-местную операцию, определенную на основном множестве.

Значением терма длины 1 называется значение составляющего этот терм предметного символа. Пусть рассматривается терм й большей длины. Предположим, что основное множество X выбрано, значения всех входящих в терм предметных и функциональных символов на этом множест ве определены и терм в имеет вид / (в, . . ., й„), где / -/г-членный функциональный символ, а в, . . ., в„ - термы меньшей длины. По индукции мы можем считать, что значения термов й, . . ., уже определены и равны некоторым элементам х-, . . ., Хп множества X. По условию символу / поставлена в соответствие /г-местная операция /о, определенная на X. Значение этой операции в точке ixi, . . ., ХпУ будет каким-то элементом х из X. Этот элемент X и будет значением терма й при заданных значениях предметных и функциональных символов.

Может случиться, что в качестве значений функциональных символов взяты частичные операции, определенные Не всюду на основном множестве. Тогда и значение терма может оказаться неопределенным. А Именно, значение терма й = / (й1, . . ., й„) считается не определенным, если значение хотя бы одного из термов й, . . ., й„ не определено или не определено значение операции в точке ( Xi, . . . • • ч пУ, где Xi, . . ., Хп ~ значения термов й, . . ., а,. Например, в арифметике натуральных чисел термы

(2 -Ь 8) : 2, (2 X 7) - 7

имеют соответственно значения 5, 7, а значения термов

5 - (3 -Ь 3), 2:3, 3 : (2 - 2), 5 -- (2 : 3)

не определены. Терм

{{Зх + у):у) + А

имеет значение 7 при значениях 2 и 3 предметных символов X, у, не определен при значениях 2, 5 и имеет значение 5 при значениях О и 1 символов х, у.

Имея несколько операций, заданных на какодьто множестве X, мопшо при помопщ термов записать бесконечное множество новых операции, определенных на том же

множестве X. Делается это следующим образом. Обозначаем заданные операции какими-либо функциональными символами /j,. . ., fs- Пусть, кроме того, вX выделены еще некоторые элементы, обозначаемые символами а, . . ., а-Рассмотрим произвольный терм й, составленный из символов а, . . ., /ц • • •> /s и вспомогательных предметных символов . . ., xi. Так как основное множество X и зна-

чения символов «1,

dr, /ц • • м /s уже фиксированы, то, задавая по произволу значения для символов х, . . Xi в множестве X, мы можем найти значение терма й (которое может оказаться и неопределенным, если некоторые из заданных операций определены не всюду). Таким образом, каждой последовательности элементов -(Хх, . . ., xty множества X отвечает определенное (или неопределенное) значение терма й и потому мы имеем if-точечную операцию на X. Говорят, что эта операция изображается термом й.

При записи термов обычно пользуются теми или иными сокращениями. Например,- если х - предметный, / - одноместный функциональный символы, то терм / (х) часто записывают в виде fx, xf или х. Далее, если х, у - предметные символы, а / - символ двуместной операции, то терм / (ж, у) обычно пишут в видеа;/. В частности, если рассматривают двуместные операции, обозначаемые символами + ,-, - , то термы -f (й,6),-(й,6),-(й, Ь) всегда сокращенно обозначают через (й) + (Ь), (й) (Ь), (й) - (Ь). Если термы й, Ь длины 1, то в указанной записи скобки опускают и пишут просто й + Ь, йБ, а - Ь.

В дальнейшем всюду, где противное не оговорено явно, под числами понимаются натуральные числа О, 1, 2, 3, . . . Цифры О, 1, 2, . . ., 9 и их последовательности 10, И, 102, . . . будут рассматриваться как предметные симво.лы, имеющие фиксированные значения, равные соответственно натур а льньш числам нуль, один, . . ., десять, одиннадцать и т. д. Совокупность всех натуральных чисел будет обозначаться символом Пустое множество будет обозначаться через 0.

Частичные функции пз X х ... x У = З" в У будут называться к-местными числовыми частичными функциями. При этом для краткости иногда числовые функции будут называться просто функциями. Символы + ,-,- будут рассматриваться как двуместные функциональные симво.лы, фиксированными значениядш которых являются обьганые арифметические операции сложения, умнонадния п вычитания. В области натуральных чисел

две первые операции всюду определенные, а операция вычитания частичная.

Далее нам будут часто встречаться числовые функции s, о", Гт, имеющие по определению следующие значения: {х) = X + i, о" {xi, . . :, Хп) = О,

{х-, . . ., Хп) = (1 < 7?г < п; и = 1, 2, . . .).

Эти функции будем называть проапейшими. Вместо s, 0 будем обычно писать s, о.

Отметим, что терм, содержащий предметные символы X, у, Z, представляет однозначно определенную операцию только в случае, если эти символы определенным образом упорядочены. Изменяя их порядок, мы изменим и операцию. Например, терм

2х + у (3)

представляет функцию, ставящую паре <(1,3) в соответствие число 5, если переменная х считается первой, а переменная у - второй. Тот же терм (3) представляет функцию, относящую паре <(1, 3) число 7, если первой считается переменная у, а второй - переменная х.

Из рассмотренных примеров видно-, что встречающиеся в термах предметные и функциональные символы могут быть разбиты на две категории: 1) символы, значения которых фиксированы, и 2) символы, значения которых не фиксируются. Первые называются индивидуальными символами, а вторые - переменными.

Пусть на некотором множестве X заданы операции .1, . . ., /s и фиксированы некоторые эле1менты а, . . ., а пз X. Тогда каждая операция на X, нредставимая некоторым термом, занисанным при помощи функциональных символов /х, . . ., fs, предметных символов а, . . ., а. п произвольных предметных переменных, называется термальной отпосите.чьно данных операций п э.чементов. Например, есчп основное мнон<ество есть множество натуральных чисел N, заданная операция есть -f п фиксировано число 1, то термальными будут все линейные функции вида

г>о -Ь -Ь . . . + ЪХп,

где 6; - положительные натуральные числа. Еслп число 1 пе фиксируется, а задается лишь операция -f, то тер-