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

Операции над множествами
<< Множества, операции над ними лекция №1		Множества и операции над ними >>

Определение 7. Пусть (X,*) — полугруппа

Список всех бинарных операций на множестве { 1, 2 }

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

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

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

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

Сл	Текст	Сл	Текст
1	Научно-практическая конференция	16	b ? 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.	18	3.Задача классификации и оценки
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 называется	20	4. Асимптотическая оценка количества
	коммутативной, если 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, тем самым теорема		полугрупп очень трудоёмки. Вряд ли
	будет доказана.		когда-то будет получена точная
15	F – подмножество в 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 презентаций об операциях над множествами

Операции над множествами	Множества и операции над ними	Сравнение множеств	Объединение пересечение множеств	Пересечение и объединение множеств
Законы о множествах