Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 6
Текст из файла (страница 6)
Оиерация едвериозиции 25 ные эквивалентности 2, 7,в), 7,д), 1, 3 и 8,а): г« = х «7д 'и' з ««уя Н1«г Ч ' ' хз Ч дз '««хр ж Накопал, воспользовавшись правилом поглощения 5, а), приходим к соотношению й = х 'о' у ««г. Преобразуем теперь к такому же виду и формулу «л«. Имеем Ж = (х ««д)х Ч уд ««у Ч я (здесь были использованы основные эквивалентности 8, в), 9, а), 9, б) и 4, а)). Па- лее, применяя основные эквивалентности 4, а), 7,.д) и 4, б), получаем З = хр ««' х о дз Ч у ««з.
С помощью закона поглощения 5, а) последнее выражение преобразуется к такому: х «7д ««ж Тем самым эквивалент- ность формул Й и З доказана. 1.8. Выяснить., какие из нижеприводимых выражений являются формулами над множеством логических связок 8 = (1, 8е, «7, Ю, -, — «) . Проверить, можно ли некоторые из приведенных ниже выражений (и какие), не являющиеся формулами над Я, превратить в формулы, добавляя скобки: 1) х — «хц 2) х«7(1у); 3) хб«(йу); 4) (х««д) — «(х~р(1з)): 5) (х е- у); 6) (х 8е) 1 х; 7) (х В (г)): 8) 1(т †« (( 1 х) ух у)); 9) (х у) 1у; 10) ((х — «(1у)) ((хь'(у3ег))вд)); 11) (1х — «у); 12) ((х 8е (1 х)) ' ' (х 9 (х — «х)) Ч (1 х)). 1.9.
Выяснить, является ли выражение А формулой над множест- вом Ф. Проверить, можно ли, добавляя скобки, запятые и переменные (не обязательно все эти знаки), превратить некоторые из приведен- ных ниже выражений (и какие) в формулы над соответствующими множествами Ф: )А= цдбб( *И Ф=(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) А = (Ц(х 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
