Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 5
Текст из файла (страница 5)
3. Формулы. Реализация булевых функций формулами. Пример 9. Локазать, что выражения й« = 1л) — «1(1у3гг и йз = (я Ч (1 у)) — «(я оо 1 у) не являются формулами над множеством логических связок (1, 3о, Ч, — «), но что, добавляя скобки, каждое из этих выражений можно превратить в формулу над указанным множеством связок. Р е ш е н и е. Лля доказательства того, что некоторое выражение й нг явллегпся формулой над каким-то фиксированным множеством Ф (функциональных символов и«или логических связок), достаточно выявить какое-либо свойство, присущее каждой формуле над заданным множеством Ф, но которым не обладает выражение й.
Утверждение о том, что любая формула над множеством Ф обладает выявленным свойством, обосновывается обычно по индукции по «сложности» формул (например, по числу связок или по числу функциональных символов, входящих в формулы). В выражении й« вЂ” — 1 я) — «1(1 у во я нарушено несколько свойств, присущих формулам над множеством (1, йо, Ч, -«): а) обе скобки, содержащиеся в йы не имеют парных им скобок; б) отсутствуют внешние скобки; в) не отделена скобками связка — «от остальных связок. Лобавляя скобки, выражение й«можно превратить, например, в формулу или ((1л) — «(1(1(уйг)))), или ((1 л) — «(1((1 у) 3гг))), или ((1 л) — «((1(1 у)) 3г г)). В выражении йг = (л Ч (1 у)) — «(я Уг1 и) не хватает только двух пар скобок: внешних и отделяющих связку 3о от связки 1.
Формула, соответствующая выражению йз, имеет вид ((л«7(1 у)) -«(я й (1 у))). Лля обоснования того, что оба выражения й«и йз не являются формулами над множеством связок (1, 3г, ~«, — «), достаточно, например, установить справедливость такого утверждения: всякая формула над множеством связок (1, оо, 'я', — «), отличная от формул вида л, у, ...., обладает парой внешних скобок. Показательство этого факта проведем по индукции — — по числу связок 1, ог, Ч, — «в формулах.
Базис индукции. Если в формуле й только одна связка, то с точностью до переименования переменных (с отождествлением) 24 Гас 1. Способы гадания и сводапва 41упкцпй алгебры логики формула й имеот один из следующих видов; й = (з х), й = (х8с у), й = (х Ч у) и й = (х — э у). Следовательно, базис индукции справедлив. Индуктивный шаг. Предположим, что доказываемое утверждение верно для формул, содержащих не более в связок (в > Ц, и установим его истинность для формул с числом связок, равным .в + 1. Имеем или й = ( 1 З), или й = (й 8с с), или й = (З 'о' ь), или й = = (Ж вЂ” > к), причем одна из подформул З или С в формулах трех последних видов может быть (с точностью до переименования переменных) формулой, равной х.
Очевидно, что индуктивный шаг также справедлив. П р и м е р 10. Построив таблицы функций, реализуемых формулами й= Их4у) — г ((уЮ (тчг)) ~ г)) и 'З = Ихчу) (х — э (у® 63 (х бс г)))), выяснить, эквивалентны ли эти формулы. Решение. Принимая во внимание тот факт, что функция т — > у обращается в 0 только на наборе (1, 0), а функция х ). у равна 1 а б л и ц а 1 5 лишь на набоРе (О, 0), мы можем УпРостить пропедуру построения таблипы функции воя(х, у, г), реализуемой формулой й. В самом деле, угя = 0 тогда и только тогда, когда х ).
у = 1 и (у Ю (х М г)) ~ г = О, т.е, когда х=у=О и (Оео(ОЧг)) ~г= = г ) г = г = О. Следовательно, сои = 0 только при х = у = 0 и г = 1 (табл. 1.5). Таблицу функции 1от(х, у, г), реализуемой формулой 21, будем строить шаг за шагом (табл. 1.6). Таблица 1.6 Сравнивая таблицы функций воя и сох, видим, что ря ф уьл. Значит, формулы й и З неэквивалентны.
Пример 11. Используя основные эквивалентности (см. и. 3 после задачи 1.20), установить эквивалентность формул й = (х ). у) э (хг — э Пх ~ (у г)) Ч (х у 9 г))) В = Их -э у) ~ (х ). 1у ))) '1 у Решение. Применяя основные эквивалентности 8,в), 9,а) и 9, б), получаем й = х Ч у Ч хгЧ (х(у г) Ч (ху 9 г)).
Используя затем основные эквивалентности 7,д), 4, а), 8,б) и 8, а), имеем й = (х Ч у) Ч Ч (х Ч у) Ч ((х Ч (у Юг)) Ч ((х ~у)ся Чхуг)). Палее применяем основ- у Д фрикции алгебры логики. Оиерация едвериозиции 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 хд, ху.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
