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

1. Дискретная математика

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

2.

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

3.

Алгеброй называется множество, вместе
с заданной на нем совокупностью
операций
Ω = { φ1 , φ2 , ... , φn } , т. е.
система
А = (M ; φ1 , φ2 , ... , φn )
.

4.

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

5.

Множество
M М называется
замкнутым относительно
n-арной операции на М, если
φ(М ′ )⊆ M ′
n
,
т. е. если значения на аргументе из
M′
принадлежат
M′
.

6.

Если
M ′ замкнуто относительно
всех операций
φ1 , φ2 , ... , φn ,
алгебры А с носителем М, то система
А′ = (M ′ ; φ1 , φ2 , ... , φn )
называется подалгеброй алгебры А

7. Примеры:

Алгебра
R , , – называется полем
действительных чисел.
Обе операции бинарные, поэтому
тип этой алгебры (2,2).
Сигнатура
, .
Подалгеброй этой алгебры является,
например, поле рациональных
чисел.

8. Примеры:

N p = {0,1, 2, ... , p 1}
.
Определим на N p операции:
– «сложение по модулю р»,
– «умножение по модулю р»,
следующим образом:
a b c и a b d ,
где с и d – остатки от деления на р чисел
а + b и а b соответственно.
Пусть

9. Примеры:

Пусть, например, р = 7, тогда
N p = { 0,1, 2, 3, 4, 5, 6 }
и
3 4 0 , 3 4 5,
4 6 3
.
Часто обозначают: a + b = с (mod p) и
a b = d (mod p).

10. Примеры:

Конечным полем
характеристики р называется
алгебра
N p , ,
если р – простое число.

11. Пример:

Булеаном U называется
множество всех подмножеств
множества U (обозначается B(U)).
Булева алгебра множеств над U
или алгебра Кантора – алгебра
В=(B(U), , , ). Ее тип (2,2,1),
сигнатура Ω = ( , , ).
Элементами основного множества
булевой алгебры являются
множества (подмножества U).

12. Пример:

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

13. Пример:

Множество
U = {a , b , c , d }
тогда основное множество
алгебры В содержит 16
элементов.
B B a, b , , ,
является подалгеброй В.

14. Свойства бинарных алгебраических операций

Операция φ называется
ассоциативной, если для
любых элементов а, b, с
a b c a b c a b c

15. Пример:

1. Сложение и умножение чисел ассоциативны,
что позволяет не ставить скобки в
выражениях
a +b+c
2. Возведение в степень
– не ассоциативна, так как
не равно
a b c a
и
a b c
.
b
a a b
b c
bc
a b c a a
b c.

16. Свойства бинарных алгебраических операций

Операция φ называется
коммутативной, если для
любых элементов a, b
a b b a

17. Пример:

1 Сложение чисел коммутативно («от перемены
мест слагаемых сумма не меняется»):
a b b a
2. Умножение чисел коммутативно («от перемены
мест множителей произведение не меняется»):
a b b a

18. Пример:

3 Вычитание и деление – некоммутативные
операции.
a b b a
a/b b/ a
2. Умножение матриц – некоммутативная
операция, например:
1 2 2 2 2 3 2 2 1 1 2 4
0 1 0 1 0 1 0 1 0 1 0 1

19. Свойства бинарных алгебраических операций

Операция φ называется
дистрибутивной слева
относительно операции ψ, если
для любых a, b, с
a b c a b a c

20. Свойства бинарных алгебраических операций

Операция φ называется
дистрибутивной справа
относительно операции ψ,
если для любых a, b, с
a b c a с b c

21. Пример:

1 Умножение дистрибутивно относительно
сложения слева и справа
a b c a b a c
a b c a c b c

22. Пример:

2 Возведение в степень дистрибутивно
относительно умножения справа.
a b c a b
c
a b a с b c
c
c

23. Пример:

но не слева, так как
a b c a
b c
a b a c a
b
c
a a
b c

24. Пример:

3. Сложение не дистрибутивно относительно
умножения
a b c a b a c
a b c a c b c