1 - Булевы функции. Булевы алгебры. Булевы функции. ДНФ и КНФ. Критерий Поста. Минимизация ДНФ (1059972), страница 3
Текст из файла (страница 3)
Каждой переменной входящей в формулу, должен соответствовать один аргументфункции, некоторые из аргументов могут быть ене связаны с какими-либо переменными. Еслитакое соответствие установить, то набор значений переменных, входящих в формулу, можно записать как булев вектор. При этом каждому булевому вектору будет соответствовать значениеформулы, и мы получаем корректно заданную булеву функцию.Рассматривая формулы как способ описания функций, естественно не различать те формулы, которые порождают одинаковые функции при фиксированном соответствии между переменными и аргументами функции.На практике мы часто пользуемся эквивалентными преобразованиями. Например, если f1 —булева функция из табл.
1.3, то f1 (x1 , x2 ) = f1 (x2 , x1 ). Знак равенства означает, что формулызадают одну и ту же функцию, т.е. эквивалентны. Вообще говоря, знак равенства в данномконтексте рассматривается как знак тождества, т.е. формулы дают одно и то же значение прилюбых значениях входящих в равенство переменных.
Если состав переменных слева и справаодин и тот же, то тождество как раз и означает, что левая и правая части задают одну и ту жефункцию. Однако возможно и такое равенство x ⊕ x = 0, также верное при любых значенияхнеизвестных. Но в левую часть входит переменная x, а в правой части вообще стоит константа.Левая часть задает функцию двух переменных, а правая часть — нульарную операцию (константу). Надо либо отказаться признать такое равенство, либо установить эквивалентностькаких-либо функций.
Второе более удобно.Две формулы* Φ[x1 , . . . , xn ] и Ψ[y1 , . . . , ym ] с наборами переменных x1 , . . . , xn и y1 , . . . , ymсоответственно назовем эквивалентными, если равенство Φ[x1 , . . . , xn ] = Ψ[y1 , . . . , ym ] остается верным при любых значениях всех переменных. Если наборы переменных не совпадают,то значение одной из формул или обеих не зависит от значений некоторых переменных.
ТакиеÌÃÒÓÌÃÒÓРис. 1.2ÔÍ-12ÔÍ-12x4ÌÃÒÓÌÃÒÓf2(x3)ÌÃÒÓ6x33ÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ7переменные назовем фиктивными. Переменную, не являющуюся фиктивной, будем называтьсущественной. У двух эквивалентных формул существенные переменные должны быть общими, хотя часть общих переменных может быть и фиктивными.Следующая теорема отражает обычные правила преобразования формул, приводящие кэквивалентным формулам.Теорема 1.1. Если формулы Φ[x1 , . . . , xn ] и Ψ[y1 , . .
. , ym ] эквивалентны, то замена в каждойиз них всех вхождений какой-либо из переменных произвольной формулой приведет к двумновым формулам, эквивалентным между собой.J Объединим списки переменных у формул и напишем равенствоΦ[z1 , . . . , zk ] = Ψ[z1 , . . . , zk ].ÔÍ-12Предположим, что все вхождения переменной zk заменены формулой ∆[u1 , .
. . , ul ]. Получимe 1 , . . . , zk−1 , u1 , . . . , ul ] и Ψ[ze 1 , . . . , u1 , . . . , ul ]. Обозначения исходят из того, что переформулы Φ[zменные формулы ∆ не входят в формулы Φ и Ψ. На самом деле это допущение несущественнои служит лишь упрощению рассуждений.Задав произвольные значения переменным z1 , . . . , zk−1 , u1 , . . . , ul , мы получим для переменной zk значение ∆(u1 , . . . , ul ). Проверка равенства значений двух формул равносильна проверкеисходного равенства, в котором в качестве значения переменной zk взято ∆(u1 , . . . , ul ). Поскольку исходное равенство верно, то и после подстановки равенство останется верным. IÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИJ Пусть дана формула Φ[x1 , .
. . , xn ], в которую входит подформула Ψ[x1 , . . . , xn ] (мы можемсчитать, что подформула включает все переменные исходной формулы, рассматривая недостающие как фиктивные). Заменим подформулу Ψ новой переменной z, которая не входит в списокx1 , . . .
, xn . Получим новую формулу Γ[x1 , . . . , xn , z], связь которой с исходной формулой можнозаписать в виде.Φ[x1 , . . . , xn ] = Γ[x1 , . . . , xn , z]ÌÃÒÓe 1 , . . . , xn ] приведет к новой форЗамена формулы Ψ[x1 , . . . , xn ] эквивалентной формулой Ψ[xмулеΓ[x1 , . . . , xn , z].eÔÍ-12ÌÃÒÓТеорема 1.2. Если в формуле заменить одну из подформул эквивалентной, то новая формула будет эквивалентна исходной.z=Ψ[x1 ,...,xn ]Надо показать, что при любых значениях неизвестных верно равенствоΓ[x1 , . .
. , xn , z]= Γ[x1 , . . . , xn , z].eНо нетрудно заметить, что, задавая значения неизвестных, мы в силу эквивалентности формулe получим один и тот же набор значений переменных в формуле Γ. Значит, в обеих частяхΨиΨравенства мы получим одно и то же значение. IВ функции f (x1 , . . . , xn ) назовем i-й аргумент фиктивным аргументом, если значениефункции не зависит от значения этого аргумента, т.е. функцииf (x1 , . . . , xi−1 , 0, xi+1 , . . . , xn ) и f (x1 , . . . , xi−1 , 1, xi+1 , .
. . , xn )совпадают. Вместо двух этих равных друг другу функций можно рассмотреть функциюf˜(x1 , . . . , xi−1 , xi+1 , . . . , xn ) = f (x1 , . . . , xi−1 , 0, xi+1 , . . . , xn ),у которой количество аргументов на единицу меньше. Такое преобразование назовем удалением фиктивного аргумента.ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12z=Ψ[x1 ,...,xn ]ÌÃÒÓÌÃÒÓz=Ψ[x1 ,...,xn ]ÌÃÒÓÔÍ-12z=Ψ[x1 ,...,xn ]ÌÃÒÓ[∅] = ∅;[[X]] = [X];X ⊂ [X];[X] ∪ [Y ] ⊂ [X ∪ Y ].Теорема 1.3. Если F — полное множество булевых функций, каждая из которых представима формулой над множеством G, то и G — полное множество.Но поскольку [F ] совпадает с множеством всех булевых функций, то и [G] совпадает с множеством всех булевых функций, т.е. G — полный базис. IÔÍ-12J Так как каждая функция из F есть формула над G, то F ⊂ [G].
Из свойств замыканиявытекает, что[F ] ⊂ [[G]] = [G].ÌÃÒÓПервое свойство носит формальный характер. Второе вытекает из конечности процедурыпостроения любой формулы: достаточно, следуя по дереву синтаксического анализа, последовательно заменять функции из [X] их формулами над X. Третье и четвертое свойства очевидны.Из четвертого свойства вытекает, что если X ⊂ Y , то [X] ⊂ [Y ].
Действительно, включениеX ⊂ Y равносильно равенству X ∪ Y = Y . Если X ⊂ Y , то в силу свойства 4 заключаем, что[X] ∪ [Y ] ⊂ [X ⊂ Y ] = [Y ]. Следовательно, [X] ⊂ [Y ].Из указанных свойств замыкания вытекает следующее утверждение.ÔÍ-121)2)3)4)ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12Две функции назовем эквивалентными, если после удаления в каждой из них всех фиктивных аргументов, мы получим равные функции.Нетрудно проверить, что введенное отношение на множестве булевых функций действительно является отношением эквивалентности.
Точно так же на множестве все булевых формул эквивалентность (в смысле равенства значений при любых значениях переменных) — этоотношение эквивалентности.Введение этих отношений преследует единственную цель: обозначить степень неоднозначности, с которой функции записываются формулами. Можно утверждать, что при фиксированномпорядке переменных каждому классу эквивалентных формул соответствует ровно один классэквивалентных функций. Вопрос: является ли это соответствие биекцией? Можно ли утверждать, что каждый класс эквивалентных функций определяется некоторым классом эквивалентных формул? Ответ зависит от выбора набора базовых функций, или базиса, т.е. множества F .Пусть F — некоторое множество функций. Его замыканием назовем множество [F ] всехбулевых функций, которые представимы формулами с базисом F (формулами над множеством F ).
Если замыкание множества F совпадает с F , то это множество называется замкнутым. Множество F называется полным, если его замыкание совпадает с множествомвсех булевых функций.Термин полный базис“ как раз и означает, что любую булеву функцию можно записать”аналитически, используя в качестве исходных функции базиса. Замыкание множества — совокупность всех функций, которые могут быть представлены формулами над этим множеств.Замкнутое множество F — такое множество, которое не может быть расширено добавлениемфункций, представимых формулами над F .Замыкание может рассматриваться как операция на совокупности всевозможных множествбулевых функций.
Такая операция обладает следующими свойствами:ÌÃÒÓÌÃÒÓВозможно и противоположное преобразование — введение фиктивных переменных, аименно:ĝ(x1 , . . . , xi−1 , xi , xi+1 , . . . , xn ) = g(x1 , . . . , xi−1 , xi+1 , . . . , xn ).ÌÃÒÓÔÍ-12ÌÃÒÓ8ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ91.3. ДНФ и КНФСтандартный базис. Элементарные формулы — литералы.
Элементарная конъюнкция (дизъюнкция). Дизъюнктивная (конъюнктивная) нормальная форма и совершенная форма. Теорема: любая булева функция, отличная от 0 (от 1) представима в виде СДНФ (СКНФ). Полнота стандартного базиса. Примеры полных базисов: базис Жегалкина, штрих Шеффера,стрелка Пирса.Стандартный базис — это набор из трех исходных операций булевой алгебры: сложения(объединения), умножения (пересечения) и отрицания.Здесь мы будем называть литералом переменную x или ее отрицание x и обозначать x̂.Булево пересечение нескольких литералов, определяемых различными переменными, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
