Новиков Ф.А. Дискретная математика для программистов (860615), страница 23
Текст из файла (страница 23)
Реализация двойственной функцииФормула, реализующая двойственную функцию, определённым образом связанас формулой, реализующей исходную функцию.ЗАМЕЧАНИЕДалее используется обозначение / ( • • • ) = f /(• • •).119Э.Э. ДвойственностьТЕОРЕМАЕсли функция <р(х\,..., хп) реализована формулойД/lI , • • • , Ян), • .
• J fn{xЬ • • • > Жп))>то формулаГ(/Г(®11 • • • . ®п), • • • , /п(®1. • • • . ®Т»))реализует функцию ip*(x 1 , . . . , жп).ДОКАЗАТЕЛЬСТВО^•"(xi, . . . , хп) =<p(xi}... , in)= 7 ( / i ( ® i , • • • >5?п). • • • , / п ( ® 1 , • • • , а ? п ) )= 7 ( Л ( ® 1 » • • • > ®п), • • • > (/п(®1, • • ч ®п))= 7 ( / l (®1> • • • > Я „ ) , • • •• • • »®п))===е= / * ( / * 0 Ь • • • ,Z n ), ' • • j / n f a l i • • • i^n)).3.3.3. Принцип двойственностиПринцип двойственности устанавливает связь между структурами формул, реализующих пару двойственных функций.
Рассмотрим две системы булевых функций F = {/1, • • • 1 fm} и F* = { / Г , . . . , / ш } и введём обозначение=(Принцип двойственности) Пусть F = { Д , . . . , /т} — система булевых функций, a F* = {/*,...,— система двойственных функций. Тогда еслиформула 7 над базисом Fреализует функцию f , то формула J* над базисом F*, полученная заменой функций fa двойственными функциями fa*, реализует функциюТЕОРЕМАfuncJ[F] = / = • func J*[F*] = /*.Индукция по структуре формулы Э\ База: если формула J имеет вид f(x 1,...
,хп), где / G F, то формула J* = f*(x 1 , . . . ,хп) реализует функцию /* по определению. Индукционный переход по предыдущей теореме.•ДОКАЗАТЕЛЬСТВООТСТУПЛЕНИЕХорошо известен принцип математической индукции для натуральных чисел:(Р(1) & (Р(п) = » Р(п + 1))) = • Vn <Е N (Р(п)).Этот принцип является справедливым и для других множеств, упорядоченных болеесложным образом, нежели натуральные числа (см. 1.8.7). Например, в доказательствепредыдущей теоремы был использован принцип индукции в следующей форме.Пусть задана некоторая иерархия (ориентированное дерево, см.
9.2.1). Предположим, что1) некоторое утверждение Р справедливо для всех узлов иерархии нижнего уровня (листьев дерева);2) из того, что утверждение Р справедливо для всех узлов, подчиненных данному узлу,следует, что утверждение Р справедливо для данного узла.Тогда утверждение Р справедливо для всех узлов иерархии (дерева).•120Глава 3. Булевы функцииСЛЕДСТВИЕ= 123*1 * =3*2*•Пример Из xi А ^2 = xiУх-2 по принципу двойственности сразу имеем xi V х 2 == Xi A Х2.3.4. Нормальные формыВ данном разделе на примере булевых функций обсуждается важное понятие«нормальной формы», то есть синтаксически однозначного способа записи формулы, реализующей заданную функцию.3.4.1.
Разложение булевых функций по переменнымПусть xv = f х А у V х А у. Очевидно, чтоJx,X = \I х,ТЕОРЕМАесли у = 0,если у = 1,jl,X = \10,если х = у,если х ф у,Ху = X = у.(О разложении булевой функции по переменным), . . . , Хт, Хтц-1, . . . , Хп) ==VяГ А . . . А х ^ Л/(б7Ь...,(7т,хт+1,...,хп),где дизъюнкция берётся по всем возможным наборам значений (<ti, ..., <гт).Рассмотрим значение формулы в правой части на наборе знаап.
ИмеемДОКАЗАТЕЛЬСТВОчений а\,...,Уxi1 А ... Ах°^ А /((71,... ,ат,Хт+1, • • • ,хп)(<rll...,am)( а ь ... ,ап) =J=\Jа^1 А ... А а^" A / ( < x i , . . . , crm, a m + i , . . . , ап).(сг 1,...,<тт)Все конъюнкции, в которых Зг ai Ф ai равны 0 и их можно опустить, поэтомув дизъюнкции остаётся только одно слагаемое, для которого Уг е 1 ..п (a^ = <7i),и окончательно имеемa®1 А .
. . А а£п А / ( а ь . . . ,аТп,агп+ь. . . ,а п ) = / ( а ь . . . ,ап).•ЗАМЕЧАНИЕЗдесь доказывается, что некоторая формула реализует заданную функцию. Для этого достаточно взять произвольный набор значений аргументов функции, вычислить па этомнаборе значение формулы, и если оно окажется равным значению функции на этом набореаргументов, то из этого следует доказываемое утверждение.1213.4. Нормальные формыСЛЕДСТВИЕ1/ ( х 1 , .
. ,,xn-i,xn)СЛЕДСТВИЕ 2= (хп A f(x 1 , . . . ,xn-i,f{x и...,хп)=1)) V (хп A f(x 1 , . . . , х „ _ 1 , 0 ) ) .х?1 А ... А\J{(ст1,...,стп)|/(сг11...,стп) = 1}..3.4.2. Совершенные нормальные формыРеализация булевой функции f(xi,...,хп) в виде формулыVx^A...Ax£"{(ai ,...,crn)|/(ai,...,£Tn) = l}называется совершенной дизъюнктивной нормальной формой (СДНФ).ЗАМЕЧАНИЕСДНФ называется совершенной, потому что каждое слагаемое в дизъюнкции включаетвсе переменные; дизъюнктивной, потому что главная операция — дизъюнкция, а почемуона называется нормальной, объяснено далее, в отступлении в конце подраздела,Если при записи С Д Н Ф используется установленный порядок (см.
3.1.1), тоС Д Н Ф однозначно определяет множество наборов значений переменных, па которых функция, реализуемая СДНФ, принимает значение 1. Тем самым С Д Н Фоднозначно определяет таблицу истинности реализуемой функции, а значит, любые две различные С Д Н Ф над одним и тем же набором переменных неравносильны.ЗАМЕЧАНИЕПри рассмотрении дизъюнктивных (и конъюнктивных) форм мы имеем дело с формуламивидаV s . и Д Si,ieiieiгде I — некоторое множество индексов, a Si — некоторые формулы. Множество индексовможет быть пусто. В этом случае удобно считать, что пустая дизъюнкция имеет значениеО, а пустая конъюнкция — значение 1:/ =0V 5г = 0, / = 0Д Si = 1.ieiТЕОРЕМА 1ieiВсякая булева функция имеет единственнуюСДНФ.ДОКАЗАТЕЛЬСТВОf(xi,..
. ,Хп) =\/х\Х А...Лх°п<71 ,...,<7ПVА/((71,...,<7п)=х?1 A...A<" Af{ai,...,an) ={(«Л,-..,*n)|/(ai,...,an) = l}Vх^1 А . . . А х^ п .{(^1 ,...)«7П)|/(«ТЬ...,<7П) = 1}•122Глава 3. Булевы функцииВсякая булева функция может быть выражена через дизъюнкцию,конъюнкцию и отрицание:СЛЕДСТВИЕV / G P n (Э!Г[{ V . A , - . } ] ( / = func У)).ЗАМЕЧАНИЕЕсли / = 0, то {((TI,... ,<7п) | /(CTI, ... ,ап) = 1} — 0. В соответствии с соглашениемпредыдущего замечания пустая формула считается СДНФ нуля.Всякая булева функция имеет единственную совершенную конъюнктивную нормальную форму (СКНФ):ТЕОРЕМА 2/(:хи...,хп)=Д*n) = l}ДОКАЗАТЕЛЬСТВОПо принципу двойственности из предыдущей теоремы.•ОТСТУПЛЕНИЕГоворят, что некоторый класс формул X имеет нормальную форму, если задан другойкласс формул X', которые называются нормальными формами, такой, что любая формулакласса X имеет единственную равносильную формулу из класса X'.Если задан алгоритм, позволяющий для любой формулы построить её нормальную форму, то наличие у класса формул нормальной формы обеспечивает разрешимость, то естьналичие алгоритма проверки равносильности.
Действительно, в этом случае достаточносравнить нормальные формы двух формул.Один и тот же класс X может иметь несколько различных нормальных форм, то естьнесколько различных классов X'.Примеры1. СДНФ и С К Н Ф являются нормальными формами для булевых формул надлюбым базисом.2. Формулы видап^щхги (... (anx + an-i)x + ... + ai)a: + а 0i=0являются нормальными формами для полиномов одной переменной степепи п.3. Множество формул, построенных из рациональных функций одной переменной, ех и In® (то есть множество формул, реализующих элементарные функции математического анализа), нормальной формы не имеет.
Доказательствопоследнего утверждения выходит за рамки этого учебника.3.4. Нормальные формы1233.4.3. Эквивалентные преобразованияИспользуя уже доказанные равносильности, можно преобразовывать по правилузамены одни формулы в другие, равносильные им. Преобразование формулыв равносильную называется эквивалентным преобразованием.Пример Используя равносильности из подраздела 3.2.2, покажем, что имеетместо правило склеивания/расщепления: (х Л у) V (х Л у) = х. Действительно:(х Л у) V (х Л у) = х Л (у V у) = х Л 1 = х.ЗАМЕЧАНИЕЕсли равносильность из предыдущего примера применяется для уменьшения числа операций в формуле, то говорят, что производится склеивание, а если наоборот, то расщепление.Для любых двух равносильных формули J2 существует последовательность эквивалентных преобразований из 5*1 впосредством равносильностей, указанных в подразделе 3.2.2.ТЕОРЕМАЛюбую формулу (кроме тех, которые реализуют 0) можно преобразовать в СДНФ с помощью равносильностей из подраздела 3.2.2 и правиларасщепления из предыдущего примера по следующему алгоритму:ДОКАЗАТЕЛЬСТВО1.
Элиминация операций. Любая булева функция реализуется формулой над базисом {A, V, -i} (например, в виде СДНФ). Таким образом, любая присутствующая в формуле подформула с главной операцией, отличной от дизъюнкции,конъюнкции и отрицания, может быть заменена подформулой, содержащейтолько три базисные операции. Например, элиминация импликации выполняется с помощью равносильности х\ —> я 2 =V ж2. В результате первогошага в формуле остаются только базисные операции.2.
Протаскивание отрицаний. С помощью ипволютивпости отрицания и правил де Моргана операция отрицания «протаскивается» к переменным. В результате второго шага отрицания могут присутствовать в формуле тольконепосредственно перед переменными.3. Раскрытие скобок. По дистрибутивности конъюнкции относительно дизъюнкции раскрываются все скобки, являющиеся операндами конъюнкции.
В результате третьего шага формула приобретает вид дизъюнктивной формы:где Ак — это либо переменная, либо отрицание переменной.4. Удаление нулей. Если в слагаемое дизъюнктивной формы входят переменнаяи её отрицание (х A -кг), то такое слагаемое удаляется. Если при этом формула оказывается пустой, то процесс прерывается и считается завершённым(исходная формула реализует 0).124Глава 3. Булевы функции5. Приведение подобных. С помощью идемпотентности конъюнкции удаляютсяповторные вхождения переменных в каждую конъюнкцию, а затем с помощьюидемпотентности дизъюнкции удаляются повторные вхождения одинаковыхконъюнкций в дизъюнкцию. В результате пятого шага формула не содержит«лишних» переменных и «лишних» конъюнктивных слагаемых.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
