Задачи И Упражнения По Дискретной Математике, Гаврилов, Сапоженко, страница 10

6) 7(х з) (0010П 10 7) 7(х ) = (хг У хг У хз) . х4 У хгхгхз,' 8) 1(х ) = хг — > (хг — > хзх4); 9) 7(х ) = (010111110111001Ц: 10) 7(хв) = (0110111011100101). 2.5. Представить в указанной форме соответствующую компонен- ту функции 1(хо) (рассматривая эту компоненту как функцию от «оставшихся» переменных): 1) 1(х ) = хгхг -Ф хз, хз-компоненту в совершенной к.н,фц 2) У(хз) = (хз ~ хг) хз, хз-компоненту в совершенной д.н.фб 3) ((х ) = хгхг (хг тз), хг-компоненту в совершенной д. н. фд 4) 7(х ) = (11101101), хг-компоненту в совершенной д.

н. ф.; 5) 7(х5з) = (01011011), хз-компоненту в совершенной к.н.фл 6) Дхха) = (хг М хг Ч хз)х4 Н хгхгхз, хгхз-компоненту в совершен- ной д. н. фл 7) У(хд~) = хг — > ((хгхз -+ х4) — > хг), хг-компоненту в совершен- ной к. н. фд 8) У(х ) — ((хг ~ хг) (хз) ~ (хг.(х4), хз-компоненту в совершен- ной к. н. фд 9) Дх~) = (0110111010110111), хгхв-компоненту в совершенной д.

н. ф.; 10) 7(х~) = (1011011101111000), х4-компоненту в совершенной к. н. ф. 2.6. Показать, .что число различных подфункций у функций 1" (хи) и д(ха) одинаковое, если: 1) функция д(ха) получается из функции 7(ха) переименованием переменных без отождествления; 2) функция д(х") получается из функции Д(х") заменой некото- рых (быть может, всех) переменных на ик отрицания; 3) д(хп) = 1'(х"); 4) функции 1"(х") и д(х") двойственные. 2.7.

Подсчитать число различных подфункций у функции Дхо), хд- и хюкомпоненты которой известны (напоминаем, что подфунк- ции функции Д(х") следует рассматривать как функции, зависящие от всех переменных хы хг, ..., х„): 1) Д(хо) =хг 'д...'~хп, Й(х, ) = 1 (и Э 2); 2) уо(х") = хг 61 ..

61 ха Л(хп) = хг бз .. 6зхп (и ~ )2), 3) 1о(х ) =*я . хо Л(х ) = хг ..хо (и 3 2); 4) уо(хп) = тг ..хоЧхг...хп, Д(хп) = хг...х, (и > 2); 5) 1о(х ) = хг . хо; Л (х ) = хг у ... у х, (и 3 2); 5) Д(х ) =гг дхп Л(х ) хз о ° Лхо (п~)3)~ у в. Савциальиыв представления булевых функций 47 7) ув)Хь) = ХЗ...Хь, Д)Х") = Х2'4 ХЗ )П ~ )3); 8) Уо~1х в) = хз -+ х„, 21 1хв) = хз... х„1п > 3). 2.8. Найти число функций 11х"), удовлетворяющих условию: 2во21х") = Я1х") при всех 4, у таких, что 1 < 1 < у < и.

2.9. Показать, что число различных функций 2'1х"), для которых данная функция 21хь) является цодфункдией, не меньше 22 — 122 — 1)2 1к < и). 2. Днзъюнктнвные н конъюнктнвные нормальные формы. ФоРмУла х,'вгх;ьвв ... ввх;', где ов 6)0, 1), х, — ха х, — хп~ 1ьс11,2,...,11), 1=1,2,...,г )г>1 и п>1), называется конъюнкцией иад множеством Х" = 1х1, хэ, ..., х„). Аналогично, формула х~,' 12 х~,' 42...

42х," называется диэьюнкцией над .ииожествои Х". Если х,, у'. -х;,„при у ~ в, то конъюнкция 1соответственно дизъюнкция) называется элементарной (сокращенно э. к. и э. д, соответственно). Выражения вида х, ' называются буквами. Число букв в э. к. 1и в э. д.) называется рангом э. к. 1соответственно э. д.). Константа 1 считается по определению э. к.

нулевого рангоь а константа 0— э. д. нулгвого ранга. Формула вида оь К уК 12 12К 113) ( краткая запись 1„4 К4), где К; .. попарно различные элементарные конъюнкции 11 = 1,2,..., в) и в > 1, называется диэъюиктивной нормальной формой 1сокра4ценно д. и. ф.). Формула вида Уб — Р1 ьг Р2 ьв ° ~ Рз 114) (краткая запись Й Р4), где Р, попарно различные элементарные дизъюнкции 14 = 1,2, ..., в) и в > 1, называется конъюнктивной нормальной формой 1сокращенно к. н. ф.). Число в в формулах 113) и 114) называется соответственно длиной д.

н. ф. и длиной к. и,. ф. Сумма рангов всех конъюнкций, входящих в д. н. ф., называется сложнослюю д. н. ф. Аналогично, сумма рангов всех дизъюнкций, входящих в к. н. ф., называс тгя сложностью к. н. ф. Дизъюнктивная 1соотвотственно конъюнктивная) нормальная форма над множеством переменных Х" = 1х1, хз, ...., х„) называется совери1еииой., если она составлена из элементарных конъюнкций 1соответственно элементарных дизъюнкций) ранга и 1ср. с определением в и. Ц. Простейший (но весьма громоздкий) способ построения дизъюнктивных и конъюнктивных нормальных форм для булевых функций состоит в использовании эквивалентных преобразований. Пример 6.

С помощью эквивалентных преобразований построить д н.ф фуНКЦИИ 11х ) = 1121 2 22тз) ' 122 9 хзх4) 2 х1хзх4)42 "Х112 ° 48 Гя. 1. Способы задания и свобыпва фуикиий аягебрь1 возики Решение. Используя основные эквивалентности из 31, преобразуем «постепенно» части формулы, задающей функцию 11Х~), к д. н. фл Х1 с Х2ХЗ Х1 Ч Х2ХЗ (см. 8, в)) хг 1Х хзх4 = хгхзха Ч Угхзхз = хг(УЗ Ч ха)Ч Угхзха; (см. 8, .а) и 4, а)) (Х1 1 Х2ХЗ)(хг Ю ХЗХ4) + У1хгхя = = (х1 Н хгУЗ) (хг(хз ~1 УЗ) Ч Угхзха) -+ Угхгхя — — 1см. 8, в)) = (У1 Ч ХЗУЗ)(хг(УЗ Ч Уа)Н Угхзха) Ц Угхгха = (см.

4, а)) = У1 и Хгхз 11 Хг 1УЗ и УЗЬУЗХЗХ4 11У1хгх4 = (см. 4, б)) Х1 Х2ХЗ 1 Х21УЗ 3 Ув) ссУгхзх4 Н Угхгхв = (см. 7 д) и 4 а)) = х1 хг Ч хз) с (хгя Уз Ч Х4)(хг Ц хз Ч ха)Ч Ч Х1Х2Х4 (см. 3, в), 4, б), 7, д) ) = хгхг ' ' 21хз ' ' (хг Н хзхв) хг 1гхз Ч Ув)Ч Х1хгх4— (см. 3, в), 7, а), 7, в) ) = х1хг о х1хз Ня хгхз с хгх4 'с хгхзхе Чс хгхгх4 11; ~(х ) = х1х2 Ч х1хз Ч х2хз Ч УЗУЗ Г хгхзх4 ч У1хгха Ч У1Х2— (см. 4,а), 7,д)) = ХЗУЗ Ц хгхз ЧУгУЗ Ц УЗУ4 Ч хгхзхв 2 Угхгха с 'сХ1 'Х2 — Х2ХЗХ4 3 1хгх4 г 1 схг— — 'гхзх4 'с Х224 'с Х1 с Х2 (см.

5,а)) (см. 6,а)) (см. 5,а)) (см. 6,а)) = Хгхя Ч Х1 Ч У2 =Х1 'с Хг СХ4. Очевидно, что полученная д, н, ф. является и к, н, ф. Если булева функция задана некоторой д.н.ф., то совершенную д. н. ф. этой функции можно получить, используя преобразования вида А = А хЧ А.х и АЧА = А. Аналогично, совершенная к.н.ф, булевой функции может быть построена из какой-либо к, н, ф, этой функции спомощьюпреобразовапийвица А = (А''х) (АОУ) и А А = А. Дистрибутивный закон х . (у Ч 2) = х у'д х, . 2 (см. 3, а) в 3 1) совместно с эквивалентностями х х = х, х х = О, А .

О = О, А Ч О = А и законом поглощения А Ч А В = А позволяет переходить от к. н, ф. булевой функции к некоторой д. н. ф., задающей эту же функцию. Аналогично, используя дистрибутивный закон х Ч у 2 = (х Ч р) . 1Х, Ч 2) (см. З,б) в 21), эквивалентности ХЧХ=Х, ХНУ=1, АЧ1= 1, А . 1 = А и закон поглощения А . (А Н В) = А, можно иэ д. н. ф, булевой функции построить некоторую к. н. ф. той же функции. у Я. Специальные предепгавленпн булевых функций 49 П р и м о р 7. Используя преобразования вида А = А х Ч А х и А Ч А = А, построить совершенную д. н. ф. функции Д(хйз) = = У1 Ч хгхг Ч хгхз.

Решение. Функция у задана д.н.ф. Каждая из входящих в эту д. н. ф, конъюнкций элементарная. Значит, для построения совершенной д.н.ф. достаточно «пополнить» каждую из конъюнкций недостающими буквами х;, применяя соотношение А = А. х Ч А х, а затем устранить повторения («привссти подобные слагаемые») с помощью эквивалентности А Ч А = А. Имеем х1 = хгхг Ч У1УЗ = = х1х2хз Ч х1х2хз Ч х1х2хз х1х2хз1 Х1х2 = х1Х2хз Ч хгх2хз, х2хз = = хгтгтз ч хгхгхз. Следовательно, ~(х ) = хзхгхз ч хзхгхз ч х,тгхз ч Ч х1х2хз Ч х1х2хз Ч х1х2хз Ч х1Х2хз. Пример 8.

Применяя дистрибутивный закон хЧ уг = (х Ч у) х х (х Ч г) и эквивалентности и Ч х = 1., А Ч 1 = 1 и А 1 = А, преобразовать д.н.Ф. х1 Ч хгхг Ч хгхз в к.н, ф. Решение. Имеем х1Ч У1 .хг = (х, ЧУ1) (х1 Ч хг) = 1ое(х1Ч Ч хг) = х1 Ч хг. Лвлес, (Х1 Ч хг) Ч хгхз = (х1 Ч хг Ч Уг) оье (ХЗЧ хг Ч Чхз)=(х1Ч1) (х1Чхгцхз)=1.(х1ЧхгЧхз)=хгЧхгцхз. Пример 9. Подсчитать число функций г"(Уп), у которых совсршенная к. н, ф. является одновременно и д, н, ф.

(не обязательно совершенной) . Решение. Совершенная к.н.ф. функции у(х") есть «произведение» элементарных дизъюнкций ранга и: Р, Рг .... Р, (в > 1). Если и = 1, то имеется три возможности: Х1, У1 и х1 . х1. Очевидно, что дизъюнктивными нормальными формами являются только х1 и х1 (причем даже совершенными д. н, ф.), Пусть теперь и > 2. Если з > 2, то формула Р, Рг ....Р, нс может быть д.н.ф., так как в каждой элементарной дизъюнкции Р, содержится не менее двух букв.

Значит, нужно исследовать только случай, когда в = 1. Имеем Г(хп)=х 'ЧхвЧ...ЧХ„", где п,б(0,1) (1=1,2,...,и). Каждая такая функция однозначно определяется заданием набора (а1, иг,..., и„). Следовательно, число соответствующих функций равно 2" (при любом и > 1). П р и м е р 10. Найти длину совершенной д. н. ф, функции у'(х " ) = =(х1ЧхгЧ... Чх„) (х1ЧхгЧ... Чх„), и,>2. Решение. Принимая во внимание определение длины д.н.ф.

булевой функции и процедуру построения совершенной д. н. ф., описанную в з 1, заключаем, что длина совершенной д. н. ф. равна мощности множества 1Чу (множества наборов, на которых функция у обрагцается в 1). Следовательно, достаточно выяснить, на скольких наборах значений переменных выполняется равенство (Х1 Ч Уг Ч... Ч Уп) . (х1 Ч Х2 1 ° Ч Хл) — 1. Очевидно, что это равенство справедливо тогда и только тогда, когда х1 Чхг Ч... Ч х, = 1 и х1 ЧхгЧ ... Чхо = 1. Палее, элементарная дизъюнкция х ' Ч х,' Ч... Ч х„обращается в 1 на любом нв; боре, кроме набора (о1, ог, ..., пп), ибо если х, = ее, для нскоторо- 4 Г.