ТЕОРИЯ МНОЖЕСТВ СТРУКТУРЫ (РЕШЕТКИ). ИЗОМОРФИЗМ. СИСТЕМАТИЗАЦИЯ ВВЕДЕННЫХ

и управления, кафедра АПВТ, ХНУРЭ
Лектор – д.т.н., проф. Хаханов В.И.
ДИСКРЕТНАЯ

МАТЕМАТИКА

понятиями
Содержание:
Определение структуры
Подрешетка, интервал, сравнимые элементы,
структурные ноль

и единица
Дедекиндовы (модулярные) решетки
Дистрибутивные решетки
Изоморфизм множеств, алгебр
Алгебраические системы. Модели
Схема взаимосвязей между понятиями

Тема: Структуры (решетки). Изоморфизм

12-14 с.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств,

математической логике и теории алгоритмов. М.: Наука, 1984. С. 4-10.
Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. 23-25 с.
Дискретная математика: Гипертекстовые учебные материалы (электронный учебник) / В.И. Хаханов, С.В. Чумаченко. 2004. http/…/10.13.20.100/nserv/library/ education/Чумаченко/Дискретная математика/ Дистанционный_учебник/index.htm.

множество,
операции (объединение, пересечение),
законы (ассоциативный, коммутативный, элиминации),

алгебра

Ключевые слова:
структура (решетка),
дедекиндова (модулярная) решетка,
дистрибутивная решетка,
подрешетка, изоморфизм

котором каждое двухэлементное подмножество имеет единственные точную верхнюю (sup) и

точную нижнюю (inf) грани
Решетка (структура) – это алгебраическая система
, для элементов которой справедливы законы:
xx=x, xx=x;
xy=yx, xy=yx;
x(xy)=x, x(xy)=x,
и  x,yM ! sup{x,y}=xy, inf{x,y}=xy
Рассматриваемая система не является решеткой, если не существуют супремум или инфимум, либо они не единственны
Структуры иллюстрируются диаграммами

Определение структуры

Множество всех подмножеств данного множества (булеан), упорядоченное по включению

3. Диаграммы

А и В не являются структурами
Почему?

В

p

q

операциями ,  (+, •; ,), удовлетворяющими свойствам:
xx=x, xx=x;
xy=yx,

xy=yx;
x(xy)=x, x(xy)=x;
x(yz)=(xy)z, x(yz)=(xy)z
 x,yM: xy ! sup{x,y}=xy=y, inf{x,y}=xy=x
Понятие решетки относится к середине XIX в. Впервые его ввел немецкий математик Дедекинд. Термин «решетка» принадлежит американскому ученому Гаррету Биркгофу из Принстонского университета.

– подрешетка M´ с наименьшим элементом ma и наибольшим элементом

mb:
I=[ ma, mb ]={ mM´ | mammb }
Def: Нулевой и единичный элементы в решетке называются структурными нулем и единицей.
Def: дополнительные элементы
xy=1, xy=0
х – дополнение элемента у в решетке : x=y, y=x
Def: два элемента, обладающие общим дополнением в решетке, называются связанными
Def: два элемента в структуре сравнимы, если в диаграмме их можно соединить путем из стрелок

решетка Н дедекиндова  HmH
Пояснение:
2,3,4Hm, 34
(32)4 3(24)

54 31
4  3

в Брауншвейге
Учился в Геттингенском университете
Профессор Высшей технической школы

в Брауншвейге
Дал теоретико-множественное обоснование теории действительных чисел
Ввел теоретико-множественное понятие отображения
Разработал основы теории структур
С его именем связаны многочисленные математические утверждения и термины: кольцо, поле, структура, сечение, функция

Дедекинд Рихард Юлиус Вильгельм (XIX-XXвв.)

, HgH
Пояснение:
2,3,4Hm
(23)4 (24)(34)
54 11
4

 1

и M* изоморфны, если между ними существует изоморфизм, сохраняющий порядок





Изоморфизм

множеств

алгебры, образованные множествами одинаковой мощности, изоморфны (операции одинаковы, отображение –

взаимно-однозначное соответствие множеств-носителей)
Суть изоморфизма можно выразить следующим образом: если алгебры А и А* изоморфны, то элементы и операции в алгебре А* можно переименовать так, что А* совпадает с А

Изоморфизм алгебр. 1

изоморфной ей алгебре А*, что позволяет автоматически распространять такие соотношения

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

Изоморфизм алгебр. 2

отношения, в которых находятся элементы множества (тúповая характеристика структуры), а

затем постулируют, что данные отношения удовлетворяют определенным условиям – аксиомам структуры.

коммутативный;
б) дистрибутивный;
в) элиминации;
г) ассоциативный?
3. Какой закон в

дополнение к обязательным определяет решетку как булеву алгебру:
а) дистрибутивный;
б) коммутативный;
в) элиминации;
г) ассоциативный?

1. Решетка определяется на:
а) произвольном множестве;
б) линейно упорядоченном множестве;
в) частично упорядоченном множестве;
г) неупорядоченном множестве?

б) {a}U{c};
в) {b}∩{a,b,c};
6. Обосновать, является ли решетка Н дедекиндовой

и дистрибутивной?

4. Какие из элементов структуры Н сравнимы:
а) {a} и {a,c};
б) {a} и {c};
в) {b} и {a,b,c};
г) никакая пара не является сравнимой?