Дизъюнктивные нормальные формы и теорема о разложении

Таблица. 4

Простейшие функции

Простейшими называют функции от двух переменных. В табл.5.3 приведены все функции, существенно зависящие от двух переменных. Для восьми из них введены названия и обозначения в табл. 4.

Таблица. 3

Задание. Объясните, почему остальные 6 функций не вошли в таблицу.

Функция конъюнкция ещё называется функция И или логическое умножение и обозначается х&у=хÙу= х×у= ху

Функцию дизъюнкции ещё называют функцией ИЛИ (логическим сложением).

С помощью простейших можно строить более сложные функции, заменяя переменные функциями. В результате функции сопоставится формула, задающая последовательность выполнения операций. Для определения порядка вычисления функций можно использовать скобки. Например, функция, приведенная в табл. 5.1, может быть описана формулой

f = (x1Å(x2Åx3)).

Свойства простейших функций.

Между операциями над множествами, описанными в главе 1, и некоторыми простейшими функциями можно провести следующую аналогию. Для множества А сопоставим каждому элементу универсального множества функцию а=1, если аÎА, и а=0, если аÏА. Точно также переменную можно связать с любым множеством. Тогда имеет место следующие условия. Для элементов из `Афункция `а=1, для элементов АÇВ–а×b=1, для элементов АÈВ аÚb=1. Значит, свойства операций, рассмотренных в главе 1, будут верны и для простейших функций.

Ниже перечислены свойства простейших функций, в истинности которых просто убедиться элементарной проверкой с помощью перебора.

• Коммутативность функций конъюнкции, дизъюнкции, сложения по модулю 2: хÚу=уÚх.
• Ассоциативность этих же функций: (хÚу)Úz= хÚ(уÚz)=хÚуÚz.
• Дистрибуция: хÚ(у×z)=(хÚу)×(хÚz), х×(уÚz)= (ху)Ú(хz),х(уÅz)=(ху)Å(хz).
• Правило де Моргана: (хÚу)=`х×`у, (х×у)=`хÚ`у.
• Свойства констант: х×0=0,х×1=х,хÚ0=х,хÚ1=1,хÅ1=`х,хÅх=0,хÚ`х=1,х×`х=0.

Используя эти свойства, можно преобразовывать формулы, удаляя лишние элементы, раскрывая скобки, вынося элементы за знаки скобок и т.п.

Введём понятие степени булевой переменной. Будем считать, что x¹=x, x⁰=`x.

Из определения следует, что х^a=1, если х=a, и х^a=0, если х¹a. В справедливости этого можно убедиться простым перебором значений.

Конъюнкция x1^a1x₂2^a2...x_nn^an называется элементарной, если в ней каждая переменная встречается не более одного раза.

Рангом элементарной конъюнкции называется число букв, образующих эту конъюнкцию.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.

Длиной ДНФназывается число элементарных конъюнкций, образующих эту ДНФ. Длину ДНФбудем обозначать буквой L.

Дизъюнктивная нормальная форма, имеющая наименьшую длину по сравнению со всеми другими ДНФ, эквивалентными данной функции, называется кратчайшей ДНФ (КДНФ).

Дизъюнктивная нормальная форма, содержащая наименьшее число букв x_i^ai по сравнению со всеми другими ДНФ, эквивалентными данной функции, называется минимальной ДНФ (МДНФ).

Теорема о разложении. Для любой функции f(x₁,x₂,…,x_n,) f(x₁,x₂,…,x_i,…,x_n)=Úx1^a1× x2^a2 … xiai^{× ×}f(a₁,a₂,…,a_i,x_i+1…,x_n)

"a₁a₂…a_i

Доказательство. Возьмём произвольный набор значений переменных (b₁,b₂,…,b_n) и подставим его в выражение справа и слева от равенства. Получим

f(b₁,b₂,…,b_n)=Úb₁^a1× b₂^a2 … b_i^{ai× ×}f(a₁, a₂,…, a_i, b_i+1, …, b_n)

"a₁a₂…a_i

Справа для любого набора значений (a₁, a₂, …, a_i), не равного (b₁,b₂,…,b_i), соответствующая конъюнкция будет равна нулю, так как она в силу условия x^a = 0, если x¹a,будет содержать нулевой сомножитель. Останется единственная конъюнкция, где (a₁, a_2, …, a_i)=(b₁, b₂, …, b_i), то естьт.е. получим равенство f(b₁,b₂,…,b_n)= f(b₁,b₂,…,b_n), что и доказывает теорему.

Следствия из теоремы.

2.1. f(x₁,x₂ …)=x₁f(x₁=1)Ú`x₁×f(x₁=0). Это равенство известно как формула разложения К. Шеннона.

2. f(x₁,x₂,…,x_n)=Úx₁^a1× … x_n^{an× ×}f(a₁,a₂,…,a_n) =Úх₁^a1× х₂^a2 … х_n^an×

"a₁a₂…a_n "(a₁a₂…a_n)ÎT1

Это равенство получается из формулы при i=n, здесь Т1 –множество наборов значений аргументов, на которых функция равна 1. Оно известно как представление функции в виде совершенной дизъюнктивной нормальной формы (СДНФ).

Совершенная дизъюнктивная нормальная форма состоит из элементарных конъюнкций ранга n, то естьт.е. конъюнкций наибольшего возможного для данной функции ранга, поэтому с этой точки зрения СДНФ является наиболее сложной.

Любую функцию можно представить в виде СДНФи это представление единственно, так как оно однозначно сопоставляется таблице истинности функции.

ПримерПример. Рассмотрим Найдём разложение функциюи f=(aÅb)®`ac, найдём её разложение по переменной а:
.F=a×f(a=1)) Ú`a×f(a=0) =a×((1Å b)® 0)Ú `a×((0 Å b)® c)=

a×(`b®0)Ú `a(b®c). Здесь мы учли, что (1Åх)=`х, (0 Å х)=х. Если ещё учесть, что (х®0)=`х, что следует из таблицы истинности импликации, то получим окончательную формулу для функции
f =a×b Ú`a× (b®c).

ПримерПример. Представим функцию импликации в виде СДНФ, для чего запишем её табличное представление (табл.5.5). Здесь в множестве Т1 три набора 000, 001 и 111, поэтому в СДНФ будет три конъюнкции

х®у=`х×`уÚ` х×уÚ х×у