Научная литература
booksshare.net -> Добавить материал -> Математика -> Мальцев А.И. -> "Алгебраические системы" -> 48

Алгебраические системы - Мальцев А.И.

Мальцев А.И. Алгебраические системы — Наука, 1970. — 392 c.
Скачать (прямая ссылка): algebraicheskiesistemi1970.djvu
Предыдущая << 1 .. 42 43 44 45 46 47 < 48 > 49 50 51 52 53 54 .. 133 >> Следующая


Рц (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 полагаем равным Л.
Предыдущая << 1 .. 42 43 44 45 46 47 < 48 > 49 50 51 52 53 54 .. 133 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed