Множества и операции над ними. Отношение принадлежности. Множество. Элемент. Унификация объектов, страница 6

2. Функции на двухэлементном множестве {0,1}

Рассмотрим операцию композиции функциональных отношений:

Построим таблицу (некоммутативный моноид):

0	f₀	f₁	f₂	f₃
f₀	f₀	f₃	f₀	f₃
f₁	f₀	f₂	f₁	f₃
f₂	f₀	f₁	f₂	f₃
f₃	f₀	f₀	f₃	f₃

¨ Упражнение

1. Найти левые и правые нейтральные элементы в этой алгебре.

2. Сколько существует различных классов бинарных алгебр на двухэлементном множестве

(Внимание, таблица 2´2 заполяется двумя значениями 16 способами, но некоторые заполнения попарно изоморфны)

Пусть - левый и правый нейтральные элементы бинарной алгебры

Бинарная алгебра имеет нейтральный элемент

Опр.: Левым нулевым элементом называется

Правым нулевым элементом называется

Элемент называется нулевым, если является одновременно левым и правым нулевым элементом.

единичный нулевой элемент .

Обратные элементы:

Обычно используют следующие обозначения:

(нейтральный, но не нулевой).

Теорема о гомоморфном наложении группоидов:

- Бинарные алгебры;

F – гомоморфное наложение, если

1) - сюръективное функциональное отношение

2) -соотношение гомоморфизма

В этом случае:

1. Если в нейтральный элемент нейтральный элемент , причем .

2. Если у элементаобратный элемент, то у обратный элемент.

3. Если

4. Если - ассоциативна, то - ассоциативна

5. Если - коммутативна, то - коммутативна

Док-во:

3. , т. е. любое b имеет обратный элемент.

, т. к. F – сюръекция.

Пример: ассоциативна и коммутативна, тогда 0,1 – нейтральные элементы для .

Если в группоиде * - ассоциативна, то существует не более одного нейтрального элемента.

Док-во:

К моноидам: (При условии, что у нас есть единичный элемент и ассоциативная бинарная операция).

Опр.: Элемент называется обратным слева, если

Опр.: Элемент называется обратным справа, если

Опр.: Элемент называется обратным , если он обратим слева и справа.

Пусть - левый обратный элемент к

- правый обратный элемент к

, т. е. левый и правый обратный элементы совпадают.

Пусть - два обратных элемента.

, т. е. обратный элемент единственный.

Итог по бинарным алгебрам:

- группоид (или просто бинарная алгебра)

- ассоциативна – полугруппа

- моноид

- группа

Также все это можно разделить на коммутативные и некоммутативные группоиды, подгруппы, моноиды, группы.

Классификация бинарных алгебр:

асс.

не асс.

Условные обозначения:

- группоид

- полугруппа

- моноид

- группа

- коммутативная группа (Абелева группа)

Опр.: Группа – это моноид, в котором все элементы обратимы.

Группа – это система вида , где

G – множество элементов,

· - бинарная операция

e – единичный элемент ()

-1 – унарная операция вычисления обратного элемента

Т. о. группа – это система вида со свойствами:

1).

2).

3).

В группе, как и в моноиде, единственный нейтральный элемент e; левый и правый обратный элементы совпадают. У каждого элемента существует единственный обратный элемент.

Свойства групп:

1). Правила левого и правого сокращения:

G – группа;