Введение в прикладную комбинаторику, Кофман А. (984071), страница 51
Текст из файла (страница 51)
(А2.12) ') Рассмотрим группоиды (Е, Т), (Г, х) и отображение Л множества Е в Р. Говорят, что Ь вЂ” гомоморфиам Е в Г, если (Уха Е) (Уу ~в Е) Ь (х Т у) = Л(х) л П (у). Из диаграмм на рис. 515 видно, что Р (А; х) = 1 — Р (А; х), или 1 (х) =1 — 1,(х). ПишУт также 1,(х) вместо !а(х). (А2.13) (А2.14) ЙА; х) -I, Га(х) -О, Г(А)х)-У-У,(~)-)-Г(А! ) б) г(А!Х)-о, г(х)-6 Р(А ! х)-1-Га (х)-У-Г(А! х) а) Рис. 5!5. Характеристическая функция пересечения, Рассмотрим подмножества А с Е, В ~ Е и их характеристические функции 1а (Х) = Р(А! Х) 1Ь(х) = Р (В! Х) (А2.15) Если хеи АД В, то можно записать Р(АД В; х) =1. (А2.16) Если ХФ АПВ, то Р (А () В; х) = О.
(А2.17) Легко видеть (рис. 516), что если известны значения 1,(х) и !ь(х), то значение Р(АД В;х) равно их произведению. Таким образом, Р(А() В; х) =Р(А; х) Р(В; х) (А2.18) или 1аЬ (Х) = 1а (Х) ~Ь (Х). (А2.19) Легко видеть (рис. 517), что Р(А() В; х)=~,(х) )-)ь(х) при условии, что 1+1=1, 1+0=1, 0+1=1, 0+0=0. (А2.21) (А2.22) 417 Характеристическая функция объединения. Как и раньше, положим 1а(х) = Р (А! х), !аь(х) = Р(В; х).
(А2 20) Можно ли представить и" (А() В; х) с помощью соотношения из обычной алгебры? Получим это соотношение, используя найденные ранее результаты. Е Е Г(А и В;х) =!, У,(х)=1, У,(х)=), Дх) уа(х!=! а) Г(Аив;х) =0, е(х)-У, ге(х)-0, У~у(х) ' ед (х) 0 0У Е Г(А п В; х) = О, 0а га(х) б Г (х) . (х)=0 0) Г(лиВ; ')=0, (х)=0, ге( )=0, ;( ),(.)- г) Рнс. 516.
Напомним теорему де Моргана '); А[) В=А() В. (А2.23) Таким образом, Р(А() В; х) =Р(АД В; х) = 1 — г (А [) В; х) (дополнение), = 1 — [г'(А; х) г" (В; х)] (пересечение), =! — [1 — и" (А; х)][1 — г'(В; х)] (дополнение), = 1 — [1 — )',(х)] [! — [а(х)] (булево обозначение), = 1, (х) + (а (х) — (, (х) 1а (х) (после упрощения). (А2.24) ') Теореиа де Моргана утверждает, что (А <= Е, В <= Е)=РАЦВ АД В, (А <= Е, В ~ Е)='РАУВ = АЦВ. 418 Следовательно, Р(А(3 В; х) = 1,(х)+ 1,(х) =1,(х) + 1ь(х) — 1,(х)1ь(х), (А2.25) ! ч „(х)=! (х)+)' (х) — )' (х)! (х). (А2.26) Приходят к таблице 1 сложения: (А2.27) Когда множества не пересекаются, и только в этом случае, можно не различать + и +.
Рис. 517. Алгебра характеристических функций. Характеристические функции могут принимать только два значения: 0 или 1; все числовые значения, получающиеся при операциях , +. и †, также равны 0 или 1. Это говорит о том, что булева алгебра, 419 Г(А В,х)=), Г,(х)-б ~;(х)-б га(х) '~ь (х) 1 а) ЙА и В; х)-У, у~(х) =О, Фх)-б Дх)й~(х)-/ д) +1=1+1 — 1. 1=1, +0=1+0 †0=1, +1=0+! — 0 1=1, -)-0=0+0 †0=0. с(А и В;х)-У, Г,1х)=0 т;1 )=О, Дх!ХЯх) 1 б) Е Е(АвВ;х) Р, фх)-0, б(х)-0,, 5а(х)зги(х) О г) оперирующая с характеристическими функциями, есть двузначная алгебра '). Таким образом, если а и р — значения двух характеристических функций, то (А2.31) (А2,32) О»=О, 1' 1. Отсюда аз=а, далее (а + р)т = (а + 8 — аб)т = ат + рт + азрт — 2атр — 2арз + 2ар =а+))+ар — 2ар — 2ар+2а()=а+ р — ар=акр, (А233) а также (ар)т атрз ар (а)- "= (1 — а)' = 1 — 2а + ат = 1 — 2а + а = а.
(А2.34) Итак, булеза алгебра описывается таблицами: а + р = а + р — ар, (А2.28) ар= ра, (А2.29) а =1 — а. (А2.30) Характеристическое свойство чисел О и 1 — быть равным своему квадрату: Известно, что булева структура,У(Е) (с операциями П, 0 и -) изоморфна алгебре логики (с операциями /~, ~/ и «не»). Алгебра логики Булеза алгебра, или Алгебра характеристи(двузначная логика) алгебра подмножеств ческих функций подмнонекоторого множества жести некоторого множества Л (н) Д (пересечение) ° (булево произнедениз) )/ (или *)) О (объединение) + (булеза сумма) «не» (дополнение) (отрицание) Чтобы проверить, тождественны ли две характеристические функции, можно воспользоваться либо таблицей истинности, ли- ') Не следует смешивать ее с двоичной системой счисления.
«) Слово «нли» понимается здесь в неисключаюшем смысле, т. е. выска. зывзние «А или В» истинно и тогда, иогда истины А и В вместе. (гдрим, ред.) бо представить каждую из них в одной из двух канонических форм, которые будут даны позднее. Таблица истинности. Эта таблица составляется для всех значений каждой из функций при всех возможных значениях двоичных переменных, входящих в нее. Следующий пример иллюстрирует использование такой таблицы. П р и м е р. м+м т ат+зт ат Из этой таблицы видно, что функции (а+ р)у и ау+ 1)у (А2.35) тождественны, т. е.
булева алгебра дистрибутивна. Числа О, 1, ... ..., 7, стоящие слева, взяты для облегчения перечисления двоичных переменных. Так, числу б соответствует число 110 в двоичной системе, откуда а = 1, р = 1, у = О. Канонические формы. Рассмотрим подмножества А„ Ам..., А„множества Е и соответствующие им характеристические функции хь хз, ..., х„которые будут называться также булевыми переменными. Имеем х, =), (х) =г" (А,; х), х,, = 1, (х) = Е (А,; х), (А2.36) х„= ~, (х) = Р (А„; х). Итак, если х~ А„ (1=1, 2,, „и).
(А2.37) Пусть (А2,38) Ф(А„А„..., Ал) — булева функция от и подмножеств и ( 1, если хенФ(Ао А„..., А„), 1 0 если хФФ(А А. А ) ее характеристическая функция. Сопоставим Ф(А„А„..., А„) 421 Ф(А1 Аз Аз)=(А| ПАз)() Аз (А2.40) сопоставляется гр (х„х„х,) = х,х, + х,, Очевидно, что ф(х~> ХМ ° ° ° г Х ) =ГЛ>(а л а ) (Х), (А2.41) так как по построению ( 1, если хенФ(Ао А„..., Ал), (А2.42) Рассмотрим функцию у=ф(хн хз, ..., хл) и положим (А2.43) у = х,г + х,а, где г и а — некоторые бинарные функции. Если х~=1> хз=О> то у=ф(1, хз, ..., хл)=г, (А2.44) (А2.45) и если х,=О, х,=1, то у=ф(0, х„..., хл)=а.
Итак, У Хгф (1> Хзг ° г Хл) '+ Хгф (0> Хм ° > Хл) ° (А2.46) (А2.47) Поступая аналогично с хз, имеем ф (1> хзг ° > хл) = хзф (1г 1> хм ° ° хл) + хзф (1 0 хз> ° хл) > (А2.48) ..., хл). (А2.49) ф(0, Хзг ° ° ° г Хл) = Хзф(0> 1> Хзг ° ° ° > Хл) Ч- Хзф(0> Ог Хзг Отсюда у=х,хзф(1г 1, х„..., хл) +х,х,ф(1, О, хз, ..., Хл) + $ хзхзф(0> 1, Хз, ..., Хл) '+ ХзХзр (О, О, хз> ° > Хл).
(А2.50) Действуя так же с хз, ..., хл, получим у =хзхзхз ... хл-зхлф(1> 1> 1> ...г 1, 1) з- -Ф- Хзхзхз... хл зхлф(1, 1, 1» . ° ° 1> 0) + + х,х х ... хл,х„ф (1, 1, 1, . °,, О, !) + +. х,х,х,... хл,хлф(1, 1, 1, ..., О, 0) + .. + х,хзхз ... хл,хл>р(0, О, О, ..., 1, 1) + + Хзхзхз Хл зхлф (0> 0> О> ° ° ° г 1> 0) + + х,х,хз... хл,хлф(0, О, О, ..., О, 1) ч- -1-х,хзхз...
Хл,хлф(0> О, О, ..., О, ). (А 2.51) 422 функцию ф(хо х„..., хл), заменяя в выражении для Ф под- множества А„А„..., А„соответственно переменными х,. х„..., хл, а операции (), Д, — соответственно на +, Например, Положим ') ф =»р(0, О, О,..., О, 0), ф, =»р(0, О, О,..., О, 1), ..., ф,з,=ф(1, 1, 1...,, 1, 0), ф,,л 1=ф(1, 1, 1,..., 1, 1), (А2,52) »Л1 = Х1Х2Хз, ..., Хо »хз, то = х1х2хз ... х„ 1х, (А2.53) т =ХХ2Х ...
Х Х1 У тзл 1=Х!Х2ХЗ ... Х Х. Тогда у = тофо+. т1ф1.+ ....+ т, 1фз 1. (А2.54) Форма (А2.54) называется дизъюнкгивной канонической формой, или первой канонической формой. Положим теперь у=и(хо х„..., х„)=(х1+г')(х,+.з'), (А2.55) где г' и з' — некоторые бинарные функции. Действуя, как и раньше, полагая сначала х,=! и х,=О, затем х,=! и х,=О и т. д., получаем у=[Х1'+Хо+ . ° . +Хз 1+Хо+р(0, О, ..., О, 0)! ° ' [Х» '+ Хз + ° ° ° + Х„1 + Х„+ !» (О, О, ..., О, 1)] ° ° [х, + х,+ ... + х„1+ х„[- !»(1, 1, ..., 1, О)] [х, + х,.+ ... + х„, + х„[- и (1, 1...
„1, 1)]. (А2.55) Обозначим М,= х, + х, + ... -+ х„, + х„, М, = х, + х, .+ ... -+ х„, .+ х„, ..., М,,=х, +-хз+ ... +-х,.+ х„, Мзз 1 = Х, +. Х,.+ ... + Х„, -[- Х»г (А2,57) Тогда ум = (Мзл 1 + !»о)(Мзз 2.+ !»1) . ' ' (М1'+ !»зя,) (Мо ! !»2н 1). (А2,58) Форма (А2.58) называется конъюнктивной канонической формой, или второй канонической формой. Можно доказать, что разложения (А2.54) и (А2.58) единственны.
Пример. Детали вычислений мы оставляем читателю. Пусть у = а (Ы + 6с) + а(з (с + й). ') За индекс 1 у »р» берется число, соответствующее двоичное разложение которого указано в скобках. Находим последовательно 1ро=О, % = 1, ЧЪ2 — — 1, !рай — — 1, 1р,=О, 1р3=0, 1ро= О, 1р1=0„ (А2.59) 1рз —— О, ЧЪ= 1, ф1о=О, 1рп= 1, 1рм — — 1, 4Р!3=1, 4р14=0, 1рм=О.
Для простоты выписываем члены т1 с ненулевыми коэффи- циентами! т1=аЬс41, то= аЬсгз, то= аЬс41, то=аЬсс(, (А2.60) т11 —— аЬсс(, т12 = аЬсс), т13 —— аЬсг(. Тогда У»! гн! + 1н2+' л23 + п13+ 1п11+ гн12+ 11113 Мз=а+Ь+с+д, М„=а+ Ь+ с+с(, М„=а+Ь+с+44, Мп —— а+Ь+с+а1, М„=а-+Ь+с+42. (А2.61) Тогда (А2.62) ум = МоМ,МЗМ,М,МоМ14М1,Мм Легко перейти от одной формы к другой, учитывая, что р1=1р11 (А2.63) (А2.64) Булевы уравнения.
Мы ограничимся здесь простейшими уравнениями. Рассмотрим уравнение с (х„хз, ..., х„) =! . (А2.65) Говорят, что это уравнение решено, если оно представлено в виде 4Ролзо+4Р,т!.+ ... +4Р4 !тз» 1=1, (А2.66) так как достаточно затем определить и-выборки (х„хз, . „х„), для которых У= 1. Уравнение с" (х„хз, ..., х„) =О (А2.67) сводится к (А2.68) Пример.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
