Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике.pdf), страница 7

символ переменной или 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' реализуется формулой Й*, имеющей такое же строение, как и формула Я, и Й* = = С[11, ..., 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. Функции алгебры логики. Операция суперпозиции 5. Фиктивные и существенные переменные.

Отождествление переменных у булевых функций. Переменная х1 (1 < 1 < и) фуНКцнн У(Х1 ., Хг 1,ХОХ,Л1г ..., Хв) НаЗЫВаЕтСя Сущгоглогииай, если можно указать такие наборы Н и,З, соседние по 1-й компоНвптв (т. Е. О = (О1, ..., а, 1, О, 11,41...., Нн) И 43 = (О1, ..., Ог 1, 1, Ц,Е1, ..., Цв)), ЧтО 1(Н) ~ 1(42). В ПРОТИВНОМ СЛУЧаЕ ПЕРЕМЕННаЯ Х, называется фиктивной (или несущественной) перемонной функ- ЦИИ 1(Х1г ..., Х; .1, ХО Хгиъз, ..., Х„).

ДВЕ ФУНКЦИИ ) (Хйв) И д(У ) Называются равными, если множества их существенных переменных совпадают и на любых двух наборах Н" и 1)гл, различающихся, быть может, только значениями несущественных переменных, значения функций одинаковы: 1(йл) = д(9 ). Если 1(хн) и д(у ) равные функции, то одну из них можно получить из другой путем добавления и4гили изъятия фиктивных переменных.

Пусть 1 < 11 < 12 « ... 11„. < п. Говорят, что функция ус(х1, ... Хгг — 1 Х Хгг41 ° ° Хгг — 1г Хгг41, ..., Хгг — 1г Хм41, ..., Хл) ПОЛУЧС- на из фУнкЦии 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'(Х ) = ((Хзхз гг ХЗ) (Х1Х4 'и'Х2ХЗ)) — ~ (((Хз 9 9Х4) г Хз) ~ (Х1 ' (Хз 1 (13 9Х4)))).

Решение. Для решения данной задачи можно действовать так же, как при решении прсдыдущей, т.е. сравнивать значения функции на парах соседних наборов, чтобы выяснить, совпадают или нет соответствующие подфункции функции 1(х~) (ибо переменная х, фиктивна тогда и только тогда, когда Д'(х ) = 11'(х~)). Однако при 3 Г. П. Гаврилов, А. А. Сапожонка 34 Гл, 1. Способы задавил и свойапва фупкиий алгебры логики задании булевой функции в «аналитической форме» для выяснения того, какие переменные у нее существенные (а какие фиктивные), иногда бывает полезно преобразовать исходное выражение к некоторому специальному виду, например к совершенной диэъюнктивной нормальной форме или полиному Жегалкина (см.

з 2, пп. 2 и 3). Оказывается, что переменная х, функции 1 (х") является фиктивной тогда и только тогда, когда; 1) в совершенной д.н. ф. этой функции вместе с каждой элементарной конъюнкцией вида х, ' К содержится и элементарная конънгнкция хо'К (см. задачу 2.16) или 2) в полиноме Жегалкина, реализующем эту функцию, переменная хг отсутствует. Для решения сформулированной задачи мы сначала преобразуем (с помощью основных эквивалентностей) исходное аналитическое задание функции 1(х~) к достаточно простой дизъюнктивной нормальной форме (см. э 2,п.