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

5) Лля оценки гипотез Н1 и Нз проводятся пять разнотипных экспериментов: Аы Аз, Аз, Ал, Аз. Каждый эксперимент упорядочивает гипотезы по предпочтению относительно некоторого признака. Гипотеза Нз принимается только в следующих случаях: а) в большинстве экспериментов предпочтение отдавалось НП б) в экспериментах А1 и Аз предпочтение отдавалось гипотезе Нз, но в эксперименте Ал предпочтение отдано гипотезе Ны Гипотеза Нз принимается в случаях, когда: в) в экспериментах Аз и Аз предпочтение отдавалось ей, а в экспериментах Ас и Ал гипотезе Нп г) в экспериментах Аг и Аз предпочтение отдавалось гипотезе Нз, а в экспериментах Аз и Ал ..

гипотезе Нь Полагаем я, = О, если эксперимент А, «поддерживает» гипотезу Н„и х = 1, если в эксперименте А. предпочтение отдано гипотезе Нз (у = 1, ..., 5). Записать в виде булевых функций ул, (тв) и Гно(ха) условия принятия гипотез Нг и Нз (1д, (сез) = 1) тогда и только тогда, когда по набору Нз принимается гипотеза Н, (1 = 1, 2). Выяснить, возможна ли такая ситуация, когда окажутся принятыми обе гипотезы. 6) Четырем членам Вы Вз, Вз, Вл некоторой комиссии сформулированы следующие условия посещения заседаний (хотя бы одно из них они должны выполнить): а) в заседании не участвует ни Вы ни Вз, но должен быть Вз, б) в заседании принимают участие Вэ и Вл, но отсутствует Вз, .в) на заседании должны присутствовать Вз и В». у 1. Функции алгебры логики.

Операция гуперпогиции 23 Выяснить, обязан ли присутствовать на заседании комиссии член Вз, если в нем не участвует Вз. 7) Проект принимается, если большинство из шести экспертов Сы ..., Св высказалось в его пользу. Кроме того, проект все же принимается, если указанное условие не выполнено, но за, принятие проекта высказались: а) либо эксперты Сы Сз, Сз, б) либо эксперты Сз, Сл, Св, .в) либо эксперты Сы Св, Св.

Записать в виде булевой функции «" (о в) условие принятия проекта, считая, что оц = 1 в том случае, когда 1-й эксперт высказывается за принятие проекта, и л; = 0 в противном случае. Выяснить, будет ли обязательно принят проект, если известно, что за его принятие высказались ровно трое из экспертов Сы Сз, С4 и Св, а кто-то один из экспертов Сз и Св высказался против. 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 хд, ху. — ь ху, ~ ху, ). ху. Соответствующим об- разом записываются и более сложные формулы: например, форму- ла (((1 х) — ь у) Й (1(г Ь х))) в бесскобочной записи будет иметь вид Й -ь 1 ху 1). гх, Показать, что если каждую из связок Й, Ч, 9, — >, ~, ). оценить числом +1, связку 1 числом О, а каждый символ переменной . числом -1, то в бесскобочной записи произвольное выражение А над множеством б будет формулой тогда и только тогда, когда сумма оценок всех вхождений символов в А равна — 1 и в каждом собственном начальном отрезке выражения А (т.