Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
137
нет, то повторяем тот же процесс над ними. Поскольку алгебра St конечна, то указанный процесс оборвется и мы получим искомое разложение а на минимальные слагаемые. Остается доказать взаимную однозначность отображения ф, т. е. что представление каждого элемента а в виде суммы различных минимальных ненулевых элементов единственно. Пусть
а = O1 + ... + as = + ... + bt
— два таких разложения. Умножая обе части на аи получим Cii = CLibi + . . . + афі. Произведение atbj тогда и только тогда отлично от нуля, когда a, = bj. Поэтому каждый член первой суммы встречается во второй и, наоборот, каждый член второй встречается в первой, что и требовалось доказать. Сохранение операций сложения, умножения и взятия дополнительного элемента при отображении ф очевидно.
Для бесконечных алгебр Буля можно утверждать в общем случае, что каждая бесконечная алгебра Буля изоморфна подалгебре алгебры всех частей подходящего бесконечного множества. ГЛАВА III
ЯЗЫКИ ПЕРВОЙ И ВТОРОЙ СТУПЕНИ § 6. Синтаксис и семантика
6.1. Термы. Выше указывалось (см. п. 2.2), что в теории алгебраических систем изучаются преимущественно лишь свойства систем, остающиеся инвариантными при изоморфизмах систем на системы. Одним из языков, на котором удобно выражать инвариантные свойства систем, является язык 2-й ступени. Строится он следующим образом.
Алфавитом называется произвольная совокупность попарно различных символов. Предполагается, что мы можем рассматривать произвольные конечные последовательности букв, каждая из которых «воспроизводит» тот или иной символ алфавита. Эти последовательности букв называются словами в данном алфавите. Далее мы не будем символы алфавита отличать от воспроизводящих их букв. Например, пусть алфавит состоит из символов 0, 1, + , = , а, Ъ. Последовательности
аа, abab, а+ = 1, 0 + 1=1, + 1 = ++а
суть слова в указанном алфавите. Число букв слова называется его длиной. Два слова называются (графически) равными, если они имеют одинаковые длины и соответствующие их буквы равны. Например, слова 0+1 и 1+0 различны, так как различны их первые буквы. Совокупность всех слов в данном алфавите называется формальным языком в этом алфавите. Для того чтобы говорить о свойствах слов данного формального языка, мы употребляем некоторые символы, не принадлежащие алфавиту языка. Эти символы называются символами метаязыка или мета- СИНТАКСИС И СЕМАНТИКА
139
символами. В частности, в выражениях вида «рассмотрим какие-нибудь слова А ж В формального языка» буквы А, В не входят в состав алфавита формального языка и являются метасимволами.
Итак, пусть А, В — слова какого-нибудь формального языка. Выписывая сначала буквы первого слова А и приписывая затем к ним все буквы слова В, получим новое слово, называющееся композицией слов AtB и обозначающееся через AB. Отсюда видно, что композиция есть особая бинарная операция, определенная на множестве слов данного формального языка. Иногда ее обозначают точкой и называют операцией умножения слов. Результат этой операции, конечно, зависит от порядка слов-сомножителей. Например
аЪа-Ъа = ababa, Ъа-аЪа = ЪааЪа.
Однако операция композиции слов, очевидно, ассоциативна.
Наряду с обычными только что определенными словами в данном формальном языке иногда вводят в рассмотрение еще особый символ Л, называемый пустым словом. По определению полагают
A-A =A-A = А
и длиной пустого слова называют число 0.
Отрезки слова называют его подсловами. Ясно, что слово А і есть подслово данного слова А тогда и только тогда, когда существуют слова X, Y, удовлетворяющие уравнению
А = XA1Y. (1)
Может случиться, что слово А имеет несколько отрезков, равных заданному слову A1. В этом случае уравнение (1) имеет несколько решений для X, Y. Первый отрезок А, равный A1, называется первым вхождением A1 в слово А; второй отрезок слова А, равный A1, называется вторым вхождением A1 в А и т. д. Если X1, Y1, X2, Y2, • • ч Xn, Ytl — все решения уравнения (1) и
дл. X1 <?№• XiC . . . < дл. X1 140
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
где дл. обозначает длину слова, то решение X1, Y1 отвечает первому вхождению A1 в А, решение X2, Y2 отвечает второму вхождению и т. д. Решения X, Y, для которых X = A или Y = A, не исключаются. Если Z1 — Л, то A1 называют начальным отрезком или начальным подсло-вом слова А. Отрезки длины 1 являются просто буквами данного слова. Пустое слово Л, согласно сказанному, имеет т 1 вхождений в слово длины т, видных из разложений
Л-uj ... ат = Cb1- А - а2 ... ат = ... = . . . ат-А.
Пусть A1 — подслово слова А и В — какое-нибудь заданное слово. Рассмотрим ?-е вхождение A1 в А, отвечающее разложению А = XA1Y. Слово XBY называется результатом подстановки слова В в слово А вместо ї-го вхождения слова A1 и обозначается символически через Sbi {A', A1, В), где Sbi — символ операции подстановки. Например,
Sb2 (abac; а, с) — abcc, Sb1 (ab; А, с) — cab, Sb1 (cab; а, А) — cb.
На этом мы пока прервем абстрактное изучение формальных языков и займемся изучением строения конкретного языка, названного выше языком 2-й ступени. Алфавит языка 2-й ступени состоит из символов: & (конъюнкция, читается И),
