Материал: Ответы на экзаменационные вопросы по дискретной математике

означает, что свойство (аксиома) присутствует (обязательно соблюдается).

означает, что свойство (аксиома) отсутствует (может соблюдаться, а может и не соблюдаться).

Таблица 3

Как видим, в магме есть только замкнутость, значит те структуры, которые обладают замкнутостью, магма обобщает:

Магма Полугруппа Моноид Группа Абелева группа.

То есть всякая абелева группа — это магма, всякая группа — это тоже магма и т. д. (Всякая группа — это моноид, всякий моноид — это полугруппа…)

Нейтральный элемент и обратимость будут описаны позже.

Полугруппа

Полугруппа — множество с одной бинарной операцией (множество замкнуто относительно этой операции), обладающей свойством ассоциативности:

Коммутативная полугруппа — полугруппа с коммутативной бинарной операцией. То есть, помимо ассоциативности, для любых элементов также выполняется:

Подполугруппа — подмножество полугруппы , если оно само является полугруппой относительно ограничения операции на подмножество . Для этого достаточно, чтобы (то есть соблюдалась замкнутость) и соблюдалась ассоциативность.

Примеры:

1. Множество натуральных чисел с операцией сложения — коммутативная полугруппа:

1. (замкнутость)

2. (ассоциативность)

3. (коммутативность)

2. Множество натуральных чисел с операцией умножения — коммутативная полугруппа:

1. (замкнутость)

2. (ассоциативность)

3. (коммутативность)

3. Множества (целых, рациональных, действительных, комплексных) чисел с операцией сложения (или умножения) — коммутативные полугруппы.

4. Множество — подполугруппа коммутативной полугруппы по сложению (или по умножению).

5. Множество — не подполугруппа полугруппы по сложению, так как (то есть нарушена замкнутость). Но — подполугруппа полугруппы по умножению.

6. Множество с операцией деления — не полугруппа (и как следствие не подполугруппа полугруппы ), так как нет ассоциативности:

7. Множество нечётных чисел с операцией сложения — не полугруппа, так как сумма двух нечётных чисел даёт чётное число, то есть нарушена замкнутость.

8. Множество матриц одного размера с операцией сложения — коммутативная полугруппа.

9. Множество квадратных матриц одного порядка (размера ) с операцией умножения — полугруппа (но не коммутативная).

Моноид

Если в множестве введена некоторая операция «», то нейтральным элементом по отношению к этой операции называется такой элемент , что для любого элемента выполняется равенство: . Такого элемента может и не быть. Но если он есть, то он единственен по определению для : .

Моноид — полугруппа с нейтральным элементом .

Коммутативный моноид — моноид с коммутативной бинарной операцией.

Очевидно, что любой моноид является полугруппой, а обратное неверно.

Подмоноид — подмножество моноида , если оно само является моноидом относительно ограничения операции на подмножество . Для этого достаточно, чтобы было полугруппой и существовал нейтральный элемент в для .

Примеры:

1. Множество натуральных чисел с операцией умножения — коммутативный моноид:

1. (замкнутость)

2. (ассоциативность)

3. (коммутативность)

4. (наличие нейтрального элемента: ).

2. Множество натуральных чисел с нулём с операцией сложения — коммутативный моноид:

1. (замкнутость)

2. (ассоциативность)

3. (коммутативность)

4. (наличие нейтрального элемента: ).

3. Полугруппа с операцией сложения — коммутативный моноид, причём нейтральным элементом является число 0, так как .

Это же верно относительно полугрупп: — множество рациональных чисел, — множество вещественных чисел, — множество комплексных чисел.

4. Те же полугруппы с операцией умножения — коммутативные моноиды, причём нейтральный элемент — , так как .

5. Множество чётных чисел с операцией умножения — не моноид (но коммутативная полугруппа), так как единица не принадлежит этому множеству. Однако с операцией сложения — коммутативный моноид (нейтральный элемент — принадлежит множеству чётных чисел).

6. Множество — подмоноид коммутативного моноида по умножению (нейтральный элемент ).

7. Множество матриц одного размера с операцией сложения — коммутативный моноид, причём нейтральный элемент — нулевая матрица, то есть матрица, все элементы которой 0.

8. Множество квадратных матриц одного порядка с операцией умножения — моноид (но не коммутативный), причём нейтральным элементом является единичная матрица такого же порядка, то есть матрица, на главной диагонали которой стоят 1, а все остальные элементы 0.

9. Список с операцией конкатенации и пустым списком как нейтральным элементом.

10. Словарь. Нейтральный элемент — пустой словарь. Операция — объединение словарей по ключу, при равенстве ключа для значений должна быть определена операция слияния (замечание: если операция слияния значений некоммутативна, то слияние словарей тоже будет некоммутативно). Например, можно определить операцию слияния как: 1) числа складывать, 2) строки конкатенировать, 3) списки конкатенировать, 4) для вложенных словарей проводить операцию рекурсивно. Например, далее первый словарь объединяется со вторым и получается третий:

    1. {"a" => 2, "b" => "cd", "c" => [1, 2], "d" => {"e" => 1}, "f" => 1}.

    2. {"a" => 3, "b" => "e", "c" => [3], "d" => {"e" => 2}, "g" => 1}.

    3. {"a" => 5, "b" => "cde", "c" => [1, 2, 3], "d" => {"e" => 3}, "f" => 1, "g" => 1}.