Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 6
Текст из файла (страница 6)
Выяснить, является ли выражение А формулой над множест- вом Ф. Проверить, можно ли, добавляя скобки, запятые и переменные (не обязательно все эти знаки), превратить некоторые из приведен- ных ниже выражений (и какие) в формулы над соответствующими множествами Ф: )А= цдбб( *И Ф=(7' 2) А =)х(~рцг, Ф = (60~, уб«); 3) А=( 0«(абб( "'(х)В =О" 4) А — уР«( (г«( „) 5(г«(1 д)) ф — (1 у(г) (г) 500) ое) А д<г)(д,«з«(х д уц«(х)) уц«х) ф (уб«д«г« ~,(з«). 6)А= '(Р'(д'(х '(аВ '"(дт ф (0 У«г) дбб 50«др(г«). 7) 4 5(г«(д«(г«(1) дбб(2 д«0«(х))) ф (1 2 д«г«5(г«диац). 8) Ае д (, (.' 5 (, (.
д)'В. ф — (1 д(з) 5(Ц „,(г>) дгР«) 9) А = дрц(И~ «(1 д,~з«(2, х, уц«(х)))), ф — (1 2 уц«д(г> 1,(г« ~р(з«). 10) А = 60«(х, д««г«(х, 1«ц(1))), Ф = (1, (Пг, 50«, дг«г«). 1.10. Выписать все подформулы формулы А над множеством Ф; 1) А = ((х д) — «((1д) — «(хь'я))), Ф = (1., ь, о — «); 2) А = (((х 3е д) де я) 6«((( 1х) 6« у) «7г)), Ф = ( 1, 3е, Ч, В, †«); 3) А = (~г«(д«г«(1, х)., Ь~з«(х, 1, дг«г«(д~г«(х, х)))), Ф (1 2 у«гг «г« 5(з« „,0« ). [ц(([з«(й~г«(1 ) [з)(1, 0«(1)) <ц( В ф (1 У[з«РЦ 5(г«(1 53) [з)(1 П 53)) символом 51 указаны «пустые» места; 26 Гл, 1.
Способы задания и сводапва функиид алгебры логики 3)А=~'Ь'(.— ) й'(хЙ )) =О' ~"' ~") где ~~ ~(П, П) = д~ц(П вЂ” > П) и уг 1(П, П) = Ь~ц(ПЙП) (здесь сим- волом П указаны те «пустые» места, которые характеризуют «ар- ность» соответствующих логических связок). 1.11. Выяснить, сколькими способами можно расставить скобки в выражении А, чтобы всякий раз получалась формула над множеством логических связок 11, Й, ч', 9, -ь, Ц, если: 1)А=1х9д — >х; 2)А=х — >х)х — ьх; 3) А=хддЙ 1х).г; 4) А=1х91у — ь1г; 5) А = 1 1 х .). 1 1 1 р; 6) А = х д 1 д 9 х 9 х 1 х, 1.12.
Сложностью формулы над множеством связок Э = (1, Й, 'с, 9,, — ь, ~, Ц назовем число связок в ней. Индукцией по сложности формулы доказать, что в формуле: 1) ненулевой сложности содержится хотя бы одна пара скобок; 2) число левых скобок равно числу правых скобок; 3) нет двух связок, стоящих рядом; 4) нет двух символов переменных, стоящих рядом. 1.13. Индексом связки в формуле назовем разность между числом левых скобок, предшествующих рассматриваемой связке в данной формуле, и числом правых скобок, предшествующих этой связке. До- казать, что всякая формула ненулевой сложности над множеством Ь (см.
предьгцушую задачу): 1) содержит единственную связку индекса 1; 2) единственным образом представляется в каком-нибудь одном из видов (1 ге), (ЙЙЗ), (й Ч З), (Й 9 З), (Й З), .(хь — > З), (Й ~ З), (Й ь Ж), где Й и З --- формулы над множеством 9. 1.14. Рассмотрим бесскобочную (польскую) запись формул над множеством связок 9 = 11, Й, Ч, 9,, — ь, ), Ц: вместо (1 х), (хЙд), (хну), (х 9 у), (х — у), (х — > д), (х ) р), (х « у) будем писать 1х, Й хд, Ч ху, 9 хд, ху. — ь ху, ~ ху, ). ху.
Соответствующим об- разом записываются и более сложные формулы: например, форму- ла (((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) А = ((((х 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ера(й)) определяется по индукции: (а) если й --.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
