Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 19
Текст из файла (страница 19)
В двумерной таблице, каждой схроке которой взаимно одно- значно соответствует точка пространства Р„„каждому столбцу— точка пространства Р„„на пересечении строки и схолбца запи- сывается значение булевой функции ((хз, хт, ..., Х„) в соответст- вующей точке пространства Р„. П р яме р 2.1. Построим таблицу Вейча дпк некодиостью заданной булевой функции У(хз, кз,, кз), аадввая двоичные наборы [ез, аз, ..., ез) десятпч- иымн зквнввпентамя 2 еч 2" ': ( 1 на [О, б), [5, 29), [2, 10], ][ 0 нв [3, 11], [13, 31]. Ъудева функпня у[к!, вз, ..., хз) задень пнтервапамн, слева в вввдратной свобке указан минимальный, справа — максимальный здементы.
Единичная обвасть втой функции вквюч ает интервалы, содер!казцне соответствующие точен: [О, 6] = (О, 2, 4, б), [5, 29] = (5, 13, 21, 29), [2, 10] = (2, 10), Нулеваяобдасть включает точки, образующце указанные интервалы! [3, и) = (з, и), [13, з1] = (13, 19, 22, 2з, 20, 2т, зо, 31).
Мопщость еднннчной области равна 9, нулевой обдастн — 10, в остапьпьпс 13 тачках булеза функция У(кз, кз, ..., хз) не определена. Заданно булевой функции навывается «роткеоречиемя, если пересечение единичной н нудевой обдвстн непусто. Представим нсподное мнояество Рз = (хз, кз, ..., хз) в аиде деквреовавро- пввеаення Рз = (кз, вз) н Рз = (хз, кз, гз): Рз зз Рз х Рз; нпяннй нндекс у ндентнфнкатора пространства Р указывмт равмерность про- странства. Прн таком раабненнн перемепньос хз, кз,..., хз таблица Вейча ддя заданной функпнн имеет внд табл. 2.5.
Табднпа 2.5 з в. л. гззо!«!з 98 Гл. 2. Математическая логика 1 2.2, разложение Шеннона. Декомпозиция булевых функций 99 9 2.2. Разложение Шеннона. Декомпозиция булевых функций Рассмотрим разложение булевой функции у (хг, хз, ..., х„) по Й переменным (для определенности по хг, хз, ..., ха) — разяожекие Шеннона. Теорема 2.1. Любая функция у(хг хз, ..., х„), не равная тождественно нулю, представимо в ви5е разложения Шеннона у(Х1> Хз> ..., Ха> Ха+1> ..., Хз) = 1 р х, > ят1, оз, ..., оь, ха+1, ..., х„), У(а>,аз,... аз) >' 1 где (тт = О, 1; ( = 1, ..., >с, х; ' = ( -" > — » — > .» > — х, я,— О Используя метод полной индукции, покажем, что х = 1 <-у ер х; = ос (табл. 2.6). Подставим произвольно вместо первых й переменных их значения: х1 — а',хз = ят, ...,хь = сг~.Тогда левая часть доказываемой формулы Таблица 2.6 равна у(о1> ст'...>.
оь, ха+1, ..., х„). Правая часть представляет собой дизъюнкцию 0 0 1 =1 2 конъюнкций вида х >хзт...х,'у(а1, 0 1 0 ат,..., ОЫ Ха+1, .. з Х„), КатарЫЕ Этай цад- 1 0 1 = 0 становкой разбиваются на два класса. К 1 1 1 первому классу относится конъюнкция, у которой набор (я1, стз, ..., аь) совпадает с наборам (>71, стз, ..., оь): (я1) (оз) ~...(сть) у(ст1 юз ..., оь, х1.~.1 ..., х ) = а З 1я1> О'2» . ° . аа> Ха+1» ° ° . Хв) ° Эта конъюнкция равна левой части формулы. Ко второму классу относится 2~ 1 конъюнкций, у каждой пз которых хотя бы в одной переменной х;, т Е 11, 2, ..., Ц, стт ф а;. Следовательно, каждая из них равна нулю.
Тогда согласно закону, характеризующему действия с константами: а Ч О = а, получаем, что левая и правая части формул равны при любой подстановке переменных Х1> Хз» ° ° Хь ° Следствие. Лредеяьное разложение Шеннона (>с = и) булевой функции у (х1, хз, ..., х„), ке равной О, имеетп вид з ~(хг> хз, ..., хз) = Ч ф ха'. (2.11) т(а>, аз, ..., а„)) ( (а>,аа,...,а )=1) Предельное разложение Шеннона булевой функции у(хг> хз,..., х„) является ее совершенной дизъюнктивной нормальной формой.
В алгебре Буля справедлив принцип двойственности, поскольку, как было показано в гл. 1, она является дистрибутивной решеткой с дополнением. Согласна атому принципу имеем следующие двойственные разложения Шеннона булевой функции у (х1, хт,... ..., хь, ха+1,..., х„) по (с переменным: 7(Х1, Хз, . ° ., Хь Ха+1 Хк) 1 'Ч' Й х'' у(а1, аз,.", оь, ха+1 хз). Ы(а>,аз,...,аз) '=1 Согласно закону двойного отрицания а (х1> хт» хв) У(х1> Хз, ..., Х„) ИМЕЕМ уа(Х1> Хз, °, Хь> Ха+1» Хз) = ~(х1> хз, > хь> ха+1» х„) = 1 ~/ Й Ха' Дат, >72, ..., Сга, Ха+1, ..., Х„) = У(а>, аз, ..., аз) >=1 / а Й ~ Ч Х ЧПО1> яз, ..., Оа> Ха+1> ...> Хв), (2.12) У(а>,аз,...,аз) >=1 Таким образом, любая булева функция у(хг, хт, ..., х„), не равная тождественно 1, представима в виде выражения (2.12).
При (с = и двойственное предельное разложение имеет вид у ц За(Х1,Х2,...,Х )= Й ( ЧХ~). (у(а»»т> " ап) О) Двойственное предельное разложение Шеннона булевой функции у (х1, хз, ..., х„) является ее совершенной конъюнктивной нормальной формой. Пример 2.2. Построим совершенные ДНФ н КНФ булевой фунвцнн у(х>, хз, хз), заданной таблицей истинности (тзбл. 2.7). Таблица 2.7 Гл.
2. Маглемашическая логика 100 3 2.2. Разложение Шеннона. Декомпозиция булевых функций 101 Совершенные ДНФ и КНФ втой фунвкии имеют соответственно вид у(х>> хз> хз) — У>хзпз >' х>хзУз Чх>Узхз Ч х>хзхз, у(х>, хз, хз) = (х, Ч х, Ч Уз)(х, Ч хе ЧУзДх, Ч хз 4 хзКУ, чУз Ч лз).
Далее будет рассмотрена теория ДНФ, из которой на основании принципа двойственности легко построить теорию КНФ. Будем называть булевы функции у(х1, хт,..., хь, хьфг, ... ..., х„) в выражениях (2.10) и (2.12) остаточными мультипликапзивиыми и аддипзивиыми функциями соответственно. Укажем на важную связь между разложениями Шеннона и таблицами Вейча. Представим исходное пространство Р„(Х) в виде декартова произведения пространств Рь(Х,) и Р,(Хь), Х, 11 Хь = Х,Х, Г1 г)Хь=ы, В+в=я: Р„(Х) = Рь(Х,) х Р,(Х6).
Каждой строке таблицы Вейча взаимно однозначно сопоставим точку пространства Рь(Х,), столбцу — точку пространства Р, (Хь) и рассмотрим разложение Шеннона булевой функции у(х„, х„,..., х,„, хь,, хЬ„..., хЬ,) по первым ф переменным. Тогда, очевидно, з-я строка таблицы Вейча, идентифицируемая конъюнкзз> озз озь цией х„еех„ее...еех,ь, соответствует остаточной функции 1 (>Уз> > сгзз » ° .. Оез > хЬ» х6з » ° ..
Хбз). Будем называть разложение Шеннона булевой функции у(Х) строчным, если разложение осуществляется по переменным, соответствуюшим строкам таблицы Вейча. Аналогично определяется спюлбцевое разложение Шеннона булевой функции у(х): у-й столбец таблицы Вейча, идентифицируемый конъюнкцией хь ' егх з' Й...еех ", соответствует остаточной функции у(хз» х, ..., тз„, с>Ь> сг~ ° ° ° сгЬ,) ° Найденная связь позволяет сводить исследование булевых функций к анализу функций от меньшего числа переменных путем построения декомпозиции исходных булевых функций.
Декомпозицией булевой функции у(хь, хз, ..., х„) называется пасет, носителем которого являются терминальные (хД и функциональные (у, Р;, >ру, ...) переменные, сигнатурой — отношение включения одной переменной в качестве аргумента другой. Теорема 2.2. Булева функция у(хь, х2, ..., х„) декомпозируема, если найдетея разбиение ее переменных (х,„х „... ..., х,„), (хь,, хЬ, ..., хЬ,) гпакое, чгпо при объединении стирок или столбцов в соответствующей таблице Вейча не образуется противоречивого задания, при каспаром (!обтзт',] < >с или (!обтФь] < в, где [] — целое ближайшее число; )ч' — число различных строк таблицы Вейча (чиело оетагпочиых булевых функций строчного разложения), каждад пара которых >р;„>рьз не находи>пса в отпношении включения: >р;, (с >р;,; № — число различных егполбцов гпаблицы Вейча (чиело оетатпочных булевых функций (>рту етолбцевого разложения)', попарно не находящихся в отношении включенид: ьоу> (с >р;.
Пример 2.3. Рассмотрим построение девомпозидии булевой функпни У(х>, хз, ..., хз), зеленной табл. 2.5. Остаточные функпни строчного рззлонения з>з, Ьз> и >зз, Ь>з молодятся в отношении включеннв»зо Э Ч>„з>з О Нз; обьединлл соответствующие строки, получаем табл. 2.8. Тоблике 2.8 Отсюда полУчнм № = 2, к = 2, (ьобз 2] < 2.
Следовательно, монио вместо двух термпнвльных леременныт, х, и хз, ввести функдионвльную переменную >з> и, водирув первую строну в тзбл. 2.8 нулем, вторую — единнпей, получить вввиснмость ь»(х>, хз))> ю >>(2, 3). Аналогично, обьединюг столблы (О, 1, 2, 4, 6, 7), (3] и (5), получаем твблнпу Вейчв в виде табл. 2.9, Твблипв 2.9 Отсюда лолУчим № зз 3, Я зз 3, (ьобз 3] < 3. Три полученных рвзлнчных столбпз кодируем, вводи две функднонвльные переменные ьзз, ч>з; первый столбеп звкодируем в виде 00, второй — 01, третий — 10. Отсюдв получаем зввиснмости Ь>з(хз> хз, хз))> = Ч(5), Юз(хз> хз, хз)]> = Ч(3) В результвте введения фуикпионзльныт переменньис ч», >рз, нз получвем твблипу Вейте (табл. 2.10), окределлюшую звдвнную функкню у(х>> хз, °, хз) через фунвпионвльные переменные Ь>>, ~оз, Нз. Твбликв 2.10 Твблидв Вейчв (твбл. 2.10) определяет внешнюю функпию Г1 ив 0,2,6, (т>» >>з> ч>з) 10 нв 1, 4, 5 Гл.
2. Мап4емал4ическах хоеика 102 Ю '21 х, .тт тз т У-У(Х~ Хт -'Х~> Х1 Хт Хз Х4 Х5 Р(т1(Х!,хт), Ф2(Х6, 24, Хп ч6(хз,х4'Х5)) Рис. 2.1 Таблица 2.11 построенной декомпозипдпт (рис. 2.1) заданной булевой Фупкдпи У(х1, х2 ° ° ~ х6) = Р(Ю1(х1 х2), ((52(хз~ х4 х6) 446(хз~ х4~ х6)) ° Исследование Фунпвии от пяти переменных звмеиеио нв виввиз одной Функпии от двух переменных и трех функпий от трех переменных. 32.3. Мкнимизацр(я булевых фуикциж в классе ДНФ Часто, как было уже показано, двоичные наборы задают дев сятичными зквивалентами: (а1, ат, ..., ак) н 2; (г;2" ', булеву 4м1 функцию — перечислением десятичных зквивалентов, соответствующих конституентам (конъюнкциям предельного разложения Шеннона).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
