Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 11
Текст из файла (страница 11)
и. ф.). Формула вида Уб — Р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 Г. П. Гаврилов, А. А. Саножепко 50 Га. й Способы задания и свойыпва 21уикпий аягебрь1 возики Значит, дизъюнкция х1 Ч Уг Ч... Ч х„равна 1 на всех наборах, за исключением единичного набора 1 = (1, 1, ..., 1), а дизъюнкция х1 Ч "хг Ч...
Ч хп равна 1 на всяком наборе, кроме нулевого: 0 = (О, О, ... ..., 0). Таким образом, получаем ~2Ч1 ~ = 2" — 2. 2.10. С помощью эквивалентных преобразований построить д. н. ф. функции ~(у"): 1) ~(х ) = 1сУ1 Ч хг Ч хз) . (Х1 хг Ч хз); 2) 11х ) = (Узхг 9 Хз) . (Угхз 4 Хг); 3) 7(х ) =(Х1 хг)ч(хзхз6'1хг -эхз)); 4) ~(х~) = (Х1 4 хгхз) 4 ИУ1 ~ хг) ) хз); 5) ~(х ) = х1 — + (хг 4 хз) 63 (Х1 ~ (хг Ю ХЗ))', 6) ~(х ) = хгх2 ч Уз (х1 4 Х2хз); 7) 11'ХЗ) = (Х1 Ч хгхз) . (Х1Уг Ч Хз) 1хгхг Ч хз); 8) г(ХУ ) = (Х1 Ч хгхзх4) ' Ях~ Ч Х4) В хгх ) Ч Уг (хз Ч Х1У4):, 9) ~(х ) = (Х1 4 Х2) (Хг 1 ХЗ) ' (ХЗ 1 Х1Х4)~ 10) 2 (Х ) 1Х1 4 Х2) (1хг ~ 2'3) Х1Х4) 1Х1 4 1ХЗ ~ Х4)) 2.11. Используя эквивалентные преобразования, построить к.н.ф. функции 7(хо): 1) ~(х ) = ((Х1 с У2) Ю (Х1 ~ У2)) ' (Х1 22 ' (Х1 с Х2)); 2),~(х ) = х1Х2 1 (х1 ф (хг (х1 + хг)))) 3) ~(х~) = хзтг Ч хгхз Ч (х1 — 4 хгхз); 4) Дх 3) = (У1 — 4 (хг — 4 хз)) 61 х1хгхз, 5) 11х ) = (х1 (хг -4 хз)) Ч (хг — 4 хгхз); 6) 1 (х ) = хзхг Ч хгхз Ч хзх4 Ч хгх4,' 7) ~(х ) = (Х1 хг)Ч (Х1хз Х4)Ч хгхз.
2.12. Применяя преобразования вида А = А . т Ч А . х и А Ч А = = А, построить из заданной д.н.ф. функции Дхп) ее совершенную Д.Н, фс У(х ) х1х2 " 23 2) 7(х ) — ХЗУ2 ч Х223 1' х123; 3) У(х~) = т1 Чхгхз ЧУгхз, 4) 7(х') = хгхг Чхгхз ЧУЗ', 5) 1(х~) = Х1 ЧУг Ч Х1хз; 6) 1(х~) = х1хгхз Ч хзхзх4'; 7) 1"1Х ) = хгхг Ч Угха Ч хзх4, 8) 11У ) = х1 Ч 1сгхз Ч хгх4. 2.13. С помощью преобразований вида А = (А Ч х) (А Ч х) и А . А = А построить из заданной к. н. ф. функции Дхп) ее совершен- ную к.н. фс ~(х ) = (Х1 ~ У2) ' ХЗ', 2) 1 1Х ) = (Х1 Ч .'с2) ' (Уг ХЗ) ' тз', 3) 1(х ) = (Х1 22) ' (Х1 Ч хз) ' (хг Ч хз); 4) Г(хз) = Х1. Хг ' (У1 Ч хз) (х1 ЧУЗ)' 5) 141х~) = 1У1'Ч хг) ° хг ° '1х1'Ч Уз) ° 1Уг Ч хз); 6) 11Х ) = (Х1 Чхг 1 хз) ' 1Х1 ЧхгЧХ4) 7) 1(Х ) = (Х1 ЧХ2) '(ХЗЧХЗ) (ХЗ ЧХ4); 8) 7 (х ) = х1 Уг хз .
1Х1 Ч Уг Ч хз Ч 24). у 2. Спеииальпые предеппавлеаин булевых фупкиий 51 2.14. Используя дистрибутивный закон х(у Ч г) = ху Ч хз и эквивалентности х х=х, х х= О, А 0=0, АЧО= А и АЧ ЧА В = А, перейти от заданной к.н.ф. функции 7'(хп) к д,н,фл 1) 1(х з) = (У, Ч У,) . х„Ч з) (Уг Ч Уз). 2) 1(х~) = хг (хг Ч хг Ч Уз) . (хг ЧУз); 3) ((х ) = (хг Ч хг) ° (хг Ч хз) (хг Ч хг Ч хз); 4) гл(х ) = (Уг Ч хг) (Уг Ч хз) (Уг Ч хз) (хг Ч хз); 5)1(х )=(хгЧхгЧхз). хгЧхгЧхз) (хгЧхгЧхз); 6) ((х~) = (хг Ч хг) (хг ЧУз) (хг Ч ха) (хз ЧУл); 7) ~(х~) = (хУг Чхг Чхз Чха) хг ЧУнЧхз) (хг Ч хл). 2.15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
