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

(у Ч г) Й х(у Ч г) = х у. . (у Н д) (у Ч г). Раскрывая скобки в последнем выражении и используя эквивалентности х х = х, х.х = О, х 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,п. 2), а затем, подставляя на места соответствующих переменных 0 и 1, получим нужные нам подфункции функции 1'(ха) и сравним их между собой. Сначала воспользуемся эквивалентностями х — 4 у = х Ч у, х = х, х у=хегу и х~гу=хЧу1. Получаем г (Х ) = ((2'1Х2 Ч УЗ) 1Э (Х1У4 Ч Х2ХЗ)) Ч (хг 9 хл) Ч хз Ч х1 Хг Ч (хз чг Х4)) ° Далее применяем эквивалентности хбзу=хуЧйу, хЧу=х р, хсоу=х у=хуЧху, х.у =йЧу, х = х, хц1у = хиз уВ1 = х111у = хуЧху. Это приводит нас к такому соотношенинх 1(х ) = (хгхг Ч хз)х124 Ч хгхз Ч хзхг Ч хз(хгх4 Ч хгхз) Ч Ч (хгхл Ч хгхл)хз Ч хг Ч хг(хзхл Ч хзхл).

лак как Х1Х4 Ч Х2ХЗ = Х1Х4 ' У2ХЗ = (У1 Ч Т4) ' (Хг '1 Хз) и Х1хг Ч хз = хзхг хз = (Х1 Ч хг)хз, то из последнего выражения для 1(х 4) после раскрытия скобок получаем формулу х1хг 'Ч х1хгхз Ч х1хгхл Ч х1хгхзхл Ч х1хгхз Ч Ч Х1ХЗ Ч Х2ХЗХ4 Ч Хзхл Ч 21хзх4 Ч Хгхглз Ч хгхгхзх4 Ч Ч х2хз Ч Х2хзх4 Ч х2хзтл х1 Ч 22хзх4 Ч х2хзх4. С помощью правила поглощения йЧй121 = й эта формула можот быть преобразована к следующему виду: х1 Ч хзх4 Ч 2:гхз Ч хгхзх4 Ч хгхзхл Ч хгхзх4.

С использованием эквивалентностей х Ч х = 1 и х 1 = х получаем г (Х ) = Х1 Ч ХЗХ4 Ч Х2ХЗ Ч Х1ХЗХ4 Х2ХЗ(Х4 Х4) = х1 Ч хзх4 Ч х1хзх4 Ч хз(х2 Ч х2) = х1 Ч хзх4 Ч х1узх4 Ч хз. у 1. Функции алгебры логики. Операция суиериаэиции 35 Наконец, применяя еще раз правило поглощения и эквивалентность ХУЧХ =УЧу, имеем 1(х ) =Х1 ЧхзЧХ4. Отсюда сразу следует, что переменная хг фиктивная. Далее, так как 1(0, О, 1, Ц = О, а 2'(1, О, 1, 0) = г'(О, О, О., Ц = 2'(О, О, 1, 0) = 1, то остальные три переменные у функции 1(х~) существенные. П р и м е р 15. Выяснить, можно ли, отождествляя и переименовывая переменные в функции ((х~) = (Х1 Чхг Чхз)У4Ч хгхгх4, получить функцию д1(Х1, хг) = х1 Ч хг или функцию дг(Х1, хг) = х1 ~ хг. Решение. Легко заметить, что у(0) = 1 и 4"(Ц = О.

Следовательно, всякая функция, которая получается из функции 1(х ) путем отождествления и переименования переменных, на нулевом наборе равна 1, а на единичном О. В то же время функция д1(х ) этому условик1 не удовлетворяет (д1(0, 0) = 0 и д1(1, Ц = Ц. Значит, функцию д1 из функции 1 описанным выше способом построить нельзя. Далее, хотя функция дг на 0 равна 1 и на 1 равна О, отсюда еще не следует, что ее можно получить из функции 1, отождествляя и переименовывая переменные. Чтобы выяснить, получается или нет указанным способом из функции 1 функция дг, можно, естественно, перебрать все возможности построения из функции 1 двуместных функций (с помощью отождествления н переименования переменных) и сравнить полученные функции с функцией дг.

При этом нужно будет рассмотреть семь вариантов: Ц х1 = хг = хз = х, х4 = У; 2) хг=хг=хл=х, хз=у; 3) хг=хз=хл=х, хг=у; 4) хг= Хз Х4 х~ Х1 У '1) х! Х2 Х1 Хз Х4 У~ б) Х1 Хз хг х4 У 7) х1 х4 х хг хз У. Такая процедура несколько утомительна. Можно поступить иначе. Предположим, что функцию дг указанным путем из функции 1 построить можно. Из соотношений дг(0, Ц = дг(1, 0) = 1 следует, что должна существовать пара противоположных наборов Й = (а1, аг, аз ал) и 14 = (о1, 412, аз, ол), на которых функция 1 обращается в 1, т.е.

функция Зг(хг хг, хз, х4) = ((Х1; хг: хз, Х4) Йу(хг, хг, хз Х4) не должна быть равна О. Тот набор (любой), на котором функция уг(хл) равна 1 (если уг ф и: 0), и определит соответствующее отождествление переменных. Имеем з'(ХХ ) = ((Х1 Ч Х2 Хз)Х4 Ч Х1Х2Х4) ' ((Х1 1 Х2 Хз)Х4 Ч Х1112Х4) = хз хгх4(х1 Ч хг Ч хз) Ч хгхгх4(У1 Ч хг Ч хз) = Х1 хгх4 Ч хгхгх4. Очевидно, что 42(х4) равна 1 только на наборах (1, 1, О, 0), (1, 1, 1, 0), (О, О, О., Ц и (О, О, 1, Ц. Взяв, например, набор (1, 1, О, 0), приходим к такому отождествлению; х1 = хг —— х и хз = х4 = у; оно дает 1(х, т, у, у) = (хЧ х Ч у)у Ч х ху = ху Ч уЧ Уу = ХЧ у = х ~ у.