Лекция №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Методичні рекомендації для студентів ІV курсу по виконанню психологічного завдання під час педагогічної практики. Під час педагогічної практики студент повинен
Під час педагогічної практики студент повинен відвідати уроки учителя-предметника і дати психолого-педагогічний аналіз одного з них,...
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconКонспект урока по теме
Время проведения: 1 академический час изучения нового материала и 1 академический час выполнения практической работы
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconКлассный час «Без друга в жизни туго»
Классный час, посвященный обсуждению вопросов, связанных с истинной и мнимой дружбой
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система icon3. Планирование человеческих ресурсов. Набор и селекция персонала (4 час) Занятие Набор и селекция персонала (2 час.)
Управление человеческими ресурсами как интегральный компонент общего процесса управления
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconКонспект урока Тема урока: «Алгебраическая сумма и правила её вычисления»
Цель: Обобщение и систематизация знаний учащихся по теме Алгебраическая сумма и
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconПроверено лично Монастырь за облаками «Час» ведет репортаж из женского монастыря в Индии
«Петита», Ольга Франчук, вместе с дочерью, пятиклассницей Настей, сейчас находится в Индии, в буддистском монастыре. Мы уже публиковали...
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconТема інформаційна система урок 1 структура інформаційної системи
Вважається, що в наш час обсяг інформації подвоюється приблизно кожні десять років. Робота з таким об'ємом інформації неможлива без...
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconТематическое планирование по математике, профильный уровень Класс 11 Учитель: Мартьянова Наталия Викторовна Количество часов: 204 Всего 204 час; в неделю 6 час
Планирование составлено в соответствие с примерными программами среднего ( полного) общего образования по математике профильного...
Лекция №5 (лек. 2 час + прак занят 2 час + лаб. 2 час. + самос. 2 час) алгебраическая система алгебраическая система iconКлассный час для своих бабушек, дедушек, родителей, соседей, знакомых преклонного возраста. Вед Люди пожилые
Заранее учащиеся готовят рисунки, фотографии на выставку, сувениры, приглашения на классный час для своих бабушек, дедушек, родителей,...
Разместите ссылку на наш сайт:
Уроки, сочинения


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