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

(Э х «хи (Э хих1)' 3) 7(хп) = ((х1 «7Х2 2..Лхп) — «х1 хг ... хп) -« — «(Х1 гЭ хз гЭ... ЭЗ хгг це 1); 4) «(Т.и) = (Х1 — «(Х2 — « . — «(,Хп — 1 — «Хп) .)) -«(Х1 — «Хп)(Х2 -«Хи)... (Хи 1 -«Хи); 5) У(хи) = (х ~ хз) Е (хг ~ хз) Э " 6 (хп — ~ х.) Е (х. ~ х ); 6) У(Х ) = (Х1 «Х2)(Х2 «ХЗ) ° ° ° (Хп — 1 «Хп)(Хп «Х1) (Х1 (Э Х2 и« ° ° ° гЭ хгг). 1.35. Булевы функции Дх") (и > 1) и д(у™) (т > 1) существенно зависят от всех своих переменных.

Переменные Х1, ..., Х„„у«, ... ..., уп, попарно различные. Показать., что функция 1(д(у«г ..., у ), Хг г ..., Х„) СУЩЕСТВЕННО ЗаВИСИт От ВСЕХ СВОИХ ПЕРЕМЕННЫХ. 1.36. Локазать, что всякая булева симметрическая функция (см. задачу 1.6, 7)), отличная от константы, существенно зависит от всех своих переменных. 1.37. Пусть п > 1 и функции ахти) и д(хп) таковы, что сумма 2'(хи) (Э д(хи) обращается в 1 на нечетном числе наборов.

Доказать, что длЯ всЯкого 1 = 1, ..., п пеРеменнал хг ЯвлЯетсЯ сУществснной хотя бы у одной из функций, 2" или д. 1.38. Через Р" (Х") (и > 1) обозначим множество всех булевых фУНКЦИй, ЗаВИСЯЩИХ От ПЕРЕМЕННЫХ Х1, Хз, ..., Хи И ПРИ ЭТОМ От каждой из них существенным образом. 1) ВЫПИСатЬ ВСЕ фуНКцИИ МНОжЕСтВа Ре(Х2). 2) Найти число элементов множества Р'(Хз). и 3) Локазатьг что ~Р" (Х")) = 2 ( — 1)" („) 22 я=а 4) Показать, что 1пп „= 1. )Р'(Х")) и — гж 22" 38 Гл, 1. Способы задавил и свойапва функций алгебры логики 1.39.

Выяснить, можно ли из функции 1, отождествляя и переименовывая в ней переменные, получить функцию д: 1) ((;з) (11001011) (-г) (1011). 2) 1(х ') = (10101100), д(хг) = (1000); 3) 7"(хз) = (00110010), д(хг) = (0110); 4) 1'(х~) = (011011011110001Ц, д(хз) = (01100111); 5) 1(хл) = (1111110100011011), д(хг) = (100Ц; 6) 1 (Х ) Х1Х2 Ч Х1ХЗ Ч Х2ХЗ .У(х ) Х1хг~ 7) 1(х~) = (Х1 ''хг)хз сохгхг, д(хг) = Х1 нхг,' 8) У(х ) = (х1 -+ (хг -+ хз)) -+ (х1 -4 хз), д(хг) = х1 -+ хг,' 9) 1 (Х ) = (Х1Х2 М ХЗХ4) 1 (Х1Х2 е (ХЗ Ч Х4)), д(т ) = х1 — 4 (хг 11 хз); 10) ((х') = (х,х, 11 х,х,) 111(х,,х, 11 х,х,), д(х ') = х, ~ х,.

1АО. 1) Доказать, что если функция 1(хз) существенно зависит от всех своих переменных и удовлетворяет условию 1(0) = 1(1), то найдется пара переменных, отождествляя которые можно получить функцию, существенно зависящую от двух переменных. 2) Показать, что условие 1(0) = 1(1) отбросить нельзя. 1.41. Пусть и ) 2 и функция 7(хп) такова, что ~й11~ > 2" Показать, что при отождествлении в ней любых двух переменных получается функция, отличная от тождественного нуля. 1.42. 1) Пусть функция 1(Х1, хг, хз, ..., х„) (п > 3) удовлетвоРЯет Условию: сУмма 1(0, О, хз, ..., Хп) Ю 7(1,. 1, хз, ..., х,) обРашается в 1 на нечетном числе наборов. Доказать, что в этом случае фУнкциЯ 1(Х1, хг, хз, ..., Хп) сУп1сственно зависит от всех п — 1 переменных.

2) Показать, что утверждение 1) справедливо и в том случае, когда вместо сУммы 1(0, О, хз, ..., х„) Ю 1(1, 1, хз, ..., Х„) беРетсЯ импли- кациЯ 1(0,. О, хз, ..., Хп) 4 1(1, 1, хз, ...,. Х„). Однако заменить Ю на вс или Ч нельзя. 1.43. Доказать, что число О(д(хп)) тех функций 7(Х1, хг, . ..., х„, х„е1), из которых отождествлением переменных можно полу- ЧнтЬ ДаННУЮ ФУНКЦИЮ д(Хп) = д(Х1, Хг, ..., т.„), УДОВЛЕтВОРЯЕтСООтношению Фд(*")) 11ш „= 1. и — 4ж П 22" 1А4.

Пусть функция 1(хп) удовлетворяет условию: для некото- рЫХ НабОрОВ Оп, 11п И у" таКИХ, Чта Пп -4 )дп -4 у", ВЫПОЛНяи1тея .- ~(1")=И") ~~((д") Д ка--, -: 1) функция 1"(х") зависит существенно не менее чем от двух переменных; 2) можно так отождествить переменные у функции 1"(хп), что получится функция, существенно зависящая не менее чем от двух, но не более чем от трех переменных. у и Специальные првдсгпавленан булевых функций ЗО 1Аб. Показать, что если функция Дх") существенно зависит не менее чем от двух переменных, то найдутся три набора а", Да и у ", удовлетворяющие условиям р1Л", 53 в) = р155гц у" ) = 1, сх" ~ ун и 51Л а5: у(7н) ~ у(55 и) 1.46. Последовательность вершин ~5о, Вг, ...,Д г, Д„куба В" называется ггеггью 1длиньг к), соединяюгцей вершины 55о и Дь, если р(55г, 55,ьг) = 1 при г = О, 1, ..., и — 1. Пусть функция Дх") изменяет свое значение т раз (т ) 1) в вершинах некоторой цепи Ло, 55г, ...,.55ь г, 55,о соединяющей вершины 55в и Д такие, что р1ь5о, 55ь) = к.

Локазать, что функпия 51х "г) существенно зависит не менее чем от т переменных. 1.47. Показать. что если функция Дхгг) существенно зависит от переменной х; 11 < г < п), то двойственная ей функция ~'1х гг) также зависит существенно от переменной хо О 2. Специальные представления булевых функций 1. Разложения булевых функций по переменным. Совершенные дизъюнктивная и конъюнктивная нормальные формы.

Пусть 11х") булева функция и 1 < гг < гх « ... г,ь < и. Функцию, получаемую из давка) подстановкой на места переменных хгы хео ..., хг„констант ог, оз, ..., оь соответственно, называют х„'х„г ... х,„'-компонентой функции Дхв) или подфункцией функции Д~х") и обозначают через ф "," ","1х") или Я ' 'Д~х ).

При А — О подфункция функции Дх ) просто совпадает с самой этой функцией. Если к ф О и к р'. -и, то подфункция Д'„'г "'"(ха) называется собстввннои. Подфункции функции 5'1х") различны., если они отличаются как функции от переменньгх хг, хх, ° ха. Справедливо следующее представление: г 1* 2* ° г г ГдЕ 1 ( гг < гх « ... гя ( П гв' ) 1) И дИЗЪЮНКцня бЕрЕтея ПО ВСЕМ наборам (о„оз,, оь) из В". Это представление называешься р вложением функцгт 5 гхгг) по 5а переменным х„, хпы ..., х„. Если 5с = 1 и гг — — г, то выражение 11) можно записать в форме )г,х") = х, ) гх„..., х, г, О, х,.ьг, ..., х„) У ггхг йхг, ..., х, г, 1, х,+г, ..., х„). (2) Представление 12) назьгвается разложением функции 11х") по переменной х,. Оно бывает полезно при доказательстве каких-либо свойств булевых функций по индукции.

40 Гл. 1. Способы задания и свойс~ава функций алгебры логики При к = н представление (1) имеет вид 1(х') = ~/ хз'хз" . х„ У(о~ ог, .,,,оа) (3) ( 1 2 и его называют разложением функции 1(ха) по всем п переменным. Если 1(х ") ф О, то выражение (3) можно записать в иной форме: У(х ) у хз хз '''ха (4) 1Р>=1 где дизъюнкция берется по всем наборам о = (оы оз,..., о„) б В", на которых функция 1'(ха) обращается в 1. Правая часть формулы (4) называется совершенной дизьюнктивной нормальной формой (сокращенно совершенной д. н. ф.) функции 1'1х ха). Кроме приведенных выше разложений булевых функций, широко используются еще такие разложения: а) 1(ха) = бб (х"' '1х""1..лх "Чун'"'"л" 1х")), 15) („„„„..., а,д где 1 < 1з < 1з « ... гь < и (к.

> 1) и конъюнкция берется по всем наборам (оы оз, ..., оь) из В"; б) 1 (х ") = (хе 1 1 1хы ..., х; ш 1, х;+ы ..., х,„)) х х х, Ч ~(х„..., х, „О, '„,,....,. а)); (б) в) 1'(хба) = О5 (х, ' М х.„"4 .. Л х'„'1 Дою пю .: па)) ' (7) оаю.,.,а ) г) 7(хха) = 55 (х 7," 1... 1х„-), (8) н:1я)=е где конък>нкция берется по всем наборам о = (оы оз, ..., о„) б В", на которых функция 1'(х") обращается в О, и предполагается, что 11ха) ф 1: правая часть формулы (8) называется совершенной коньюнктивной нормальной формой (сокращенно совершенной к.

н. ф.) функции 1'(х а); „) ура) ® ~ аг Хя~убдм...,а(тв) (~ оав,,пь) где 1 < 1г < 1з «... 1ь < н (й > 1) и суммирование ведется по шод 2 и по всем наборам (оп ог, ..., пь) из Вь; е) 1(х") = х;~(хш ..., х,; с, О, х;+ы..., ха) ~З 9 х,~(хы..., х, ы 1, хь„,, ..., ха); (10) ж) ~(ха) = 13 хз~'х~~г... ха" ~(оы оз, ..., о„); (11) (аоаа.....

я 1 з) у(-а) Я3 '~, аг а„ (12) а:1(а)=-1 где суммирование (по шод 2) ведется по всем наборам о = (оы пз,..., оа) б В", на котоРых фУнкциЯ 7'(ха) обРащаетсЯ в 1. З Я. Специальные предепгавленин булевых функций 41 П р и м о р 1. Разложить по переменной хс, применяя формулы (2) и (6), и представить в совершенных д.н.ф. и к.н.ф. следующие функции: Ц Л (хг, хг) = х!, '2) 1г(хг, хг) = хг,' 3) гз(хг, хг) = х! У хг,' 4) гл(хг, хг) = х! -+ хг, 5) Ь(хс,хг,хз) = хг хз, 6) Ь(хг, хг,хз) = хгхг †> Уз. Решение.

Ц Так как г! (О, хг) = 0 = 1 и г"! (1, хг) = 1 = О, то, используя формулы (2) и (6), получаем !г(хг, хг) = х! — — У! 1 Н !!х! 0 = (У! !!О) (х! !! Ц. Палее имеем уг(0, 0) = гс(0, Ц = 1 и г'г(1, 0) = г'с(1, Ц = О. Значит, для построения совершенной д.н.ф. функции Ь надо взять наборы (О, 0) и (О, Ц (функция г"! равна 1 только на них), каждому из этих наборов сопоставить соответству- ющую конъюнкцию (набор1 (О, 0) -- - конъюнкцию хсхг = хгхг, ней!о- ру (О, Ц вЂ”.- конъюнкцию х!хг! —— хгхг), а затем полученные конъюнк- ции соединить знаком дизъюнкции: У!УЗ М Угхг.

Аналогично, для построения совершенной к. н. ф. функции у! надо взять все наборы, на которых г! обращается в О, т.е. наборы (1, 0) и (1, Ц, каждому из этих наборов сопоставить соответствующую дизъюнкцию (набору (1, 0) дизъюнкцию х! Ч х о = х" !! х! = У! !! тг, набору (1, Ц дизъюнкцию хг! !!х,! = х! 'ь*хг = У! !!Уг), а затем полученные дизъюнкции соединить знаком конъюнкции: (х! !! хг) л е (У! Н хь). 2) Ь(0, хг) = хг и Ь(1, хг) = хг.

Значит, разложения (2) и (6) по переменной х! для функции Ь таковы: гг(хг, хг) = х! хгч х! хг и уг(хг, хг) =',х! Чхг) . (х! Мхг). Палее, Ь(0, 0) = гг(1, 0) = 0 и сг(0, Ц = Ь(1, Ц = 1. Следовательно, совершенная д. н.ф. функции уг имеет вид х, хг !l х„хг — — УгхгМ хгхг, а совершенная к. н, ф. такова: о (х! Ч хг ) (х! !! хг ) = (х! Ч хг) (х! Ч хг) = (х! Ч хг) (х! Ч хг). 3) гз(0, хг) = 0 !! хг = хг, Ь(1, хг) = 1 Ч хг — — 1. Поэтому имеем гз(хг~ хг) = х! ' хг Ч х! ' 1 и гз(х!) хг) = (х! Ч Ц ' (х! ь' хг). Вычисляя значения функции уз на различных наборах значений переменных, получаем гз(0, 0) = О, Ь(0, Ц = Ь(1, 0) = Ь(1, Ц = 1. Затем строим совершенные дизъюнктивную и конъкгнктивную нормальные формы функции )з: ,о!,со — о о хгхг У хгхг ~ тгхг — хгхг ~ хгхг Ч хгхг, х! 4 хг — х! Ч хг — х! М хг.

4) Ь(0, хг) = 0 — ь хг = 1, 14(1, хг) = 1 †! хг = 0 ~у хг = хг. Сле- довательно, Ь(хг,хг) = х! . 1Ч х! хг и 14(хг, хг) = (У! Ч тг) ве 3е (х! Ч Ц, Палее, ул(0, 0) = гл(0, Ц = Я1, Ц = 1 и 14(1, 0) = О. Значит, совеРшеннаЯ д.н.ф. фУнкции Ь имеет вид хогхг Нхостг! !! Нхгхг = УгхгМ хгхг !! х!хг, а совершенная к. н, ф, такова: х! Ч хо = о = х! !У хг — — х! '4хг. 6) Ь(0 хг хз) = Ь(1, хг, хз) = хг хз. Поэтомураэложенияэтой функции по переменной хг, полученные по формулам (2) и (6), та- ковы: х! ' (хг хз) ь х! (хг хз) и (У! Ч (тг хз))(х! Ч (хг хз)). Вычисляя значения функции Ь на различных наборах значений пе- 42 Гл, 1.