Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
V (дизъюнкция, читается ИЛИ), 1 (отрицание, читается НЕ),
-> (импликация, читается ВЛЕЧЕТ),
V (квантор всеобщности, читается ДЛЯ КАЖДОГО), 3 (квантор существования, читается СУЩЕСТВУЕТ), = (знак равенства, читается РАВНО),
называемых логическими символами, а также из символов;
ж, F, Р, А, ( (левая скобка), ) (правая скобка), , (запятая). СИНТАКСИС И СЕМАНТИКА
141
Слова вида.
(хА ... A) = (Xlsm) = хт (^ = 0,1,...),
(А ... AFA ... A) = (AnFAm)=F^ (т, п = 0, 1, ...),
(А ... АРА ... А) — (AnPAm) = Рт] (т, п = 0, 1,
называются соответственно предметными, функциональными и предикатными переменными. Число т называется номером переменного, а число п — арностью соответственного предикатного или функционального переменного. На символы хт, F^m, Р{т следует смотреть как на сокращенные обозначения соответствующих слов рассматриваемого языка. Знак равенства будет дальше играть двойную роль. С одной стороны, это будет алфавитный символ языка 2-й ступени, а с другой — это будет знак равенства, употребляемый в метаязыке, на котором будут выражаться свойства слов языка 2-й ступени.
Указанный выше алфавит языка 2-й ступени конечен, но каждая из совокупностей: предметных переменных, функциональных переменных произвольной арности и предикатных переменных этой арности — бесконечна. Тем не менее иногда к алфавиту языка 2-й ступени добавляются еще дополнительные символы, играющие роль предметных, функциональных или предикатных переменных.
Не все слова языка 2-й ступени употребляются для выражения свойств алгебраических систем, а лишь некоторые из них, называемые термами и формулами. В этом пункте будут изложены определение и простейшие свойства термов, а в следующем пункте — формул.
По определению полагаем:
1) каждое слово вида Xi или F^ есть терм;
2) если aj, . . ., ап — термы, то слово F(f (Ct1, . . ., ап) также терм;
3) слово называется термом, если оно является термом в силу условий 1), 2).
Отсюда, например, следует, что слова
(F[°\ х2, F? (X1)), F<2> (Ff (хи х2), С (X1, X1)) 142
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
являются термами, а слова
Ff Ff (X^Ff(X1)), Ff{PT, FT) — не термы.
Мы теперь хотим определить понятие значения терма при заданных значениях функциональных и предметных переменных, входящих в запись терма. Задать значение re-арного функционального переменного Ff^ — это значит поставить ему в соответствие конкретную п-арную операцию, определенную на фиксированном «основном» множестве А. Задать значение предметного переменного Xi — это значит поставить ему в соответствие какой-то элемент at из указанного основного множества А. При этом множество А фиксируется заранее и значения всех функциональных и предметных символов задаются в А. Значение произвольного терма T определяем далее индукцией по числу функциональных букв в записи терма. Если терм имеет вид Xi или то значение его совпадает со значением предметной переменной хи или Fi0K Если же терм T имеет вид F\n) (T1, . . ., Tn) и значения термов Ti, . . ., Tn равны соответственно элементам аи . . ., ап из А, то значение терма T равно значению соответствующей операции выполненной над эле-
ментами ai, . . ., ап. Иначе говоря, чтобы получить значение терма, надо выполнить над значениями предметных переменных все те операции, которые указаны в записи терма. Например, пусть требуется вычислить значение терма
Ff (X1, Ff (X1, х2)), (2)
когда значения хи х2 равны соответственно 2, 3, a Ff, Ff «обозначают» операции + и • на множестве N = = (0, 1, 2, ...}. Последовательно находим
Ff (хи х2) = 2 + 3 = 5, Ff (Xi, Ff (хи х2)) = 2- 5 = 10.
Если же Ff обозначает операцию сложения натуральных чисел, a Ff — операцию возведения в степень х^2, то при тех же значениях предметных переменных X1 = 2, х2 3 значением терма (2) будет число 22+3 = 32. СИНТАКСИС И СЕМАНТИКА
143
Иногда в качестве значений функциональных переменных допускают частичные операции, определенные не для всех значений предметных переменных. В таком случае и значение терма может оказаться неопределенным. А именно, значение терма, содержащего символы частичных операций, тогда и только тогда определенное, когда, выполняя над значениями предметных переменных последовательно операции, указанные в записи терма, мы все время будем получать определенные значения. Например, рассмотрим частичную алгебру ({О, 1, 2, . . .}; +, • , —), где +, • — обычные операции сложения и умножения чисел, а у — х — частичная операция вычитания, определенная только для пар X ^ у. Тогда имеем
1 4 0-(2 - 1) = 1, (2 — 3) + 3 = неопр., 1 4 0-(1 — 2) = неопр.
Следующая теорема указывает одно из наиболее замечательных свойств термов.
Теорема 1. Пусть задан гомоморфизм а некоторой алгебраической системы И = (A, Q) в однотипную систему §5 = (В, Q'), и пусть T (Xi, . . ., хТ) — какой-то терм, построенный из функциональных переменных Ffli\ . . ., F^m*' и предметных переменных Xi, . . ., хТ.
Значениями функциональных переменных F^^, . . ., F^"^ в системе SI будем считать операции Fi, Fs ? Q, а значениями тех же функциональных переменных в системе 35 будем считать одноименные операции Gi, . . ., Gs ^ ??2'. Тогда для любых элементов ai, . . ., аТ в 91
