В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 21
Текст из файла (страница 21)
от всевозможных набо>» > ''' > ров переменных хь хъ ..., х„, причем коэффициент а,,; может равняться 1 или О, что показывает, входит данный конъюнктивный одночлен в сумму или нет. Булева функция~(хн ..., х„) называется линейной, если в представляющем ее полиноме Жегалкина отсутствую~ слагаемые, имеющие степень выше первой, т.е. если представляющий эту функцию полипом имеет вид ао + а,х, + ... + а„х„, причем постоянные коэффициенты ао, а„..., а„могут образовывать любой набор из 0 и 1. 5.1. Выпишите все полиномы Жегалкина от одной переменной. Сколько имеется различных таких полиномов? Решение. Нетрудно видеть, что каждый из этих полиномов О, 1, х, х+ 1 представляет собой соответствующую булеву функцию от одного аргумента. 5.2.
Выпишите все полиномы Жегалкина от двух переменных. Сколько имеется различных таких полиномов? Для каждой булевой функции от двух аргументов найдите представляющий ее полипом Жегалкина. Р е ш е н и е. Полипом Жегалкина от двух переменных х, у имеет следующий вид: аху+ Ьх+ су+ а'. Расставляя вместо коэффициентов а, Ь, с> й всевозможными способами константы 0 и 1, мы получим 24 = 16 различных полиномов Жегалкина от двух переменных. Укажем для каждого из них соответствующую булеву функцию от двух аргументов: Оху + Ох + Оу + 0 = 0 = Мо(х У)' Оху+ Ох+ Оу+ 1 = 1 =й~(х, У)> Оху + Ох + 1 у + 0 У К5(х> У) > Оху+Ох+ 1у+1 =У+ 1 =У'=йо(х У)' Оху+ 1х+ Оу+ 0 = х+хо(х, у); Оху+ 1х+ Оу+ 1 = х+ 1 = х' = йг(х У)' Оху+ 1х+ 1У+ 0 =х+ У Кб(х> У)> Оху+ 1хо- 1У+ 1 =х+у+ 1 =(х+ У) =хо+у 89(х>У)э 1ху + Ох + Оу + 0 = ху = «>(х, у); 1ху + Ох + Оу + 1 = ху + 1 = (ХУ) х! У ям(х> У)> 1ху+ Ох+ 1у+ 0 = ху+ у = (х+ 1)у = х'у = (х ~> у)' = (у -+ х)' = йо(х у); 1ху+Ох+ 1у+ 1=ху+у+ 1=х'у+ 1=(х'у)'=х»у'=у-ох=оп(х,у); 1ху+ 1х + Оу+ 0 = ху+ х = х(у+ 1) = ху = (х ' ' у) (х + у) 82(х> у)> 1ху+ 1х+ОУ+1=ху+х+1=ху'+ 1=(ху')'=х'»у=х-+у=аз(х,у); 1ху + 1х+ 1у + 0 = ху+ х+ у = х(у + 1) + у = ху' + у = ((ху' -+ У)(У -+ -+ХУ )) = ((Х '4УЧ )>)(У ЧХУ )) =((Х '4 У)У ) = (ХУ ) =ХЧ У=59(Х> У)> 1ху + 1х + 1у + 1 = ху + х + у + 1 = (х» у) + 1 = (х ~> у)' = х 4, у = = яо(х, у).
5.3. Докажите, что имеется 2'" различных полиномов Жегалкина от н переменных. 102 Р е ш е н и е. Сначала нужно подсчитать, сколько всевозможных конъюнктивных (не обязательно совершенных) одночленов от л переменных х„хъ ..., х„существует. В предыдущей задаче перечислены все от двух переменных ху, х, у, а (сопя!).
Их четыре. От трех переменных — восемь: ху~, ху, хг, ух, х, у, х, а (сопя!). Комбинаторика позволяет подсчитать их число для произвольного и. Конъюнктивных одночленов от 0 переменных — С„', от 1 переменной — С„', от 2 переменных — С„', ..., от и переменных — С~. Всего число одночленов от и переменных равно С~ + + С„'+ С~+ ... + С„" = 2". Чтобы теперь получить полиномы Жегалкина, нужно около каждого из 2" конъюнктивных одночленов поставить (умножить на) 0 или 1 и результаты сложить. (Для случая и = 2 эта процедура подробно проделана в предыдущей задаче.) Таким образом, полиномов будет столько, сколько существует наборов, составленных из 0 и 1 длины 2".
А эту задачу мы уже решали при подсчете числа булевых функций от л аргументов. Таких наборов и, значит, полиномов Жегалкина будет 2'". 5.4. Докажите, что всякая булева функция обладает единственным (с точностью до порядка слагаемых и сомножителей) представляющим ее полиномом Жегалкина. Р е ш е н и е. Мы знаем, что как число всех булевых функций от п аргументов, так и число всех полиномов Жегалкина от и переменных (предыдущая задача) равно 2'". Это означает, что каждой булевой функции соответствует единственный полипом Жегалкина. Остается одна деталь.
В предыдущей задаче мы все-таки не доказали, что различные полиномы Жегалкина задают различные булевы функции. Покажем это. Пусть полиномы р(х„..., х„) и д(хь ..., х„) различны. Это означает, что в одном из них, например в р(х„..., х„), имеется слагаемое з = х... х,, ..., х,, не содержащееся в другом. Допустим, что выбранное слагаемое имеет наименьшее возможное число букв, так что все слагаемые, имеющие менее чем /с букв, одинаковы в обоих полиномах. Рассмотрим теперь двоичный набор с длины и, составленный из 0 и 1 так, что для всех переменных, входящих в з, значения равны 1, а для всех остальных переменных значения равны О. Покажем, что на этом наборе полиномы р и д принимают разные значения: р(о) ~ д(с). Ясно, что на этом наборе значений переменных любое слагаемое как первого, так и второго поли- нома, отличное от з и содержащее равное с ним или большее число переменных, обращается в О, так как содержит переменные, не входящие в к Само слагаемое з принимает на этом наборе значение 1.
В итоге первый полипом р(х„..., х„) примет значение 1 + рм где ро — значение, которое примет сумма тех конъюнктивных одночленов, которые содержат меньшее по сравнению с одночленом з число переменных. Аналогично, вто- 103 рой полипом д(хь ..., х„) примет значение д„где да — значе- ние, принимаемое суммой тех конъюнктивных одночленов из д, которые также содержат меньшее, чем в одночлене з, число переменных.
Но такие одночлены в р и д, согласно выбору з, одинаковы. Значит, у, = да. Но тогда 1 + ра ~ Е. Следовательно, р(о) ~ д(о), и полиномы р и д задают различные булевы функ- ции. Утверждение доказано. 5.5. Если в совершенной дизъюнктивной нормальной форме, представляющей булеву функцию, произвести замену всех знаков дизъюнкции знаками суммы Жегалкина, а все отрицаемые пере- менные заменить согласно тождеству х' = х+ 1, то получится вы- ражение, содержащее из булевых функций лишь конъюнкцию и сумму Жегалкина и представляющее ту же булеву функцию, что и исходная СДН-форма.
Докажите данное утверждение. 5.6. Для следующих булевых функций найдите представляющий их полипом Жегалкина: а) х'(у~' ч у'~); ж) х(у -+ ~) ч (х'у ч ху'Нх+ 1); б) (х -+ (у — э ~')Ну~' -+ х); з) х 'ч уч х', в) (х+ 1Ну+ 1)г' ч ух; и) х у ~' ч х у~' ч х уч ч худ ч хуг.', г) х'~' ч (х'у ч ху')~; к) харч (х+ х)уч х'~', д) х~у~~чхх; л) х ~ ч (х ~чх~ )учху ~ .
е) (х'чуч~)(хчуч~'Нх'чу'ч~); Решение. л) Для нахождения полинома Жегалкина нужно выразить все встречающиеся в данном выражении булевы функ- ции через сумму Жегалкина (сложение по модулю 2) и конъюнк- цию, а затем, пользуясь свойствами функций, максимально уп- ростить полученное выражение. Проделаем это для данной буле- вой функции: х'х' ч (х'~ ч х~')у ч ху'~' = (х' ч ху')~' ч (х'х+ х~')у = =(х'+ху')~'ч (х'у~ ~- худ') = (х'г.' + ху'~') ч (х'у~ + ху~') =(х'~' + + ху'х'Нх'у~ + ху~') + х'~' + ху'~' + х'у~ + худ' = х'~' + ху'~' + х'ух + + ху~'= (х+ 1Н~+ 1)+х(у+!Н~+1) + (х+ 1)у~+ху(~+ 1) = х~+ х+ + ~+ 1+ ху~+ ху+ х~+ х+ худ+ ух+ хух+ху = ху~+ у~+ ~+ 1.
5.7. Выясните, верны ли следующие равенства, отыскав поли- номы Жегалкина, представляющие булевы функции в обеих час- тях этого равенства: а) х -+ (у -+ ~) = (х -+ у) -+ (х -+ ~); б) (ху -+ х) -+ (х -+ ~) = х' ч у ч ~; в) ху -+ х = (х -+ ~Ну -+ ~); г) (х ++ уНху' ч у) = ху; д) (х ++ у')' = х ++ у; е) г -+ (х ч у) = (~ -+ х) -+ (х -+ у); ж) х ++ у = (Х2 ++ у~Н(х 'ч ~) ++ (у ч ~))1 з) ху ч (~ -+ х) = х' -+ ~', и) (х -+ у) -+ ~ = х -+ (у -+ ~); к) ((х -+ ~Ну -+ ~)) = ((х ч у) -+ ~); л) х ++ у = ху ч х'у'. 104 Решение.
л) Для функции в левой части равенства имеем: х с-» у = (х+ у)' = х+ у+ 1 . Для функции в правой части равенства находим: хуч х у' = хух у'+ху+ х у' = О+ ху+ (х+ 1)(у+ 1) =ху+ ху+ + х + у+ 1 = х+ у+ 1. Следовательно, рассматриваемое равенство действительно выполняется. 5.8. Отыскав для каждой из следующих булевых функций пред- ставляющий ее полипом Жегалкина, установите, какие из функ- ций тождественно равны 1, а какие — 0: а) (у -+ ~) -» ((х — » у) -» (х -» г)); б) х-»(х'-»у); в) (х -» у) -» ((х -» (у -» а)) -» (х -» ~); г) ((х -» у) -» х) -» х; д) (х-» (у-» х)) -» ((у' -» х')' (х-» у)); е) (х -» у~) -» ((х -» у) -» (х -» а)); ж) х' -» (х -+ у); з) (х-» (у-» а))(х-»у)(х-» а)', и) ((х -» у) -» (у' -» х')) -» ((у' -» х') -» (х -» у)); к) (х' ч (у -» х))', л) (хчу)'чх'учх Р е ш е н и е. л) Находим полипом Жегалкина для данной функ- ции: (х ч у)' ч х'у ч х = (ху + х + у + 1) ч (х + 1) у ч х = (ху + +х+у+1) ч (ху+у) чх=(ху+х+у+1) ч(ху+ух+ху+ + у + х) = (ху + х + у + 1) ч (ху + х + у) = ху + ху + ху + ху+ +ху+х+ху+х+ху+ху+у+у+ху+х+у+1+х+у+ху=1.
5.9. Проверьте, что каждая булева функция от одного аргумен- та линейна. 5.10. Найдите все линейные булевы функции от двух аргумен- тов. Сколько имеется таких функций? 5.11. Докажите, по всего имеется 2" " линейных булевых функ- ций от л аргументов. Р е ш е н и е. Число таких функций равно числу двоичных набо- ров длины л+ 1. Таких наборов, как мы знаем, имеется 2" ' штук. Все получающиеся при этом булевы функции будут различны, так как различны будут представляющие их полиномы Жегалкина. 5.12. Докажите, что все следующие булевы функции линейны: а) х'у'~чху'~'чх'у~чху~; б) ((х ч у ч ~) -+ ху~') ч (х+ у)~; в) (х'уч ху')~' ч (х+у)а; г) (х+у)~ч (х'у' ч ху)а; д) х'у~ч (х+ я+ 1)у' ч ху~', е) ((хчуч~')-+ху'г.')ч(х'г.чх~')у; ж) х'ус' ч х'у~ ч ху~' ч худ; з) х'(у'~ ч у~') ч (у + а)х; и) (х ч у' ч фх ч у' ч г,')(х' ч у' ч С)(х 'ч х' ч ~'); к) ху~' ч ((х' ч у ч ~) -» худ) ч х'у'~; л) худ ч ху'~ч х'у~' ч х'у'~'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
