- •Элементы общей алгебры
- •Алгебраические системы
- •Арифметика
- •Целочисленное деление
- •Алгебра матриц
- •Алгебра многочленов
- •Векторная алгебра
- •Алгебра логики
- •Арифметика вычетов по модулю n
- •Алгебра множеств
- •Операции с нефиксированным числом операндов
- •Свойства алгебраических операций
- •Коммутативность
- •Нейтральный элемент
- •Симметричный элемент
- •Ассоциативность
- •Вычисления в полях вычетов
Арифметика вычетов по модулю n
Базовое множество состоит из всевозможных остатков при делении целых чисел на n: Zn ={0,1,,n–1}, их называют вычетами.
Бинарные операции: сложение по модулю n, которое обозначим +n, это остаток от деления на n обычной суммы целых чисел; аналогично определяется и умножение по модулю n, которое обозначим n, это остаток от деления на n обычного произведения целых чисел.
С использованием операции mod (см пример 2) можно записать
x +n y =(x+y) mod n, x n y =(xy) mod n.
Пусть, например, n=5. Имеем Z5 ={0,1,2,3,4}. Примеры "модулярных вычислений": 1 +5 2 = 3, 1 +5 4 = 0, 3 +5 4 = 2, 1 5 2 = 2, 2 5 2 = 4, 3 5 2 = 1.
Операция XOR в алгебре логики – не что иное, как сложение по модулю 2, а конъюнкция – умножение по модулю 2.
Любую бинарную операцию на конечном множестве можно задать с помощью квадратной таблицы (ее называют таблицей Кэли), в которой каждая строка соответствует конкретному значению первого операнда, а каждый столбец – конкретному значению второго операнда. Так, операции алгебры логики задаются следующими таблицами Кэли:
Таблица 1.4
Формальная операция
a
b
c
a
a
b
c
b
b
c
a
c
c
a
b
-
0
1
0
1
XOR
0
1
0
1
0
0
0
0
0
1
0
0
1
0
1
1
1
0
1
1
1
1
1
1
0
1
0
1
Таблицы Кэли сложения и умножения по модулю 5 Таблица 1.3
-
+5
0
1
2
3
4
5
0
1
2
3
4
0
0
1
2
3
4
0
0
0
0
0
0
1
1
2
3
4
0
1
0
1
2
3
4
2
2
3
4
0
1
2
0
2
4
1
3
3
3
4
0
1
2
3
0
3
1
4
2
4
4
0
1
2
3
4
0
4
3
2
1
С помощью таблицы Кэли можно задавать и чисто формальные операции на некотором конечном множестве, не имеющие (по крайней мере, на первый взгляд) никакого конкретного смысла. Пусть, например, базовое множество M={a,b,c}, о природе элементов a,b,c ничего не известно. Формальную операцию зададим таблицей Кэли. Попробуйте угадать, что это за операция, т.е. связать ее с каким-то содержательным примером.