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

е. в непустом и отличном от всего А) эта сумма неотрицательна. 1.15. Построить диаграмму, характеризующую строение форму- лы А над множеством Ф: Ц А = П1(х + (1у))) 9 Пг'оЬЙх)) ~ р)) Ф = (1,. Й, 'с, 9, — 'е, .Ц; 2) А = Д(х -+ у) — ь (1Дх / у) — ь (х / г)))) -+ Я1д) — ь г)), Ф = 11, -ьЦ); 3) А = Д(((х 9 у) 9 х) 9 у) 9 г) 9 (х 9 г)), Ф = ~9):, 1'1.

Функции алгебры логики. Операции еуперпоэиции 27 4) А = ((((х 49) ! (у 4х)) / з) 4 (х ! з)), Ф = (!, Ц; 5) А = УВ)(д)2)У)1)(х) Ь)2)(9)2)(х У<И(у)) У®(хи)) ф (~))) 9)з) ),)з)). е)з)( рц(у)з)( )) ь)з)( рцэр)з)( „„))) „) Ф вЂ” (У(з) 9)1) 6)з) ) 7) А У)з)(((х, (3,)),,) дРЦ((,ЩУ),,)) ф — (7(з) 9РЦ 3 ) л)) 1.16. Восстановить формулы по диаграммам из рис. 1.3. у х у х у 2) о) 1) лез) рц о 2) о) 3) 4) лз) х у х х 6) Рис. 1.3 28 Гж 1. Способы водопоя и свойыпва дгупкиий ввеебры возики 1.17. Построить таблицы функций, реализуемых следующими формулами над множеством связок б = (1, 33, «Х, 6«,, -+, ~, Ц: 1) Их — «у)«х(х®г)) (у ~ 2); 2) Их у) 4(т, ~ у)) — «(з — «у); 3) (х у)«х(у — «2) 4 Их 6«г)'у у); 4) х -«у Ю Их -«2) р) . г; 5) (х Ч у) -« Их ф у) ~ г) ф у; 6) (х у) -« (х . г -« у) -« х .

г; 7) Их 4 у) ~ г) ~ х) 4 у; 8) Их †« у) 9 (х †« у 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.

Построив таблицы соответствующих функций, выяснить, эквивалентны ли формулы й и гз: Ц й = (х — > у) ей Иу «у) -«х у), З = у г — «х; 2) й = (х " ,у) ф (х -« (у -« г)), З = у -« (х «хг); 3) й = т -« Иу -« г) -« у з), З = (х 1« (у -« 2)) .(х 6« у); 4) й = (х 4 у) ч (х — 2) ~ (х 6« у г), з = х (у 2) у х -« г; 5) й = Их «7 у) г †« Их г) ~Э у)) Их ~Э у) ° 2), З = (х — «уг) 33 т, — «р; 6) й = (х и у) 4 Иу ~ г) — «(х х г)), з = ху 1«(х — «ху 4 2); 7) й = (и ~ у) -« Иу ф г) †« (х 61 2)), «8 = х (у г) 6«(х -« г); 8) ~ = И(х ~ у) 4 ) ~ у) 4 (у -« г), 'З = И* ~ у) 4 Ь ~ )) ( †« Ь -+ г)); 0) й = (* у ) «х И 4 у) ~ ), х« = Их -« у . 2) 6«(х — у))у (у -« х 2); 10) й = х й у . г .

у †« х г (т 4 у), и« = (х . у †« (у 4 г)) «« х . г г. 1.20. Построив таблицы для соответствующих функций, убе- диться в справедливости следующих эквивалентностей: 1)хну=(х-«у)-«у; 2)т у=(т-«у)33(у-«т); 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' реализуется формулой Й*, имеющей такое же строение, как и формула Я, и Й* = = С[11, ..., 1,); в частности, если Й = Ф(у ', ..., еое " ), то д* = = ф ([ )"'')' [ "'1') Пример 12. С использованием принципа, двойственности построить формулу, реализующую функцию, двойственную функции 1" = (х 'Ч (1 — ~ у)) М уяГУ(х ~ у [ д).

Полученную формулу по возможности упростить. Решение. Так как (х Ч у)' = х у, 1* = О, (х т у)* = х — г у = = х у у = х у, (х у)* = х у у, (х)' = т, (х ~ у)' = х ф у и (т ( у)* = = х ~ у, то 1' = (т(Оу))(у Чд)(т ( у [ г). Применяя коммутативный и ассоциативный законы для коныонкции, а также эквивалентности 0=1, 1 х=х, х т=х, х=х, х(у=х у и т~у=х'ду, получаем 1' = х. у (у Ч у) х. у ~ д = х у.