Введение в прикладную комбинаторику, Кофман А. (984071), страница 52
Текст из файла (страница 52)
Пусть (хп «2 хз хо) =х!хз'+ хзхз'+ х1хзх4+ хзх4 = 1. (А2.69) 424 Выписываем Мо=а-+Ь+с+Й, М1 — а+Ь+с-+4(, М! = а + Ь + с 1- 4(, Мо = а + Ь -1- с + 4( 4р =1«1=0~М2» 141 = 1р1 = 1 =Ь а3 !. Имеем последовательно Р(0, О, О, 0) = 1, Р (О, О, О, 1) = 1, Р (О, О, 1, 0) = О, Р (О, 1, О, 0) = 1, Р (О, 1, О, 1) = 1, Р (О, 1, 1, 0) = О, Р (1, О, О, 0) = 1, Р (1, О, О, !) = О, Р (1, О, 1, 0) = 1, Р (1, О, 1, 1) = 1, Р (1, 1, О, 0) = 1, Р (1, 1, О, !) = 1, Р (1, 1, 1, 1) = 1. Таким образом, решения уравнения (А2.69) (О, О, О, 0), (О, О, О, 1), (О, О, 1, !), (О, 1, О, 0), (О, 1, (1, О, 1, 0), (1, О, 1, 1), (1, 1, О, 0), (1, 1, О, 1), (1, 1, Разложение (А2.69) запишется в виде Р (О, О, 1, 1) = 1, Р (О, 1, 1, !) = О, Р (1, 1, 1, 0) = 1, (А2.70) таковы: О,!), (1, 0,0,0), 1, 0), (1, 1, 1, 1).
(А2.71) Р (Х1~ Х2, Хз, Х4) = Х1Х2ХЗК4 '+ Х1Х2ХЗХ4 "+ Х1Х2ХЗХ4 3 Х1Х2ХзХ4 '+ 1 ХЗХ2ХзХ4 '+ Х1Х2Х Х4 '+ ХЗХ2Х Х4 '+ Х1ХЗХ Х4 ! Х1Х2ХЗХ4 + + х,хзх,ха+ х,хзхзх, + х,хзхзх,. (А2.72) Булевы уравнения вида Р=! или Р=О встречаются во многих задачах. Например, рассмотрим конечное множество Е = (а„аз...,, а„). Тот факт, что А с: Е, описывается уравнением РА(Х1, КЗ, ..., Хз)=1 (А2.73) где х„х„..., х„— булевы переменные, соотнесенные эле- ментам Е.
П р и м е р, Пусть Е = (а„а„а„а4). Определим подмно- жества А с: Е условием (а, ~ А и а, ен А) или (а, ен А и аз Ф А) или (аз ФА и азФА и изе=А) или (азФА и а4ФА). (А2.74) Это условие сводится к уравнению (А2.69), решения кото- рого уже найдены. Выпишем подмножества А: (О, 0,0, 0) — О, (О, О, О, 1) — [а4), (О, О, 1, 1) — (аз, а4), (О, 1, О, 0) — (аз), (О, 1, О, 1) — (а,, аз), (1, О, О, 0) — (а1), (1, О, 1, 0) — (а1, аз), (1, О, 1,!) — (ап ам аз], (1, 1, О, 1) — (а„аз, а ), (1, 1, 1, 0) — (ао аз, аз), (1, 1, 1, 1) — (а„аз, аз, а.1). Это все подмножества, удовлетворяющие условию (А2.74).
Булевы уравнения можно использовать прн доказательствах. Действительно, сказать, что условие Ж = 1 дает результат 42в Я = 1 (!)Г и Я вЂ” булевы функции), равносильно доказательству того, что (А2.78) (А2.79) (А2,80) (А2 81) (А2.82) (А2.83) (А2.84) но) ~н~ысгь, (А2,86) (А2,87) (А2,88) (А2,89) (А2.90) (А2.91) (А2. 92) (А2. 93) Моргана; (А2. 94) (А2. 95) (А2.
96) (а)=а; аЬ=а+Ь, ) теорема де а-+ Ь= аЬ а+аЬ=а+ Ь а(а+ Ь) =аЬ. УПРАЖНЕНИЯ А2.А. Дать первую и вторую канонические формы функций; в) у = хзхзхзйвз(х~ 4-хз), б) у = хз+хз+хзхз в) у =хзхз+хзхз+хзхе А2.Б. Доказать тождества; в) (аЬс+ Ьс) аЬс ас, б) ос + аЬсЬ + аЬс 4- асЬ = а (Ь + с) 4- Ьс 4- Ьс, в) аЬс+ аЬс+ аЬс+ аЬс+ аЬс =аЬ+ с 426 27 + Я = 1 тождественно. (А2.76) Утверждение; й"=! — необходимое и достаточное условие того, что Я = 1, — равносильно тому, что (У+ Я)(тз'+ Я) =йЯ+ вГЯ=! тождественно.
(А2 77) Основные формулы двухалементной булевой алгебры. Дадим здесь сводку основных формул для булевых характе- ристических функций а, Ь и с: аЬ= Ьа, 1 коммутати а+Ь=Ь+а) (аЬ) с = а (Ьс), ассоц (а + Ь) + с = а + (Ь + с) аа=а, ндемнотентн а + а = а а(Ь+ с) = аЬ+ ас, а + (Ьс) = (а + Ь) (а + с) ) дистр па=О, а )- а = 1, а0=0, а+О=а; а1= а, а+ 1=1; А2.В. Решить уравнении: а) к,х,х, = 1, б) хзх, + хз + хз = О, в) хзхз + хз(хз ч- хз) 1. А2.Г.
Решить системы уравнений: а) х,хз + хз = 1, к,х,хз = О, б) хзхз — — 1, к,х,=1, х,х,=1. А2.Д. В обычной алгебре нз хук=о вытекает, что по крайней мере один сомножитель равен нулю. Показать, что в двухэлементной булевой алгебре из лук = 1 следует, что каждый из соиножителей равен 1. АЗ. Кольцо классов вычетов по модулю а Рассмотрим множество Е, на котором заданы два закона композиции * и о. удовлетворяющих следующим свойствам.
!) Для нсех х, у, ген Е (хоу)*г=хо(у*г) (ассоциативность), (АЗ.!) х о е = е з х = х (существование нейтрального элемента), (А3.2) х * х = х * х = е (для любого элемента существует обратный), (АЗ.З) (А3.4) х о у = у о х (коммутативность) Итак, множество Е относительно закона композиции е образует коммутативную группу, 2) Для всех х, у, генЕ (А3.5) (х о у) о г = х о (у о г), закон композиции о ассоциативен. 3) Для всех х,у,г из Е (х чу) ог =(х о г) з (у ох) (дистрибутивность слева), (А3.6) г ° (хау)=(гох) о(гоу) (дистрибутивность справа).
(АЗ.7) Множество Е с законами композиции е и °, для которых выполняются вышеуказанные условия, называется кольцом. Законы композиции о и о обозначают также через + и первый называют законом сложения, а второй — законом умножения. Кольцо часто обозначают через (Е, +, ). Пример кольца приведен на рис. 518. Для кольца выполняются следующие свойства. 1) Можно определить вычитание как закон композиции, обратный сложению з; но относительно вычитания кольцо не яв* ляется группой. Имеем также (вх Ф 0)х — 0 ~ 0 — х.
Разность обозначается х — у=х+( — у). (А3.8) 427 2) Умножение дистрнбутивно относительно хо(у — г) =хоу — хог, (х — у) г = хг — уг. вычитания (А3.9) (А3.10) 3) Имеем ( — х)( — у) =ху, ( — х) у = — (ху), х( — у) = — (ху). (А3.11) (АЗ.12) (АЗ,13) Заканкелтаееацаи ск оакснкомпозиццио Рис. 5!8.
4) Можно использовать запись: х"=хх ... х (и раз), (х") = х-", хрх =х хе =хе+с. (А3.14) (А3.15) (А3.16) 5) Кольцо называют коммутатнвным, если Х о у = у о Х. Характеристика кольца. Обозначим через пх, где пеиХ (..., — 1, О, 1, ...) и (А3.17) х я Е, (А3.18) сумму и элементов кольца, каждый из которых равен х: х+х+ ... +х при п>0, а раа пх= при и = О, (А3.19) ( — х)+( — х)+ ... +( — х) при и < О. л раа Пусть е — нейтральный элемент относительно закона °, Наименьшее целое положительное п, для которого пе=О, (А3.20) называется характеристикой кольца.
Если такого и не существует, то говорят, что кольцо имеет характеристику нуль, 428 Для коммутативных колец характеристики и ) 0 (л простое) имеем С~=иг/ (деий), рФО, рФ и), (А3.21) (А3.22) и, если существует единица е, С„'= п (дв) = О. (А3.23) Отсюда получаем (а+ Ь)" =а" + Ь", (А3.24) (а — Ь)" = а" — Ь". (А3.25) Кольцо классов вычетов по модулю и.
Рассмотрим отношение эквивалентности, нли сравнимости, на множестве Х = (..., — 1, О, 1,...), определяемое следующим образом. Пусть л ен М,; г ен Ь); а, Ь, г/, г/' ен Х. Два числа а н Ь называют сравнимыми ио модулю и, если их разность делится на п, т. е. они дают один и тот же остаток при делении на и: а = лг/+ т, (А3.26) Ь= лг/'+ г. а — Ь = л (г/ — г/'). а = Ь (гпод и).
(А3.27) Отсюда Записывают (АЗ. 28) (А3.29) Например, — 17 и- =31 (лог( 3), (АЗ.ЗО) 163 — 79 (гпог1 14). (АЗ.31) аэ =— О(гпог( п), а, = 1 (тог1 п), класс 0: класс 1: (АЗ.32) класс л — 1: а„, = и — 1 (гпоб и). 429 Все числа вида а + йл, где а, й ен Х, л ен М, образуют класс, называемый классом вычетов. Следовательно, имеем и классов вычетов. Фактор-множество Х/6, где 6 — рассматриваемое отношение эквивалентности по модулю и, обозначается через Х/и. Его элементы: Например, при а=7 имеем (АЗ.ЗЗ) Классы можно обозначать произвольно.
Например, класс ( — 2): а з— = — 2(аког(7), класс ( — 1): а г =— — 1 (гпог( 7), класс (О): а,— = 0(шо47), класс (1): а, — = 1(шод 7), (А3,34) класс (2): аз— = 2(гпог(7), класс (3): аз= — 3(шог( 7), класс (4): а,— = 4(гпог(7). Обычно их обозначают по наименьшему положительному их представителю: (О), (1), ..., (п — Ц. Вводя сложение и умножение по модулю и, можно проверить, что для любого л ен 5), множество классов вычетов по модулю л образует коммутативное кольцо, П р и м е р ы. Рассмотрим множество классов вычетов по модулю 5; имеем (2) + (4) = (1), (А3.35) (3) + (2) = (О), (АЗ.З6) (3) + (1) = (4), (А3.37) (2) (З~ = (1), (А3.38) (3) (4) (2). (А3.39) Приведем кольца Х/2, Е/3, Х/4, Е/5, Е/6 (рис. 519 — 523).
Основные свойства кольца Х/и. 1) Характеристика кольца У/и равна а. Например, для 2/4 имеем (см. рис. 521) 4 (3) = (3) + (3) + (3) + (3) [2) + (3) + (3] (1) + (3) (О) (А3.40) 430 5)3! =)3)+)3]+)3) +)3)+ )3) =)3). (А3.41) 2) Нейтральный элемент относительно умножения для кольца Х/и, где и простое, равен )1). Это следует из теоремы Ферма: для всех й ен Х, лен(з)э, и — простое число, имеем й" = — й (глоб и).
(А3.42) 3) Обратимым элементом кольца Х/и называют элемент а, для которого аа '=а 'а=)1). (А3.43) Например (см. рис. 518 — 522), )1) — обратимый элемент кольца Х/2, )1) и )2) — обратимые элементы кольца У/3, )1) и )3) — обратимые элементы кольца Х/4, (1), )2), )3), (4) — обратимые элементы кольца Х/5, )1) и )5] — обратимые элементы кольца Х/6. УПРАЖНЕНИЯ АЗ.А. Показать, что на 2 существует единственная операция: !) дистрибутивная относительно сложения, 2) сводящаяся к умножению на М. АЗ.Б.
Рассмотрим пары (х, у) еэ 2 Х Х. Введем на множестве Е этих пар следующие законы композиции; для всех (хну,), (хз, уз) щ Е имеем (хь У,) ч (хз, Уз) = (х~ + хэ, Гп + Уз), (хп Ги) ь (хз, Уз) = (ххэ+ ЮУз, хьрз+ хзгн). Показать, что получаем кольцо. АЗ.В. Описать кольца 2/7, 2/8. АЗ.Г. Показать, пользуясь (АЗЛ2), что нейтральный элемент относительно умножения в кольце 2/л есть (1). АЗ.Д.
Указать обратимые элементы в кольцах 2/7 и 2/8. А4. Поля Галуа Прежде чем перейти к свойствам полей Галуа, напомним понятие поля. Полем (Е,е, ч ) называется кольцо, которое обладает нейтральным элементом относительно умножения и для любого не равного нулю элемента которого существует обратный элемент относительно умножения. Другое определение: кольцо есть поле, если все его элементы, отличные от нуля, образуют мультипликативную группу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
