Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 66
Текст из файла (страница 66)
Полагая затем, что 1(0, Ц=О,ибера в=у=2=О,получаем У(.((О, У(О, О) У(У(О, О), У(0 О))) = ХУ(О, Ц, У(1, Ц) = Х(О, П1, Ц) Отсюда, принимая во внимание условие задачи, выводим, что Д(1, Ц долж- но быть равно О. Но взяв х = 0 и у = 2 = 1, имеем .7Ц(0, У(1, Ц), ~(У(0, Ц, ~(0, Ц)) = 7(7(0, 0): ДО, 0)) = У(1, Ц = О. Это противоречит условию задачи. Следовательно, 7(0, Ц = 1.
Аналогично доказывается, что и 1(1, Ц = 1. Значит, 1" (х, у) = х э у или 1'(х, у) = 1. Палее соотношения а) д) проверяются непосредственно (например, с использованием основных эквивалентностей). 2) Но вытеказот. Лостаточно рассмотреть функцизо 1"(х, у) = х у. 125.4) 7* =(х — 1У) — 1(уэх) =хЧУ4(уНх) =1=0; д=(хНУ) й 3е (у Ч х) = х — 1 у л О. Значит, д не двойственна к 1. 6) Не является. 8), 9), 1Ц Является. 1.26. 2) Пусть формулы й и 4В (над множеством 8) эквивалентны. Тогда в силу Определвния эквивалентности формул реализуемыЕ ими функции Равны, т.е. 1'э = 1"х.
Значит, 1"я = 1"в. ПРимвнЯЯ УтвеРждение Ц данной задачи, имеем уя = 1я. и ув = ув*. Следовательно, ря* = ув-, т.е. Я* и 4В - — эквивалентные формулы. 127. Ц 1* = (х 1 ЧУ (ХЧО)Нх у 2)* = =(хЧО) ° (УЧХ (хЧУЧх)=х ° ((УЧХ) (УЧУ))=х (9642). 2) 7'" = хуЧ ху Чуя. 5) ~* = (х Фу) .з. 10) ~' = (х 'Н (я Ве)) у. 1.28. Ц Лве фиктивные переменные. 3) Одна фиктивная переменная. 5) Фиктивные переменные Х1 и хз. 1.29.
4) ( гн 1. 8) 7' гн 1. 9) ~ гн О. 10) 7 ов 1. Гв. й Способы забавна и свойшлви функций алгебры возика 329 1.30. 1) Существенных переменных нет. 3) Только хг. 9) ПеРеменные х1 и хг. 10) ПеРеменные хг, хз и х4. 1.31. 2) Достаточно рассмотреть функпию хг Ю хг.
3) Возможно ди фихсированных переменных. 1.33. 1) У функции нечетное число значений, равных 1. Значит, все ее переменные существенные. 2) Все переменные существенные (так как, например, ио ~ о1, оо ф ог, ОЗ г О11 И Сдо д'- Ог). 5) Лве существенные переменные - - хг и гз (оц = о,+1 (1 = О, 2, 4, 6, 8,10.,12,14); о»=оотг (1=0,1,...,7); од~од и оо~о4). 9) Три существенные переменные хг, хг и хд (оц = а,, 4 (1 = О, 1, 2, 3,8,9,10, 1Ц). 1.34. 1) При и ) 3.
2) При и ф 3. 3) При и = 2т»- 1 (т в 1). 4). 6) При и ) 3. 1.37. Имеем гдуогд — — (4474»(гду П 1»сд)) С (гдов»з71 П »Уд)). Значит, ~М7»ед~ = ~Юу(4- ~»Уд( — 2~йсу С Мд~. Так как (гуутд! нечетное число (см. условие задачи), то одно из чисел )»У7! и )447д( нечетное. НапРимеР, число )»УУ). Тогда фУнкциЯ 1 обРащаетсЯ в единицу на нечетном числе наборов, и в силу задачи 1.31, 1) каждая переменная у 7" существенная. 1.38. Ц х»хг, хг Ч хо, хг — 1 хг, хг — р хг, х1 -д хг, хг — 1 хг, х1 Ю хг, хг х, хг~хг, хгйхг.
2) ~Р'(Хз)~ = 218. 1.39. 1), 2), 5), 7)-10) Можно. 3), 4), 6) Нельзя. 1.40. 2) Лостаточно рассмотреть одну из функций — ди(х1, хг, хз) = = хгхг 4д хгхз »д хгхз или хг 64 хг р хз. 1.41. Если при отождествлении некоторой пары переменных хг и хг (1 < у < й < и) получается функция, тождественно равная О, то 1"(ха) должна обрадцаться в 0 на всяхом наборе вида (о», ..., о 1, е, 41,«1,...
..., од — 1, и, оьрг,..., о„). Но число таких наборов 2" . Значит, выполнялось бы неравенство ~гд'7 ~ ( 2" — 2" ' = 2" ', что противоречит условию задачи. 1.42. 2) Тот факт,что 49 нельзя заменить на й и 47, обосновывается, например, с использованием функций 7(х") = хз...х (и ) 3). 1.46. Наборы Д~ и 191+1 соседние при всяком 1' = О, 1, ..., й — 1.
Пустыг номер той компоненты, в которой наборы Н и Н „.1 отличаются друг от друга. Если 1(»з ) ~ )(19».1), то хц существенная переменная функции г(злн). Покажем, что числа 1о, 11, ..., 11, 1 (номера соответствующих компонент) все разные.
Прелположим противное, т.е. что для некотоРых Р и 9 (О < Р < У ( й — 1) выполнЯетсЯ Равенство гр — — гд. Тогда имеем р(1)р, 484) = р(Д~«1, 4»д) — 1. Используя это соотношение и «свойство треугольника» для расстаяния Хэмминга, пОлучасм й = РУо, дг ) < РЯо, 3р) ц- РУр, дд) + РЦЭР«, дг) < р — 1 1 — 1 < ) р(»81, д1« ) + р()Зр»-1, А) — 1»-') . р(ТЗЬ д1- ) < »=О 1=4 330 Ответы, указвнпя, решенпя < р + у р1)зп !дг~.з) — 1 + й — д = р + (д — р — 1) — 1 + й — д = й — 2, г =.гее Это противоречие показывает, что наше предположение ложно. Следовательно, все номера го, гы ..., гь г разные, а поэтому число существенных переменных у функции 7!х") не меньше числа перемен ее значений на рассматриваемой цепи, т.е.
нс меньше пь 2.1. 3) (10001000). 4) 10111011Ц. 7) (1111111111001100). 10) !1111111100000000). 2 2. 1) г !хо) = Уз (хг -з хА Н х ~ хо! УДУз) = Уг = (11001100). 3) 7(*з) = )ОППООО)! 7г)хчз) = (01ОПО10). 7) г Ех ) — хезхгхз 0З х4) Н хзузеж ); уо (х~) = 10101010110011001). 2.3.
2) хзхгхз Ч хзУгхз Н хзхгхз. 4) хгхгхз Ч хехгУ Ч:сехгхз Ч хзУгхз. 7) УзхгУзх4 Ч УзхгУзх4 Ч хзх хзУ4 Н хсйгхзх4 Ч хзхгхзхо 24. 1) езхз Ч хг)зеУз Ч Уг). 2) зехз Н Уг)зеУз Н хг)зеУз Н хг). 6) серег ч хг ч хз) еехз ч хг ч Уз)еехз и хг ч хз)еехз н хг ч Уз). 8) (Уз ЧУ Н хз Н хс)1Уе Ч Уг Н хз Н Уз)!Уз Ч Уг 'Н Уз Ч х4). 2.5. 2) 7о!ехз, хг) = хз ~ хг = УзУ Ч хо.'сг Ч хзУг. 5) ггз'еехм хг) = зе1101) = Уг Ч хг; 7) уз (хз, хз, х4) = хз — е хз — з хс = = 1хз Ч хз Н х4)1хз Ч хз Ч хз)1Уз Ч хз Н Ув). 9) гсоз (хы хз) = хз хз = УзхзН хзхз. ги 2.6. 2) Пусть д(хм х, ..., х„) = 1Ех ', х.
г, ..., х„"), где х * = У, при о., = 0 и х,* = х, при сг, = 1. Подходящее взаимно однозначное соответствие между подфункциями функций д и 7" задается так: подфункции д,"„'* *,"„"" 1хЗ") сопоставляется подфункция у~во ' '~, 1х"), где шь, = е =т, ' (0<пг(гс; 7=1,...,т). 4) Вытекает из 2) и 3). 2.7. 1) 7(х") = хз Н хг Ч... Н х„. Число разных подфункций равно 2ч -Ь 1. 2), 3) Разных попфункций 2" т~ — 1. 4) При л = 2 число разных подфункций равно 5, а при п > 3 их число 3 2" 5) 3 2" ' + 1. 6) 2о + 1. 7) При и = 3 число разных подфункций 9, а при и.
> 4 их 3 2г" г 4-5. 8) 2" 4- 7 при и > 4; 12 при п = 3. 2.8. При и = 2, используя прямой перебор, легко находим, что таких функций 8. (Это,7о(хз, х ) = О, зз(хз, хг) з— в 1, хз бз хг, хз тг, тз -э хг, хз -в хг, хг з хз и хг з хз.) При и > 3 сначала следует доказать, что функция 71хн) обладает таким свойством: если веса наборов а" и Сз" либо одновременно четные, либо одновременно нечетные, то 1!о") = 7))го). Значит, при п > 3 функция 7(х7') однозначно опродоляется значениями на 1"л.
1 Способы эа!)анин и свойства функций алгебры логики 331 наборах 0 и(1, О, ..., 0). Следовательно, тахих функций 4 (это фо(хо) = О, — ! ра 22(х") = 1, фг(х") = х! бах со... чг х и фз(х") = х! 62 ха чг .. Ю х Ю 1). 2.10. 4) ф(х ) = х! Ч хгхз хгхг Н хз = (х! Н хгха~ Ч (Уатг Н хз) = = х! Ч хгха Н х! Н х Н хз = т! Ч Уг Н тз. 10) ф(х ) = х! Ч х2(х2хз Н хзх4)х! Ч хзха = хахг(ха Н ха Н хаза)У!хала = хахгхзх4. 2.11. 1) ф(х ) = ((У! Н хг) б!Уах )(х! Хг(У! Н хг)) = = (тах Ю хахг)(х! Хг) = (Х449 тг)(х! Хг) = 0 = = (х! Ч хг)(х! Ч хг)(х! Н хг)(х! Н хг). 3) Дх ) = ха ха Ч хгхз Н х! Н хгхз = х! Н хг Н хз.
б) 1(х ) = (х! Н хг Ч хз Н У4)(х! Н хг Н ха 'Н х4). 2.12. 2) 24(хч ) = хай!ха Ч УЗУгхз Н хахгхзЧ хахгхз Н хахУ2УЗ Ч хахгхз = = хзУгУз Ч хзхгхз Ч хахгхз Ч хахгхз Ч хзхгхз. 5) 1(х ) = х!У! Н хахг Ч хахг Н хахг Ч хахгхз Н хахгхз = = хзхгхз Ч хахгхз Ч хзхгхз Н ха хгхзЧ УзУгУз Ч хайгхзЧ хатгхз. 2 13 1) Дтз) = (х! Ч хг Ч хз)(х! Ч хг Н Уз)(х! Н хзКх! Ч хз) = = (х! Ч х Н хз)(х! Ч хг Н хз)(х! Ч хг Н хз)(х! Ч хг 'Н хз)(х! Ч хг Ч тз). 5) (х! Ч Уг Н хзЦх! Ч Уг Н хз)(х! Н хг Н хзЦх! Ч ха Ч хз) бс бс (У! Н хг Ч хз)(х.
Ч хзЧ ха) се (х! ЧУг Чха)(х! ЧУ! Ч хз). 2.14. 3) 24(хз) = (х! Н хгхЯх! Н х! Н хз) = = хахг Н хахз Н хзхгУз Н хгУз = хзх Н хахз Н Угхз = хзхз Н хгхз. б) ф(х ) = (хгхг Н хзхз Н хгхз)(хгхз Н хгУ4 Н хзха) = = хах2хз Ч хзх2Х4 Ч аах2хзл4 Ч хах2хзх4 = хзх2хз Ч хах2ха. 2.15. 2) Дх ) = (х! Ч хг)(хг Ч хг)(х! Ч хз)(хг Н хз) Ч хгхз = = (х! Ч хгЧ хг)(х! Н хг Н хз)(хг Ч хз Н хг)(х! Н хг Ч хз) Й Й (х! Н хз Ч хз)(хг Ч хзЧ хз) = (х! Ч тг Н Уз)(хг НУ!)(х! Н хг Ч хз) = = (х2 Ч хз)(х! Н х2 Н хз). 5) Дх ) = (х! Ч хг)(хг Н хг) Ч хгхз = (х! Н хг)хг Н хгхз = = хг Ч хгхз = (хг Ч хг)(хг Ч хз) = хг Ч Уз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
