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

З,б) в 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),7(х ) = х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) 1(У ) = х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) 1(х ) = (хУг Чхг Чхз Чха) хг ЧУнЧхз) (хг Ч хл). 2.15. Используя дистрибутивный закон х Ч у г = (х Ч у) Ус (т Ч г) и эквивалентности хЧ х = х, хЧ У = 1, А Ч 1 = 1, А 1 = А и А (А Ч В) = А, перейти от заданной д.н.ф. функции 7"(хп) к ее к. н.

фл 1) 1(х ) =хгУг'Чхе', 2) 1(х ) = хзйг Ч ггхз Ч хгхз; 3) 1(х ) = Уг Ч хгхз Ч хгхз', 4) 1(х ) = Уг Ч хг Ч хгУгхз', 5) ((х ) =УгУг ЧУг Ч хгУз, '6) ге(х ) = хгхг Ч хгхз ЧУгхл Ч хзхл,' 7) 1(х ) = хгхгУзхл Ч хгхгхз Ч хгхл:, 8) Х(х ) = хг Чхгхз'ЧУгхзхл'Чхгхзхл. 2.16. Доказать, что переменная х; функции 7'(хп) У': 0 является фиктивной тогда и только тогда, когда совершенная д.н.ф, этой функции вместе с каждой элементарной конъюнкцией К содержит также конъюнкцию Кп отличающуюся от К..

только г-й буквой, т.е. К = х~* К и К~ = х~*К, где К -- конъюнкция ранга п. — 1. Замечание. Справедливо также утверждение, двойственное задаче 2.16: переменная х, является фиктивной переменной функ- ции 7'(хп) ~ 1 тогда и только тогда, когда совершенная к.н. ф. этой функции вместе со всякой элементарной дизъюнкцией Р содержит такую элементарную дизъюнкцию Рп которая отличается от Р лишь г-й буквой, т.е.

Р =х,* ЧР и Р~ =х,* ЧР, где Р дизъюнкция ранга п — 1. 2.17. Подсчитать число функций 7(хп), у которых совершенная д. н. ф. удовлетворяет следующему условикп 1) отсутствуют элементарные конъюнкции, у которых число букв с отрицаниями равно числу букв без отрицаний; 2) каждая элементарная конъюнкция содержит котя бы две буквы с отрицаниями (и ) 2); 3) отсутствуют элементарные конъюнкции, содержащие нечетное число букв с отрицаниями; 4) в каждой элементарной коныонкции число букв с отрицаниями не больше числа букв без отрицаний; 5) какова бы ни была элементарная конъюнкция Км найдется (другая) элементарная конъюнкция Кп отличающаяся от К только первой буквой (т.е. К = х 'К и К~ = хв'К, где К -- конъюнкция ранга п, — Ц; 52 Гл, й Способы задания и ввойапва функций алввбрьт логики 6) какова бы ни была элементарная конъюнкция Км натщется элементарная конъюнкция Кт, отличающаяся от Кг двумя первыми буквами (т.е.

К, = хв'хвгК и Кт = хт'х~~'К, где К вЂ”. коньюнкция ранга и, — 2 (и, > 2)). 2.18. Найти длину совершенной д. н. ф, функдии т'(хи); 1)Дхп)= )/ х;х, п>2; 1« т< 2) т"(хп) = т~г (х, т х,), п > 2; тйь<1<п 3) У(х") = (((хт ~ хг) ~ хз) ~ ~ хп — т) ~ хп, тт ) 2; 4) У(хй ) = хт — т (хг т (хз т ° т (ха — 1 т хп) ° ° )) тт 3 2; 5) .т (х ) — ( ° ((хт > хг) + хз) т ° ° хп — 1) > хп и > 2~ 6) т'(хп) = (хт''Охг) (хт М хг) — т тг ...

х, и > 3; 7) У(хп)=хтхг...х бтхзто...~Зх, п>3: 8) Дхп) = (хт ттхг М хз '~ . Л х„) — ~ ((...(хз ха) хп т) х„), тт > 4. 2.19. Пусть множества Х = (хы ..., х ) и У" = (Ут,, У ) не пересекаются. Предполагая, что длины совершенных д. н. ф. функций 1(х'и) и д(у") равны соответственно к и 1, найти длины совершенных д. н. ф. следующих функций: 1) У(х )ттд(д"), 2) У(х ) д(у"); 3) У(х ) ОЗ д(у"); 4) У(х") -+ д(туп).