Операции над множествами
<<  Множества, операции над ними лекция №1 Множества и операции над ними  >>
Определение 7. Пусть (X,*) — полугруппа
Определение 7. Пусть (X,*) — полугруппа
Список всех бинарных операций на множестве { 1, 2 }
Список всех бинарных операций на множестве { 1, 2 }
Картинки из презентации «БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ» к уроку алгебры на тему «Операции над множествами»

Автор: 1. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока алгебры, скачайте бесплатно презентацию «БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ.ppt» со всеми картинками в zip-архиве размером 110 КБ.

БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ

содержание презентации «БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ.ppt»
Сл Текст Сл Текст
1Научно-практическая конференция 16b ? 1. Но a ? 1 = a, b ? 1 = b, значит, a
учащихся Псковской области «Шаг в будущее» = b. Осталось убедиться, что для любых a,
11 – 13 декабря 2013 года, г. Псков b ?S ?(ab) = ?(a)?(b), то есть для любого
БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И x ?X ?(ab)(x) = ?(a)?(b)(x). Сделаем это
ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ цепочкой равенств, пользуясь
Работу выполнил: Кузьминский Евгений соответствующими определениями и
Михайлович МАОУ «Гуманитарный лицей» г. ассоциативностью умножения:
Псков, 11 класс. Научный руководитель: ?(ab)(x)=fab(x)=(ab)x=a(bx)=fa(fb(x))=fafb
Яблокова Галина Анатольевна учитель x) =?(a)?(b)(x).
математики МАОУ «Гуманитарный лицей» г. 17Определение 12: Подстановкой n - ой
Псков. г. Псков 2013. степени называется взаимно однозначное
2Введение. Задача исчерпывающего отображение множества А из n элементов в
описания всех конечных полугрупп появилась себя. Пусть множество А = {а1, а2, а3},
в алгебре практически одновременно с тогда существуют шесть различных
возникновением теории групп и полугрупп. С перестановок элементов а1, а2, а3: (а1,
использованием трудоемких вычислительных а2, а3), (а1, а3, а2), (а2, а1, а3), (а2,
процедур, требующих применения самых а3, а1), (а3, а1, а2), (а3, а2, а1). В
современных аппаратных решений, к середине случае, когда ?А? = n всевозможных
2013 года были получены точные значения различных перестановок элементов множества
для количества различных (с точностью до А будет n?= 1?2?3?…?n (n-факториал).
изоморфизма) полугрупп мощности от 1 до 3!=1?2?3=6. Определение 13: Произведением
10. В представленной работе сделана двух подстановок называется подстановка,
попытка дать аналитическую оценку для получаемая в результате последовательного
количества полугрупп специального вида, выполнения сначала 1 - ой, а затем 2 - ой
прежде всего – полугрупп с рангом из перемножаемых подстановок.
нильпотентности 3. 183.Задача классификации и оценки
3Цель работы – дать аналитические количества конечных полугрупп. Наиболее
оценки количества полугрупп, состоящих из сложной задачей, связанной с описанием
n элементов, с точностью до изоморфизма. всего многообразия конечных полугрупп,
4Задачи. Провести алгебраическое является задача полной классификации всех
описание задачи оценивания количества полугрупп порядка n. В общем случае не
полугрупп над конечными множествами; существует удовлетворительных описаний
Описать ситуация с оценками количества структуры всех полугрупп для n>10.
бинарных ассоциативных операций Однако для небольших значений n можно дать
(полугрупп) над конечными множествами; исчерпывающие описания для полугрупп
Дать определение нильпотентных и соответствующей мощности. Простейшим
r-нильпотентных полугрупп, установлены случаем является случай n=2. Для этого
основные свойства нильпотентных полугрупп; значения существует всего 16 бинарных
Установить, что асимптотически количество операций на множестве и все их можно явным
полугрупп над конечным множеством может образом описать:
быть оценено количеством полугрупп над 19Список всех бинарных операций на
этим множеством с индексом нильпотентности множестве { 1, 2 }. Список всех бинарных
3; Получить формула суммирования, операций на множестве { 1, 2 }. Список
определяющая количество полугрупп с всех бинарных операций на множестве { 1, 2
индексом нильпотентности 3. }. Список всех бинарных операций на
5Бинарные операции и свойство множестве { 1, 2 }. ?Полугруппа ({0,1}, .
ассоциативности. Определение 1. Пусть A, ? Полугруппа ({0,1}, . 1 . 1 . 1 . 1 . 1 .
B, C— тройка непустых множеств. Бинарной 1 . 1 . 1 . 1 . 1 . 1 . 2 . 2 . 1 . 2 . 2
или двуместной операцией в паре A, B со . Тривиальная полугруппа O2. ). 2·(1·2) =
значениями в C называется отображение P?C 2, (2·1)·2 = 1 . Полугруппа с левым нулем
где P содержится в A?B. Если A=B=C, то LO2 . 1 . 2 . 1 . 2 . 1 . 2 . 1 . 2 . 1 .
действие называется внутренним, если A=C 1 . 1 . 2 . 2 . 1 . 2 . 2 . 2·(1·2) = 1,
или B=C — внешним. В частности, любое (2·1)·2 = 2. Полугруппа с правым нулем RO2
внутреннее действие является внешним. . ? Группа (Z2, +2). ). 2 . 1 . 2 . 1 . 2
6Определение 2. Бинарная операция на . 1 . 2 . 1 . 1 . 1 . 1 . 2 . 2 . 1 . 2 .
непустом множестве X — это отображение ? 2. 1·(1·2) = 2, (1·1)·2 = 1 . ? Группа
из прямого произведения X?X в X. Пример: (Z2, +2). 1·(1·1) = 1, (1·1)·1 = 2 .
пусть P(U) — множество всех подмножеств 1·(2·1) = 1, (1·2)·1 = 2 . 2 . 2 . 2 . 2 .
множества U. Операции пересечения и 2 . 2 . 2 . 2 . 1 . 1 . 1 . 2 . 2 . 1 . 2
объединения - это бинарные алгебраические . 2 . 1·(1·1) = 2, (1·1)·1 = 1 . 1·(2·1) =
операции на множестве P(U). 2, (1·2)·1 = 1 . 1·(1·2) = 2, (1·1)·2 = 1
7Определение 3. Бинарная алгебраическая . Тривиальная полугруппа O2 .
операция * на множестве X называется 204. Асимптотическая оценка количества
коммутативной, если x * y = y * x для всех полугрупп на n элементах. Обозначим для
x, y ? Х . Определение 4. Бинарная натурального числа n через ?(n) количество
алгебраическая операция * на множестве Х неизоморфных полугрупп мощности n. Для
называется ассоциативной, если ( x * y )* полугруппы S обозначим Sk= {s1s2 · · · sk
z = x * ( y * z) для всех x, y, z ? Х. | si ? S}. Определение. Полугруппа S
Пример: операция сложения на множестве называется нильпотентной, если существует
целых чисел является коммутативной и число r?N такое, что . Наименьшее такое
ассоциативной. rназывается рангом нильпотентности
8Определение 5. Множество Х с заданной полугруппы S, а сама полугруппа S
на нем бинарной алгебраической операцией, называется r-нильпотентной.
называется группоидом. Определение 6. Пара 21Лемма 1. Пусть S – конечная
(Х,*), состоящая из множества Х и бинарной полугруппа. Следующие два утверждения
алгебраической операции * называется равносильны: (I) S является нильпотентной
полугруппой, если операция * ассоциативна. (II) S содержит нулевой элемент z и для
Пример: множество натуральных чисел (N,+) каждого элемента s?S существует ks?N,
является полугруппой, так как операция такое что Доказательство (I)?(II): Если S
сложения на N ассоциативна. является r-нильпотентной и через z
9Определение 7. Пусть (X,*) — обозначить единственный элемент в , тогда
полугруппа. Подмножество называется sz=zs=z для всех s?S, таких, что zs, sz ?
замкнутым относительно операции *, если . Таким образом, z - нулевой элемент
x*y принадлежит Y для всех x,y ? Y. полугруппы. Более того, для всех s?S.
Определение8. Пусть .Пара (Y,*) называется 22(II)?(I): пусть k=max { ks | s?S} и
подполугруппой полугруппы (X,*), если Y n=|S|. Рассмотрим произведение элементов
замкнуто относительно операции *. s1s2…sk+1 длины k+1 в S. Тогда
10Определение 9. Пара (Х,*), состоящая последовательность префиксов вида (s1…si)
из множества Х и бинарной алгебраической где 1?i?k+1 должна будет содержать
операции * называется моноидом, если дубликаты, например, для определённости,
операция * ассоциативна и существует s1s2…sh=s1…sm, где h<m?k+1. Выполняя
нейтральный элемент е ? Х, такой, что последовательные замены вида s1…sh на
е*х=х*е=х Определение 10. Моноид Х с s1…sm получим, что s1…sh=s1…sh(sh+1…sm)=…=
операцией * называется коммутативным, если =s1…shz=z. Поскольку h строго меньше m и,
* — коммутативна. тем более, числа k, можно утврждать, что
11Определение 11. Пусть Y — подмножество s1s2…sk=z Таким образом, все произведения
в X. Будем говорить, что (Y,*) является длины по крайней мере k будут равны z,
подмоноидом моноида (X,*), если Y содержит следовательно, полугруппа S является
нейтральный элемент e и замкнуто k-нильпотентной.
относительно операции *. 23Теорема 1. Пусть S будет нильпотентной
12Пусть S и T – полугруппы с операциями полугруппой порядка n, (n?4) и рангом
? и * соответственно. Изоморфизмом S на T нильпотентности n-1. Тогда S=T?{x}, где Т
называется всякое взаимно однозначное – моногенная подполугруппа в S с рангом
отображение ? S на T, удовлетворяющее нильпотентности n-1 Теорема 2. Для n?5
условию: для любых x, y ?S ?(x?y) = ?(x) * существует n+[n/2] нильпотентных полугрупп
?(y). Полугруппы, для которых существует мощности n и рангом нильпотентности n-1.
изоморфизм одной на другую, называются 24Теорема 3. Пусть S – нильпотентная
изоморфными. полугруппа порядка n (n?5) и рангом
13Теорема 1. Любая полугруппа с единицей нильпотентности n-2. если n?6 или S имеет
изоморфна некоторой полугруппе минимальное порождающее множество мощности
преобразований. Доказательство: Итак, 3, то S=T?{x, y}, где Т – моногенная
пусть S – произвольная полугруппа. Будем подполугруппа в S с рангом нильпотентности
считать, что она мультипликативная. Нужно n-2 Теорема 4. Для n?6 количество
указать такое множество X, что в полной нильпотентных полугрупп мощности n и ранга
полугруппе преобразований T(X) найдется нильпотентности n-2 и минимальным
подполугруппа, изоморфная S. В качестве X порождающим множеством из 3 элементов
возьмем множество, полученное из S равно (21n?+22n-96)/8 для чётных n и
присоединением символа 1, не (21n?+22n-81)/8 для нечётных n.
принадлежащего S. Распространим умножение 25Теорема 5. Для n?7 существует 5n+
в S на множество X, определив произведения [n/2]+[n/3]-1 нильпотентных полугрупп
a ? 1 и 1 ?a для любого a ?S, а также мощности n, рангом нильпотентности n-2 и
произведение 1 ? 1. Положим a ? 1 = 1 ?a = минимальным порождающим множеством из 2
a, 1 ? 1 = 1. Тем самым задана операция элементов. Как следствие, количество таких
умножения на множестве X. Легко убедиться, полугрупп равно (21n?+66n-104)/8-[n/3] для
что она ассоциативна, то есть X является чётных n и (21n?+80n-93)/8-[n/3] для
полугруппой относительно этой операции. нечётных n.
Видим, что 1 есть единица в X. 26Теорема 6. Для n?N количество
14Теперь каждому a ?S поставим в различных 3-нильпотентных полугрупп
соответствие преобразование fa множества мощности n равно где Таким образом,
X, заданное условием: для любого x ?X получена искомая формула, позволяющая
fa(x) = ax Ясно, что fa действительно оценить количество различных бинарных
является преобразованием X: ведь, согласно ассоциативных операций.
определению умножения на X, мы имеем ax ?S 27Выводы. Задача подсчёта и
и, значит, ax ?X. Множество всех таких классификации конечных полугрупп является
преобразований fa обозначим через F. сложной и интересной проблемой. Алгоритмы,
Установим, что F есть подполугруппа в позволяющие с дать точные описания
T(X), изоморфная S, тем самым теорема полугрупп очень трудоёмки. Вряд ли
будет доказана. когда-то будет получена точная
15F – подмножество в T(X), и нужно аналитическая формула для подсчёта числа
убедиться, что оно замкнуто относительно полугрупп, но в данной работе проведена
умножения, то есть для любых fa, fb?F асимптотическая оценка числа полугрупп,
найдется такой элемент c ?S, что fa fb= получены формулы, точно описывающие
fc. Пользуясь определением преобразований, количество полугрупп специального вида.
составляющих F и определением умножения 28Список литературы. Takayuki Tamura.
преобразований, а также ассоциативностью Notes on finite semigroups and
умножения в X, получаем для любого x ?X determination of semigroups of order 4, J.
последовательно fa fb(x) = fa(fb(x)) = Gakugei. Tokushima Univ. Math.,
a(bx) = (ab)x = fab(x). Мы видим, что в 5:17–27,1954. S.K.Winker, L.Wos, and
качестве требуемого элемента c можно взять E.L.Lusk. Semigroups, antiautomorphisms,
ab. and involutions: a computer solution to an
16Теперь убедимся, что отображение ?, open problem. I. Math. Comp.,
сопоставляющее каждому элементу a ?S 37(156):533–545,1984. Andreas Distler and
преобразование fa , будет искомым Tom Kelsey. The monoids of orders eight,
изоморфизмом S на F. По определению, ? nine & ten. Ann. Math. Artif. Intell.,
отображает S на F, надо проверить, что ? 56(1):3–21,2009. Jobst Heitzig and Jurgen
взаимно однозначно, то есть из того, что Reinhold. Counting finite lattices.
?(a) = ?(b), следует a = b. Так как ?(a) = Algebra Universalis, 48(1):43–53,2002.
fa и ?(b) = fb , условие ?(a) = ?(b) Vaclav Koubek and Vojtech Rodl. Note on
означает, что fa = fb , а это означает, the number of monoids of order n. Comment.
что для любого x ?X fa(x) = fb(x). В Math. Univ. Carolin., 26(2):309–314,1985.
частности, fa(1) = fb(1), то есть a ? 1 = 29Спасибо за внимание.
БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ.ppt
http://900igr.net/kartinka/algebra/binarnye-assotsiativnye-operatsii-i-polugruppy-nad-konechnymi-mnozhestvami-260650.html
cсылка на страницу

БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ

другие презентации на тему «БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ»

«Множества чисел» - Раскрыть знак модуля. Множество вещественных (действительных) чисел. Деление с остатком. Множество целых чисел. Основные свойства модуля. Числовые множества. Презентация по теме: «Действительные числа». Тогда множество целых чисел можно записать так: Z ={…,-n,…-2,-1,0,1,2,…,n,…}. Определение модуля можно расширить: Пример.

«Научно-практическая конференция» - Ученый - поэт - общественный деятель… Великий сын России… Самый умный из соотечественников ... Шестая школьная научно-практическая конференция, посвященная Хузангаю 2007. Вторая школьная научно-практическая конференция, посвященная 290-летию . «Золоте яичко” Бизнес-план. Чему учат в школе… Из истории школьной научно-практической конференции.

«Сравнение множеств» - Графический диктант. Сравнение множеств. Работа в тетради. Множество Насекомых. Физкультминутка. Множество Животных. Практическая работа на компьютере. Множество Птиц. Информатику мы учим Много знаний мы получим Думай, думай голова Изучаем множества Руки вверх и раз ,два, три А теперь наклоны вниз Ну-ка рыбка, покажись Повороты вправо, влево Сели и взялись за дело.

«Урок Множества» - Аннотация. Берёза, осина, колокольчик. Москва, Одесса, Лондон, Париж, Чебоксары. Рубашка, свитер, платье, шуба. Урок рассчитан на учащихся ,второй год изучающих информатику. Научатся определять принадлежность элемента множеству (классификация по одному множеству). Цели: Задачи: Назови множество. Игра «Рыба, птица, зверь…».

«Множества и операции над ними» - Множества записываются в различных видах: 1) в фигурных скобках простым перечислением: А={1,2,3} 2) графически. Операции над множествами. Декартовым (прямым) произведением множеств А и В называется множество упорядоченных пар. Множества. Декартово произведение множеств. Мощность множества – множество с конечным числом элементов.

«Теория множеств» - Обозначается А?В. Например, отрезок [а, b] не является подмножеством полуинтервала (а, b], т.к. а?[а, b], но а?(а, b]. Основные числовые множества: Дополнением множества А называется разность U\А.. Элементы множества – точки внутри соответствующего круга. Абитуриенты, получившие оценки 3 и 4, образуют множество А?В.

Операции над множествами

6 презентаций об операциях над множествами
Урок

Алгебра

35 тем
Картинки
900igr.net > Презентации по алгебре > Операции над множествами > БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ