Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система icon

Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система



НазваниеЛекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система
Дата17.10.2016
Размер
ТипЛекция


Я не хочу на этой стадии исследовать логическое оправдание этой формы аргументации; пока я рассматриваю ее как практику, которую мы можем наблюдать в поведении людей и животных.

Бертран Рассел

Лекция № 5

(лек. 2 час + прак. занят 2 час + лаб. 2 час. + самос. 2 час)


АЛГЕБРАИЧЕСКАЯ СИСТЕМА


Алгебраическая система

Алгебраической системой A называется совокупность ‹M,O,R›, первая составляющая которой M есть непустое множество, вторая компонента O – множество алгебраической операций, третья компонента R – множество отношений на множестве M.

Пояснение.

1. Множество M алгебраической системы A называют несущим, или основным множеством.

2. Совокупность алгебраических операций и отношений алгебраической системы называют сигнатурой Σ. В этом случае алгебраическая система записывается парой ‹M, Σ.› .

3. Алгебраическая система ‹M,O› называется универсальной алгеброй (или просто алгеброй), если на основном множестве M множество отношений R пусто (т.е. R = ).

4. Алгебраическая система A = ‹M,R› называется реляционной системой (или моделью), если на основном множестве M заданы только отношения R (т.е. в этом случае пусто множество операций O, что означает O = ).

Пример 1. Алгебраической системой является аксиоматическая теория множеств ‹M, , -, › (где O = {, -} – множество из операций объединения и операций дополнения -, а R = {} – множество, состоящее из отношения включения .

Пример 2. Алгебра Кантора (алгебра множеств) - ‹B(M), , , несущим множеством является булеан B(A) (т.е. множество всех подмножеств данного множества U), а множеством операций O = {, , -} -, булевы операции объединения , пересечения и дополнения -.

Пример 3. Метрическое пространство ‹M,R›, где R – метрика, является реляционной системой. Пояснение. Пространство – множество объектов (точек) с введенным отношением между точками и операциями над элементами множества. Метрическое пространство – это множество точек Х с расстоянием между ними d≥0, удовлетворяющее трем аксиомам:

1. Аксиома идентичности. d=0 тогда и только тогда , когда x=y.

2. Аксиома симметрии. d(х,y)=d(y,x).

3. Аксиома треугольника. d(х,y)=d(y,z)+d(z,y), где

Расстояние d(х,y) называется метрикой, а пара ‹X,d› - метрическим пространством.

Замыкание и подалгебры

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



Если X замкнуто относительно всех , то называется подалгеброй алгебры , где , k = ni/

Пример 1. Алгебра - поле действительных чисел.

Тип – (2,2).

Все конечные подмножества, кроме {0}, не замкнуты относительно сложения и все конечные подмножества, кроме {0} и {0,1}, не замкнуты относительно умножение.

Кольцо целых чисел образует подалгебру рациональных и, соответственно, вещественных чисел.

Пример 2. Алгебра - алгебра подмножеств над множеством M.

Тип – (2,2,1).

При этом - подалгебра.

Пример 3. Алгебра гладких функций , где - операция дифференцирования.

Множество полиномов одной переменной x образует подалгебру которая обозначается R[x].

Тип – (1).


Теорема. Непустое пересечение подалгебр образует подалгебру.

Доказательство. Пусть - подалгебра алгебры . Тогда




^ Замыканием множества относительно сигнатуры Σ (обозначается [X]Σ) называется множество всех элементов (включая сами элементы X), которые можно получить из X, применяя операции из Σ.


Морфизмы

Из вышеприведенных определений следует, что каждая алгебраическая структура выделяет класс отображений между объектами с данной структурой, согласованных с операциями этой структуры.

Такие отображения называются морфизмами. Изоморфизм множеств был рассмотрен выше.

Гомоморфизмы. Алгебры с различными типами имеют различное строение. Пусть A = и B = - две алгебры одинакового типа. Если существует f: A → B, такая что

,

то говорят, что f - гомоморфизм из A в B (гомоморфизм «уважает» операции)

Пусть A = , B = , тип = (1) и f: A → B. Действие этих функций изобразим с помощью следующей диаграммы:

φ

A → A

f↓ ↓f

B → B

Пусть f – гомоморфизм. Если взять конкретное и двигаться по двум различным путям на диаграмме, то получится один и тот же элемент (так как f(φ(a)) = ψ(f(a))), т.е. диаграмма коммутативна. Коммутативной диаграмма называется потому, что условие гомоморфизма можно переписать так



где - суперпозиция функций.


Рассмотрим морфизмы с другой стороны.

Пусть даны алгебраические системы A = , B = . Отображение φ: A → B называется гомоморфизмом системы A в систему B, если выполняются следующие условия:

1) для любого функционального символа f(n), соответствующих функций fА и fВ в системах A и B и любых a1, a2, …, выполняется



2) для любого предикатного символа соответствующих предикатов PА и PВ в системах A и B и любых a1, a2, …,an выполняется



Если φ: A → B – гомоморфизм , то будем его обозначать φ: AB

При гомоморфизме сохраняются действий операций и отношения. Это позволяет переносить изучение свойств с одной системы на другую.

Пример. Пусть A = , B = , где N10 +{0,1,2,3,4,5,6,7,8,9}, а +10 - сложение по модулю 10. Тогда f:=a mod 10 - гомоморфизм из A в B.

Гомоморфизм, обладающий дополнительными свойствами, имеют специальные названия.

Гомоморфизм, который является инъекцией, называется мономорфизмом.

Гомоморфизм, который является сюръекцией, называется эпиморфизмом.

Гомоморфизм, который является биекцией, называется изоморфизмом.

Если A = B, то гомоморфизм называется эндоморфизмом, а изоморфизм называется автоморфизмом.


^ ФУНДАМЕНТАЛЬНЫЕ АЛГЕБРЫ

На множестве М может быть задано много различных операций. Чтобы выделить одну из них используют обычно скобки <М, *> и говорят, что операция * определяет на М алгебраическую структуру. Так, например, на множестве целых чисел помимо хорошо известных операций сложения и умножения целых чисел n и m можно ввести много других, например, операцию суть которой состоит в следующем m○n = n m - 3n и т.п.

В зависимости от операции получаем различные алгебраические структуры: <М, *>; <М, +>; <М, х>; <М, ○>. Это бинарные операции, но операции могут быть в общем случае n–арными: при n = 1 – унарные, при n = 2 – бинарные, при n = 3 – тернарные и т.д. и их комбинации. Такие алгебраические структуры составляют специальную теорию универсальных алгебр. Изучение в общем виде алгебр для нас не представляет практического интереса, поэтому рассмотрим наиболее часто используемые алгебры, т.е. фундаментальные алгебры.

Подведем итог сказанному. Алгебра A = – это совокупность A носителя и сигнатуры Σ. Носитель A – это множество, которое может состоять из нескольких множеств, тогда алгебра будет называться многоосновной. Сигнатура Σ также является множеством, элементами которого являются множества {F1,i1 , F2,i2 , …,Fn,in,}, где первый индекс указывает местность операции, а второй индекс указывает порядковый номер, например, операции F2,i2бинарные операции, номер данной операции i2, где i2 принимает значения 1, 2, …, n2.


Алгебры с унарными операциями

Самые простые алгебры A = – это алгебры с унарными операциями F1,i1, где i1 принимает значения 1, 2, …, n1. Эти операции определяют свойства элементов и самой простой алгеброй будет алгебра, когда i1 = 1, т.е. A = .


Алгебры с бинарными операциями

Бинарные алгебры имеют вид A = – это алгебры с бинарными операциями F2,i2, где i2 принимает значения 1, 2, …, n2. Из этих алгебр самой простой будут алгебры с одной бинарной операцией, т.е. A = , где A = MM, а F2,1 =*, т.е. *: MMM. Рассмотрим более подробно эти алгебры.


Алгебры с одной бинарной операцией

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

Бинарная операция * на множестве М называется ассоциативной, если a*(b*c) = (a*b)*c для всех a, b, c принадлежащих множеству М.

Бинарная операция * на множестве М называется коммутативной, если a*b = b*a для всех a, b принадлежащих множеству М. Требования коммутативности и ассоциативности независимы, т. из ассоциативности не следует коммутативность и наоборот.

^ Пример.

1. На множестве целых чисел n и m задана алгебраическая структура <М, *> такая, что n*m = -m – n = . Эта алгебраическая структура коммутативна, что очевидно n*m = -n – m = -m – n = m* n, но не ассоциативна:

m*(n*p) = -m - (n*p) = -m - (-n - p) = -m + n + p;

(m*n)*p = -(m*n) – p = -(- m - n) – p = m + n – p

Таким образом m*(n*p) ≠ (m*n)*p, т.е. эта алгебраическая структура не ассоциативна.

2. Рассмотрим множество Мn(R) всех квадратных матриц порядка n>1 на котором задана операция умножения Ч в обычном смысле. Так построенная алгебраическая структура ассоциативна, но не коммутативна. (докажите)?

Названия свойств операций будут присваиваться и соответствующим алгебраическим структурам <М, *>, т.е. коммутативная или ассоциативная алгебраическая система или то и другое одновременно.

Рассмотрим еще один элемент e множества М, который может быть только один, если он существует на данной алгебраической структуре. Этот элемент e называется нейтральным или единичным. Он обладает свойствами: во-первых, e М, а во-вторых, для любого элемента m М выполняется равенство – 'e*М = М*e' = М, где 'e, e' - соответственно левый и правый нейтральный элемент.


Полугруппа

Множество М с заданной на нем бинарной ассоциативной операцией f2 называется полугруппой <М, f2>. Пусть S полугруппа на алгебраической структуре с f2 ≡ *. Подмножество S' S называется подполугруппой, если а*b S' для всех а, b S', тогда подмножество S' замкнуто относительно операции *. Для полугруппы для любых a, b, c принадлежащих М выполняется для бинарной операции условие

a * (b * c) = (a * b) * c


Пример 1. Множество непустых слов A+ в алфавите A образует полугруппу относительно бинарной операции конкатенации.

Пример 2. Любое множество функций, замкнутое относительно суперпозиции, образует полугруппу.


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

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

^ Теорема (Маркова-Поста). Существует полугруппа, в которой проблема распознования равенства слов алгоритмически неразрешима.


Моноид

Полугруппа с единичным (нейтральным элементом) принято называть моноидом или просто полугруппой с единицей. Мощность моноида, как множества обозначается |М| или Card М.

Моноид – это полугруппа с единицей.

Теорема. Единица моноида единственна.

Доказательство. Пусть . Тогда

^ Теорема. Всякий моноид над М изоморфен некоторому моноиду преобразований над М.

Доказательство. Пусть М = <М, *> - моноид над М = {e,a,b,c, ….}. Построим . Тогда


Группоид

Алгебра вида <М, f2> называется группоидом.

Если f2 — операция типа умножения (), то группоид называют мультипликативным, если f2 - операция типа сложения (+), то аддитивным.

Пусть А = <М, f2) — группоид; обозначим операцию f2 как . Тогда элемент называется правым нейтральным элементом группоида А, если для всякого выполняется равенство те = т ; элемент группоида А = <М,> называется левым нейтральным элементом, если для всех выполняется равенство ет = т. В этих определениях использовались выражения «все элементы», «всякий элемент». В дальнейшем для краткости вместо слов «все» или «всякий» будем использовать символ (перевернутая буква А — первая буква английского слова All — все). Если элемент е, , группоида А = <М, > является одновременно левым и правым нейтральным элементом, то его называют двусторонним нейтральным элементом или просто нейтральным элементом.

Никакой группоид не может иметь более одного нейтрального элемента. Действительно, если

те = ет = т и те'=е'т=т

справедливо для всех , то

е' = е'е = е.

Если группоид <М,> мультипликативный, то нейтральный элемент называется единицей и обозначается 1; если аддитивный, то нейтральный элемент называется нулем и обозначается 0.

Группоид А = <М,> называется идемпотентным, если его сигнатура удовлетворяет закону идемпотентности

.

Группоид <М,>, сигнатура которого удовлетворяет закону коммутативности

.

называется коммутативным или абелевым.

Группоид <М,>, в котором выполняется закон ассоциативности называется ассоциативным или полугруппой.


Группа

Полугруппа <М,> в которой выполнимы обратные операции: для любых каждое из уравнений , обладает единственным решением, называется группой.

Пример.

Рассмотрим понятие группы на примере группы подстановок, содержащей шесть элементов. Группу подстановок исследовал выдающийся французский математик Галуа в связи с решением уравнений в радикалах.

Подстановкой n-й степени называется взаимно однозначное отображение множества из п элементов на себя.

Рассмотрим три элемента: х1, х2, х3. Существует шесть перестановок из трех элементов (3! = 6): х1х2х3, х2х3х1, х1х2х3, х3х1х2, х2х1х3, х3х2х1. Запишем две перестановки из трех элементов друг под другом:



Эта запись означает, что х1 переходит в х2, х2 - в х3, х3в х1.

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





Введем операцию умножения над подстановками.

Произведением подстановок называется подстановка, получаемая в результате последовательного выполнения сначала первой, а затем второй из перемноженных подстановок. Например,



Выражение бв, б,в = а, b, с, d, е, f определяет табл. 1.1.

Таблица 1.1

б

в

а

b

с

d

е

f

a

а

b

с

d

е

f

b

b

а

d

с

f

е

c

с

е

а

f

b

d

d

d

f

b

е

а

с

е

е

с

f

а

d

b

f

f

d

е

b

с

а

В рассматриваемой алгебре <М, > выполняется закон ассоциативности, но не выполняется закон коммутативности.


^ Абелева группа

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


^ Алгебра с двумя операциями

Рассмотрим алгебраические структуры с двумя операциями. Эти структуры нашли широкое применение при решении практических задач.


^ Кольца

Алгебра <М, , +>, которая по умножению является мультипликативным группоидом, по сложению — абелевой группой, причем умножение связано со сложением законами дистрибутивности

а(b + с) = аb + aс,

(b + с) а = bа + са,

называется кольцом.


Тело

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


^ Поля

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


Отношения

Фундаментальным понятием дискретной математики является понятие отношения, которое используют для обозначения связи между объектами или понятиями.

^ Квадратом множества М называется декартово произведение двух равных между собой множеств: ММ = М2. Бинарным отношением Т в множестве М называется подмножество его квадрата: . Элементы тi, и тj, находятся в отношении T, если .


Граф

Совокупность множества М с заданным в нем бинарным отношением называется графом G:

,

где М - носитель графа (множество вершин); Т - сигнатура графа (множество дуг).

Рассмотрим задание бинарного отношения с помощью матрицы смежности и фактор-множества.


^ Матрица смежности

При матричном задании используют двумерную таблицу — матрицу смежности, каждой строке (столбцу) которой взаимно однозначно сопоставляют элемент множества М. Тогда каждая клетка (i, j) взаимно однозначно соответствует элементам множества М2. Клетку (i, j), которая соответствует элементу, принадлежащему , как-то отличают, например зачерняют или помещают в нее единицу; остальные клетки оставляют незачерненными или записывают в них нули.

^ Пример.

Рассмотрим предложенную фон Нейманом блок-схему ЭВМ, которая состоит из множества устройств


Фактор-множества

Если отношение R обладает свойствами: рефлексивное симметричное транзитивное, т.е. является отношением эквивалентности (~ или ≡ или Е) на множестве M, то множество классов эквивалентности называется фактор множеством множества M относительно эквивалентности R и обозначается M/R



Здесь есть подмножество элементов множества M эквивалентных x , называемых классом эквивалентности.

Из определения фактормножества следует, что оно является подмножеством булеана: .

Функция называется отождествлением и определяется следующим образом:



Примеры на эквивалентность

1. R - отношение равенства (=).

Отношение равенства x = y является эквивалентностью на любом множестве A, так как оно

рефлексивно (x = x),

симметрично (x = y y = x),

транзитивно (x = y & y = z x = z).

2. R - отношение подобия треугольников.

Отношение подобия на множестве треугольников является отношением эквивалентности.

рефлексивно (x = x),

симметрично (x = y y = x),

транзитивно (x = y & y = z x = z).

3. R - отношение равномощности.

На любом множестве B(U) отношение равномощности |A| = |B| является отношением эквивалентности. Для любых множеств A, B, C выполняются следующие свойства:

рефлексивно: (A ~ A поскольку idA : A ↔ A),

симметрично: если A ~ B, то B ~ A (так как из f: A ↔ B следует f-1: B ↔ A),

транзитивно: если A ~ B и B ~ C, то A ~ C (так как из f: A ↔ B, g: B ↔ C следует f◦g: A ↔ C).

4. R - отношение принадлежности.

Отношение принадлежности к одной студенческой группе на множестве студентов МГСУ является отношением эквивалентности.

рефлексивно (x = x),

симметрично (x = y y = x),

транзитивно (x = y & y = z x = z).

5. R - отношение вычисление одной и той же функции.

Пусть M – множество программ, вычисляющих одну и ту же функцию. Отношение E = {(x,y)| программы x и y вычисляют одну и ту же функцию} на множестве M является отношением эквивалентности.

рефлексивно (x = x),

симметрично (x = y y = x),

транзитивно (x = y & y = z x = z).



11.02.2014




Похожие:

Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconКонспект урока Тема урока: «Алгебраическая сумма и правила её вычисления»
Цель: Обобщение и систематизация знаний учащихся по теме Алгебраическая сумма и
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconЛекция Собственность и экономическая система государства (2 ч.)
Смысл этого понятия довольно точно передавал австрийский экономист Л. Мизес (1881-1973), заменяя словосочетание «экономическая система»...
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconЛекция №2 Метрические пространства Определение и примеры
Определение и примеры. Важнейшая операция анализа – это предельный переход. В основе этой операции лежит тот факт, что на числовой...
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconЛекция затухающие колебания в среде с вязким и сухим трением и в электромагнитном контуре c активным сопротивлением
Бания. Ясно, что незатухающие колебания являются идеализацией и что любая реальная система имеет трение (механическая система), активное...
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconЛекция 2 Арифметические основы компьютеров Система счисления
Система счисления — это совокупность приемов и правил, по которым числа записываются и читаются
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconЛекция №5 операционная система ms-dos
...
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconСистема vrv или система на базе чиллера и фанкойлов
Стемы централизованного кондиционирования: vrv и система чиллер + фанкойлы. Их использование приводит к практически идентичному результату,...
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconЛекция Финансовая система План
В связи с этим финансовая система представляет собой совокупность различных сфер финансовых отношений, каждая из которых характеризуется...
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconЛекция 2-3 Тема: Система счисления. Сложение, вычитание, умножение чисел. Представление в компьютере целых чисел со знаком и без знака. Прямой, обратный, дополнительный код
Система счисления — это совокупность приемов и правил, по которым числа записываются и читаются
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconЛекция 6 7 Тема: Сюжет и композиция
Система образов художественного произведения. Художественный мир: пространство и время (хронотоп), система персонажей, принципы и...
Разместите ссылку на наш сайт:
Уроки, сочинения


База данных защищена авторским правом ©izlov.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
связаться с нами