Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 74
Текст из файла (страница 74)
Докажите, что (Я,*) — полугруппа, в которой каждый элемент является идемпотентом. Почему (5,*) не является полурешеткой? 9.3. РЕШЕТКИ В предыдущем разделе были рассмотрены множества с одной бинарной операцией. В данном разделе рассматриваются множества с двумя бинарными операциями. ОПРЕДЕЛЕНИЕ 9.28.
ЧУ-множество (Я, <), которое является и нижней, и верхней полурешеткой, называется решеткой. а) Коммутативность алЬ=Ьла; а~/Ь = Ь\/а. 6) Ассоциативность (а л Ь) л с = а л (Ь л с); (а / 6) ~/ с = а У (Ь \/ с). в) Поглощение а л (а ~/ 6) = а; а~/(ал6) =а. ДОКАЗАТЕЛЬСТВО. Для доказательства пунктов (а) и (б) см. теорему 9.!О и упражнения в конце раздела. Покажем, что а Л (а У Ь) = а: а<а а < а~/Ь по определению частичного порядка; по определению наименьшей верхней грани.
В решетке (5, <) будем обозначать наименьшую верхнюю грань а,6 Е Я через а ~/ Ь (называемое соединением а и Ь), а наибольшую нижнюю грань а, Ь Е Я через а л Ь (называемое пересечением а и Ь). Решетка будет обозначаться через (5,'/,л), чтобы подчеркнуть используемые бинарные операции. На основе свойств наименьшей верхней грани и наибольшей нижней грани докажем следующие свойства решетки, которые можно использовать в качестве альтернативного определения. ТЕОРЕМА 9.29. Пусть (Я,'/,л) — решетка, тогда следующие свойства имеют место для всех а, 6, с Е Я. 404 ГПАВА 9. Алгебраические структуры Поэтому а есть нижняя грань для (а, а У 6).
Допустим, что с — нижняя грань для (а,а'ч'Ь). Тогда с < а, так что а — наибольшая нижняя грань для (а,аы6) и, следовательно, а = ад (ам 6). Доказательство того, что а и (ад 6) = а оставляем читателю. ПРИМЕР 9.30. Пусть 5 — булеан (множество всех подмножеств) множества А с частичным порядком сГ < у', если Ьг с И для всех Ьг, )г а Я. Тогда нвг(0; 1') = Ьг и 'у' и ннг(Ьг, Ъ') = Ьг О 1', поэтому (Я,~~, гт) является решеткой.
с) ПРИМЕР 9.31. Пусть Я вЂ” множество положительных целых чисел с частичным порядком; п < т, если т делит п. Тогда нвг(т,п) = НОК(т,п) и ннг(т,и) = НОД(т, и) для всех т, и Е Я. Поэтому 5 с бинарными операциями НОК и НОД является решеткой. П ПРИМЕР 9.32. Рациональные, действительные и целые числа с обычным частичным порядком образуют решетку, где нвг(т,п) = шах(т,п) и ннг(т,и) = шш(т, п). П ОПРЕДЕЛЕНИЕ 9.33. Непустое подмножество 5 решетки (5,'ч', д) называется иодрешеткой решетки Я, если для всех а,6 Е 5 а д Ь Е Я и а у 6 Е Я.
Следовательно, в примере 9.30, если  — подмножество множества А и 5— булеан множества В, то (Я, и, И) будет подрешеткой решетки (5, О, О), В примере 9.31, если  — множество всех положительных делителей фиксированного целого числа и, то 5 с бинарными операциями НОК и НОД будет подрешеткой решетки Я. В примере 9.32 целые числа образуют подрешетку рациональных чисел, а рациональные числа, в свою очередь, образуют подрешетку действительных чисел. ОПРЕДЕЛЕНИЕ 9.34.
Решетка (5,'ч', л) называется ограниченной, если множество Я, как ЧУ-множество, имеет наименьшую верхнюю грань и наибольшую нижнюю грань. Наименьшая верхняя грань обозначается через 1, а наибольшая нижняя грань — через О. Эквивалентно, решетка ограничена, если существуют элементы О, 1 е Я такие, что 0 л а = 0 и 1 Н а = 1 для всех а е Я. Поскольку 0 — наименьший элемент множества, и 1 — наибольший элемент множества, получаем следующий результат. ТЕОРЕМА 9.3$. В ограниченной решетке 1 л а = 1 и 0 и а = а для всех а из решетки. ПРИМЕР 9.30. Решетка в примере 9.30 ограничена, А — максимальный элемент решетки и Я вЂ” минимальный элемент.
ьз ПРИМЕР 9.37. В примере 9.31, если Я вЂ” полурешетка всех положительных делителей фиксированного целого числа и, то 5 ограничена с максимальным элементом п и минимальным элементом 1. П РКЗДЕЛ 9.3. Решетки 405 В главе 2 отмечалось, что для множеств А, В и С выполняются соотношения Аг1(ВиС) = (АпВ)и(Аг~С) и Аи(ВПС) = (АыВ)п(АиС). Эти соотношения были названы свойством дистрибутивности для множеств. Далее будет дано определение аналогичных свойств для решеток.
В качестве упражнения предлагаем читателю доказать, что решетки, изображенные на рис. 9.6, не дистрибутивны. а Рис. 9.6 Хотя подобное утверждение выходит за рамки данной книги, однако можно показать, что решетка дистрибутивна тогда и только тогда, когда она не содержит ни одну из этих двух решеток в качестве подрешеток. Следовательно, решетки на рис. 9.7 не являются дистрибутивными. Рис. 9.7 Булева алгебра, о которой шла речь в разделе 2.3, является специальным случаем ограниченной дистрибутивной решетки. Теперь перейдем к системе обозначений булевой алгебры из раздела 2.3, заменив бинарную операцию 7 на +, а бинарную операцию д на . Далее решетка будет обозначаться как (5, +, ).
Для удобства приведем определение булевой алгебры еще раз. Более подробно данный вопрос рассмотрен в разделе 2А. 406 ГЛАВА й. Алгебраические структуры ОПРЕДЕЛЕНИЕ 9.39. Булева алгебра — это ограниченная дистрибутивная решетка (5, +, ), в которой имеется унарная операция ' на множестве Б такая, что х+ х' = 1 и х х' = О. Для х Е 5 х' называется дополнением х.
Следовательно, булева алгебра, обозначаемая как (о, +,,', 1, О), обладает следующими свойствами, которые выполняются для всех х,у, г б 5. 1. Законы ассоциативности х + (у+ г) = (х + у) + г; х . (у г) = (х . у) . г. 2. Законы коммутативности х+у = у+х; х у=у.х. 3. Законы дистрибутивности х (у+а)=(х у)+(х г); х+ (у г) = (х+ у) . (х+ г). 4. Законы дополнения х+х' = 1; х.х =О. 5. Законы тождества х+О=х; х 1 =х.
° УПРАЖНЕНИЯ 1. Какое изображение из приведенных ниже представляет собой решетку? а) б) ! а Ь РДЗДЕЛ 9.3. Решетки 407 в) г) д) 2. Покажите, что приведенные ниже решетки не дистрибутивны. 3. Покажите, что решетка, изображенная на рис. 9.8, не дистрибутивна. 4. Покажите, что решетка, изображенная на рис. 9.9, не дистрибутивна. Рис. 9.9 Рис. 9.8 5. Какие из приведенных ниже решеток являются дистрибутивными? 408 ГЛАВА 9. Алгебраическое структуры а) б) в) г) д) е) 6.
Докажите, что для всех а, Ь, принадлежащих решетке, а ч (а л Ь) = а. 7. Атомом в булевой алгебре называется ненулевой элемент х, обладающий таким свойством, что для каждого у из алгебры либо ху = х, либо ху = О. а) Пусть 5 — булеан (множество всех подмножеств) множества (а, Ь,с). Пусть (5,о,й,',йс) — булева алгебра на Я с обычным определением пересечения и объединения. Что является атомами данного множества? б) Пусть Я вЂ” множество всех высказываний, полученных из р, д и т с использованием обычных пропозициональных связок л, ч и . Покажите, что в булевой алгебре (Я,ч',А,-,Т,Е) атомы — это элементарные конъюнкции, определенные в разделе!.5.
в) Найдите атомы булевой алгебры, изображенной на рис. 9АО. РАЗДЕЛ 9.4. Группы 409 г) Найдите атомы булевой алгебры, изображенной на рис. 9ЗБ а Рис. 9.10 Рис. 9.Л 9.4. ГРУППЫ Ранее отмечалось, что множество неотрицательных целых чисел с операцией + образуют моноид. Однако, если включить в рассмотрение множество всех целых чисел с той же операцией +, то опять получим моноид, но обладающий свойством, которое отсутствовало в первоначальном моноиде, а именно: для каждого целого числа а существует целое число — а такое, что а + ( — а) = ( — а) + а = О, единице моноида.
Аналогичным образом, если рассмотреть множество положительных рациональных чисел с операцией умножения, то снова получим моноид, и для каждого рационального числа д существует рациональное число д такое, ч Р что в д = 1, единице моноида. Рассмотрим свойства, фигурирующие при решении ч р уравнения 2х+ 3 = 7. Сначала прибавляем — 3, — элемент, обратный к 3 относительно сложения, к обеим частям уравнения, и получаем (2х+3)+( — 3) = 7+( — 3). После использования ассоциативности получаем уравнение 2х+(3 — 3) = 4. Затем применяем свойство обратного элемента и получаем 2х+ О = 4. Используя свойство нейтральности О относительно сложения, имеем 2х = 4.
Затем для получения окончательного решения применяем свойства нейтральности и ассоциативности. Группы — это нечто большее, чем только абстракция множества действительных чисел с операцией сложения или множества положительных целых чисел с операцией умножения. Далее показано, что множество перестановок и элементов образует группу. Группы имеют важное применение в физике и во многих других областях. Они используются в теории чисел, теории кодов, в комбинаторике. Любой моноид (Я, о), обладающий свойством, что для каждого элемента моноида з существует элемент моноида з ' такой, что з о з ' = з ' о з = 1, единице моноида, называется группой.
Более формально понятие группы может быть определено следующим образом. 410 ГЛАВА 9. Алгебраические структуры ОПРЕДЕЛЕНИЕ 9.40. Группа представляет собой множество С вместе с бинарной операцией (или произведением) о на С х С, обладающей следующими свойствами; 1. а о (Ь о с) = (а о Ь) о с для всех а, Ь и с из С (т.е. операция о на о ассоциативна). 2.
В С существует элемент 1, называемый единицей, который обладает свойством а о 1 = 1 о а = а для всех а из С. 3. Для каждого элемента а из множества С существует элемент а ' из множества С, который называется оБратным элементом для а и такой, чтоаоа '=а ~оа=1. Если группа С обладает таким свойством, что а о 6 = Ь о а для всех а, Ь из С, то она называется коммдтативной, или абелевой группой.
Снова наблюдается ситуация, что поскольку с — бинарная операция на С, то отсюда вытекает, что если д,д' е С, то д о д' е С. Это свойство называется замкнутостью. ПРИМЕР 9.41. Примеры групп включают следующее: 1. Четные целые числа с операцией сложения. 2. Множество (и х га)-матриц с действительными элементами и бинарной операцией сложения. 3. Классы вычетов по модулю некоторого положительного целого числа и, образующие У„с бинарной операцией сложения.
ь) ОПРЕДЕЛЕНИЕ 9.42. Если С вЂ” группа с п элементами, то п называется порядком группы С. Пусть о = 1г, — г, — 1, Ц, где г = чà — Т. Легко убедиться, что это множество вместе с операцией умножения образует группу порядка 4. Заметим, что всякая группа является полугруппой. Обратное, вообще говоря, неверно. ТЕОРЕМА 9.43.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
