Лексико-графический порядок.

Пусть в списке букв конечного алфавита А порядок букв зафиксирован, т. е. всегда один и тот же, как, например, в русском и латинском алфавите. Тогда этот список определяет полное упорядочение букв, которое назовем отношением предшествования и обозначим “ ”: , если предшествует в списке букв).

На основе отношения предшествования букв, строится отношение предшествования слов, определяемое следующим образом:

Пусть даны слова и .

Тогда, тогда и только тогда, когда

1) , где ( - слова возможно непустые, - буквы);

2) , где - непустое слово.

Это отношение задает полное упорядочение множества всех конечных слов в алфавите А, которое является лексикографическим упорядочением слов.

Операции и алгебры

N-арная операция на множестве М – это функция типа

,

где n – арность операции. Операция замкнута относительно множества М по определению, т. е. операция над элементами множества М, и результат тоже элемент М.

Алгеброй называется множество, вместе с заданной на нем совокупностью операций , т. е. система

.

М – основное (несущее) множество (носитель алгебры) алгебры А.

Тип алгебры – вектор арностей операций.

Сигнатура – совокупность операций W.

Множество называется замкнутымотносительно n-арной операции на М, если

,

т. е. если значения на аргументе из принадлежат .

Если замкнуто относительно всех операций , алгебры М, то система

называется подалгеброй алгебры А (при этом рассматриваются как операции на ).

Примеры:

1. Алгебра – называется полем действительных чисел.

Булеаном U называется множество всех подмножеств множества U (обозначается B(U)).

Булева алгебра множеств над U или алгебра Кантора – алгебра B(U), ). Ее тип (2,2,1), сигнатура ( ).

Элементами основного множества булевой алгебры являются множества (подмножества U).

Для любого B( ), ) – является подалгеброй В.

Например, если , то основное множество алгебры В содержит 16 элементов; алгебра B( ), ) – подалгебра В. Ее несущее множество содержит четыре элемента.