double arrow

Система образующих алгебры


Множество М´Í М называется системой образующих алгебры (M; Σ), если [М´]Σ =М. Если |М′|<∞, то алгебра называется конечно-порождённой. Бесконечные алгебры могут иметь конечное число образующих.

Если алгебра имеет одну образующую, то все её элементы являются степенями образующей – такая алгебра называется циклической.

Арифметика: (N;+): конечно порождённая, циклическая, образующей алгебры является 1 любой элемент n получается n-кратным применением операции + – «возведение в степень».

Пусть А={а1, а2, …, аn, …} – алфавит (конечный или бесконечный). Элементы алфавита называются буквами. Словом в алфавите А называется конечная последовательность (упорядоченная) букв, записанная друг за другом: х1х2х3…хn, хk Î A, – причём каждая буква в слове может встречаться произвольное число раз. Длиной слова называется общее количество букв. Слово нулевой длины обозначается Λ. Множество всех слов в алфавите А вместе с нулевым словом обозначается А*. Два слова, подряд записанные друг за другом образуют новое слово, в том же алфавите. – Следовательно, это действие является бинарной операцией, которая называется конкатенацией и обозначается ^. (А*, ^) – алгебра.




Алгебра термов.

Пусть задана сигнатура Σ=<φ1,…, φn> типа <n1,…,nn> и множество символов V={x1,…,xk,…}.

Определим множество термов Т = { t1,…,tn ,…}в сигнатуре Σ следующим образом:

1) V Ì T

2) t1,…,tn Î T & φ Î Σ → φ(t1,…,tn) Î T

Эта алгебра называется свободной алгеброй термов. Операциями в ней являются подстановки (суперпозиции) формул над множеством Σ.

NBНосителем Σ-алгебры является множество термов – формальных выражений, построенных с помощью знаков операций сигнатуры Σ. Т.е., с Σ-алгеброй не связано никакое конкретное множество, являющееся носителем. Единственная семантика (содержание) терма – его структура. Её можно представить графически в виде дерева. Свободные Σ-алгебры используются, в частности, в программировании для представления абстрактных типов данных.

Прямое произведение алгебр

Пусть заданы алгебры A = (А, {f}) и B = (В,{y}) одного типа.

Прямым произведением алгебр A‰B называется алгебра (А‰В, {q}), где операции q определяются следующим образом: q(<a1,b1>,…, <an,bn>) = <f(a1,…,an), y(b1,…,bn)>.


Лекция 6

Алгебры с одной операцией







Сейчас читают про: