Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 7
Текст из файла (страница 7)
4, а) х й у = х Ч у; б) х Ч у = х й у (правила де Моргана). 5, а) хЧ (х Й у) = х; б) х Й (х Ч у) = х (правила поглощения). 6. а) х'Ч (х й у) = х Ч у; б) т й (х Ч у) = х й у. 7. а) хйх=хйО=х6«х = 0: б)хЧх=хЧ1=х х=х — «х=1, в) х Ч х = хйх. = хй 1 = х Ч 0 = х 6«0 = х; г)х6«1=х — «О=х О=х~х=х«х=х; д)х=х. 8.
а) х6«у = (хйу) Ч (хйу) = (х Чу) Й(х Чу); б) х. у = х 6«у = (х Й у) Ч (т. Й у) = (х Ч у) Й (х Ч у); в) х — «у=хЧу=((хйу)6«х)91. 9. а) х ~ у = х й у = х и у; б) х 4 у = хЧ у = х. у. В справедливости этих эквивалентностей можно убедиться путем построения таблиц соответствующих им функций. 1.21.
Используя приведенные выше (основные) эквивалентности и соотношения из задачи 1.20, доказать эквивалентность формул я1 и х«: 1) 91 = (х -« у) -+ (х у - (х 6« уИ З = (х . у †« х) -« у:. 2) л' = (х . у Ч (х †« у г)) - ((х †« у) †« г), .я« = (х -+ у) 6«(у 9 г); 3) 91 = (х й у . г) -« (х -« (у -« г)), З = х -« ((у -« г) -« х); 30 Гл. 1. Способы задания и свойства функций алгебры логики 4) й = (х — г (у — г (х г))) . (х (у — г (з у (х — г у)))), З = (т — г (у — г г)) — в х; 5) й = (х у у . з) -г ((х -в у) -в ((у у з) -г х)), З = (х -г у) о (у -г х); б) й = (х у ч * ) Е ((у — г ) -+ ~ у), м = ( (Р .
) Е у) Е 7) й = х -г ((х . у -г (х з -+ у)) -в у) . з, З = х (у -г з); 8) й = (х у) -в (х -г и)''д (х ~З у г),, З = х (г -+ у); 9) й = х М у г) (х -> Д г) (х †) (у г)), 'В = Ьх -в у) - Ь -в ( — з))) е х Ь ); 10) й = ((х Ч у) — г у з) Ч (у — г х г) у (х — ~ (у — в г)), З = (х -о у) у г. 1.22. Выписать все булевы функции, зависяьцие только от пе- ременных из множества (х, у) и являющиеся суперпозициями над множеством Р: 1) Р = (из -+ иг, ис .иг); 2) Р = (ис иг, и1 Ч иг); 3) Р = (из иЗ иг, из е1 1); 4) Р = ((из и иг) — + из иг); 5) Р = (из Ч иг .из, и, Ер иг); б) Р = (ид .
иг, из Ю иг низ); 7) Р = (иг . иг Ч из из у иг из, из .(иг Ч из)). 1.23. Глубина формулы й над множеством Ф (обозначе- ние с1ера(й)) определяется по индукции: (а) если й --. символ переменной или 0-местный функциональный символ, то с)ери(й) = 0; (б) если й = 1'гп1(йы ..., й„), где и > 1 и г гвг Е Ф, то с1ера(й) = = шах деря(йз) + 1.
1<~(о Выяснить, верно ли, что указанная ниже формула й имеет мини- мально возможную глубину среди формул над множеством Ф, реали- зующих функцию 7: 1) й = (х -в Ь гу у)) 01 у, 1 = * - у, Ф = (гр, ->); 2)й=х (у (хну)), (=х у, Ф=~,'~, 3) й = (х ~ х) ~ ((х ~ у) ~ у), ~ = ху у, Ф = (~); 4) й = х у, 7' = х о у, Ф = ( з, 3с ); 5)й=(х — гу)-+уох, 7'=херу, Ф=(1,— г); б) й=(( -+у)-+у)-( -у), У= .у, Ф=(-,— ); 7) й = ((х ( х) 4 (у ( у) 4 ((х з х) ). (р 4 у)), 7" = х ( у, Ф = (Ц; 8) й = ((х -г у) (у з г)) (г -+ х), 1 = (х Ч у у г) -з х . у Ф=(3с,— в); 9) й = (х -> у) -г (х -+ 0) у., 1 = х йз у, Ф = (О, -э, 3с); 10) й = ((х л г) †> у) .(з †> (у — в х)), 7 = х у 7 х . у у у г, Ф = (3, -+).
1.24. 1) Пусть булева функция 1(х, у) удовлетворяет соотноше- нию 1(1(х, 7(у, г)), 7(Д(х, у), 1(х, г))) = 1. Показать, что тогда у Д Функции алгебры логики. Операция еуиераогиции справедливы следующие эквивалентности а) 1(х, х) = 1: б) 1(х, 1(у, х)) = 1; в) 1(1([(х, у), 1(х, г)), ((х, У(у, г))) = 1; г) 1(1(х, у), 1(1(х, г(у, г)), 1(х, г))) = 1; д) И(х, 1"(у, г)), 1(у, 1(х, ))) = 1 2) Выяснить, вытекают ли эквивалентности б), в) и г) из д). 4. Двойственные функции. Принцип двойственности. Пусть Д(хы ..., т„) произвольная булева функция, зависящая от п ) 1 переменных.
Функция 1'(хы ..., хи), обозначаемая обычно 1*(хы ..., х„) (или, подРобнее, [((хы ..., х„))*), называетсЯ двойственной (к) функции 1(хы ..., ха). При п = 0 полагают (по определению),что функция 0 двойственна 1, а 1 двойственна О. Если функция 1(х") совпадает с функцией, которая двойственна ей, т.е. с 1*(хи). то она называется самодвойетвенной.
Самодвойственными являются, например, функции х, х и х Ю (у Ф г). Справедлив следующий принцип двойетвенносгли. Если функция 1 реализуется формулой г1, имеющей строение С[фы ..., Я, то двойственная ей функция 1' реализуется формулой Й*, имеющей такое же строение, как и формула Я, и Й* = = С[Д, ..., 1,); в частности, если Й = Ф(у ', ..., еое " ), то д* = = ф ([ )"'')' [ "'1') Пример 12. С использованием принципа, двойственности построить формулу, реализующую функцию, двойственную функции 1" = (х 'Ч (1 — ~ у)) М уяГУ(х ~ у [ д). Полученную формулу по возможности упростить. Решение.
Так как (х Ч у)' = х у, 1* = О, (х т у)* = х — г у = = х у у = х у, (х у)* = х у у, (х)' = т, (х ~ у)' = х ф у и (т ( у)* = = х ~ у, то 1' = (т(Оу))(у Чд)(т ( у [ г). Применяя коммутативный и ассоциативный законы для коныонкции, а также эквивалентности 0=1, 1 х=х, х т=х, х=х, х(у=х у и т~у=х'ду, получаем 1' = х.
у (у Ч у) х. у ~ д = х у. (у Ч г) Й х(у Ч г) = х у. . (у Н д) (у П г). Раскрывая скобки в последнем выражении и используя эквивалентности х х = х, х.х = О, х 0 = 0 и хуО = х, имеем 1'=т у.(у уЧр.гЧу.уЧд г) =туг. 1.25. Используя непосредственно определение двойственности булевых функций, а также основные эквивалентности и соотношения из задачи 1.20, выяснить, является ли функция у двойственной к функции (: 1)у=зад, у=х-у; 2)у=х~у, у=х(у; 3) (=х — ~у, д=х.у; 4) )' = (х -~ у) -> (у -~ х), д = (х -~ у) (у -~ х); 32 Га, 1.
Способы задания и сводыпва фупкиин ааеебры логики 5) 7=хбдб«з, д=хб«дФз; 6) 7'=х.дХсз, д=х (р«ХХ); 7) 7' = хдб«хе 6«дз, д = хдХ«хе Х11«з; 8) 7' = х д †« з, д = х у з; 9) 7=(хЧд«1х).1Чх у з, д= (хЧдЧз) бух.д.з; 10) 7" = хд «1 дз «1 з1 Хг 1х, д = хз Ч д1; 1Ц 7 = (™д) ««езЮ1) д= (х ~ д) О(к 1)' 12) 7' = (х †« д) (з -« 1), д = (х -« з) (х †« 1) . (д -« з) .(д -« 1). Замечание. Если функция задана в табличной или векторной форме, то при построении функции, двойственной ей, удобно бывает использовать тот факт, что на противоположных наборах двойственные функции принимают противоположные значения, т.е. осли 7 = 1(хы ..., х„) и д = 7*(х"), то д(')ы ...,.
7 ) = 7( «ы ..., 7п) при любом наборе ( уы .,., уп). В частности, если функция 1 задана вектором О1 = (ав.,оы..., Оз» з,оз х), то функция 7' задаетсявектором (Оз — ы Оз — 2, ... ~ оы Оо). 1.26. Пусть Й - — формула над множеством Я = 10, 1,. 1, 8с, Хг, 6«,, ~, — «). Формула Й* над тем же множеством Я называется двойственной (к) формуле Й, если она получается нз Й заменой каждого вхождения одного символа из пар (О, Ц, (ое, '«1), (Ф, ), (~, Ц на другой символ из той же пары. Ц Показать, что если функция 7 реализуется формулой Й над множеством Я, то двойственная ей функция 7* реализуется формулой Й' (доказательство провести двумя способами: а) непосредственно, используя индукцию по «сложности формулы», т.е. по числу вхождений в нее символов из множества Я; б) г«рименяя принцип двойственности).
2) Показать, что если формулы Й и «В (над множеством Я) эквивалентны, то эквивалентны также формулы Й* и я«*. 1.27. С использованием принципа двойственности построить формулу, рсализуюьцую функцию, двойственную к функдии 7, и убедиться в том, что полученная формула эквивалентна формуле Й; Ц 1 =х 1Хгд «зН 0)ЧУ.д з, Й=х (д~Вз); 2) ~ = (х 4 д) б« Их ~ д) 4 (х д х)), Й = х д 'у х . у Ч у з; 3) 7=(хЧд 7(д зегЦ)).з, Й=хЧдхсз; 4) 7"=х д уд с Уд з, Й=х д яЧуу з; 5) 7 = цх -« д) Хс з) (д з -« (х йз у з)), Й = (х 6« д) з; 6) 7 = (цх ' д 7 (д. з - Ц) Е Ц вЂ” «О) ~ д, Й = х з Хг д; 7) 7 = (х д д Хс з) †« (х д (х 6« д з)), Й = (х з) .
у; 8) ~=х.дХ«д ХХсз.1, Й=х зчгз дХгд 9)~=(х«/доз) гаях д з, Й=(х~дЧз) Рух.д з, 10) 7 = (х (д ХЧО) (1.1«гх.у)) Чд.1, Й = (хМ (з«91)) .д. д 1. Функции алгебры логики. Оперог1ин суперпозиции 5. Фиктивные и существенные переменные. Отождествление переменных у булевых функций. Переменная х1 (1 < 1 < и) фуНКцнн У(Х1 ., Хг 1,ХОХ,Л1г ..., Хв) НаЗЫВаЕтСя СущгогПВЕННОй, если можно указать такие наборы Н и,З, соседние по 1-й компоНвптв (т. Е.
О = (О1, ..., а, 1, О, Стг41...., По) И гло = (О1, ..., Ог 1, 1, П,Е1, ..., Пв)), ЧтО 1(11) ~ 1(42). В ПРОТИВНОМ СЛУЧаЕ ПЕРЕМЕННаЯ Х, называется фиктивной (или несущественной) перемонной функ- ЦИИ 1(Х1г ..., Х; .1, ХО Хгиъз, ..., Х„). ДВЕ ФУНКЦИИ ) (Хйо) И д(У ) Называются равными, если множества их существенных переменных совпадают и на любых двух наборах Н" и )ггл, различающихся, быть может, только значениями несущественных переменных, значения функций одинаковы: 1(йл) = д(9 ). Если 1(хо) и д(у ) равные функции, то одну из них можно получить из другой путем добавления и4гили изъятия фиктивных переменных. Пусть 1 < 11 < 12 « ...
11„. < и. Говорят, что функция уг(х1, ... Хгг — 1 Х Хгг.11 ° ° Хгг — 1г Хгг41, ..., Хн — 1 ° Хгг-11 ° ., Хл) ПОЛУЧС- на из фУнкЦии 1(хо) пУпмм опгохсдвспгвлснии пеРеменных хг.. х„, ..., хгю если гр является результатом подстановки переменной х в функцию 1 на места переменных хн, х;,, ..., х;„. В качестве х можно взять любую переменную, нс входящую в множество ХггЦхо, Хгг ° ° Хгг ). Пример 13. Перечислить все существенные и фиктивные переменные функции 1(х~) = (1100001111000011). Решение. Сравнивая значения функции на всех парах наборов, СОСЕДНИХ ПО ПЕРЕМЕННОЙ Х4г ВИДИМ, ЧтО г'(О, О, О, 0) = 1(Ог О, Ог 1) = 1(0, 1, 1, 0) = 1(0, 1, 1г1) = = 1(1, О, О, 0) = 1(1, О, О, 1) = 1(1, 1, 1, 0) = 1 (1, 1, 1, 1) = 1, 1(Ог О, 1, 0) = г"(О, О, 1г 1) = 1(0, 1, О, 0) = 1(0, 1, О, 1) = = )'(1, О, 1, 0) = 1(1, О, 1, 1) = 4"(1, 1г О, 0) = 1(1, 1, О, 1) = О, т.е.
1(х1, хз, хз, 0) = У(Х1, хз, хз, 1). Следовательно, переменная х4 фиктивная. Далее, так как 1(0, О, О, 0) = 1, а 2"(О, О, 1, 0) = 0 и 1(0, 1, О, 0) = О, то переменные хз и хз существенные. Наконец, принимая во внимание соотношения 1(0, хзг хз, х4) = (11000011) = = Г"(1, хз, хз, т4), заключаем, что переменная х1 фиктивная. Итак, у функции )(х~) переменные х1 и х4 фиктивные, а переменные хз и хз существенные. (Нетрудно убедиться в том, что 2'(хл) = хз хз.) Пример 1г1. Перечислить все фиктивные и существенные переменныс функции 2'(х ) = ((хзхзЧ хз) (тгхл гХхзхз)) — ~ (((хз 9 9Х4) г Хз) ~ (Х1 ' (Хз 1 (13 9Х4)))).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
