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

(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. Способы задания и свввс1пва фупкиий алеебрв1 логики ременных, имеем уз(0, О, 0) = уз(1, О, 0) = 72(0, 1, 1) = Тз(1, 1, 1) = 1 и Ь(0, О, 1) = Д(1, О,. 1) = Д(0., 1, 0) = 1'з(1, 1, 0) = О. Совершенная д.н.ф.

У уз имеет вид ООО1ООО хгхгха Ч хгхгхз ' ' хгхгхз Ч хгхгхз — хгхэхз Ч хгхгхз Ч хгхгхз Ч хгхгхз а совершенная к. н, ф, такова; х1 Чхг Ч аз) - х1 Чха Ч хз) (х1 Чхг Ч хз) . (х1 Чхг Ч хз) = = (х1 Чхг Чхз) '(х1 Чхг Чхз) (х1''хг Чхз) '(х1 Чхг Чхз). б) Ь(0, хг, тз) = О -2 хз = 1, Ь(1, хг, хз) = 1 хг -э хз = хг -э — 1 хз. Следовательно, разложения этой функции по переменной х1, полученные по формулам (2) и (6), имеют вид х1 1 Чхг (хг — 1 хз) и (х1 Ч (хг -в хз)) (У1 Ч 1).

Вычисляем значения функции ув на различных наборах значений переменных: ув(0, О, 0) = 1в(0, О, 1) = = 1в(0, 1, 0) = гв(0, 1, 1) = 1'в(1, О, 0) = 1в(1, О, 1) = (в(1, 1, 0) и ув(1, 1, 1) = О. Зна 1ит, совершенная д. н. ф. функции Д такова: х1Угхз Ч У1Угхз Ч хгхгхз Ч УгхгУз Ч г:1хгхз Ч хгхгхз. Совершенная к.н.ф. функции имеет вид У1 Ч Уг Ч хз.

Замечание. Совершенная дизъюнктивная нормальная форма функции Д(х1) = х1 (как функции от одной переменной х1) совпацает с совершенной к.н.ф. и есть просто х1. В самом деле, Г'(0) = 1 и Д(1) = 0; следовательно, совершенная д. н, ф. функции 1(х1) = х1 имеет вид х1 — — х1 и совершенная к.н.ф. такова же: У = х = х1. о — о Аналогичное утверждение справедливо и для функции 1(хг) = хг: ее совершенные диэъюнктивная и конъюнктивная нормальные формы совпадают с ней самой, т.е. с хг.

Эти факты интересно сравнить с соответствующими результатами для функций 11 и уг из приведенно- го выше примера. Пример 2. Представить в совершенной д.и.ф. и совершенной к. н. ф. функцию 1с(хйз) = (01101001). Решение. Функция 1 принимает значение 1 на наборах, номера которых равны 1, 2, 4 и 7, т. е, на наборах (О, О, 1), (О, 1, 0), (1, О, 0) и (1, 1, Ц. Конъюнкции, соответствующие этим наборам, имеют вид , О О 1 — — О 1 Π— —, 1 О О х1х2хз х1хгхз х1х2хз х1т2хз х1хгхз х1х2хз и х1х2хз = хгхгхз.

Значит, совершенная д. н. ф. функции 1(йз) такова: У1Угг:з ЧУ1тгУз Ч х1У2Уз Ч хсхгтз. Пля построения совершенной к.н.ф. рассматриваем все те наборы, на которых функция 1' обра- щается в О. Это наборы (О, О, 0), (О, 1, 1), (1, О, 1) и (1, 1, О). Соот- ветствующие им дизъюнкции имеют вид о о о х1 Ч хг Ч хз — — х1 Ч хгЧ хз — — х1 Ч хг Ч хз, о Т,Т 1 о о х1 Ч хг Ч хз — — х1 Ч хг Ч хз —— х1 Ч х2Ч хз, х1 Ч хг Ч хз — — х1 Ч хг Ч хз — — х1Ч хгЧ хз, Т о Т о 1 о Х1 ЧХг Чтг — — Х1ЧХ2ЧХЗ вЂ” — т1ЧХ2Чтг.

Т Т о о о,,1 Перемножая эти дизъюнкции, получаем совершенную к. н. ф. функ- ции ~: (х1 Ч хг Ч хз) (х1 Ч хг Ч хз) (х1 Ч хг Ч хз) (х1'Ч хг'Ч хз). у д. Специальные предегпавленин булевых функций 43 П р и м е р 3. Представить в совершенной к. н. ф. хю, хз- и хзхз-компоненты функции Хл(хо) = (хз — ь хххз) Ю хз, рассматривая их как функции, зависящие только от «оставшихся» переменных. Решение. хюкомпонентой функции 1(хз) является Л(х ) = х(1, хз, уз) = (1 > хзуз)Юхз = (ОЧхзхз)чьхх = хзхз 9 хз = хз ь хз.

Аналогично, хз-компонента функции у" (х з) есть функция д(х з) = = У(хы О, хз) = (х1 — > О. тз) ьЗ 0 = хз — > хз, а хзхз-компонента функция узод(х ) = У(хы 1, 0) = (хз — г 1 0) Ю 1 = хь Ю 1 = хь Очевидно, что совершенная к.н.ф. функции ьвз(хз, хз) = хз Ч хз совпадает с ней самой, совершенная к. н. ф. функции уьз(хы хз) = хз — е хз есть хз М х„= хй Ч хз — — хз Ч хз и, наконец, совеРшеннаЯ к.н.ф.

— о .о функции уьз(хз) = хз --. зто просто хь Пример 4. Показать, что если Д(х"): — уз(хп) для всякого 1 (1 < ~, '< п), то функция 1(х") есть константа. Решение. Разложив функцию у по переменной хь (см. формулу (2)), получаем (х") = х'уо(хд") У х.Л(х") = х Ыхп) У х.1о(х") = = (хг 'й хд1о(ха) = 1 ' Уо(х") = )о(хп) т.е. х, фиктивная переменная функции )(хС"). Так как х, произвольно выбранная переменная., то, значит., все переменные функции 1(х") фиктивные. Следовательно, Д(х") есть константа. П р имер 5.