Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 23
Текст из файла (страница 23)
Это максимальное число определяется весом производной. Весом производной от булевой функции называется число конституент этой производной. При использовании блоков, исключающих В переменных, находят производные )с-го порядка от реализуемой функции и ищут максимальное значение веса производной Р(д"//д(ху„х;2, ... ..., х;,)), которое и определяет исключаемые переменные.
Для полученных остаточных булевых функций снова находятся производные: определяются веса, а производная от рассматриваемой остаточной функции, имеющая максимальный вес, определяет соответствующие переменные, которые исключаются на этом Гл. 2. Математическая логика 120 вычислим вес пронзвадпьо( д//дхь — = (х(УЗЧ х(ху ч ° хзх<ч д/ дхз У Узхь) Щ (х<х< Ч хьхзх< Ч У<хь) Таблица 2.21 'Таблица 2.20 х; И1) Р(д//дхз) = 8; Р(д//дхз) зз 5; д/ ы (х<УЗхз Ч х<хзх< У х<хзхь Ч дхь УУЗхз'4хзхь) и<(хьц2хзч Ч У<УЗХ< Ч хьхз Ч х<хзхь), — = (хьхзхз ЧУ(хз Ч х(хьхь У Э/ дх< Ч х<хз Ч Узхзхь) 9 (х<ха тз Ч Ч х<хзхь Чхзхзхь '4 хзхь), Таблица 2.23 Таблица 2.22 Рис.
2.8 д/(Ц = („У, ч,<х<) Е дХ2 Щ (х< Ч к<УЗ Ч хь), ~ — = (Уз Ч Уь Ч хзх< У Эу(1) дхь Ч У2ХЬ) ШУ2язь Таблица 2.19 Таблица 2.25 Таблица 2.24 Р(д/(Ц/д,) = З; Р(д/(1)/дх<) = 5; ярусе для атой остаточной функции, и т. д., пока остаточные функции не будут иметь простую реализацию.
Пример 2.9. Синтезируем логическую схему, реалнзуюшую булеву фуяк- пию /(х<, хз, ..., хь) = х<УЗхз ЧУ<хзх< Ч хьхзУЗ Ч х<хзхь Ч Узхзхь Ч хзУ<хь, испальауя блоки исключения одной переменной (рис. 2.8, а). Определим переменную хн по которой пронвводнаяд//дх; имеет максимальный вес, т. е. функ- пия /(хь, хз, ..., хь) аависит ат нее наиболее существенно. Имеем — = (У2хз '4 я<УЗ Ч х2х< Ч х2 хзхь'4 УЗ У< Хь) аь (Уз Х< Ч У2хзХЗ Ч Узу<хь). дх, Для вычисления веса производной д//дх(, зависящей от четырех перемен- ньюс хз, хь, х<, хь, представим 4-мерное пространство с обрвауюшими (хз, хз, х<, хь) в виде декартова праизведекня двух двумерных пространств (хз, хз) х х(х<, хьу с обраауюшнмн (хз, хь) и (х<, хь) соответственно.
Тогда производную д//дх< монна задать в виде двумерной таблицы: каидому значению аз, ез переменных хз, хь взаимно одновначяо соответствует строка таблицы, столбцу — значения а<, аь переменных х<, хз и ив пересечении ь-й строки и у-го столбца, вааимно одноанвчно соатмтствующем тачке четырехмерного про. странства с образующими (хз, хз, х<, хь), ааписываем значение д//дхь в втой тачке. Вес прояввадпой д//дх< равен числу единиц в втой таблице (табл. 2.19).
3 2.5. Дифференцирование булевых функций 121 Итак, Р(д//Эх~) = 7, Аналогично з = 2, 3, 4, 5 (табл. 2.20 — 2.23). Имеем: = (У<хзх< Ч хьх<Уь У х<х< Ч д/ д. ЧУзх<хь) Щ (х<хз Чхьхзх<Ч Ч х<ХЗУЗ Ч хзхьУ Уьх<хь), Р(д//дх<) = 5; Р(д//дхь) = 7. Максимальное значеняе щат Р(д//дх;) получена при дифференцировании функции / по переменной хз.
Исключая зту переменную, получаем две остаточные функции: единичную /(х<, хз, хз = 1, х<, хь) = /(1) и нулевую /(х<, хз, ха = О, х<, хь) = /(О); /(1) = х<Уз ч х(УЗ ч х(хзх< ч Узхь, /(0) = х<х< ч Чхьхзх< Ч У<ха. Аналогично определяем оптимальное исключение переменных нв следующем ярусе логической схемы (табл. 2.24-2.27): Гл. 2.
Матемапзическая лоеика — = (хьхз Ч хьУз Ч хьхз Ч д/(1) а, Ч х2хь) ЕЬ (х1хг Ч Х1Уь Ч Угхь)ь а/(1) = (хьхг Ч хьхгхь Ч хг) Щ а*. = Е (х1У2 Ч х1 Ч хгхгхь) Твблипв 2.28 Твблипа 2.27 Р(а/(1)/ах,) = 1; Р(а/(1)/ахь) = З. — зз (хьхь Ч хе Ч хьхь)ьо д/(О) дхг Щ (Уьхь ч Уьхз), Твбликв 2.29 Р(д/(о)/а.,) = г; Р(д/(0)/дхг) = 2; а/(о) = (Уь хь Ч х2х ь ч хь ) Е дхь ог (хгхь Ч х2хь)1 Таблнкв 2.31 — ьх (Х1 Ч Х2) ЩХЬ, а/(о) дхь Таблипа 2.30 Р(д/(О)/дхь) = 4; Р(д/(О)/дхь) м 4.
Исключая переменную х1, получаем остаточные функпнп вика /(хг = 1,хг, хз = 1, хь, хь) = /(1, 1) = хз Ч хь Ч хзхь Ч хгхь = Уз Ч хь Ч хь, /(хь'= О, хз, хз = 1, хь, хь) = /(1, 0) = хзха, /(О) — Уьхь Ч хьхгхь Ч Уьхь = Угхь Ч хзхь Ч Уьхь. определяем оптимальное исключение переменной лля булевой фуикпин /(О) = = /(хъ хз, О, хь) (табл. 2.28-2.31): д/(О) — = (хзхьхь Ч хьхь) Е дхь Е (хь Чхзхь ЧУьхь), Твблика 2.28 Исключая переменную хь, получаем остаточные функкпн вила /(хь, хз, хз = О,хь = 1, хь) = /(О, 1) = хиь Ч хз, /(Х1, хз, хь = О, хь = О,хь) = /(О, 0) = хь.
В результате получаем лотичесвую схему, реелиаующую функкию /(хь, хг„ " , хь) (рнс 2 8, 6). 82.6. Разлозхение функции е заданной ьпочке просзпранства 123 Критерий оптимального исключения переменных имеет эвристический характер, что основано на предположении о том, что чем больше вес производной Р(д)/дхе), тем больше функция / зависит от переменной х;. Если имеются блоки исключения /с переменных, то построение схемы проводят аналогично, вычисляя вес производных й-го порядка Р(д"~/д(х;„х;„..., х;„)).
$2.6. Разложение булевой функции в заданной точке пространство В дискретной математике отсутствует понятие предела, однако в выражениях (2.13)-(2.15) используется термин "производная". Это связано с разложением булевой функции в ряд, аналогичный ряду Маклорена в тачке ОО...О нли ряду Тейлора в произволь- ной точке пространства. Рассмотрим данные разложения булевой функции /(хь,хз,..., х„). Две функции / и /а называются взаимно ортогональными, если их конъюнкция равна О: / 68/а = О.
Выражение (2.11) эквивалентно равенству ,/(Х1, Хг, ..., Х„) = $~ ОЬ Хо"', (Ч(вью~ - оо)) (у (Оз,ег,...,оь ) х1) где 16,— сложение по шод 2, так как сь Ч д = сь йь /2 Щ сь/2 и кон- ституенты единицы функции /(х11 хг,..., Х„) попарно взаимно ортогон альпы. Заменим в выражении (2.16) в каждой конституенте х; на (х; Е сл 1). Применяя следующие тождества: коммуьпатпиености сз йь /у = /2 йг сз; ассоциатиеноспзи сь 9 ()У Ю 7) = (сз 6У /2) ОУ 7' дистрибутпиености конъюнкции относительно сложения но модулю 2 сьес /2ьть = сзесФ ьть сзес7))' (2.17) ( 7) ( ) ( действия с констангпами сз9сзсхО, сь91=сь, сзЩО=сь, сьЩсз=1; получаем представление функции /(Х1, хг, ..., Х„) в виде и и ДХ1ь Х21..., Хп) ~о Щ $~ Дьх;1 Щ $~ /;„зхьзХ12 Щ" ььх1 112'м1 $~~ у1112„льхуь х;, "х;ь ьть ° 9,/12., „хтхг...х„, (2.18) 124 Гл.
2. Матвематлическал логика 22.6. Раэлохсеиие аоуикции е заданной и!очке оростлраисп!ва 126 ГдЕ УО Л, Л!12 Лоо,..д„,, Лг... = 0,1; 21, 22, и за Е (О, 1, ..., тз), индексы (зы 22, ..., зз) попарно не равны друг другу, что в дальнейшем обозначаем как 8(21, (1, ..., Зз). Выражение (2.18) называется яолинамом Жегалкина функ- ции у (х11 хз, ..., Хп).
Последовательнооп продифференцируем полинам Жегалкина ФУНКЦИИ У(Х1, Хз, ..., Хп) ПО ПЕРЕМЕННЫМ Х1, Хз, ..., Хэ И ОПРЕДЕ- лим значение этой производной в точке 00...0. Учитывая, что = — ٠—, (2.19) дх дх дх' — ~й*,)= й *„, (2.20) дху 1,24х1 т) ззхз,ттзо "' после дифференцирования по переменным хт, хз,..., хз получаем д"у = .Узз..й. дхздхз...дхз Действительно, после дифференцирования по переменным хт, хз, ..., Хе все члены разложения в выражении (2.18) до у12 з обращаются в О, а в результате подстановки хе+1 = ха+2 =...
... = Хп зх 0 остальные члены этого разложения, кроме Лз,,з, так- же будут равны О. Отсюда получаем теорему о разложении любой буЛЕВОй фуНКцИИ У(Х1, Хз, ..., Хп) В таЧКЕ 00...0. Теорема 2 3. Любая булева утункцил у(х1, хз, ..., хп) яред- ставима своим значением в точке 00...0 и значениями всех ороиэводных ду д21 дпу дх;,' дх;,дх;,' ''' дх!дхз...дхп в этой тлочке в виде т! „„..., .)=т!1,1,...,11ЗЗà — / ! ду ., д*; дзУ й х, Е й; 1 х;хт Е ...
дх;дх,( оф1 и деу , дх;, дх;,... дх;, (оо 11,12 „ ,1зх1 дите 'и ХЧ Х'2 *оз Э ° ° От 6С Х1Х2... Хп, (2.21) дхздхз...дхп( о З1, Зз, ...,Зь, ...,З„Е (1,2,..., И~, 8(З1,22, ...,ЗЮ ...,Зп). Пример 2.10. Найдем резланенне Отпевай функкии У(хо, хз, хэ, хо)~ = Ч(0, 2, 4, Б, 13) !1 — = у(,„= ц аз у(; = о); ду дхо У(х! = 1) = хзУзхо, зз(х! = 0) = хгУЗУ4 У УгхэУ4 У ХЗУэхо Ч хзхэУ4 = хо, дт — х2хзхо оа х4 — х2хэх4 ' У4 Ч х2хзх4 х4 Уо Ч х2Уз! дхо ож1, т (ХЗ зп 1) = У1УЗУ4 Ч Хохэио Ч Х1УЗХ4 оз Х!Хо УХ!Узко, 1(хз = 0) = з'!Уэлоч хохэио — — У!Уо, дт — = (кохо Ч х!Узхо) 6 У!Уз = х!Уэхо! дхз 1=2, 1=3, у(хэ = 1) = хохзхо Ч хохгхо = У!Уз, У(хэ = 0) = х!хзх, Ч хохгхоЧхохзхо = У!Уз Ч хохгхо, д зо У1У4 оа (У1У4 У зох2х4) зз х!хгх4! дхз 1 = 4, тз(хо = 1) = хохзУз, тз(хо = О) = У1УзУэ Ч Уохзхз Ч хохзхэ Ч хохгхз = Уо, ду — = хохгУЗ чтхо = хохзхз Уо Ч хохзхэ хо =УоЧ хгУЗ дхо Вычислим вторые смешанные пранзвадные дзу/(дхо дх, ): дгу д У' ду '! 1=1,дм2, = — ~ ~— ~ зз(У4 ЧУЭ) ЕУЗ оз дходхз дхз ~дх~/ =хо Ч хз ° Уо'У (Уо Ч Уэ) ° хо = Уэхо; о = 1, у' оз 3, 1=1,1=4, = хзхэ Ю 1 = Уз Ч хз! дхо дхо о = 2,,1 = 3 Х1Х4 дхг дхз зз к!УЗ; 1=2,1=4, 1=2,1=4, — Х1 Х2 ° в тачке ОООО.
Вычисляем производные первого порядке и смешанные нраизвадиые ат булевой фуиккнн у(хм хг, хз,хо): 127 12.7. Исчисление высказывание Гл. 2. Математическая логика 126 Вычислим третьи смешанные кроивводные д'УУ(дх« дх« дхз): азУ д (' ау дх« дхз дхз дх« ~дхз дхз ) « = 1, У = 2«х ж 3« д'1 аУаУ~ '=1,1=2,1=4, дх« дхз дх дх «, дхз дх«) д'У д / дзУ а«1 д у азу Нзкоиед«четвертая смошзннвя кронвводнвя д«У/(дх« дхз дхз дх«) имеет а'1 д ( д«1 ) дх« дхз дхз дх«дх« дхз дхз дх« Производные дУ дУ азУ азУ д У д1 д У ах«' дхз' дх«дхз' дх«дхз дхздхз' дхздх«дхзах« дзУ д'У д'1 дх«дхз дхз' дх« дхздх« ' дх дхз дх« 1(х1, хз«хз«х«) зз 1 6 х1 ог х«о«х«х««а х!хох««з х1ляхзх« ° Для получения разложения булевой функции в ряд, аналогичный ряду Тэйлора в точке огот... а „, введем новые координаты х' Х«2,..., Х'„, ГдЕ Хг = Х; «2Г а» З = 1, 2, ..., П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
