Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 6
Текст из файла (страница 6)
— ь ху, ~ ху, ). ху. Соответствующим об- разом записываются и более сложные формулы: например, форму- ла (((1 х) — ь у) Й (1(г Ь х))) в бесскобочной записи будет иметь вид Й -ь 1 ху 1). гх, Показать, что если каждую из связок Й, Ч, 9, — >, ~, ). оценить числом +1, связку 1 числом О, а каждый символ переменной . числом -1, то в бесскобочной записи произвольное выражение А над множеством б будет формулой тогда и только тогда, когда сумма оценок всех вхождений символов в А равна — 1 и в каждом собственном начальном отрезке выражения А (т.
е. в непустом и отличном от всего А) эта сумма неотрицательна. 1.15. Построить диаграмму, характеризующую строение форму- лы А над множеством Ф: Ц А = П1(х + (1у))) 9 Пг'оЬЙх)) ~ р)) Ф = (1,. Й, 'с, 9, — 'е, .Ц; 2) А = Д(х -+ у) — ь (1Дх / у) — ь (х / г)))) -+ Я1д) — ь г)), Ф = 11, -ьЦ); 3) А = Д(((х 9 у) 9 х) 9 у) 9 г) 9 (х 9 г)), Ф = ~9):, 1'1. Функции алгебры логггки. Операции еуперпоэиции 27 4) А = (Ц(х 4 у) ! (у 4 х)) / з) 4 1х ! з)), Ф = 1), Ц; «) А — ур)(у(з)уИ)(х) г(з)( )з)(, ° у(г)(, )) у®(х)))) ф 1~)г) у~з) ),)з)).
г)з)~ (цгг(з)~ )) ь)з)г (цгг:)з)~ „„))) „) Ф вЂ” (у(з) д(1) 6)з) ) 7) А У)з) И(х, (1у)) ,,) дн)((, Щ у),,)) ф — у<з) у® 1 > л)) 1.16. Восстановить формулы по диаграммам из рис. 1.3. у х у х х 2) (г) 1) лез) рц (г 2) (г) 3) 4) ,лг) х у х х 6) Рис. 1.3 28 Гж 1. Способы водопоя и свойыпва дгупкиий ввеебры возики 1.17.
Построить таблицы функций, реализуемых следующими формулами над множеством связок б = (1, 33, Ч, Ю,, -+, ~, Ц: 1) Ихву)Ч(х92)) (9 ~ 2); 2) Их у) 4(т, ~у)) 4(з-ду); 3) (х у)Ч(у — д 2) 4 Ихняя)'уу); 4) х -1 уй Их 4 2) р) .г; 5) (х ч у) 4 Их ф у) ~ г) ф у; 6) (х у) -д (х . г -4 у) -г х . г; 7) Их 4 у) ~ г) ~ х) 4 у; 8) Их 4 у) 9 (х 4 у 2)) ~ (х 4 у). 1.18. По функциям д"(х1, хг) и 9(х1, хг), заданным векторно, построить векторное представление функции Ь: 1) аг = (0010)~ ад = (1000)~ Ь(х1~ х2; хз) У(х1~ 23)Й9(хг~ х1)~ 2) сх е: (0100) сгд: (1 101) Ь(х1 х2) У(х1~ 9(х2:'с1)) " 9(х2 У(х1~х1)) 3) ае = (1001), сед — — (1110), Ь(х1 х2 хз~ х4) У(х1 хз) 6Э 9(х2 У(х1: х4))) для функции Ь построить и таблицу Пгд(Ь), 4) ау = (0110), ад — — (1011), Ь(х1, хг, хз) = 1(9(х1, тз), 1(хг; т1)); 5) ау = (1101), а„= (011Ц, Ь(х1 х2) д (9(х1 х2) х2) е 9(хг: г (хг: 11)) 6) ау = (1000), ад — — (0110), Ь(х1, тг, .тз, хд) = = 1(х1; 1(хг: х1)) д 9(1(х1, хг), 9(х1, хз))) Ю 1(9(хз, х4), 1(хг, хгЦ, для функции Ь построить и таблицу Пг,г(Ь).
1.19. Построив таблицы соответствующих функций, выяснить, эквивалентны ли формулы й и гз: Ц й = (х — > у) ей Иу д у) -4 х у), 21 = у г — 4 х; 2) й = (х " ,у) ф (х -Е (у -1 г)), З = у -г (х 'дг); 3) й = т 4 Иу 4 г) 4 у з), з = (х зс (у 4 2)) .(х 63 у); 4) й = (х 4 у) ч (х — 2) ~ (х ю у г), з = х (у 2) у х -1 г; 5) й = Их Ч у) г — г Их г) ~Э у)) Их ~Э у) ° 2), З = (х 4 уг) 33 т, 4 р; 6)й=(хуу)4Иу~г)4(х х г)), з=ху11(х — дхувз); 7) й = (и ~ у) 4 Иу ф г) 4 (х 61 2)), % = х (у г) 61(х -4 г); 8) ~ = И(х ~ у) 4 ) ~ у) 4 (у -4 г), 'З = И* ~ у) 4 Ь ~ )) ( — г Ь -+ г)); 0) й = (* у ) 1х И 4 у) ~ ), З = Их 4 у . 2) Ю (х — у))у (у -4 х 2); 10) й = х й у .
г . у 4 х г (т 4 у), З = (х . у 4 (у 4 г)) 9 х . г г. 1.20. Построив таблицы для соответствующих функций, убе- диться в справедливости следующих эквивалентностей: 1) х Ч у = (х 4 у) 4 у; 2) т у = (т 4 у) 33 (у -4 т); 3) х 4 у = Их ~ х) ~ (у ~ р)) ~ Их ~ х) ~ (у ~ у)):, р 1. Фуикчип алгебры логикт Операция суперпозичии 29 4) х Ч (у г) = (х Ч у) (х Ч г); 5) х~ (у - ) = ((хйу) - (хй )) - х; 6)х-«(у г)=(х — «у) (х-«г); 7) х Ч (у -«г) = (х Чу) -«(х Ч г): 8) х й (у -«г) = (х -«у) -«(х й г); 9) х — «(у Ч г) = (х — «у) Ч (х — «г); 10) х — «(у й г) = (х — «у) й (х -+ г); 11) х -«(у -«г) = (х -«у) -+ (х -«г). При оперировании с функциями алгебры логики бывают полезны следующие эквивалентности (большинство из них называют обычно основныяи эквивалентностями алгебры логики).
1. х о у = у ох.- . коммутативность связки о, где символ о является общим обозначением для связок Й, Ч, .6«,, ~, ).. 2. (хоу) ог = хо(у ох) .—. ассоциативность связки а, где о ". об- щее обозначение для связок Й, Ч, 6З, 3. а) хй (у Ч г) = (хй у) Ч (хй г) --. дистрибутивность конъюнк- ции относительно дизъюнкции; б) х Ч (у Й г) = (х Ч у) Й (х Ч г) - дистрибутивность дизъюнкции относительно конъюнкции; в) х й (у 6«г) = (х й у) 6«(х й г) -- дистрибутивность конъюнкции относительно сложения по шоб 2. 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, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
