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

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

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

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

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

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

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

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

УПРАЖНЕНИЯ

1. Определите свойства отношений  и их вид, где М – множество натуральных чисел:

 - ”быть меньше”;  - ”быть больше или равно”;  - ”иметь общий делитель, отличный от 1”;  - ”быть делителем”;  - ”иметь общий остаток от деления на 3”. Задать эти отношения различными способами, если .

   Какие их этих отношений являются отношениями порядка, отношениями эквивалентности?

2. Определите свойства отношений  и их вид, где  - множество прямых на плоскости (см. рис 1):

 - ”быть параллельной”;

 - ”быть перпендикулярной”;

 - ”пересекаться” (иметь одну и только одну общую точку)

   Задать эти отношения различными способами, если

Рис. 1

3. Определите свойства отношений  и их вид, где М – множество элементов структуры, изображённой на рисунке 2:

 - ”быть непосредственно связанным с …”;

 - ”быть начальником”;

 - ”быть непосредственным начальником”;

 - ”быть подчинённым”;

 - ”быть непосредственно подчинённым”;

 - ”быть предком”;

 - ”быть потомком”.

   Задать эти отношения различными способами.

Рис. 2

4. Определите свойства отношений  и их вид, где М – множество натуральных чисел:

 - ”быть меньше”;  - ”быть больше или равно”;  - ”иметь общий делитель, отличный от 1”;  - ”быть делителем”;  - ”иметь общий остаток от деления на 3”. Задать эти отношения различными способами, если .

   Какие их этих отношений являются отношениями порядка, отношениями эквивалентности?

5. Определите свойства отношений  и их вид, где М – множество людей:

 - ”любить”;  - ”быть моложе”;  - ”быть сыном”;

 - ”жить в одном городе”;  - ”быть соседом (жить за стенкой)”.

6. Определите свойства отношений  и их вид, где М – множество точек плоскости:

 - ”иметь одинаковое расстояние от начала координат”;    - ”лежать на одинаковом расстоянии от оси ОХ”;  - ”быть симметричным относительно оси ОУ”.

   Сделать рисунок, задать 6 точек, на их примере построить матрицу бинарного отношения. Определить будут ли эти отношения отношениями эквивалентности. Если да, как разбивается плоскость на классы и каков индекс разбиения.

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

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

,

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

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

.

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

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

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

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

,

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

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

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

Примеры:

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

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

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

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

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

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