Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 10
Текст из файла (страница 10)
В самом деле, если, например. 1(0, хг) = сг, то функция г"(1, хг) должна быть равна тождественно а; но тогда (см. формулу (2)) (х~ при о = О, г(х ) =хгогхго= )— ~хг при о =1, т.е, фУнкциЯ 1(х ) зависит несУщественно от пеРеменной хг, что противоречит условию.
наложенному на функцию Г" (ха). Палее, так как функция 1(хг) существенно зависит от обеих переменных. то 1"(О, х ) ф 1'(1, хг) и 1'(хы 0) ф 1'(х, 1). действительно, если, например, ДО, хг) = 1(1, хг), то, используя формулу (2), получаем (ср. с решением примера 4): 1"(х ) = хг1"(О, хг)'дхг1'(1, хг) = хг1"(О, хг) Ч У хг1'(О.,хг) = (хг Ч хг) 1'(О, хг) = 1 4с 1'(О,хг) = 1(О,хг), т.е. переменная хз фиктивная. Это противоречит условию, наложенному на функцию 1(хзг). Из всего сказанного относительно функций 1(0, хг), 1'(1, хг) 1'(хы 0) и 1'(хы 1) следует,. что ДО, хг) = хг, .1'(1, хг) = = хго = хг — — хг, 1 (хы 0) = хг и ~(хы Ц = х' = х'.
Отсюда вытекает, что у функции у(юг) семь разных подфункций: она сама., О., 1, хсы у ец Специальные представления булевых функции 45 хы хг и х,. Нетрудно получить и выражение для функции 1(х ), воспользовавшись, например, формулой (10): з (х ) = хзх2 и хзх2 = (Х1 ч' 1) Х2 ® хз(Х2 йз 1) = хгх2 ~~ Х2 л' хзх2 ~~ хз х! ® 22 (Х4 хг, если П = О, = хз ег хг е4 и ев 1 = 4( (хзйхг, если п=1.
(Здесь, как и выше, мы использовали эквивалентности х, = х" Ю 1, а также очевидные тождества х = х - и = хааа.й 1.) 2.1. Рассматривая соответствующую компоненту функции 7'(хп) как функцию, зависящую от всех переменных хы хг, ..., Хп, представить ее в векторной форме: 1) з (Х ): Хз + (Х2 чг Хзхз), Х2-КОМПОНОНту 2) ((х ) = Хзхг ~ (Хг — 4 хгхз), хз-компоненту; 3) 7 (х ) = (Уз '4 х2 ~l хз) 4 (хз 4 (У2 е хз)), хыкомпоненту; 4) 2'(х ) = (01110100), хыкомпоненту; 5) 2 (х ) = (11001110), хг-компоненту; 6) з (х ) = (10011110), хз-компоненту; 7) з (х ) = (хз ез хг) — > (хз — 4 хзх4), хгхл-компоненту; 8) з (х ) (хз дх2хз Ч х4) аг (хзхгхз е х4), х1У2хз компоненту; 9) 7'(х~) = (0101011011100011), Угхв-компоненту; 10) ((х ) = (1101101100001001), хгхзх4-компоненту.
2.2. Используя хз — и У,-компоненты функции 7" (хп), построить в векторной форме ее х -компоненту, причем эту компоненту следует рассматривать как функцию, зависящую от всех перемен- НЫХ Хмхг~ . ~ Ха' Ц (1( 3) х > хз 74(хз) — Х2 хз кОмпоненту 2) л ( ) х е (х ) хз хз, хыкомпоненту; 3) лз(.-з) (00111100), фх ) = (Ш10000), хг-компонентУ ) 2(хз) (10101111) у2(хз) х, ~ хз, уз-компоненту; 5) ~~(Х ) =Т ЯЗХ4,(~(х ) =Х2 '4Х4) Х2 У 6) у2(х4) — х ) х Х4 Д(х4) = Узхзхв, х4"кОмшшснту~ 7) зо(х ) = хгхз ~Э х4, з'4 (х ) = (1011011110110111), хз-компоненту.
2.3. Представить в совершенной д.н.ф. следующие функции: 1) з (Х ) (хз ПХ2) е Хз 2) з (х ) (Х1 е Х2) е (хз ~ хгхЗ)~ 3) Д(х з) (01010001) 4) Д(х з) (01111000) 5) з'(х~) = (10001111); 6) з'(х~) = (хз -4 хгхзхл) (хз — + хзхг); 7) 1(х~) = (хзйзхг) (хз — 4 хгх4); 8) 1(х~) = (0100100011000010); 9) 7(х~) = (1000011100110001); 10) 7(х~) = (1100100010010011).
46 Га. 1. Способы задания и свойыпва угупкиий ааеебрь~ возики 2.4. Представить в совершенной к.н.ф. следующие функции: 1) 7(х~) = хг 9 хг, 2) 7(хг) = хе .( хг., 3) 1(х') =х,хг гх,хз 1х,х,; 4) Дх') = х,х, Юхе; 5) 7'(х з) (01011101). 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), х, — хц х, — хь~ ььс11,2,...,п), к=1,2,...,г )г>1 и п>1), называется конъюнкцией иад множеством Х" = 1х1, хэ, ..., х„). Аналогично, формула х~,' 12 х~,' 42... 42х," называется диэьюнкцией над .ииожестаои Х".
Если х,, у- 'х;,„при у ~ к, то конъюнкция 1соответственно дизъюнкция) называется элементарной (сокращенно э. к. и э. д, соответственно). Выражения вида х, ' называются буквами. Число букв в э. к. 1и в э. д.) называется рангом э. к. 1соответственно э. д.). Константа 1 считается по определению э. к. нулевого раигоь а константа 0— э.
д. иулсоого ранга. Формула вида о~ К уК 12 12К 113) ( краткая запись 1„4 К4), где К; .. попарно различные элементарные конъюнкции 11 = 1, 2,..., 2) и э > 1, называется диэъюиктиоиой нормальной формой 1сокра4ценно д. и. ф.). Формула вида Уб — Р1 ьг Р2 ьг ° ~ Рз 114) (краткая запись Й Р4), где Р, попарно различные элементарные дизъюнкции 14 = 1,2, ..., 2) и э > 1, называется конъюнктионой нормальной формой 1сокращенно к. и. ф.). Число я в формулах 113) и 114) называется соответственно длиной д.
и. ф. и длиной к. и,. ф. Сумма рангов всех конъюнкций, входящих в д. н. ф., называется сложностью д. н. ф. Аналогично, сумма рангов всех дизъюнкций, входящих в к. н. ф., называется сложностью к. и. ф. Дизъюнктивная 1соотвотственно конъюнктивная) нормальная форма над множеством переменных Х" = 1х1, хз, ...., х„) называется сооери1еииой., если она составлена из элементарных конъюнкций 1соответственно элементарных дизъюнкций) ранга и 1ср. с определением в и. Ц. Простейший (но весьма громоздкий) способ построения дизъюнктивных и конъюнктивных нормальных форм для булевых функций состоит в использовании эквивалентных преобразований.
Пример 6. С помощью эквивалентных преобразований построить д н.ф фуНКЦИИ 11х ) = 1121 2 хгТ2) ' 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) (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
