Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 72
Текст из файла (страница 72)
Наименьшая верхняя грань и наибольшая нижняя грань множества не обязательно являются элементами этого множества. Пусть Я вЂ” множество рациональных чисел и пусть < — обычное отношение "меньше или равно", и <— отношение "меньше" для рациональных чисел. Тогда для множества А = (х 6 Я: 0 < х < Ц с частичным порядком < имеем 0 = ннг(А) и 1 = нвг(А), однако 0,1фА. П Если для каждого двухэлементного подмножества ЧУ-множества А существует наименьшая верхняя грань, принадлежащая А, то на множестве А можно определить следующее бинарное отношение, Если а и Ь принадлежат А, то пусть аУЬ = нвг(а, Ь). Если используются обозначения булевой алгебры, то вместо аУЬ записывают а+ Ь. ОПРЕДЕЛЕНИЕ 9.8.
ЧУ-множество А, все двухэлементные подмножества которого имеют наименьшую верхнюю грань, принадлежащую А, называется верхней нолурешеткой и обозначается (А,'Х) или (А, +). 394 ГляВА 9. Алгебраические структуры Если для каждого двухэлементного подмножества ЧУ-множества А существует наибольшая нижняя грань, принадлежащая А, то на множестве А можно определить следующее бинарное отношение. Если а и 6 принадлежат А, то пусть адЬ = ннг(а,Ь). Если используются обозначения булевой алгебры, то вместо алЬ записывают а Ь. ОПРЕДЕЛЕНИЕ 9.9.
ЧУ-множество А, все двухэлементные подмножества которого имеют наибольшую нижнюю грань, принадлежащую А, называется нижней полурешеткой и обозначается (А, д ) или (А,.). В примере 9 3 (1, 2) / (1, 3) = (1, 2 3) и (1, 2) д (1, 3) = (Ц.
В этом случае наименьшая верхняя грань и наибольшая нижняя грань — объединение и пересечение множеств соответственно, и обозначения совпадают с обозначениями теории множеств. В примере 9.6 6 / 15 = 30 и 6 л 15 = 3. В этом случае наименьшая верхняя грань и наибольшая нижняя грань — это наименьшее общее кратное и наибольший общий делитель соответственно. Доказательство приведенной ниже теоремы, в которой сформулированы алгебраические свойства полурешеток, предоставляется читателю.
ТЕОРЕМА 9АО. а) Пусть А — верхняя полурешетка. Тогда для всех а,Ь,с Е А а ~/ (Ь |/с) = (а / Ь) / с, а Ч а = а и а ~/ 6 = Ь |/ а. б) Пусть А — нижняя полурешетка. Тогда для всех а, Ь,с е А а д (6 л с) = (аЛЬ) Лс, ада=а и аЛЬ=ЬЛа. ° УПРАЖНЕНИЯ 1. Постройте диаграмму Гессе (см. раздел 2.6) для ЧУ-множества из примера 9.3. 2. Постройте диаграмму Гессе для ЧУ-множества из примера 9.6. 3. Постройте диаграмму Гессе для ЧУ-множества из примера 9.4. 4.
Постройте диаграмму Гессе для ЧУ-множества из примера 9.5. 5. По диаграмме Гессе для ЧУ-множества, изображенной на рис. 9.1, определите: а) наибольший элемент ЧУ-множества (если он существует); б) наименьший элемент ЧУ-множества (если он существует); в) максимальный и минимальный элементы ЧУ-множества; г) является ли рассматриваемое ЧУ-множество верхней или нижней полу- решеткой (или и тем, и другим)? РАЗДЕЛ 9,1. Вновь о частично упорядоченных множествах 395 а Рис. 9.1 6. По диаграмме Гессе для ЧУ-множества, изображенной на рис.
9.2, определите: а) наибольший элемент ЧУ-множества (если он существует); б) наименьший элемент ЧУ-множества (если он существует); в) максимальный и минимальный элементы ЧУ-множества; г) является ли рассматриваемое ЧУ-множество верхней или нижней полу- решеткой (или и тем, и другим)? в Ь с а Рис, 9.2 7. По диаграмме Гессе для ЧУ-множества, изображенной на рис. 9.3, определите: а) наибольший элемент ЧУ-множества (если он существует); б) наименьший элемент ЧУ-множества (если он существует); в) максимальный и минимальный элементы ЧУ-множества; г) является ли рассматриваемое ЧУ-множество верхней или нижней полу- решеткой (или и тем, и другим)? а Рис. 9.3 8. По диаграмме Гессе для ЧУ-множества, изображенной на рис.
9.4, определите: а) наибольший элемент ЧУ-множества (если он существует); б) наименьший элемент ЧУ-множества (если он существует); в) максимальный и минимальный элементы ЧУ-множества; г) является ли рассматриваемое ЧУ-множество верхней или нижней полу- решеткой (или и тем, и другим)? 396 ГЛАВА 9. Алгебраические структуры а Рис. 9.4 9. По диаграмме Гессе для ЧУ-множества, изображенной на рис. 9.5, определите: а) наибольший элемент ЧУ-множества (если он существует); б) наименьший элемент ЧУ-множества (если он существует); в) максимальный и минимальный элементы ЧУ-множества; г) является ли рассматриваемое ЧУ-множество верхней или нижней полу- решеткой (или и тем, и другим)? а Рис.
9.5 1О. Основываясь на диаграммах Гессе из предыдущих упражнений, опишите их характерные свойства, которые гарантируют, что а) ЧУ-множество имеет максимальный элемент; б) ЧУ-множество имеет наименьшую верхнюю грань (или наибольший эле- мент); в) ЧУ-множество имеет минимальный элемент; г) ЧУ-множество имеет наибольшую нижнюю грань (или наименьший эле- мент).
11. Докажите следующее: а) пусть А — верхняя полурешетка. Тогда ам (ЬУ с) = (а'и 6) ч'с для всех а, Ь с Е А, а У а = а для всех а Е А и а Н Ь = 6 '~а для всех а Ь Е А; б) пусть А — нижняя полурешетка. Тогда а А (Ь д с) = (а А Ь) А с для всех а Ь се А, ада = а для всех а Е А и адЬ = ЬАа для всех а 6 Е А. !2.
Докажите, что в каждом конечном ЧУ-множестве имеются максимальный и минимальный элементы. 13. Докажите, что в каждой конечной верхней полурешетке имеется наимень- шая верхняя грань (или наибольший элемент). РАДЕЛ 9.2. Полугруппы и полурешетка 397 14. Докажите, что в каждой конечной нижней полурешетке имеется наибольшая нижняя грань (или наименьший элемент). 15. В главе 2 булевы операции У и л на множестве (О, Ц определены таблицами: Была введена также булеза матрица как матрица, у которой все элементы О или 1. Если А = ~А„) и В = )В;,) — булевы матрицы размерности т х и, то 1Г = А У В опРеделаетсЯ как Ьгм = А, ч Вгу пРи 1 < г < т,1 < 1 < и; У = АлВ определяется как к', = А,.
лВгу при 1 < 1 < т, 1 < 1 < и. Пусть 5 — множество всех булевых матриц размерности и хи. На множестве Я определим отношение < следующим образом: А < В для А,В с Я, если А„< В,, при 1 < г', з' < и. а) Докажите, что множество Я с этим отношением представляет собой ЧУ- множество. б) Докажите, что А У В вЂ” наименьшая верхняя грань для (А,В). в) Докажите, что Ал — наибольшая нижняя грань для (А,В). г) Докажите, что 5 является и верхней, и нижней полурешеткой. д) Что является наибольшим и наименьшим элементом для множества 5? 9.2.
ПОЛУГРУППЫ И ПОЛУРЕШЕТКИ В определении 4.2! бинарная операция на множестве 5 определена как функция Ь: 5 х Я вЂ” 5. Поскольку множество значений бинарной операции на множестве 5 является подмножеством множества Я, то, по определению, бинарная операция обладает свойством замыкания, когда результат операции над двумя элементами г и г множества Я также является элементом Я. Существует достаточно много примеров бинарных операций. Например, если Я вЂ” множество положительных целых чисел, то произведение и сумма — бинарные операции, поскольку и произведение, и сумма положительных целых чисел есть положительное целое число. Во многих случаях такие операции являются еще и ассоциативными, например, как для сложения положительных целых чисел (а+Ь) +с = а+ (6+с) и умножения положительных целых чисел (а 6) . с = а ° (Ь с).
Пусть Я вЂ” множество матриц размерности и х и, элементы которых — целые числа. Сумма и произведение элементов из 5 снова являются элементами Я. Более того, если А, В и С вЂ” матрицы размерности и х и, то (А . В) . С = А (В С) и (А + В) + С = А + (В + С). В приведенном ниже определении бинарным операциям с такой структурой даны специальные названия. 398 ГЛАВА 9. Алгебраическое структуры ОПРЕДЕЛЕНИЕ 9.11. Множество 5 с такой бинарной операцией * на 5 х 5, что для всех а, Ь и с из 5 имеет место (а * Ь) * с = а ь (Ь*с), называется полугруппой и обозначается (5, *), или просто 5, если понятно, какая операция имеется в виду. Если, в дополнение к этому, для всех а и 6 из 5 выполняется а * Ь = Ь* а, то множество 5 с оператором * называется абелевой, или коммутативной полугруппой.
Если в (5, *) существует элемент 1 такой, что 1* а = а *1 = а для всех а из А, то такое 1 называется единицей полугруппы (5,*), а (5, ь) называется полугруппой с единицей, или моноидом. Если (5, *) — полугруппа, и 5 С 5, то 5 называется подполугруппой полугруппы 5, если ь — бинарная операция на 5.
Это эквивалентно следующему: ф, *)— подполугруппа полугруппы (5,*), если 5 С 5, и для каждых а, Ь Е 5 имеем аь6 ~ 5. Отметим еще раз: тот факт, что ь является бинарной операцией на множестве 5 х 5, означает, что если з, з' е 5, то з * з' е 5. Указанное свойство называется замкнутостью. ПРИМЕР 9.12.
Множество 5 матриц размерности и х и является моноидом (5, ). Единицей в данном случае будет матрица 1 с единицей в качестве элементов главной диагонали и нулем в качестве прочих элементов, так что ~1, если 1 = д; ( О, если 1 ф 1. Следовательно, единичная матрица размерности 3 х 3 имеет вид И:И ПРИМЕР 9.13. Если (5, ) — полугруппа матриц размерности п х и, элементами которых являются рациональные числа с операцией матричного умножения и если (5,.) — полугруппа матриц размерности п х и, элементы которых — целые числа, тогда (5, ) — подполугруппа полугруппы (5, ).
П ПРИМЕР 9.14. Для положительного целого числа и положим 5о = (х; х целое число и х > п) и (О). Полугруппа 5о — коммутативный моноид с операцией сложения целых чисел и нулем в качестве единицы. Пусть 5„' = (х: х целое число и х > п) О (Ц. Полугруппа 5„' — коммутативный моноид с операцией умножения целых чисел с единицей в качестве единицы. Если т > п, то 5о подполугруппа полугруппы 5о и 5' — подполугруппа полугруппы 5„' П ПРИМЕР 9.15. Пусть 5 — множество всех функций из непустого множества А в само множество А с бинарной операцией композиции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
