XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 18
Текст из файла (страница 18)
Проблема работы с такими объектами возникла в связи с развитием современных информационных технологий и переходом от собственно вычислений (т.е. операций над числами) к обработке сложных структур данных. Так, проблемы программирования и машинного перевода привели к задачам работы с языковыми структурами, проблемы автоматизации проектирования — к задачам обработки графических объектов. Современная дискретная математика проникнута алгебраическим духом, поскольку оказалось, что именно на алгебраической базе наиболее удобно разрабатывать общие подходы к работе с объектами различной природы.
2.1. Операции. Понятие алгебраической структуры Множество векторов в пространстве с операцией сложения векторов, операцией векторного умножения, множество квадратных матриц с операциями сложения или умножения, множество функций с операцией сложения — вот примеры некото- э.ь Операции. Понятие атгевравческой структуры 113 рых множеств с операциями, рассматривающнхсв в различных разделах математики. Выясним, что общего есть в свойствах операций на этих множествах и в чем их различие. Определение 2.1. Пусть А — произвольное непустое множество и и — натуральное число. Любое отпображение 4в +А называют и-арной (или п-местпной) операцией на множе- стве А.
Таким образом, согласно приведенному определению, и-ариан операция ы каждому кортпежу (ам ..., а„) Е А" однозначно сопоставляет элемент 6 Е А. Компонентпы корптежа называют при этом арерментпами операции ы, а Ь вЂ” реэрльтпатпом применения операции ы к аргументам ам ..., а„. Длл и-арной операции используют обозначение 6=ы(ам ..., а„) 6 = ат...
а„ьт. Обычно, если и = 2, пишут а1 ы аз. При и = 1 и и = 2 говорят соответственно об унарной операции и бинарной операции. Специально вводят понятие нульарной операции (т.е. длл и = О). Под нульарной операцией на множестве А понимают произвольный фиксированный элемент множества А. Нульарные операции позволяют фиксировать элементы множества А, обладающие некоторыми специальными свойствами. Примером выполнения нульарной операции является, например, фиксирование нуля в множестве целых чисел с операцией сложения.
Примером унарной операции служит дополнение заданного множестпва до универсального мкожвсшвв. Наиболее важными в алгебре и, следовательно, наиболее исследованными являются бинарные операции. Примерами 114 2. АЛГЕБРЫ: ГРУППЫ И КОЛЬЦА таких операций могут служить сложение и умножение чисел, сложение и умножение матриц, сложение векторов линейного пространства. Рассмотрим бинарную операцию на множестве А, обозначив ее звездочкой (я). Эту операцию называют: 1) ассоциатпивной, если (хау) *я = ха(ух я) для любых х, у,яЕА; 2) номмутпатпив ной если х * у = у я х для любых х, у Е А; 3) идемпотпентпной если х * х = х для любого х Е А. Ассоциативность операции * позволяет для любых элементов ат, аз, ..., а„ Е А однозначно трактовать результат выражения ат * аз я...
я а„, так как отказ* ° ..*аа = ат*(а2 я ° .. яав) = = (ат * аз) * (аз я ... * а„) = (ат я аз я ... я а„ т) я а„. Операция сложения, заданная на множестве натуральных чисел, являетсл ассоциативной и коммутативной. Операция умножения матриц ассоциативна, но не коммутативна. Идемпотентными являются операции объединения и пересечения множеств. Элемент 0 множества А называют левым (правым) нулем относительно данной операции х, если О *х = 0 (х я 0 = О) для любого х Е А. Если 0' — левый нуль, а 0" — правый нуль, то они совпадают. Действительно, если 0 и 0~~ существуют, то они совпадают, так как 0 = 0 *ОЯ = 0~~, и в этом случае говорят просто о нуле отпноситпально операции.
Из приведенных равенств следует, что нуль единственный и для него одновременно выполнены оба равенства 0 я х = 0 и х * 0 = О. Пример 2.1. а. На множестве целых чисел нулем относительно операции умножения будет число О. 2.1. Оиераиии. Поиктие акгебраической структуры 115 /а 01 б. На множестве квадратных матриц вида ~ ), где элементы а и Ь вЂ” действительные числа, любая матрица вида < О О~ ~ будет правым нулем относительно операции умножения,поскольку а О О О О О Однако левого нуля в этом множестве нет, так как иначе он совпадал бы с правым нулем и был бы единственным. Но правых нулей имеется больше одного. Элемент 1 множества А называют левым (правым) нейтнральным элеменпаом относительно операции х, если 1 к х = = х (х*1 = х) для любого элемента х Е А. Для левого 1' и правого 1и нейтральных элементов, если они оба существуют, выполнены равенства 1' = 1' * 1и = 1", согласно которым они совпадают. В этом случае элемент 1, который является и левым нейтральным, и правым нейтральным, единственный, и его называют просто небтнральным элементом.
Пример 2.2. Нейтральным элементом относительно операции умножения на множестве натуральных чисел является число 1. На множестве целых чисел нейтральным элементом относительно операции сложения будет число О. /а О~ На множестве квадратных матриц вида ~ ~, где элемен- П Оъ ты а и Ь вЂ” действительные числа, любая матрица вида ~ будет правым нейтральным элементом по операции умножения, ибо Ь О И О Ь О Поскольку правых нейтральных элементов несколько, то левого нейтрального элемента по этой операции нет, так как иначе 116 2, АЛГЕБРЫ; ГРУППЫ И КОЛЬЦА существовал бы единственный нейтральный элемент (левый и правый). 1(~ Следует заметить, что не для всякой бинарной операции нули и нейтральные элементы (левые и правые, в частности), существуют.
Рассмотрим некоторые примеры бинарных операций на множествах. Пример 2.3. а. Пусть У вЂ” универсальное множестпво. Теоретико-множественные операции Ц П на множестве 2т являютсл идемпотентными, ассоциативными и коммутативными, причем иустпое множестпво является нулем относительно пересечение и нейтральным элементом относительно объединение (И П А = А и И = а, а 0 А = А 0 И = А), тогда как униерсальное множество есть нуль относительно объединения и нейтральный элемент относительно пересечения (У О А = А й У = =А, ст ОА=АОУ=У).
Операция 1 (разностеь множестве) не явллетсл ассоциативной, так как А'1(В1С) ~ (А1В) 1С. б. На множестве всех бинарных оетношениб на множестве А операция композиции отеношенит1 является ассоциативной, но не коммутативной, а диагональ множества А будет нейтральным элементом относительно этой операции (см. 1.4).
в. Пусть Х вЂ” произвольное множество, содержащее не менее двух элементов. На множестве всех отображений из Х в Х с операцией композиции отображений постоянное отображение ~р„, переводлщее любой элемент х Е Х в фиксированный элемент а е Х, будет правым нулем, но не будет нулем относительно композиции отображений. Действительно, длл любого отображения у: Х -+ Х и любого х Е Х имеем ~офе(х) = фа(у(х)) =а = уте(х) те. у'фь = уте~ что и означает, что ~де — пРавый нУль относительно опеРации композиции на множестве отображений из Х в Х. Однако длл любого х Е Х тра о,т(х) = Д~Ре(х)) = У(а), т.е. ~Ре о,т = <Ртт„1— отображение, которое любой элемент Х переводит в элемент З.Ь Опепаяпп.
Палатке аагеерапческой структуры 117 Да). Поскольку у(а) в общем случае не равно а, то уа е у ф <р . Значит, щ, не является левым нулем относительно операции композиции. ф Рассмотренные вьппе примеры множеств с операциями приводят к следующим определениям. Определение 2.2. Алгебра (униеерсальнал алгебра, й-алгебра) считается заданной, если заданы некоторое множество А, называемое носитпелеае данной алгебры, и некоторое множество операций й на А, называемое снгнатпуроб данной алгебры. Алгебру, носитель которой есть конечное множество, называют конечной алгеброй. Поскольку алгебра задается ее носителем и сигнатурой, мы будем в записи обозначать алгебру как упорядоченную пару множеств А = (А, й), полагая, что первая компонента этой пары есть носитель, а вторая — сигнатура.
Подчеркнем,что алгебра — это не просто носитель и не просто сигнатура, а „синтез" этих двух объектов. Замечание 2.1. Операции, включенные в сигнатуру, заданы как некоторые специальные отображения. Однако при этом не оговариваются свойства, которыми обладают операции на носителе. Например, они могут быть ассоциативными, коммутативными и т.д. При задании алгебр свойства операций обычно указывают дополнительно. Если существует нейтральный элемент относительно операции, то его можно задать как нульарную операцию на носителе и включить в сигнатуру, а можно не включать и описать как свойство соответствующей операции. Таким образом, одну и ту же алгебру можно задавать по-разному. Ниже приведены примеры различных описаний конкретных алгебр. В ряде случаев указание носителя алгебры предполагает и задание определенной сигнатуры. В этом случае для упрощения 118 2.
АЛГЕБРЫ: ГРУППЫ И КОЛЬЦА пишут не А = (А, й), а просто А = А и говорят „элемент алгебры А", имея в виду элемент носителя этой алгебры. Пример 2.4. а. Рассмотрим алгебру А1 =(2, (0,П,~,Ь,,И,М~). Ее носителем является множество всех подмножеств произвольно фиксированного множества М, а сигнатура состоит иэ следующих операций над множествами: объединения, пересечения, разности, симметарической разностии, дополнения,пустого множества и множества М (последние два элемента сигнатуры определяют нульарные операции). б. Для любого множества М можно определить алгебру Аг = (2мям (01, -т1) носителем которой является множество всех подмножеств множества упорядоченных пар на М, т.е.
множество всех бинарнмя отпношений на множестве М, а сигнатура состоит иэ операций объединения, комноэииии бинарнмя отношений и взятия обраптного отаношенил. в. На множестве К действительных чисел можно, например, определить такую алгебру: Аз = (К, (+,,О, Ц), сигнатура которой состоит из операций сложения, умножения, а также двух нульарных операций, обозначающих два особых числа О и 1. Обратим внимание на то, что числа О и 1 в данном случае являются соответственно нулем и нейтральным элементом относительно умножения, а число О также играет роль нейтрального элемента относительно сложения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
