Главная / Информатика / Операции на множествах и их специальные свойства

Операции на множествах и их специальные свойства

Алгебры. Любое отображение из Mn В M называют П-местной операцией на множестве М. Пусть на M Заданы N-местная операция j,…, Nm-местная операция jM. Множество М вместе с заданной на нём упорядоченной совокупностью операций W ={j,…, j}, т. е. система А=(М; j,…, j), называется Алгеброй. При этом М называется Носителем алгебры А, упорядоченный набор (N,…, N) называется ее Типом, W — Сигнатурой.

Множество MÌ M называется Замкнутым относительно П-Местной операции J На М, если J(М’)Í М’ Т. е. если значения J на аргументах из М’ принадлежат М’. Если М’ Замкнуто относительно всех операций J,…, J алгебры А, то набор А’=(М’,J,…,J) называется Подалгеброй Алгебры А (при этом J,…,J рассматриваются как операции на М’).

Примеры.

1. Алгебра (Ñ;,) называется Полем действительных чисел. Обе операции – двуместные, поэтому тип этой алгебры (2, 2). Все конечные подмножества R, кроме {0}, не замкнуты относительно каждой из этих операций. Поле рациональных чисел является подалгеброй этой алгебры.

2. Пусть Np{0, 1, 2,…, Р-1}. Определим на N операции Å («сложение по модулю Р») И Ä («умножение по модулю Р») следующим образом: АÅB=с, AÄB=D, где С и DОстатки от деления на Р чисел А+B и АB соответственно.* Например, если Р7, то Np={0, 1,…, 6}, 3Å4=0, 3Ä4=5, 4Å6=3. Если Р – Простое число, то алгебра {N; Å, Ä} называется Конечным полем характеристики р.

3. Пусть задано множество U. Алгебра B=(2U; ) называется Булевой алгеброй множеств над U; её тип (2, 2, 1). Элементами основного множества этой алгебры являются подмножества U. Для любого UÌU система В¢=( 2U¢; ) является подалгеброй алгебры В. Например, если U={А, B, с, D}, то носитель алгебры В содержит 16 элементов; алгебра В¢={2{А, С}; } – подалгебра В, её носитель содержит четыре элемента.

4. Множество F одноместных бесконечно гладких вещественных функций на Ñ, имеющих производные всех порядков, Вместе с операцией дифференцирования является алгеброй. Единственная операция этой алгебры одноместна. Множество многочленов замкнуто относительно дифференцирования и, следовательно, образует подалгебру данной алгебры.

5. Пусть A, а, а, а– вершины квадрата, пронумерованные против часовой стрелки. Рассмотрим повороты квадрата против часовой стрелки вокруг центра, переводящие Таких поворотов бесконечное множество: на углы 0, p/2, p, 3p/2, 2p, 5p/2,…, однако они задают всего четыре различных отображения множества вершин в себя, соответствующих первым четырём поворотам. Обозначим эти повороты через A, B, G , d. Получаем алгебру с основным множеством {A, а, а, а} и четырьмя одноместными операциями: a, b, g, d. Их можно задать табл. 2.1, в которой на пересечении, например, строки А и столбца g написано значение функции g(А ).

Таблица 2.1

Таблица 2.2

A

B

G

D

A

B

G

D

A

A

А

А

А

A

A

B

G

D

А

А

А

А

A

B

B

G

D

A

А

А

А

A

А

G

G

D

A

B

А

А

A

А

А

D

D

A

B

G

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

6. Множество О={a, b, g, d} отображений носителя предыдущей алгебры в себя вместе с двуместной операцией композиции отображений образует алгебру {О; }. Композиция отображений, принадлежащих множеству О, есть результат последовательного выполнения двух поворотов. Она задается таблицей 2.2 (в ней, например, на пересечении строки и столбца g написан результат композиции g). Множество {a, g}, т. е. повороты на углы 0, p, образует подалгебру алгебры {О;}.

Отметим, что любая двуместная операция на конечном множестве, может быть задана таблицей, аналогичной таблице 2.2; такая таблица называется Таблицей Кэли.

Специальные свойства бинарных алгебраических операций. Для того, чтобы последующие соотношения выглядели более привычно, условимся результат применения двуместной операции J К элементам А, B Записывать не в функциональном виде J(АB), А в виде АJB, как это принято для арифметических операций.

В качестве первого свойства, которым может обладать или не обладать бинарная операция рассмотрим ассоциативность. Операция j называется Ассоциативной, Если для любых элементов А, B, с

(АJB)JС=АJ(BJС).

Выполнение этого условия (свойства ассоциативности) означает, что скобки в выражении можно не расставлять. Сложение и умножение чисел ассоциативны, что и позволяет не ставить скобки в выражениях АBС И аBС. Пример неассоциативной операции – возведение в степень: (АBА(B). Правда, запись АB считается допустимой, но служит сокращением выражения А(B), а не (АB)с, которое равно более компактному выражению АBС.

Важным примером ассоциативной операции является композиция отображений.

Следующее свойство называется коммутативностью. Операция J называется Коммутативной, если для любых элементов А, B

АJB=BJА.

Сложение чисел коммутативно («от перемены мест слагаемых сумма не меняется»), так же как и умножение чисел; вычитание и деление чисел некоммутативны. Некоммутативным является умножение матриц: например,

´ = , но ´ = .

Следующее свойство – дистрибутивность. Это уже взаимное свойство двух операций. Операция J называется Дистрибутивной слева относительно операции Y, если для любых А, B, с

АJ(BYС)=(АJB)Y(АJС),

И Дистрибутивной справа Относительно Y, если

(АYB)JС=(АJС)Y(BJС).

Дистрибутивность даёт возможность pacкрывать скобки. Умножение чисел дистрибутивно относительно сложения слева и справа. Возведение в степень дистрибутивно относительно умножения справа: (АBАсBС, но не слева: АBС¹АBАс.