Операции. В общем случае n-местная функция типа j: M´M´ ´M®M (или j: Mn®M) называется n-арной операцией на множестве M

В общем случае n-местная функция типа j: M ´ M ´…´ M ® M (или j: Mⁿ ® M) называется n- арной операцией на множестве M. В таких случаях говорят, что множество M замкнуто относительно операции j (результат выполнения операции j на M принадлежит M).

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

1) j – ассоциативна, если для любых a, b, c из M

(a j b) j c = a j (b j c);

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

a j b = b j a;

3) j – дистрибутивна слева относительно операции y, если для любых a, b, c

a j (b y c) = (a j b) y (a j c)

и j дистрибутивна справа относительно операции y, если для любых a, b, c

(a y b) j c = (a j с) y (b j c).

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

1. Способы задания унарных операций j: M ® M на конечном множестве M ={ a ₁, a ₂, …, a_n }:

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

j=(a ₁® b ₁, a ₂® b ₂, …, a_n ® b_n),

а чаще парой строк:

· Списком всех пар “аргумент-значение” (a, b)Îj, a, b Î M, для всех возможных значений аргументов:

j={(a ₁, b₁), (a ₂, b ₂), …, (a_n, b_n)}.

Число таких пар |пр₁j|= m £| M |= n.

· Формулой j(а)= b, например lga = b.

2. Способы задания бинарных операций j: M ´ M ® M на конечном множестве M ={ a ₁, a ₂, …, a_n }:

· Таблицей Кэли – для чего слева и сверху таблицы выписываются все значения аргументов a и b из множества M соответственно, а на пересечении строки, соответствующей аргументу a, и столбца, соответствующего аргументу b, записывается результат с операции j над a и b. На рис. 3.2 приведена таблица Кэли для операции, называемой “сложением по модулю 3” на множестве M ={0, 1, 2} и обозначаемой “ mod 3”, или Å₃ (результат с выполнения операции Å₃ равен остатку от деления суммы аргументов (a + b) на 3).

· Списком всех троек ( a, b, c ), где j(a, b)= c, a, b, c Î M. Для всюду определенной операции число всех троек в списке равно | M ´ M |= n ². Например, для операции сложения по модулю 3: Å₃={(0, 0, 0), (0, 1, 1), (0, 2, 2), (1, 0, 1), (1, 1, 2), (1, 2, 0), (2, 0, 2), (2, 1, 0), (2, 2, 1)}.

· Формулой j( a, b )= c – так называемое префиксное представление операции; иное – инфиксное – представление бинарной операции формулой a j b = c, a Å₃ b = c, где Å₃ – операция сложения по модулю 3.

Пример 1. Пусть операции композиции , объединения È и пересечения Ç определены на множестве бинарных отношений Доказать:

а) ассоциативность операции композиции (составного отношения)

R ₁ (R ₂ R ₃)=(R ₁ R ₂) R ₃;

б) дистрибутивность слева композиции относительно объединения È:

R ₁ (R ₂È R ₃)=(R ₁ R ₂)È(R ₁ R ₃);

в) дистрибутивность справа композиции относительно объединения È:

(R ₁È R ₂) R ₃=(R ₁ R ₃)È(R ₂ R ₃);

г) дистрибутивность слева композиции относительно пересечения Ç:

R ₁ (R ₂Ç R ₃)=(R ₁ R ₂)Ç(R ₁ R ₃);

д) дистрибутивность справа композиции относительно пересечения Ç:

(R ₁Ç R ₂) R ₃=(R ₁ R ₃)Ç(R ₂ R ₃).

Так как бинарное отношение R Í M ´ M, по определению, является множеством пар (a, b)Î R прямого произведения M ´ M, то для дока-зательства справедливости свойств а) – в) можно воспользоваться определением равенства множеств: A = B Û (A Í B)&(B Í A).

а) R ₁ (R ₂ R ₃)=(R ₁ R ₂) R ₃.

Пусть пара элементов a, b Î M и (a, b)Î R ₁ (R ₂ R ₃), (a, b)Î(R ₁ R ₂) R ₃ и наоборот. Действительно:

(a, b)Î R ₁ (R ₂ R ₃) Û (a, с)Î R ₁ и (с, b)Î R ₂ R ₃ Û

Û (a, с)Î R ₁ и (с, d)Î R ₂ и (d, b)Î R ₃ Û

Û (a, d)Î R ₁ R ₂ и (d, b)Î R ₃ Û (R ₁ R ₂) R ₃,

где с, d Î M.

Доказанное позволяет опускать скобки, т.е.

R ₁ (R ₂ R ₃)=(R ₁ R ₂) R ₃= R ₁ R ₂ R ₃.

б) R ₁ (R ₂È R ₃)=(R ₁ R ₂)È(R ₁ R ₃).

Пусть a, b Î M и (a, b)Î R ₁ (R ₂È R ₃). Тогда

(a, b)Î R ₁ (R ₂È R ₃) Û (a, с)Î R ₁ и (с, b)Î R ₂È R ₃ Û

Û (a, с)Î R ₁ и [(c, b)Î R ₂ или (c, b)Î R ₃] Û

Û [(a, с)Î R ₁ и (c, b)Î R ₂] или [(a, с)Î R ₁ и (c, b)Î R ₃] Û

Û (a, b)Î R ₁ R ₂ или (a, b)Î R ₁ R ₃ Û (R ₁ R ₂)È(R ₁ R ₃),

где с Î M.

Аналогично доказывается свойство в).

г) R ₁ (R ₂Ç R ₃)=(R ₁ R ₂)Ç(R ₁ R ₃).

Пусть a, b Î M и (a, b)Î R ₁ (R ₂Ç R ₃). Тогда

(a, b)Î R ₁ (R ₂Ç R ₃) Û (a, с)Î R ₁ и (с, b)Î R ₂Ç R ₃ Û

Û (a, с)Î R ₁ и [(c, b)Î R ₂ и (c, b)Î R ₃] Û

Û [(a, с)Î R ₁ и (c, b)Î R ₂] и [(a, с)Î R ₁ и (c, b)Î R ₃] Û

Û (a, b)Î R ₁ R ₂ и (a, b)Î R ₁ R ₃ Û (R ₁ R ₂)Ç(R ₁ R ₃),

где с Î M.

Аналогично доказывается свойство д).

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

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

а) a Ä b = b Ä a? б) a Ä¢ b = b Ä¢ a?

a ¹ b. a = a.

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

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

а) Операция Ä неассоциативна, так как не выполняется, например:

(b Ä a)Ä b =bÄ(a Ä b)?

b Ä b = b Ä a?

a ¹ b.

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

(a Ģ a)Ģ a = a Ģ(a Ģ a)? (a Ģ b)Ģ a = a Ģ(b Ģ a)?

b Ģ a = a Ģ b? a Ģ a = a Ģ a?

a = a. b = b.

(a Ģ a)Ģ b = a Ģ(a Ģ b)? (a Ģ b)Ģ b = a Ģ(b Ģ b)?

b Ģ b = a Ģ a? a Ģ b = a Ģ b?

b = b. a = a.

(b Ģ a)Ģ a = b Ģ(a Ģ a)? (b Ģ b)Ģ a = b Ģ(b Ģ a)?

a Ģ a = b Ģ b? b Ģ a = b Ģ a?

b = b. a = a.

(b Ģ a)Ģ b = b Ģ(a Ģ b)? (b Ģ b)Ģ b = b Ģ(b Ģ b)?

a Ģ b = b Ģ a? b Ģ b = b Ģ b?

a = a. b = b.

Операция Ä – неассоциативна, тогда как Ä¢ – ассоциативна.

3. Проверим операции на дистрибутивность.

а) Дистрибутивность слева и справа Ä относительно Ä¢ не выпол-няется, так как, например:

a Ä(a Ä¢ a)=(a Ä a)Ä¢(a Ä a)? (a Ä¢ a)Ä b =(a Ä b)Ä¢(a Ä b)?

a Ä b = a Ä¢ a? b Ä b = a Ä¢ a?

a ¹ b. a ¹ b.

б) Дистрибутивность слева и справа Ä¢ относительно Ä также не выполняется, так как, например:

a Ä¢(a Ä a)=(a Ä¢ a)Ä(a Ä¢ a)? (a Ä a)Ä¢ a =(a Ä¢ a)Ä(a Ä¢ a)?

a Ä¢ a = b Ä b? a Ä¢ a = b Ä b?

b ¹ a. b ¹ a.

Операции Ä и Ä¢ не дистрибутивны слева и справа относительно друг друга.

Таким образом, операция Ä – некоммутативна, неассоциативна и недистрибутивна (относительно операции Ä¢); операция Ä¢ – коммутативна, ассоциативна, но недистрибутивна (относительно операции Ä).

Вопросы для самопроверки и упражнения:

1. Доказать дистрибутивноть справа и слева операций пересечения и объединения относительно друг друга на системе множеств:

A Ç(B È C)=(A Ç B)È(A Ç C) – дисрибутивность слева Ç относительно È;

A È(B Ç C)=(A È B)Ç(A È C) – дисрибутивность слева È относительно Ç;

(A È B)Ç C =(A Ç С)È(A Ç C) – дисрибутивность справа Ç относительно È;

(A Ç B)È C =(A È С)Ç(A È C) – дисрибутивность справа È относительно Ç;

Проиллюстрировать на примере конкретных множеств, а также диаграммами Венна.

2. Пусть R ₁, R ₂ – бинарные отношения, определенные на множестве M ={1, 2, 3, 4}. Показать на примере заданных ниже отношений R ₁, R ₂Í M ´ M некоммутативность операции композиции отношений (составного отношения), т.е. R ₁ R ₂¹ R ₂ R ₁, если:

а) R ₁ – “быть меньше”, R ₂ – “быть больше, по крайней мере на 2”;

б) R ₁ – “быть больше”, R ₂ – “иметь общий делитель, отличный от 1”;

3. Пусть операция j на множестве M ={ a, b, c } определена таблицей Кэли (рис. 3.4). Подтвердить ассоциативность и коммутативность операции j.

4. Каковы свойства операций j и j¢, заданные таблицами Кэли (рис. 3.5)?