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

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

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

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

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

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

Пусть задана сигнатура Σ=<φ₁,…, φ_n> типа <n₁,…,n_n> и множество символов V={x₁,…,x_k,…}.

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

1) V Ì T

2) t₁,…,t_n Î T & φ Î Σ → φ(t₁,…,t_n) Î T

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

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

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

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

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

Лекция 6

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