Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Рц (Z1, ... , Zm.n) •=*> Q^ (Z1O,*, . . . , ZmllOC*)
для любых термов Z1, . . ., Zm от элементов S.
6.2. Формулы. Наряду е термами и их значениями в языке 2-й ступени такую же фундаментальную роль играют понятие формулы, понятия свободных и связанных переменных в данной формуле и значения формулы. Понятия формулы, свободных и связанных переменных определяем совместно путем следующей индукции:
1) Для каждого предикатного переменного Р[п* и произвольных термов T1, Tn слово Pi^ (T1, ..., Tn) есть формула. Для каждого нульарного предикатаСИНТАКСИС И СЕМАНТИКА
147
слово Р\0) есть формула. Все переменные в этих формулах свободны.
2) Для каждых термов Ti, T2 слово Ti = T2 есть формула. Все переменные в этой формуле свободны.
3) Если % — формула, то "1? — также формула. Все переменные, свободные в формуле свободны и в "1?. Все переменные, связанные в формуле остаются связанными и в формуле 1?.
.4) Пусть ^1, ^2- такие формулы, что переменные, входящие одновременно в обе формулы, свободны в каждой из них. Тогда слова
CS1Vg2), CSfi->sa) (1)
— также формулы. Переменные, свободные хотя бы в одной из формул ^1, являются свободными и в формулах (1). Переменные, связанные в х{акой-либо из формул Sfi, — связанные и в формулах (1).
5) Пусть $ обозначает какое-либо из переменных Xu F^f, P^f, и это переменное входит свободно в некоторую формулу %. Тогда слова
(Vs)g, (is)gf (2)
снова являются формулами, в которых переменное j связанное, а все остальные переменные, входившие свободно или связанно в формулу gf, остаются такими же и в формулах (2).
6) Слово называется формулой, если оно является формулой вследствие утверждений 1)—5).
Определение 1)—6) является ¦ индуктивным, причем индукция ведется по числу знаков P^f, =, участвующих в записи формул. Существует очень простой алгоритм, позволяющий для любого заданного слова узнать, является ли оно термом, формулой или нет. Для этого сначала заметим, что в термах и формулах скобки всегда входят парами соответствующих друг другу левой и правой скобок и что пары соответствующих скобок не могут разделять друг друга. Пара скобок называется внешней, если все остальные буквы слова лежат внутри этой пары.
Из правил образования термов и формул следует, что термами и формулами, не содержащими скобок, являются
10*148
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ
[Гл. III
лишь слова
~ 17(0) П(0) . __ /ДО) E-(C) __ PCO) J і > jrt > - > 1J 7 ji - ijl
— -^1ZT 1 І -^Ї — t^1/* ^ t^i '
и т. д.
Пусть SI — какое-нибудь слово, содержащее скобки. Находим в §1 первичные пары скобок. Чтобы слово 21 было формулой, необходимо, чтобы либо внутри первичной пары находилось слово вида (3), либо чтобы 21 вместе с этой первичной парой содержало подслово вида F\l) (щ, . . ., Ui) или Pf (щ, . . ., Ui), где щ, . . ., Ui-переменные вида ха, Fa\ Пара скобок в слове называется парой высшего порядка относительно другой пары скобок, если вторая пара содержится внутри первой. Первичные пары — это пары наинизшего порядка. Переход от пар скобок внутри слова $ к парам высшего порядка должен совершаться по правилам 1)—5). Если эти правила в какой-то момент нарушаются, то слово 21 —не формула. Например, слова
(УХІ)(ХІ=Х2&.(ІХ3)Р™ (X2rX3)), (IXi) (Vx2)H X2 = X2
— формулы, а слова
(VaJ1) F? (х„ Z2), ((Vxl) Р<» (Xi) & (3*.) Р<» (Xi))
— не формулы.
Значением предикатного переменного на множестве А называется произвольный конкретный г-арный предикат Р, определенный на А. Значением формулы 21 при заданных значениях всех свободных предметных, функциональных и предикатных переменных этой формулы на фиксированном множестве А называется символ И или Л, вычисляемый по следующим правилам:
а) Пусть 21— формула вида и = v, где и, v — термы. Значениями этих термов являются некоторые элементы а, Ъ из А. Если а = Ъ, то значение 21 есть И. Если же а Ф Ъ, то значение 21 есть Л.
б) Пусть 21 — формула вида P^ (a t, ..., а 0, где Q1, ..., аг — термы. Значения этих термов равны каким-то элементам Cz1, ..., а; множества А. Значением переменного P^ служит какой-то г-арный предикат P1 заданныйСИНТАКСИС И СЕМАНТИКА
149
на А. По определению значение P (а1: ...,CLi) называется значением формулы Pj^ (Ctll ..а?).
в) Пусть формула g имеет вид H Si, где Si —более короткая формула. Вычисляем значение Si. Если оно равно И, то значение % равно Л. Если значение SI равно Л, то значение % равно И.
г) Если формула % имеет один из следующих видов:
(SI&33), (WM Щ, (Si —> ?3)
и значения формул Si, известны, то значение % вычисляется согласно известной логической таблице
Si аз (ЗШЗ) {гущ (а—>«)
и и и и и
И JI л и л
л и л и и
л л л л и
(4)
д) Пусть формула g имеет вид (Vri) SI или (3^,)SI. По условию все свободные переменные формулы % имеют заданные значения. Формула SI имеет свободными переменными все свободные переменные формулы % и, сверх того, переменное хи значение которого не задано. Так как формула SI короче формулы то> задавая для Xi какое-нибудь значение а из множества А, мы можем вычислить значение Si. Если для каждого а в множестве А значение SI равно И, то значение формулы (Vxi) SI равно И. В противном случае значение формулы (\fxt) SI полагают равным Л. Если существует такое значение для X1 в А, при котором значение SI есть И, то значение формулы (Зж;) St полагаем равным И. Если при всех значениях IiBi значение SI есть Л, то значение формулы (Зжг) SI полагаем равным Л.