В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 22
Текст из файла (страница 22)
105 Р е ш е н и е. л) Для доказательства нужно найти полипом Же- гапкина данной функции и убедиться в том, что степень этого полинома не выше первой. Полипом отыскивается следующим образом. Нужно выразить все встречающиеся в данном выраже- нии булевы функции через сумму Жегалкина и конъюнкцию, а затем, пользуясь свойствами этих функций, максимально упрос- тить полученное выражение: худ ч ху г ч худ' ч худ' = хх(у ч у)ч х~' ч (у ч у) = харч х~' = = хх ч (х+ 1)(я+ 1) = харч (х~+ х+ х+ 1) = хх(х~+ х+ я+ 1) + хг+ + хе+ х+ я+ 1 = хе+ ха+ ха+ х~+х+ ~+ 1 =х+ ~+ 1.
Полученный полипом Жегалкина есть полипом первой степе- ни, и, следовательно, данная булева функция линейна. 5.13. Выясните, какие из следующих функций линейны: а) х'у'~'чх'у'~чх'у~члух', б) х'у'~' чх'уг'чхух'члу~; в) (хчуч ~')(хчу' ч ~')(х 'чуч 2')(х 'чу 'ч я); г) (ху-+х)'ч (х'чу')(хчу)х; д) х'(у+ х) ч ((х ч у ч ~) -+ х'уя); е) х'-+ (уч ~'); ж) луч ху'~ ч худ', з) ((х' -+ у)' -+ ~)', и) х'(у'~чу') ч (у+ х+ 1)х; к) (ух' + х) -+ (х ++ ху')', л) ((х ч у ч г) -+ ху'г) ч (х'г. ч хг,')у ч ху'г.'. Решение. л) Представим данную функцию полиномом Же- галкина.
Для этого используем свойства булевых функций и выра- зим все встречающиеся в данном выражении функции через сум- му Жегалкина и конъюнкцию, а затем упростим полученное вы- ражение: ((х ч у ч я) -+ ху'~) ч (х'х ч х~')у ч ху'х' = ((х ч у ч е)' ч ху'х) ч ((х+ + 1)я ч х(х + 1))у ч ху~' = х у~' ч ху~ ч худ' '/ ((хе + 2) ч (хх + х))у = = (х' ч х)у'х' ч ху'е ч ((х~ + х)(х~ + х) + (хх + я) + (х~ + х))у = у'~' ч ч луг ч (х~+х~+ а+хе+ ~+х))у=у'(~' чхни) ч (х+ ~)у=у ((~' ч х). (~ ч я)) '/ (лу+ уя) + (х'/2 )у ч (лу+ух) = (х2 +х+ е )у '/ (ху+ уе) = = (ху~~~ + ху~ + у 2 ) ч (ху + уя) = ('9/х + ху + хя + х + ху + х + уя + у + +~+ 1) ч (ху+ ух) =(худ+ хам+ух+у+ я+ 1) ч (ху+ух) = худ+ хе+ + ух + у + ~ + 1 + ху+ уя = худ + худ + луе + ху + худ + лу + худ + хну+ + у~ + ух + ух + у~ + худ ~- хе + у + ~ + 1 + ху = ху~ + ху + хх + у + х + 1.
Поскольку полученный полипом Жегалкина кроме слагаемых первой и нулевой степени у, х содержит слагаемые второй степе- ни ху и хх, а также третьей степени ху~, то данная булева функция не является линейной. 5.14. Докажите, что суперпозиция любого числа линейных бу- левых функций является снова линейной булевой функцией. Мо- жет ли суперпозиция нелинейных функций дать функцию ли- нейную? 106 5.15. Покажите, что если в линейной булевой функции отождествить два или более аргументов, то снова получится линейная булева функция.
5.16. Приведите примеры нелинейных булевых функций, отождествление в которых двух или большего числа аргументов приводит к линейной булевой функции. 5.17. Приведите примеры нелинейных булевых функций, отождествление в которых двух или большего числа аргументов приводит к нелинейным функциям.
5. 18. Приведите примеры нелинейных булевых функций от трех аргументов, в которых нельзя отождествлением их аргументов получить нелинейную функцию от двух аргументов. Двойственность и самодвойствениые булевы функции. Булева функция ~*(хн ..., х„) называется двойственной по отношению к булевой функции Дхн ..., х„), если Ц~(хн ..., х„))' = 7(х,', ..., х„'). Булева функция называется самодвойственной, если двойственная к ней функция совпадает с ней самой. Для булевой функции 7(хн хц ..., х„) от и аргументов обозначим черезов«; = 0) булеву функцию Яхн ...,х; и О,х„„...,х„) от и — 1 аргументов, получающуюся из данной функции заменой всех вхождений ее аргумента х, значением О. Аналогично обозначение 7(х; = 1).
Говорят, что булева функция Яхн хп ..., х„) существенно зависит от своего аргумента хь если Ях; = 0) «Ях; = 1). Говорят, что булева функцияЯ«ь хв ..., х„) зависит от аргумента х; несущественно (или что аргумент х; фиктивный), если ~(х, = 0) = у(х; = 1). 5.19. Для каждой булевой функции от одного аргумента найдите двойственную ей булеву функцию.
5.20. Для каждой булевой функции от двух аргументов найдите двойственную ей булеву функцию. Решение. Используя обозначения Учебника (9 9) для булевых функций, найдем двойственные для них функции: Ко(х~ у) = (Ке(х > у'))'= 0' = 1 = йц(х~ у)1 87(х, у) = (я,(х', у'))' = (х'у')' = х" ч у" = х ч у = 8в(х, у); 8«2(х, У) = (йг(х',У))'=((х'-+У))'=х' чУ'=У'чх=(У-+х)=йп(х,У); Яз(«у) = (вз(х У))'=(«) =«=Яз(» У) 5.21.
Для следующих булевых функций найдите двойственные функции. Представьте найденные функции их СДН-формами: а) х'уг. ч ху'~' ч худ; б) «'ут ч х'уг. ' ч ху'с ч ху'с'; в) х (у + с) ч ((х' ч у ч с) -+ (х'ус)); г) (с-+(хчу))'чх(у+~); д) худ+ ху+ хс+ с; е) х'у ч (с -+ х)', ж) (я -+ х )(х -+ у); з) (х -+ (с -+ у)) (х -+ (~ -+ у')); и) х у с ч х уя ч ху ~ ч ху ~ ч «ус) 107 к) х'у'чачу'~', л) (х'-+ ~)' ч (х-+ ~)у'. Р е ш е н и е. л) Обозначим)(х, у, т) = (х' -+ ~)' ч (х -+ ~)у'. Най- дем функцию, двойственную для )(х, у, ~): )'"(х, у, ~) = ()'(х', у', ~'))' = ((х -+ т')' ч (х' -+ ~')у)' = (х -+ ~')" ((х' -+ -+ ~')у)' = (х -+ ~'К(х' -+ ~')'ч у ) = (х 'ч ~')((х ч ~')'ч у") = (х 'ч ~')(х'~ ч чу ) =х'(х'~чу ) ч ~'(х ~чу ) =х х'~чху' ч ~'х ~ч ~'у'=ху 'ч х'~чу ~'. Представим)'" в виде СДН-формы: )р' = х'у 'ч х'г, ч у'~' = х'у'(~ ч г.') ч х'(у ч у')~ч (х ч х')у'~' = х'у'~ ч чхуг чхуечхугчхуг, чху~ =ху2 чху~чхут чхух.
5.22. Докажите, что в каждой из следующих пар булевых функ- ций одна из функций двойственна другой: а) худ + у~ + у + 1, худ+ ху + х~+ х+ у+ 1; б) ху+ х~+ х+у+ ~, ху+ хт+ х; в) ху~+ху+ ~, ху~+ х~+у~; г) ху+ у2+ х+ у+ е+ 1> ху+ уя+ у+ 1; д) ху~+ ху+ х+ у, ху~+х~+у~+ х+у+ ~+ 1; е)ху+х+у+е+1,ху+е; ж) худ+ х+ 1р хуг+ ху+ х~+ у2+ у+ г.р з) ху+ у~+ х+ 1, ху+у~+ ~+ 1; и) ху2+ ху+ ха+ у+ 1> хух+ у1+ х+ у; к) ху~+ х+ ~, ху~+ ху+ х~+ у~+у; л) у~+ х+у, ух+ х+ ~.
Решение. л) Найдем двойственную функцию для данной функции)(х, у, я) = у~+ х+ у: ~* = (у ~' + х' + у )' = у т' + х' + у'+ + 1 = (у+ 1)(~+ 1)+ (х+ 1) + (у+ 1)+ 1 =ут+у+ ~+ 1+х+ 1+у+ + 1 + 1 = ух+ х+ ~, что и требовалось доказать. 5.23. Покажите, что для следующих булевых функций двой- ственные функции совпадают с их отрицанием: а) х(у + я + 1) + у~; ж) ху~ч ху'~ ч х'у~' ч х'у'~', б) х'у~"чху'~; з) ((хчучх)-+у~)чху~'чх'у'г; в) х'у~'чх'у~чху'т'чху'~; и) (х+ е+ 1)у+хе+ 1; г) (х+ я)(у+ 1) +ху+ух; к) ху+х~+у~+х+ 1; д) ху+х~+у~+х+у+~; л) ху+х~+у~+ ~. е) ху~чх'у'~', Р е ш е н и е.
л) )(х, у, ~) = ху + х~ + у~ + т. Найдем для функции Ях, у, ~) двойственную функцию:/"" = (х у'+ х~'+у ~'+ 2)' = х у'+ + х'е' + у'~' + ~' + 1 = (х + 1)(у+ 1) + (х + 1)(~ + 1) + (у + 1)(~ + 1) + + е+ 1+ 1 =ху+х+у+ 1+х~+х+ ~+ 1+ух+у+ г+ 1+~=ху+х~+ + уя + г + 1 = (ху + х~ + уе + ~)' =)'(х, у, ~). Итак, двойственная функция для)'совпала с отрицанием функции)'. )'" =)'. 5.24. Найдите все самодвойственные булевы функции от одно- го аргумента. 5.25. Найдите все самодвойственные булевы функции от двух аргументов.
Сколько из них существенно зависят от всех своих аргументов? 108 Р е ш е н и е. Проанализировав решение задачи 5.20, обнаружи- ваем четыре самодвойственные функции от двух аргументов: а1(х> у) = х> а5(х> у) = )» ф)](х> у) у > яц(х> у) х . Как Видим> все они от одного из аргументов зависят несущественно, т.е. фак- тически являются функциями одного аргумента. 5.26. Докажите, что следующие булевы функции самодвой- ственны: а) х(~-+ у) ч (у-+ ~)', б) х'угчху'~чх'у'гчх'у'г', В) ху'4 «2чут; г) х'учх'~'чу', д) ху+ хг+уг+ у+ г; е) х'уг' ч х'уя ч ху~' ч худ; ж) х'у'~ч«'уг' ч «у'~' ч худ; з) ха + (х+ я)(у + 1); и) (х — эу)'(г-+ ~) 4(хчу)'(«-+ г); к) (х 'ч уч я)(х 'чуч ~')(х 'чу' ч я)(х 'чу' ч г'); л) ху'ч«~'чу'г'.
Р е ш е н и е. л) г(х, у, я) = ху' ч х~' ч у'~'. Для доказательства самодвойственности функции Ях, у, г) найдем ее двойственную: у'~(х> у> г) = (х у'4 х г ч у~) = (х '4 у )(х '4 я )(у ' ' г ) = (х ч у я )(у '4 ч ~') = ху'ч «г ' ч у'г.' ч у'г.' = ху' ч х~' ч у'~' =у (х, у, г), что и требо- валось доказать. 5.27. Выясните, какие из следующих булевых функций само- двойственны: а) х'у'чх'«'чу'г'; ж) х'уг' ч х'угч ху'г' ч ху~' ч «у~а б) х'уг ч «у'г ч хуг.'1 з) ((х ч у ч я) -+ х'уя) ч х(у + я+ 1); в) ху+ х~+ уг; и) хугчх'у~'чху'~'чх'у'г', г) (х "4 г)у 'ч (х 'ч у)г' ч хуг; к) ху~'ч хуг' ч х>у~> ч х>у>г>; д) ((х-+у)+ 1)(г+ 1) чху'г; л) (х+1)(у-+ г)'ч(х+у)г. е) ху~'ч ху'т ч х'уя ч хуг.; Р е ш е н и е.
л) Ях, у, г) = (х+ 1)(у-+ я)' ч (х+ у)г.. Найдем снача- ла СДН-форму для данной функции: у(х, у, я) = (х + 1)(у -+ я)' 4 ч (х + у)г = х (у' ч «) ч (х ++ у) г = х уг' ч ((х' ч у)(«ч у>))>г = х у„' 4 ч (ху' ч х'у)г = х'уг "ч ху'«ч х'уг. Затем найдем функцию, двойственную г", и также представим ее в виде СДН-формы: ~ = (ху'г ч х'уг 'ч ху'г')' = (х' ч у ч т)(х ч у 'ч ч ~ИХ 'ч у ч Г) = (х 'ч у)(х ч у' ч г) = х'у' ч х'Г ч хуч уя = «'у'~' ч х'у'т. ч ч ху«ч ху«ч хуг. 'ч худ ч хуг ч хуГ = х у~'ч «у'~ ч «у« ч хуг.' ч худ Поскольку функции У и у>* имеют различные СДН-формы, то и сами зти функции различны: ~' ~ у". Следовательно, функция у несамодвойственна.
5.28. Докажите, что функция четности р„(х„..., х„) = х, + ... + х„ является самодвойственной тогда и только тогда, когда и нечетно. 5.29. Как найти таблицу значений двойственной функции, если известна таблица значений исходной функции? Найдите таблицу 109 значений двойственной функции для булевых функций, заданных следующей таблицей своих значений: Решение. Обратите внимание на то, что в выбранной нами последовательности наборов значений аргументов взаимно дополняющие друг друга наборы (т.е. наборы вида (а, Ь, с) и (а', Ь', с')) располагаются симметрично относительно средней горизонтальной линии таблицы. Теперь вспомните определение двойственной функции.
Вот таблица значений функции, двойственной для функции л): 01010001 (вместо столбца записана в строку). Таким образом, каждая из двух половин столбца значений функции ~* анти- симметрична противоположной половине столбца значений функ- цииГ, т.е. получается из этой половины симметричным отражением относительно средней полужирной линии таблицы и последующим отрицанием. 5.30.
Каким свойством обладает таблица значений самодвойственной булевой функции? Какие из булевых функций, приведенных в задаче 5.29, самодвойственны? Решение. В силу рассуждений, проделанных при решении предыдущей задачи, столбец значений самодвойственной булевой функции антисимметричен относительно своей средней линии, т.е. каждое значение в этом столбце равно отрицанию симметричного ему значения относительно средней линии таблицы. Но наборы значений аргументов, симметричные относительно средней линии, противоположны, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
