1.10.6. Операции

Операцией называют функцию, все аргументы и значения которой принадлежат одному и тому же множеству.

В общем случае n-местная функция типа (иначе ) называется n-арной операцией на множестве М.

В таких случаях говорят, что множество М замкнуто относительно операции φ (результат операции φ на множестве М принадлежит М). В частности:

1. Функция одного аргумента , имеющая тип , называется унарной операцией. Примеры унарных операций:

• элементарные функции и др.,

• операции над множествами – дополнение ,

• отображения типа АА, такие как преобразования.

2. Функция двух аргументов , имеющая тип , называется бинарной операцией. Примеры бинарных операций:

• арифметические операции: сложение, вычитание, умножение, деление, возведение в степень;

• операции над множествами: пересечение, объединение, разность \;

• операция композиций функций, отображений, отражений и др.

Свойства бинарных операций

1. φ – ассоциативна, если для любых a, b, c из М

(*)

Ассоциативность операции означает, что если выражение включает некоторую ассоциативную операцию, то последовательность действий при получении результата может быть произвольной. (Арифметические операции сложения и умножения, операции пересечения и объединения множеств, композиция отображений – ассоциативные операции).

Выполнение этого свойства означает, что скобки в (*) можно не расставлять.

2. φ – коммутативна, если для любых a, b, c

Коммутативность операции означает независимость результата операции от перемены мест аргументов. (Арифметические операции сложения и умножения, операции пересечения и объединения множеств – коммутативные операции).

Операции вычитания и деления, разности множеств, композиция перестановок и преобразований типа АА конечного множества – некоммутативны.

3. φ – дистрибутивна слева относительно операции ψ, если для любых a, b, c и φ – дистрибутивна справа относительно операции ψ, если для любых a, b, c . Арифметические операции умножения и деления дистрибутивны относительно операций сложения и вычитания слева и справа, операции объединения и пересечения множеств дистрибутивны относительно друг друга слева и справа.

Элемент е называется нейтральным для элемента а, если .

Элемент называется обратным к элементу аА, если .

Пример. Рассмотрим операцию на множестве

X={(0, 0), (0, 1), (1, 0), (1, 1)} заданную таблицей:

Легко заметить, что для всех элементов множества Х нейтральным является элемент (0, 0), и каждый элемент совпадает со своим обратным.

Операции сложения и вычитания недистрибутивны относительно операции деления и умножения.

1.10.6.1. Способы задания операций

Так как операция является функцией, то для её задания применимы любые способы задания функций, рассмотренные выше. Приведём некоторые наиболее часто употребляемые способы представления унарных и бинарных операций.

1. Способы задания унарных операций на конечном множестве .

• Перечнем всех аргументов а из М и соответствующих им значений b, a, bM, представленных строкой а чаще парой строк .

• Списком всех пар «аргумент – значение» (a, b)φ, a, bM, для всех возможных значений аргументов: .

Число таких пар .

• Формулой , например, lga=b.

2. Способы задания бинарных операций на конечном множестве :

• Таблицей Кэли – для чего слева и сверху таблицы выписываются все значения аргументов а и b из множества М , соответственно, а на пересечении строки, соответствующей аргументу а и столбца, соответственно аргументу b, записывается результат с операции над а и b.

Пример. Составим таблицу Кэли для операции, называе

	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

мой «сложением по модулю 3» на множестве M={0, 1, 2} и обозначаемой «mod 3», или . Результат с выполнения операции равен остатку от деления суммы аргументов (a+b) на 3.

• Списком всех троек (a, b, c), где a, b – соответственно первый и второй аргумент из М, с – результат выполнения операции над а и b, a, b, сM. Для всюду определённой операции число всех троек в списке (число пар элемтов)

Пример1. Для операции сложения по модулю 3:.

• Формулой – так называемое префиксное представление операции.

Иное – инфиксное представление бинарной операции формулой , например , где - операция сложения по модулю 3.

Пример 2. Являются ли ассоциативными:

а) бинарные арифметические операции;

б) бинарные операции над множествами?

• а) Арифметические операции сложения и умножения ассоциативны, так как выполняются условия: (a+b)+c=a+(b+c), например , (5+2)+3=5+(2+3);

(a∙b)∙c=a∙(b∙c), например, (5∙2)∙3=5∙(2∙3).

Операции вычитания, деления и возведения в степень неассоциативны, так как

(a-b)-c≠a- (b-c), например, (12-6)-2≠12-(6-2);

(a/b)/c≠a/(b/c), например, (12/6)/2≠12/(6/2), т.е.1≠4.

, например, , т.е. 2⁶≠2⁸.

б) Операции объединения и пересечения множеств ассоциативны, операция разности множеств неассоциативна:

• .

Иллюстрируем справедливость данных соотношений на примере конкретных множеств. Пусть A={a, b, c},

B={b, c, d}, C={b, d}.

Тогда правая часть первого соотношения:

Левая часть:

Правая часть второго соотношения:

Лева часть

Правая часть третьего соотношения:

Левая часть:

Т. е. действительно {a}≠{a, b}. (То же самое можно показать с помощью диаграмм Венна).

Пример3. Проиллюстрировать на примерах некоммутативность операций:

а) возведение в степень на множестве N;

б) композиция элементарных функций;

в) композиция преобразований и перестановок типа АА конечного множества А.

• а) Бинарная арифметическая операция возведения в степень некоммутативна, т. е. например, , но , т.е. .

• б) Некоммутативность операции композиции элементарных функций, т. е. og ≠go иллюстрируется примером: f(x)=2x и g(x)=1+x

h₁ =og =1+2x; h₂= gо=f(g(x))=2g(x)=2(1+x)=2+2x: .

в) некоммутативность операции преобразования конечного множества иллюстрирует пример 8 в предыдущем параграфе.

Пример. Какими свойствами отличаются операции и , заданные таблицами Кэли?

	a	b
a	а	а
b	b	b

	a	b
a	b	а
b	a	b

Проверим операции и на коммутативность:

а) a b b a б) a b b a

Операция – некоммутативна, – коммутативна.

Проверим операции на ассоциативность:

а) Операция неассоциативна, так как не выполняется, например, (b a) b = b (a b). так как (b b = b a

при a b

б) Операция ассоциативна, так как соответствующее условие выполняется для всех возможных троек аргументов a,b,c из M.

- ? - ?

- ? - ?

-? -?

-? - ?

- ? - ?

- ? - ?

- ? - ?

- ? - ?

Операция неассоциативна, а - ассоциативна. Операции и недистрибутивны слева и справа относительно друг друга. Таким образом, операция некоммутативна, неассоциативна и недистрибутивна

(относительно операции );

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