1 - Булевы функции. Булевы алгебры. Булевы функции. ДНФ и КНФ. Критерий Поста. Минимизация ДНФ (1059972), страница 4
Текст из файла (страница 4)
выражение вида X = x̂1 x̂2 . . . x̂k , называется элементарной конъюнкцией. Требование, чтобывсе переменные были различны обусловливается следующим. Если в конъюнкцию входит несколько одинаковых литералов, то в силу коммутативности, ассоциативности и идемпотентности конъюнкции можно, переходя к эквивалентной формуле, оставить лишь один литерал(например, x1 x1 = x1 ).
Если в конъюнкцию входит переменная и ее отрицание, то формулаэквивалентна константе 0, поскольку x x = 0 и для любой формулы Y имеем Y x x = 0.Дизъюнкция нескольких элементарных конъюнкций называется дизъюнктивной нормальной формой, или ДНФ. Например,x1 x3 + x2 x3 x4 + x1 x2 x3 x5 .ÔÍ-12есть совершенная форма.Поскольку в булевой алгебре сложение и умножение — симметричные операции и всегдаможно интерпретировать сложение как умножение, а умножение как сложение, существует идвойственное понятие — конъюнктивная нормальная форма (КНФ), представляющаясобой конъюнкцию элементарных дизъюнкций, и совершенная конъюнктивная форма(СКНФ). Из принципа двойственности для симметричных полуколец вытекает, что любомуутверждению относительно ДНФ отвечает двойственное утверждение относительно КНФ, которое получается заменой сложения (дизъюнкции) умножением, умножения (конъюнкции) сложением, константы 0 константой 1, константы 1 константой 0, отношения порядка двойственным(обратным) порядком.
Поэтому далее мы остановимся на изучении только ДНФ.ÌÃÒÓЕсли состав переменных в каждой элементарной конъюнкции данной ДНФ один и тот же, тоДНФ называется совершенной. Приведенный пример — это ДНФ, не являющаяся совершенной. Напротив, формулаx1 x2 x3 x4 + x1 x2 x3 x4 + x1 x2 x3 x4ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИJ Условимся под xσ понимать формулу x, если σ = 1, и формулу x, если σ = 0. Пустьфункция f (y1 , .
. . , yn ) принимает значение 1 на векторе (t1 , . . . , tn ) (такой вектор называютконституэнтой единицы). Тогда элементарная конъюнкция xt11 xt22 . . . xtnn также принимаетзначение 1 на этом наборе, но обращается в нуль на всех остальных n-мерных булевых векторах.Рассмотрим формулуXΦ[x1 , x2 , . . . , xn ] =xt11 xt22 . .
. xtnn ,ÌÃÒÓÌÃÒÓТеорема 1.4. Любая булева функция, отличная от константы 0 представима в виде СДНФ.в которой сумма (объединение) распространяется на все те наборы (t1 , . . . , tn ) значений аргументов, на которых заданная функция принимает значение 1. Отметим, что множество такихнаборов не пусто, так что в сумме есть по крайней мере одно слагаемое.Нетрудно заметить, что формула Φ обращается в 1 при тех, и только при тех значенияхпеременных, при которых обращается в 1 рассматриваемая функция. Значит, формула Ψ представляет функцию f . IÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12f (t1 ,...,tn )=1ÌÃÒÓ010011100101110111010111m(x1 , x2 , x3 ) = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3Аналогично строится СКНФ.
Выбираем конституэнты нуля и для каждой составляем элементарную дизъюнкцию. Получим:m(x1 , x2 , x3 ) = (x1 + x2 + x3 )(x1 + x2 + x3 )(x1 + x2 + x3 )(x1 + x2 + x3 ). #Полнота стандартного базиса позволяет подбирать и другие полные системы функций. Полнота множества F может быть установлена из следующих соображений. Предположим, каждаяиз трех функций стандартного бузиса представима формулой над F .
Тогда в силу теоремы 1.3иножество F будет полным.xyz ⊕ xz ⊕ x ⊕ y ⊕ 1.Любую такую формулу называют полиномом Жегалкина. Фактически полином Жегалкина — это многочлен над кольцом Z2 .Нетрудно сконструировать формулы над базисом Жегалкина, представляющие операциисложения и отрицания стандартного базиса (умножение у двух базисов общее):x + y = x ⊕ y ⊕ xy,x = x ⊕ 1.Пример 1.4. Рассмотрим множество из единственной функции — штриха Шеффера* . Этомножество полно, что следует из следующих легко проверяемых тождеств:x = x | x,xy = x | y = (x | y) | (x | y),x + y = x | y = (x | x) | (y | y).*Штрих Шеффера — бинарная, но не ассоциативная операция. Поэтому при использовании инфиксной формыследует быть внимательным: результат зависит от порядка выполнения операций.
В этом случае рекомендуетсяявно указывать порядок операций при помощи скобок, например писать (x | y) | z, а не x | y | z, хотя обе формыравнозначны.ÔÍ-12Пример 1.5. Базис, состоящий из единственной функции — стрелки Пирса, также являетсяполным. Проверка этого аналогична случаю штриха Шеффера. Впрочем, это заключениеможно сделать и на основании принципа двойственности для симметричных полуколец.ÌÃÒÓПоэтому базис Жегалкина — полное множество.Можно показать, что для любой булевой функции полином Жегалкина определен однозначно(точнее, с точностью до порядка слагаемых).
Коэффициенты полинома Жегалкина при небольшом количестве переменных можно найти методом неопределенных коэффициентов.ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12x ⊕ 1,ÌÃÒÓПример 1.3. Множество из операций сложения по модулю 2, умножения и константы 1называют базисом Жегалкина. Сложение по модулю 2 и умножение — базовые операциикольца Z2 , выражения, составленные с их помощью — это многочлены над кольцом Z2 .
Константа 1 в данном случае необходима для записи свободного члена. Поскольку xx = x, то всесомножители в многочлене имеют степень 1. Поэтому при записи многочлена можно обойтисьбез понятия степени. Примеры формул над базисом Жегалкина:ÔÍ-12ÌÃÒÓПример 1.2. Рассмотрим функцию трех переменных m(x1 , x2 , x3 ) (табл. 1.4), называемуюмажоритарной функцией. Эта функция принимает значение 1, если больше половины ееаргументов имеют значение 1.
Поэтому ее часто называют функциейТаблица 1.4голосования. Построим для нее СДНФ.Мажоритарная функция имеет 4 конституэнты единицы, а значит,x1 , x2 , x3 m(x)в ее СДНФ должно быть четыре слагаемых. Результат будет следую0000щий:0010ÌÃÒÓÔÍ-12J Действительно, если функция не является константой 0, то она представима либо в видеСДНФ, которая является формулой над стандартным базисом. Константу 0 можно представить,например, формулой f (x1 , x2 , . . . , xn ) = x1 x1 . IÔÍ-12ÌÃÒÓÌÃÒÓ10Следствие 1.1.
Стандартный базис является полным.xy ⊕ x ⊕ y,ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИÌÃÒÓJ Доказательство достаточности критерия состоит в построении из заданных функций формул,представляющих функции стандартного базиса. Отметим, что в стандартном базисе одна избинарных операций выражается через отрицание и другую бинарную операцию, напримерx + y = x y.ÌÃÒÓÔÍ-12Поэтому достаточно построить формулы, определяющие отрицание и умножение.Пусть F не является подмножеством ни одного из классов Поста.
Для каждой функцииf ∈ F рассмотрим формулу g(x) = f (x, x, . . . , x). Поскольку F не содержится в T0 и в T1 ,в F , во-первых, есть непостоянные функции, а во-вторых есть хотя бы одна функция f1 , длякоторой g1 (0) = 1, и есть хотя бы одна функция f2 , для которой g2 (1) = 0. Это возможно, еслиодна из функций g1 (x) и g2 (x) есть отрицание, либо обе функции постоянны и представляютконстанты0 и 1.
Рассмотрим оба случая.Пусть функции g1 (x) и g2 (x) являются константы 0 и 1. Тогда для любой функции f ∈ Fформула f (α1 , α2 , . . . , αi−1 , x, αi+1 , . . . , αn ), в которой αj — константы, есть формула над F .Выберем функцию f , не являющуюся монотонной. Тогда существуют два булевых вектора p и q,удовлетворяющие условиям p < q и f (p) = 1, f (q) = 0.
Векторы p и q можно соединить цепочкойp = p0 , p1 , . . . , pk = q непосредственно предшествующих друг другу векторов (соседних). В этойцепочке найдется два соседних вектора pj−1 и pj , которые отличаются только одной компонентойс некоторым номером i и на которых f (pj−1 ) = 1, f (pj ) = 0. Пусть αj , j 6= i, одинаковыеÔÍ-12Теорема 1.5 (критерий Поста).
Множество F полно тогда и только тогда, когда оно неявляется подмножеством никакого из классов Поста.ÌÃÒÓÔÍ-12ÌÃÒÓРассмотрим некоторые классы булевых функций:• класс функций T0 , сохраняющих константу 0, т.е. функций, удовлетворящих условиюf (0, . . .
, 0) = 0;• аналогичный класс функций T1 , сохраняющих константу 1, т.е. удовлетворящих условиюf (1, . . . , 1) = 1;• класс S самодвойственных функций, т.е. функций, удовлетворяющих условию ∀α f (α) == f (α) (здесь α — n-мерный булев вектор, отрицание которого выполняется покомпонентно);• класс M функций, монотонных относительно естественного порядка полукольца Bn , т.е.функций, удовлетворяющих условию α 6 β ⇒ f (α) 6 f (β);• класс L линейных функций — функций, представимых полиномом Жегалкина первой степени (попросту говоря суммой по модулю 2 литералов, в число которых может входить константа 0).Выделенные классы называют классами Поста.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
