Размещено на http://www.allbest.ru

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГООБРАЗОВАНИЯ РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«БАЛТИЙСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ им. И. КАНТА»

ИНСТИТУТ ФИЗИКО-МАТЕМАТИЧЕСКИХ НАУК

И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

РЕФЕРАТ

по дисциплине Алгебраические методы в информатике

«Бинарные алгебраические операции, их свойства. Группоиды. Полугруппы.»

Руководитель: д.ф.м. наук, Кащенко Н.М.

Выполнила: студентка 1 курса, Бугаева А.Г.

Группа: магистратура, 1 курс, МО-20

Калининград, 2020



Оглавление

• Введение
• 1. Бинарные и n-местные операции
• 2. Виды бинарных операций
• 3. Нейтральные элементы
• 4. Регулярные элементы
• 5. Симметричные элементы
• 6. Подмножества, замкнутые относительно операций
• 7. Аддитивная и мультипликативная формы записи
• 8. Конгруэнция
• 9. Полугруппы и группы
• Список источников

• Введение
• В математике нередко приходится комбинировать элементы некоторого множества. Так в арифметике комбинируются числа, в векторной алгебре - векторы.
• Существенной особенностью каждого из этих примеров является правило, по которому устанавливается соответствие для элементов определённых множеств. Целью данного реферата является рассмотрение ситуации, когда любым двум элементам множества ставится в соответствие элемент того же множества по определённому правилу, такое соответствие назовём «бинарной операцией».
• Бинарные операции совершаются на множествах. В зависимости от числа операций, определенного в данном множестве, в зависимости от свойств этих операций, общая алгебра подразделяется на отдельные части. Самым простым алгебраическим образованием является множество с одной алгебраической операцией, на которую не налагается никаких условий. Называется оно группоидом. Если на алгебраическую операцию наложить некоторые условия, например, предположить, что операция коммутативна, то такие группоиды называются коммутативными или абелевыми. В свою очередь, группоиды с ассоциативной операцией называются полугруппами. Теория полугрупп является одной из наиболее содержательных областей общей алгебры. Многие бинарные операции лежат в основе битовых операций, которые применяются в языках программирования и цифровой технике. Битовые операции лежат в основе обработки цифровых сигналов: посредством них из одного или нескольких сигналов на входе получается новый сигнал, который в свою очередь может быть подан на вход одной или нескольким таким операциям.
• Именно битовые операции совместно с запоминающими элементами создают множество видов современной цифровой техники.


1. Бинарные и n-местные операции

Пусть А -- непустое множество. Тогда введем следующее определение:

Бинарной операцией на множестве А называется отображение множества АЧА в А.

Обычное сложение и умножение целых чисел суть примеры бинарных операций на множестве целых чисел. Пусть Р(М) -- множество всех подмножеств множества М; объединение ? и пересечение ? -- примеры бинарных операций на множестве Р(М).

Пусть f -- произвольная бинарная операция на множестве A. Если при отображении f элемент с соответствует паре <a, b>, то есть <<a, b>, c> ? f, то вместо записи

f(<a, b>) = с или f (a, b) = с

пишут также

а fb = с или <a, b> ? с

и элемент с называют композицией элементов а и b.

Определение. Пусть Аn есть n-я степень непустого множества А и n?1. Отображение множества Аn в А называется n-местной операцией на множестве А, а число n -- рангом операции. Нульместной операцией на множестве А называется выделение (фиксация) какого-нибудь элемента множества А, число 0 называется рангом нульместной операции.

Определение. Отображение из множества Аn в А называется частичной n -местной операцией на А, если область определения отображения не совпадает с Аn.

Операции ранга 0, 1 и 2 называют также нульарной (нульместной), унарной и бинарной соответственно. Унарную операцию называют также оператором.

Для того, чтобы разобраться рассмотрим следующие примеры.

Пример 1.

1. Отображение, ставящее в соответствие каждому множеству А из Р(М) его дополнение М \А есть унарная операция на множестве Р(М).

2. В области натуральных чисел вычитание не всегда возможно. Поэтому вычитание на множестве натуральных чисел есть частичная бинарная операция.

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

4. Операция, ставящая в соответствие каждому кортежу n натуральных чисел наибольший общий делитель этих чисел, является n -местной операцией на множестве натуральных чисел.

Для обозначения n -местной операции обычно используют ту же форму записи, что и для произвольных отображений (функций). Если f есть n -местная операция на множестве А и <<a1, …, аn>, аn+1> ? f, то пишут аn+1 = f (a1, …, аn) и говорят, что аn+1 -- значение операции f для набора аргументов a1, …, аn .

2. Виды бинарных операций

Пусть T и + -- произвольные бинарные операции на множестве А.

Определение. Бинарная операция T называется коммутативной, если для любых а, b, с из А выполняется равенство

a T (b T c) = (a T b) T c.



Определение. Бинарная операция T называется ассоциативной, если для любых элементов а, b, с из А выполняется равенство

a T (b T c) = (a T b) T c.

Определение. Бинарная операция T называется дистрибутивной относительно бинарной операции + если для любых а, b, с из А выполняются равенства

(a +b) T c = (a T c) + (bT c) и c T (a +b) = (c T a) + (cT b).

Если операция T ассоциативна, то можно опускать скобки и писать aT bT c вместо aT (bT c) или (aT b) T c.

Рассмотрим примеры.

1. Сложение и умножение рациональных чисел являются коммутативными и ассоциативными бинарными операциями.

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

3. Операции объединения и пересечения подмножеств множества М. коммутативны и ассоциативны на множестве Р (М).

4. Композиция функций есть ассоциативная операция. Композиция функций не коммутативна: в общем случае равенство f?g = g?f не выполняется.

5. На множестве Р (М) подмножеств некоторого множества операции объединения и пересечения взаимно дистрибутивны друг относительно друга.

6. Умножение целых чисел дистрибутивно относительно сложения. Однако сложение целых чисел не дистрибутивно относительно умножения, так как в общем случае равенство a+bc = (a+b)(a+c) не выполняется.



3. Нейтральные элементы

Пусть T -- бинарная операция на множестве А.

Определение. Элемент е из А называется левым нейтральным относительно операции T если для любого а из А выполняется равенство еTа=а. Элемент е из А называется правым нейтральным относительно операции T если для любого а из А имеем аTе=а.

Определение. Элемент е из А называется нейтральным относительно операции T если для любого элемента а из А верны равенства еT а = а=аT е.

Рассмотрим следующую теорему: если нейтральный элемент относительно бинарной операции T существует, то он единствен.

Доказательство. Пусть е и е' -- нейтральные элементы относительно T. Тогда

е' =е' Tе=е т. е. е' =е.

Следствие. Если нейтральный элемент относительно операции T существует, то все левые и правые нейтральные элементы относительно T с ним совпадают.

Примеры:

1. Число 0 есть нейтральный элемент относительно сложения целых чисел. Число 1 есть нейтральный элемент относительно умножения целых чисел.

2. Пустое множество есть нейтральный элемент относительно операции объединения множеств. Универсальное множество является нейтральным элементом относительно операции перечисления множеств.

3. Рассмотрим множество Ф отображений непустого множества А на его непустое собственное подмножество В и операцию -- композицию отображений. Множество Ф не имеет ни одного правого нейтрального элемента. Всякий элемент ф?Ф такой, что ф(х)=х для любого х из В, является левым нейтральным элементом относительно рассматриваемой операции.

4. Регулярные элементы

Пусть T -- бинарная операция на множестве А.

Определение. Элемент а?А называется регулярным справа относительно операции T если для любых элементов b, с множества А из aTb=aTc следует b=c. Элемент а?А называется регулярным слева относительно T, если для любых элементов b, с множества А из bTa=cTa следует b=c.

Определение. Элемент а?А называется регулярным относительно операции T если он регулярен слева и справа относительно T.

Таким образом, в случае регулярности элемента а в равенствах типа

aTb=aTc и bTa=cTa

возможно «сокращение» на а.

Примеры.

1. Всякое целое число регулярно относительно сложения.

2. Всякое целое число, отличное от нуля, регулярно относительно умножения; число нуль не регулярно относительно умножения.

Рассмотрим теорему: если элементы а и b регулярны относительно ассоциативной операции T, то их композиция aTb также является регулярным элементом относительно T.

Доказательство. Пусть а и b -- элементы, регулярные относительно T. Пусть с, d -- элементы из А, удовлетворяющие условию



(1) (aTb) Tc = (aTb) Td

Поскольку операция T ассоциативна,

aT(bTc) = aT(bTd).

В силу регулярности элемента а имеем

bTc= bTd.

Отсюда в силу регулярности элемента b следует равенство

(2) с=d.

Итак, для любых элементов с, d множества А из (1) следует (2), следовательно, элемент aTb регулярен справа. Аналогично убеждаемся, что этот элемент регулярен слева.

5. Симметричные элементы

Пусть T -- бинарная операция на множестве А, обладающая нейтральным элементом е.

Определение. Элемент u из А называется левым симметричным к элементу а?А относительно операции T, если uT a=e. Элемент v из А называется правым симметричным к а относительно операции T, если aTv=e.

Определение. Элемент а'?А не называется симметричным к элементу а?А относительно операции T если aTa'=e=a'Ta. В этом случае элемент а называется симметризуемым, а элементы a и a'-- взаимно симметричными.

Примеры.

1. Относительно сложения целых чисел симметричным к данному целому числу является то же число, взятое со знаком минус.

2. Относительно умножения рациональных чисел симметричным к ненулевому числу а является 1/а число нуль не имеет симметричного относительно умножения.

Теорема: если операция T ассоциативна и элемент а симметризуем, то существует единственный элемент, симметричный к а.

Доказательство. Пусть u, v -- элементы, симметричные к элементу а относительно T, т. е.

aTu=e=uTa , aTv=e=vT a.

Тогда в силу ассоциативности T

u=uTe=uT(aTv)=(uTa)Tv=eTv=v,

т.е. u=v.

Следствие: если элемент а имеет симметричный элемент а' относительно ассоциативной операции T, то все левые и все правые симметричные к а элементы совпадают с элементом а'.

Разберем следующую теорему.

(*) Если элементы a, b симметризуемы относительно ассоциативной операции T, то элемент аTb также симметризуем и элемент b'Ta' является симметричным к аTb.

Доказательство. Пусть а' и b' -- элементы, симметричные к a и b соответственно. В силу ассоциативности T

(аTb )T(b'Ta')=((aTb) Tb') Ta'=(aT(bTb')) Ta'=(aTe) Ta'=aTa'=e.



Также убеждаемся, что (b'Ta')T (аTb )=e. Следовательно, элемент аTb симметризуем и элемент b'Ta' является симметричным к aTb.

Рассмотрим еще одну теорему: элемент, симметризуемый относительно ассоциативной операции T, является регулярным относительно T.

Доказательство. Пусть а -- симметризуемый элемент и для элементов b, с множества А верно равенство aTb=aTc. Тогда если а -- элемент, симметричный к а, то a'T(aTb)=a'T(aTc). В силу ассоциативности операции T (a'Ta) Tb=(a'Ta) Tc. Следовательно, eTb=eTc и b=c. Аналогично убеждаемся, что для любых элементов b, с множества А из равенства bTa=сTа следует b=c. Таким образом, элемент а является регулярным относительно T.

6. Подмножества, замкнутые относительно операций

Пусть T -- бинарная операция на множестве А и В?А.

Определение. Подмножество В множества А называется замкнутым относительно операции T если для любых а, b из В элемент аT b принадлежит В.

Отметим, что пустое подмножество замкнуто относительно любой операции T.

Примеры.

1. Множество всех четных чисел замкнуто относительно сложения и умножения целых чисел.

2. Множество всех нечетных чисел замкнуто относительно умножения, но не замкнуто относительно сложения целых чисел.

3. Множество всех элементов (из А), регулярных относительно ассоциативной операции T, замкнуто относительно T.

Предложение: множество всех элементов, симметризуемых относительно ассоциативной бинарной операции T, замкнуто относительно T.

Доказательство этого предложения непосредственно вытекает из теоремы (*).

Пусть В -- непустое множество, В?А, замкнутое относительно операции T. Тогда на В можно определить бинарную операцию T следующим образом:

aT'b=aTb для любых a, b из B.

Операция T' называется ограничением операции T множеством В, а операция T -- продолжением операции T на множество А.

7. Аддитивная и мультипликативная формы записи

Наиболее часто используется аддитивная и мультипликативная формы записи бинарной операции. При аддитивной форме записи бинарную операцию T называют сложением и пишут a+b вместо aTb, называя элемент a+b суммой a и b. Элемент симметричный элементу a, обозначают (-a) и называют противоположным элементу a. Нейтральный элемент относительно сложения обозначают символом 0 и называют нулевым элементом относительно сложения. При аддитивной записи свойства ассоциативноси и коммутативности записывают в виде

а+(b+c)=(a+b)+c, a+b=b+a.

При мультипликативной форме записи бинаруную операцию называют умножением и пишут a·b (вместо aTb), называя элемент a·b произведением a и b. Элемент, симметричный a, обозначают a-1 и называют обратным элементу a. Нейтральный элемент относительно умножения обозначают через е или 1и называют единичным элементом или единицей относительно умножения. При мультипликативной записи свойства ассоциативности и коммутативности записывают в виде

a· (b·c)=(a·b)·c, a·b=b·a.

Свойство дистрибутивности умножения относительно сложения записывается в виде

(a+b)·c=a·c+b·c, c(a+b)=c·a+c·d.

8. Конгруэнция

Пусть R -- отношение эквивалентности на множестве А и T -- бинарная операция на А.

Определение. Отношение эквивалентности R называется конгруэнцией относительно операции T. если для любых элементов а, b, с, d множества А из aRc и bRd следует (aTb)R(cTd).

Теорема: пусть T -- бинарная операция на множестве А и R -- конгруэнция относительно T. Тогда равенство

(1) (a/R) T*(b/R)=(aTb)/R,

где a, b? Aопределяет бинарную операцию T на фактор-множестве A/R.

Доказательство. Бинарное отношение T состоит из пар вида

(2) <<a/R, b/R>, (aTb)/R>, где a, b? A.



Надо доказать, что T* -- функция. Пусть

<<с/R, d/R>, (cTd)/R>?T*

Надо показать, что из равенства

(3) <a/R, b/R>=<c/R, d/R>

следует

(aTb)/R=(cTd)/R.

Из (3) следуют равенства

a/R=c/R, b/R=d/R

и соотношения

(4) aRc, bRd

Так как R -- конгруэнция относительно T то из (4) следует:

(aTb)R(cTd) и (aTb)/R=(cTd)/ R

Следовательно, отношение T * является бинарной операцией на фактор-множестве A/R.

ОПРЕДЕЛЕНИЕ. Бинарная операция T * определенная на фактор-множестве A/R равенством (1), называется операцией, ассоциированной с операцией T посредством конгруэнции R.



9. Группоиды. Полугруппы

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

Полугруппа G с единицей е называется группой, если для каждого ее элемента а существует такой элемент а'?G, что

(1) а·а' = а'·а = е.

Будем с этого момента алгебраическую операцию в группе называть умножением и обозначать символом обычного умножения, ее результат будем называть произведением. Элемент а' из (1) назовем обратным к а и обозначим символом а-1. Таким образом (1) запишется так:

(1') а·а-1 = а-1·а = е.

Группа - это множество, замкнутое относительно одной ассоциативной алгебраической операции, содержащее единичный элемент и такой, что для каждого ее элемента а существует обратный элемент, который удовлетворяет равенству (1').

Отметим некоторые простейшие свойства групп:

1. Всякий элемент группы имеет только один обратный.



2. (а-1)-1 = а.

3. (ab)-1 = b-1a-1.

4. ( а1а2 … аn )-1 = аn-1аn-1-1… а2-1а1-1.

Определение. Алгебру A?<A; ·> называют полугруппой, если операция · на А бинарна и ассоциативна. Другими словами, если:

1) ? (a, b ? A) ?! (c?A) ab=c;

2) ? (a, b ? A) (a·b) ·c=a·(b·c).

Полугруппу A=<A; ·> называют коммутативной, если операция · коммутативна, и конечной, если множество А конечно. Полугруппу <A; ·> называют полугруппой с сокращением, если

? (a, x, y ? A)(ax =ay ? x=y) ? (xy=ya ? x= y).

Таким образом, полугруппа <A; +> -- полугруппа с сокращением, если

? (a, x, y ? A)(a+x =a+y ? x=y) ? (x+a = y+a ? x= y).

Теорема: в любой полугруппе A?<A; +> с сокращением имеется не более чем один элемент и такой, что

и + и = и .

Доказательство. Предположим, что для элементов и и ц полугруппы А

и + и = и ? ц = ц + ц



Тогда

(и + и)+ ц = и +( ц + ц).

Отсюда следует, что

и = ц.

Определение. Полугруппу A?<A; ·> называют группой, если

? (a, b ? A) ? (x, y ? A)ax=b?ya=b.

Определения 1 и 2. Пусть A?<A; ·> -- полугруппа и А' -- подмножество А; тогда систему A'?<A'; ·> называют подполугруппой (соответственно подгруппой) полугруппы А, если система А' -- полугруппа (соответственно группа). Другими словами, если подмножество А' множества А образует полугруппу (группу) относительно той же операции, которая рассматривается в А, то систему А' называют подполугруппой (подгруппой) полугруппы А.



Заключение

В данном реферате я рассмотрела бинарные алгебраические операции и их основные свойства, которыми являются: коммутативная операция T, при условии, что для любых а, b, с из А выполняется равенство

a T (b T c) = (a T b) T c,

ассоциативная операция, где для любых элементов а, b, с из А выполняется равенство

a T (b T c) = (a T b) Tc,

а также операцию дистрибутивности, где для любых а, b, с из А выполняются равенства (a +b)

T c = (a T c) + (bT c) и c T (a +b) = (c T a) + (cT b).

Помимо бинарных алгебраических операций были рассмотренны понятия группы и полугруппы. Группа -- это множество X с бинарной операцией ·, для которой выполнены свойства ассоциативности, наличия нейтрального элемента e и для каждого элемента x существует обратный x?1.

бинарный сложение мультипликативный алгебраический



Список источников

1. Л.Я. Куликов - «Алгебра и теория чисел», Москва Высшая школа 1979

2. Ю. И. Журавлёва, Ю. А. Флёрова, М. Н. Вялый - «Дискретный анализ. Основы высшей алгебры», МЗ Пресс Москва, 2007

3. Ю. И. Журавлёв, Ю. А. Флёров, М. Н. - Вялый Учебные материалы к курсу «Основы высшей алгебры и теории кодирования» Вариант от 28 апреля, 2019

4. Ван дер Варден Б. - «Л. Алгебра», Наука, 1976

5. Ленг С. - «Алгебра», Мир, 1968

6. Мельникова Н.В., Мельников Ю.Б. Лекции по алгебре. Учебное пособие по курсу "Математика", Изд-е третье, исправленное и дополненное/ Екатеринбург: "Уральское издательство", 2003

Размещено на Allbest.ru

...