Дискретно-непрерывная математика (стр. 19 )

Обозначим множества операндов соответственно через А и В (a А и

b В), а множества результатов операции — через С (с С). Так как множество всех пар (а, b) есть прямое произведение А×В, то операцию определяют как отображение множества А×В в С, т. е. А×В→С, и часто называют законом композиции,

2. Таблица Кели. Любой закон композиции А×В→С над конечными множествами можно задавать прямоугольной матрицей (таблицей Кели). Строки таблицы отвечают элементам множества А, столбцы — элементам множества В. На пересечении строки и столбца, соответствующих паре (а, b), располагается элемент с=а b.

Хорошо известными примерами являются таблицы сложения и умножение одноразрядных чисел. В общем случае таблица, которая определяет бинарную операцию, имеет вид:

Законы композиции на множестве. Множества А, В, С, которые принимают участие в операции А×В →С, не обязательно должны быть различными. Если В=С=S, то говорят, что закон композиции определен на множестве S.

Различают внутренний закон композиции S × S → S и внешний закон композиции Ω × S → S, где Ω и S — различные множества. В случае внутреннего закона говорят, что множество образует групоид относительно операции ┬. В случае внешнего закона композиции элементы αΩ называют операторами, а Ω — множеством операторов на множестве S.

Примерами внутреннего закона композиции являются сложение а+b =с и умножение ab=с на множестве действительных чисел, а также геометрическое суммирование векторов на плоскости. Умножение вектора на скаляр может быть примером внешнего закона композиции на множестве векторов, причем операторами являются скаляры — элементы множества действительных чисел.

Пусть S — множество диференцируемых функций fi(x1, х2, .... хп) и Ω - множество операторов дифференцирования д/дхj (j = 1, 2, ..., п). Тогда паре (д/дхj, fi) можно поставить в соответствие частную производную dfi/dxj, т. е. имеем внешний закон композиции на множестве диференцируемых функций.

Ниже речь будет идти о внутренних законах композиции.

Матрица и граф группоида. Конечный группоид S относительно закона ┬ определяется квадратной матрицей п-го порядка (п — число элементов группоида), например,

Построение графа группоида основано на представлении бинарного соотношения а b=c (рис. 1.31 а), где дуги графа изображают элементы a, b, c S, причем операнды образуют некоторый путь, а дуга результата операции замыкает этот путь. Если a b=а, то b изображается петлей в конечной вершине дуги а. При построении графа сначала наносят дуги для всех элементов группоида как выходяшие из одной вершины, а затем последовательно изображают все бинарные соотношения.

На рис. 1.31, бы изображен граф группоида, заданного приведенной выше матрицей.

Рис. 1.31. Граф операции на множестве:

а - операнды a, b и результат операции с; б — граф группоида

Дуги a, b, c, d, выходящие из одной вершины, соответствуют элементам группоида. Так как a a = b, a b=с, a c = a и a d=b, то из конца дуги а проводят дуги а, b, с, d соответственно к конечным вершинам дуг b, с a, b. Две параллельные дуги a и d, направленные к конечной вершине дуги b, условно изображают одной дугой a, d. Дуга с начинается и заканчивается в конечной вершине дуги а, т. е. образует петлю. Аналогично изображают на графе и остальные соотношения, определяемые матрицей группоида.

Свойства внутреннего закона композиции. Операции на множестве S могут обладать некоторыми общими свойствами, которые обычно выражаются соотношениями между элементами с S:

коммутативность а ┬ b =b ┬ а;

ассоциативность а ┬ (b ┬ с)=(а ┬ b) ┬ с;

дистрибутивность слева (а ┬ b) ┴ с=(а┴с) ┬ (b ┴ с)

и справа с┴(a┬b)=(c┴a) ┬(c┴b).

На множестве действительных чисел сложение и умножение ассоциативны и коммутативны. Умножение дистрибутивно (слева и справа) относительно сложения, но сложение не дистрибутивно относительно умножения, так как вообще а +bс≠(а + b)(а+с).

Возведение в степень не ассоциативно, не коммутативно аb≠bа, но дистрибутивно справа относительно умножения, так как (ab)c=acbc.

Пересечение и объединение множеств взаимно дистрибутивны относительно друг друга. Если в множестве F S композиция любых двух элементов из F также принадлежит F, то F называется замкнутым относительно рассматриваемого закона композиции (подмножество четных чисел является замкнутым относительно сложения и умножения).

Регулярный, нейтральный и симметричный элементы. Закон композиции наделяет элементы множества некоторыми общими свойствами. При различных законах одни и те же элементы могут обладать различными свойствами. Поэтому имеет смысл говорить о свойствах элементов множества S относительно заданного на нем закона композиции ┬.

Элемент а называется регулярным, если из соотношений

а┬х=а┬у и х┬а=у следует х = у (сокращение на регулярный элемент). Всякое число регулярно относительно сложения, а для умножения ь регулярно всякое число, кроме нуля (0х = 0у не влечет х= у).

Нейтральным элементом е S называют такой элемент, что для всех элементов х из S справедливо е┬х=х┬е= х (если нейтральный элемент существует, то он единственен и регулярный). Среди чисел нуль — нейтральный элемент относительно сложения, а единица — относительно умножения. Пустое множество является нейтральным элементом относительно объединения, а основное множество (универсум) — относительно пересечения. На множестве всех квадратных матриц п-го порядка с числовыми элементами нулевая и единичная матрицы служат соответственно нейтральными элементами относительно сложения и умножения.

Если множество содержит нейтральный элемент е относительно закона композиции ┬, то элемент b называется симметричным (обратным, противоположным) элементу а, если а┬b=b┬а=е; при этом а называют симметризуемым элементом и b обозначается через , т. е. b=. Относительно ассоциативного закона ┬ элемент , симметричный элементу а (если он существует), единственен и регулярен.

При сложении симметричным некоторому числу х будет -х, а при умножении х-1. Например, симметричными элементами на множестве квадратных матриц п-го порядка относительно умножения есть взаимо-обратные матрицы. Множество всех собственных подмножеств относительно объединения или пересечение не содержит симметричных элементов. Множество, в котором всякий элемент имеет симметричный, называется симетризуемоюым.

Аддитивнные и мультипликативные обозначения. Свойства законов композиции можно представить в двух формах. В аддитивных обозначениях операция ┬ записывается символом сложения (+), а в мультипликативных — символом умножения (• ). Если множество наделено двумя законами композиции, то чаще всего первый из них ┬ считается аддитивным, а второй ┴ — мультипликативным. В аддитивной записи нейтральный элемент обозначается через 0 и называется нулем, а симметричный элементу а — через (-а). В мультипликативной записи нейтральный элемент обозначается через 1 и называется единицей, а симметричный элементу а — через а-1.

Если закон композиции ассоциативный и коммутативный, а элементы множества х1, х2, ..., хп S отмечены операторным индексом i, то в аддитивной записи