Новиков Ф.А. Дискретная математика для программистов (860615), страница 25
Текст из файла (страница 25)
Рассмотрим отрицание и введём обозначение </?(х): = х. Имеем: <р g Т0, таккак ip(Q) = 1, <f Т\, так как <р( 1) = 0, <р 0 T<j, так как 0 < 1, по <^(0) > </?(1).С другой стороны, (р G Т*, так как <р*(х) = Тр(х) - -чр(->х) == х = v?(x),и (р G Ть, так как (р(х) = х + 1.2. Рассмотрим конъюнкцию и введём обозначение ф(х, у): = хАу. Имеем: ф £ Т0,так как 0 Л 0 = 0, ф Е Т\, так как 1 Л 1 = 1, ф е Т^, так как ф( 1,1) = 1, иV (а, Ь) ф (1,1) ((а, b) ^ (1,1) & ф(а, Ь) = 0). С другой стороны, ф £ Т*, так какф*(х, у) — х V у, и ф £ TL. Действительно, от противпого, пусть ф(х, у) = ах ++ by + с.
Тогда имеем: если х = 0 и у = 0, то а0 + ЬО + с = 0, и значит, с = 0;если х = 0 и у = 1, то аО + Ь1 + 0 = 0, и значит, 6 = 0; если х = 1 и у = 0, тоa l + 0- 0 + 0 = 0, и значит, а = 0; если х = 1 и у = 1 , то 0 - 1 + 0 - 1 + 0 = 1, изначит, 0 = 1 — противоречие.ТЕОРЕМАКлассыТ0, ТЬТ*,Т Т Lзамкнуты.Чтобы доказать, что некоторый класс F замкнут, достаточнопоказать, что если функция реализована в виде формулы над F, то она принадлежит F.
Доказать, что произвольная формула обладает заданным свойством, можно с помощью индукции по структуре формулы (см. 3.3.3). База индукции очевидна: функции из F реализованы как тривиальные формулы над F. Таким образом, осталось обосновать индукционные переходы для пяти рассматриваемыхклассов.ДОКАЗАТЕЛЬСТВО[Го] Пусть / , / i , . . . , / n е Т 0 и Ф = f(fi(x1,...,xn),...,fn(x1,...,xn)).Ф(0,...,0) = / ( / i ( 00)Тогда/™(0,...,0)) = / ( 0 , . .
. , 0 ) = 0 .Следовательно, Ф € То.[ 7 \ ]Пусть / , / ! , . . . , / „ е Г 1 и Ф = / ( / 1 ( х 1 ) . . . , Х п ) , . . . ,fn(х 1 , . . . , хп )). ТогдаФ(1,...,1) = / ( / 1 ( 1 , . . . , 1 ) , . . . , / п ( 1 , . . . , 1 ) = / ( 1 , . . . , 1 ) = 1.Следовательно, Ф £ Т\.[Т* ] Пусть / , / ь . . . , / п G Т* и Ф = f ( f i {х\,...,Ф* =f*U*{xu... ,хп),...,хп),...,fn(x\, • • •, хп)). Тогдаf*{xu ...
,хп)) == / ( / i ( x b . . . , x n ) , . . . , / n ( x i , . . . , x n ) ) = Ф.Следовательно, Ф е Т*.[ T-g ] Пусть / , / i , . . . , / „ €и Ф = / ( / l (X!,... ) Хп), . . . , fn{x\ , ... , Хп )). Тогдаa < 0 = K / i ( a ) , . . . , / n ( a ) ) ^ (/i (/?),..., Ш))=>= » / ( / i ( a ) , • • •, / п И ) ^ f ( f i W ) , - - -, Ш))Следовательно, Ф б Г ^ .= • Ф(а) < Ф(/5).130Глава 3. Булевы функции[ TL ] Пусть / , / 1 , . . . , / п е Г £ , и Ф = / ( / 1 ( z i , . .
. ) XFL ))•••) fn {x 1 1 • • • ) Xn )). Тогда/ = CO + CIXI + . . . +f i = Cq + C\X 1 + ...fn= c0cnxn,-hc^XN,C1 X\ + . . . + 71 71 •Подставим эти формулы в формулу для Ф. Имеем:Ф(Я1, . . . , хп) = Со + Ci (cj + с\х 1 + . . . += do + d\X\ + ... + dnxn.С^ХП) + . . . + СП (Со + С^Х 1 +•Следовательно, Ф е 7L.Пример Таблица принадлежности некоторых булевых функций рассмотренным замкнутым классам:01хXI ЛХ2То++Ti++Г»+-Г^+++Ть+++-Таким образом, рассмотренные классы То, Ть Т*, Т^, Ть попарно различны, непусты и не совпадают с Рп.3.5.2. Полные системы функцийКласс функций F называется полным, если его замыкание совпадает с Рп:[F] = Рп.Другими словами, множество функций F образует полную систему, если любаяфункция реализуема в виде формулы над F.ТЕОРЕМАПусть заданы две системы функций:F = {fi,...Jm}иG={gi,...,gk}.Тогда, если система F полна и все функции из F реализуемы формулами над G, тосистема G также полна:([F] = Pnk\/ieДОКАЗАТЕЛЬСТВО=>h = funcl..m ( f i = funcg<[G]))[G] = Pn.Пусть h — произвольная функция, h е Рп- Тогда [F] = Рп{ 9г / //г} — формула над G.
Следовательно, h = func S [G].•1313.5. ПолнотаПример Система { V , Л, —>} — полная, как показано в подразделе 3.4.2. Следовательно:1)система {—>, Л } полная, так как х\2)СИСТЕМА { - > , V } ПОЛНАЯ, ТАК КАК Х \ Л Х 2 =V Х 2 = - | ( _ | X I Л -1X2);V -1X2);система {|} полная, так как ->х = х \ х, X I A X 2 = ->(XI | Х 2 ) = ( X I | Х 2 ) | ( X I | Х 2 ) ;4) система {0,1, Л, + } полная, так как ->х = Х + 1 (здесь + означает сложение помодулю 2). Представление булевой функции над базисом {0,1, Л, +} называется полиномом Жегалкина1.
Таким образом, всякая булева функция представимав виде3)(ilt...,is)ГДЕ— СЛОЖЕНИЕ ПО МОДУЛЮ 2 , ЗНАК • ОБОЗНАЧАЕТ КОНЪЮНКЦИЮ И CLill...yisG F2.ЗАМЕЧАНИЕФактически, в полиноме Жегалкина ^aii,...,i e XiiXis = J 2 x h ' ' ' хгв< поскольку еслиa,ilt...,i3= 1, то этот коэффициент можно опустить, а если a , i l t .
. . t i a — 0, то можно опуститьвсе слагаемое. Знак конъюнкции обычно также опускают.3.5.3. Полнота двойственной системыЕсли система F = {/1, • • •, Д} полна, то система двойственных функций F* = { f \ , • • •, f k ) также полна.ТЕОРЕМАПусть h — произвольная функция, h е Рп. Рассмотрим двойственную функцию h*.
Система F полна, так что h* = func !K[F]. По принципудвойственности h = funcCK*[F*].•ДОКАЗАТЕЛЬСТВОПримерполна.Система {0,1, А, + } полна, следовательно, система {1,0, V, = } также3.5.4. Теорема ПостаТеорема Поста устанавливает необходимые и достаточные условия полноты системы булевых функций.(Пост) Система булевых функций F полна тогда и только тогда, когдаона содержит хотя бы одну функцию, не сохраняющую нуль, хотя бы одну функцию, не сохраняющую единицу, хотя бы одну несамодвойственную функцию, хотябы одну немонотонную функцию и хотя бы одну нелинейную функцию:ТЕОРЕМА[F] = Рп1~>(F C T Q V F C T I V F C T + V F C T ^ V F CИвам Иванович Жегалкин ( 1 8 6 9 - 1 9 4 7 ) .TL).132Глава 3. Булевы функцииДОКАЗАТЕЛЬСТВО[ Необходимость ] От противного. Пусть [F] = Рп иFСТ0VFС TI VFСТ* V FСТ-VFСTL.Введем обозначение: г — один из индексов, 0, 1, *, ^ или L.Тогда Ti = [Ti] = > [F] с Ti = > Рп с Г*Рп = Ти по Рп ф Ti по таблице изподраздела 3.5.1.[ Достаточность ] Пусть ->(F c T 0 V F c T i V F c T + V F c T ^ V F c TL).
Тогда3 F' = (foJiJ*,UJb)(fo?T0& /1 g Ti & Д g T* & Д& fLtTL).Функции /о, / i , /*, /<;, fb не обязательно различны и не обязательно исчерпывают F. Покажем, что отрицание и конъюнкция реализуются в виде формул над F'.Тем самым теорема будет доказана (см. 3.5.2). Построение проводится в три этапа: на первом строятся формулы, реализующие константы 0 и 1, которые нужнына третьем этапе. На втором этапе строится формула, реализующая отрицание.На третьем этапе строится формула, реализующая конъюнкцию.[Константы] Построим формулу, реализующую 1.
Пусть (р(х): = fo(x,...,Тогдар(0) =ж)./о(0,...,0)^0=»у>(0)==1.Возможны два случая: с/?(1) = 1 или <р(\) = 0. Пусть <^(1) = 1. В этом случаеформула <р реализует 1. Пусть </р(1) = 0. В этом случае формула ip реализуетотрицание. Тогда рассмотрим функцию /*. Имеем:/* £ Т* =>• 3 a i , . . . , а п ( / * ( a i , . . . ,а п ) ф / * ( а ь . . . ,а п )) .Следовательно, / * ( a i , . . . , а п ) = / * ( а ь .
. . , а п ). Пусть теперь ф(х)\ = / * ( x a i , . . . , x a ").Тогдаф(0) = Д ( 0 а 1 , • • • ,0 a ") = /*(ai,...=/*(ai, • • •,o-n) — / * ( lai,an) =l a " ) = V'(l)-Таким образом, -0(0) = -0(1), откуда ф = 1 или ф = 0. Если ф = 1, то требуемаякопстапта 1 построена. В противном случае ф реализует 0, и значит, <р(ф(х)) —= ф(х) реализует 1.Построение 0 аналогично, только вместо /о нужно использовать Д.[ Отрицание ] Построим формулу, реализующую отрицание.Рассмотрим функциюU?Tz=*3a=Имеем:( а ь . . .
,а п ),/? = (6 Ь . . . , Ъп) (а ^ (3 & /<(<*) > /<(/?)).Тогда а ^ /3 = > Vi (a* = ^ V а* — 0 & bi = 1). НоФ U(P) =>аф(3=>33^ l..n ( j € J = » а,- = 0 & Ь, = 1).Другими словами, J — это множество индексов j, для которых a j ф bj. Пусть{р[х): = / ^ ( c i , . . . ,c n ), где Cj : = х, если j е J, и Cj : = aj(= bj), если j £ J. Тогда y>(0) = / ^ ( C l , . . . , C n ) { 0 / / x } = U ( a ) > U((3) = / < ( с 1 , . .
. , с „ ) { 1 / / х } = у>(1).Имеем: </?(0) > </?(!) = > </>(0) = 1 & <p(l) = 0 => <p(x) = x.1333.6. Представление булевых функций в программах[ Конъюнкция ] Построим формулу, реализующую конъюнкцию. Рассмотрим функцию f i . Имеем:Но /L ^ TL, следовательно, в полиноме Жегалкииа существует нелинейное слагаемое, содержащее конъюнкцию по крайней мере двух переменных. Пусть, дляопределённости, это х\ и х 2 . Тогдаfb=X1 -X2- fa(x3,+ X2 • /c(X3,. .
. ,X„) + Xi • fb{x3, ...,Xn)...,!„)+ fd(x3,+X N ),причём fa{x3,...,хп) ф 0. Следовательно, 3 а3,..., ап ( / а ( а 3 , . . . , ап) = 1). ПустьЬ: = / ь ( а з , . . . , а„), с: = / с ( а 3 , . . . , ап), d: = /<*(а 3 ,..., ап) и<р(хi,x2): = Д ( х 1 , х 2 , а 3 , . . . , а„) = xi • х2 + b • х\ + с • х2 + d.Пусть далее ф(х\,х2):= ф ( х \ + с,х 2 + b) + fc • с + d.
ТогдаФ(х\, ж2) = (xi + с) • (ж2 + b) + b • (xi + с) + с • (х2 + b) + d + b • с + d == xi-x2+ c-x2+b-xi+b-c+ b-xi+b-c+ c-x2+ b- c ++ d + b- c + d = xi • x2.(Функции x + а выразимы, так как х + 1 = х, х + 0 = х, а константы 0, 1и отрицание уже построены.)•Пример В системе {-sA} отрицание не сохраняет констант и немонотонно, аконъюнкция песамодвойствепна и нелинейна.3.6. Представление булевых функцийв программахДля представления булевых функций можно использовать стандартные методы представления функций (см. 1.6.5), а также некоторые специальные приёмы,и эти идеи часто оказываются применимыми для представления других, болеесложных объектов.3.6.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
