Совершенные нормальные формы

Введем обозначение: x^s=x&s Ú & , где s - параметр, равный либо 0, либо 1. Составив таблицу значений для x^s, убеждаемся, что

а) x^s равно при s = 0 и x при s =1; б) x^s=1 Û, когда x =s.

Теорема 1.1 (о разложении функции по m переменным). Каждую функцию f(x₁,...,x_n) алгебры логики при любом m (1 £ m £ n), можно представить в следующей форме:

f(x₁,...,x_m,x_m+1,...,x_n)= f(s₁,...,s_m,x_m+1,...,x_n), (1.1)

где дизъюнкция берется по всевозможным наборам значений переменных x₁,...,x_m. Это представление называется разложением функции по m переменным x₁,...,x_m.

 f(s₁,...,s_m,x_m+1,...,x_n) =

( принимает 2 значения: 0, и тогда вся конъюнкция обращается в 0, или 1 при x_i=s_i ; поэтому среди 2^m конъюнкций имеется только одна, не равная нулю, при x₁=s ₁, x₂=s ₂, ..., x_m=s _m)

f(x₁,...,x_m,x_m+1,...,x_n)= f(x₁,...,x_m,x_m+1,...,x_n). 

Пример. При n=3, m=2:

f(x₁, x₂, x₃) = x₁⁰ x₂⁰ f(0,0,x₃) Ú x₁⁰ x₂¹ f(0,1,x₃) Ú x₁¹ x₂⁰ f(1,0,x₃) Ú x₁¹ x₂¹ f(1,1,x₃).

Пусть f(x₁,...,x_n)¹0. Разложим эту функцию по всем n переменным:

f(x₁,...,x_n) = f(s₁,...,s_n).

Если значение f(s₁,..., s_n) равно нулю, то и вся конъюнкция равна 0. Составим дизъюнкцию только по тем наборам переменных, на которых f(s₁,..., s_n)=1:

f(x₁,...,x_n) . (1.2)

Такое разложение носит название совершенной дизъюнктивной нормальной формы (СДНФ).

Теорема 1.2.Каждая функция алгебры логики может быть выражена в виде формулы через отрицание, конъюнкцию и дизъюнкцию.

 При f(x₁,...,x_n)º0 f(x₁,...,x_n)= . Иначе представим f в виде СДНФ (ф-ла 1.2). 

Данная теорема позволяет для каждой функции построить формулу, реализующую ее в виде СДНФ: в таблице значений функции f(x₁,...,x_n) отмечают все строки (s₁,...,s_n), в которых f(s₁,...,s_n)=1, затем для каждой такой строки образуют логическое произведение: , после чего все полученные конъюнкции соединяют знаком дизъюнкции.

Примеры. 1) Записать СДНФ для функции xÅy. Решение. Мы имеем два набора (0, 1), (1, 0), на которых эта функция равна 1; поэтому xÅy= x⁰&y¹ Ú x¹&y⁰= y Ú x .

2) СДНФ для функции x­y =

3) Путем ~-х преобразований привести к СДНФ выражение yÚ z.

Решение. ДНФ yÚ z не является совершенной, т.к. входящие в нее конъюнкции содержат не все три переменные, от которых зависит функция. Всякую ДНФ можно привести к СДНФ расщеплением конъюнкций с помощью логической единицы.

yÚ z = 1 y 1 Ú 1 z = (xÚ ) y ( z Ú ) Ú ( yÚ ) z =

= xyz Ú Ú xy Ú y Ú Ú z = xyz Ú yz Ú xy Ú y Ú z.

СДНФ -это логическая сумма логических произведений. Возникает вопрос: нельзя ли для булевых функций получить разложение в виде логического произведения логических сумм? Покажем, что при f(x₁,...,x_n)¹1 это возможно, для чего разложим двойственную к f функцию f* ( очевидно, если f ¹0, то f *¹1) в СДНФ:

f*(x₁,...,x_n) .

Поменяв знаки & и Ú, составим тождество для двойственных формул:

f(x₁,...,x_n) .

С учетом определения двойственной функции преобразуем правую часть последнего равенства: f(x₁,...,x_n) .

Обозначив через для 1 £ i £ n, окончательно получим

f(x₁,...,x_n) . (1.3)

Это выражение носит название совершенной конъюнктивной нормальной формы (СКНФ).

Примеры. 1) Запишем СКНФ для функции xÅy. Эта функция равна 0 на наборах (0,0) и (1,1); поэтому xÅy = =(х Ú y) ( Ú ).

2) СКНФ для функции x | y = Ú

3) Путем эквивалентных преобразований привести к СКНФ выражение yÚ z = (yÚ )&(yÚz). КНФ (yÚ ) & (yÚz) не является совершенной, т.к. входящие в нее дизъюнкции содержат не все три переменные, от которых зависит функция. Всякую КНФ можно привести к СКНФ расщеплением дизъюнкций с помощью логического нуля.

(yÚ ) & (yÚz) = ( Ú yÚ0) & (0ÚyÚz)= ( Ú yÚ z ) & (x ÚyÚz)=(xÚyÚz) & ( ÚyÚz) & ( ÚyÚ ).

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

Рассмотрим функцию f(x₁,...,x₂₀)=x₁Úx₂Ú...Úx₂₀. Формула в правой части насчитывает 39 символов (20 символов переменных и 19 символов дизъюнкции), тогда как таблица для функции f(x₁,...,x₂₀) содержит 2²⁰ (более миллиона) строк.

Полнота. Примеры полных систем

Выше было показано, что всякая функция алгебры логики может быть выражена в виде формулы через элементарные функции , x₁&x₂, x₁Úx₂. Оказывается, что таким свойством обладают и некоторые другие системы элементарных функций.

Система функций {f₁, f₂,..., f_k} называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

Примеры. Системы P₂ - множество всех булевых функций и S₂={ , x₁&x₂, x₁Úx₂}.

Теорема 1.3. Пусть даны две системы функций из P₂: F={f₁, f₂,...} и G={g₁,g₂,...}, относительно которых известно, что система F полна и каждая ее функция выражается в виде формулы через функции системы G. Тогда система G также является полной.

 Пусть h - произвольная функция из P₂. Т.к. система F - полная, можно выразить h формулой над F, то есть h=c(f₁, f₂,...). По условию f₁=c₁(g₁,g₂,...), f₂=c₂(g₁,g₂,...), ... Поэтому в формуле c(f₁, f₂,...) можно исключить вхождения функций f₁, f₂,..., заменив их функциями из G:

h=c(f₁, f₂,...)=c(c₁(g₁,g₂,...), c₂(g₁,g₂,...), ...)= c’(g₁,g₂,...).

Таким образом, произвольную формулу h удалось выразить через функции системы G, что доказывает полноту этой системы. 

Опираясь на теорему 1.3, можно установить полноту еще ряда систем.

3. Система S₃={ ,x₁&x₂} является полной. В качестве полной системы выберем S₂={ ,x₁&x₂,x₁Úx₂} (см. п. 2). В соответствии с законом де Моргана, x₁Úx₂= .

4. Система S₄={ ,x₁Úx₂} является полной. Аналогично п. 3 с помощью закона де Моргана выражаем конъюнкцию через дизъюнкцию и отрицание: x₁&x₂= .

5. Система S₅={x₁­x₂}, состоящая из одной функции - стрелки Пирса, является полной. В качестве полной выберем систему S₃={ ,x₁&x₂}. Затем, =x­x и x₁&x₂=(x₁­x₁)­(x₂­x₂).

6. Система S₆={x₁|x₂}, состоящая только из одной функции - штриха Шеффера, является полной. За полную возьмем систему S₄={ ,x₁Úx₂}. Затем, =x|x и x₁Úx₂=(x₁|x₁)|(x₂|x₂).

7. Система S₇={1,x₁&x₂,x₁Åx₂} является полной. За полную возьмем систему S₃={ ,x₁&x₂}. Отрицание выразим через константу 1 и сложение по модулю 2: =xÅ1.

Формула, построенная из констант 0 и 1 и функций x₁&x₂ и x₁Åx₂ после раскрытия скобок и несложных алгебраических преобразований переходит в полином по модулю 2, который называют полиномом И.И.Жегалкина.

Пример. Общий вид полинома Жегалкина для функции трех переменных следующий:

f(x₁,x₂, x₃)=a₁₂₃x₁x₂x₃ Å a₁₂x₁x₂ Å a₁₃x₁x₃ Å a₂₃x₂x₃ Å a₁x₁ Å a₂x₂ Å a₃x₃ Å a₀ ,

где a₁₂₃, a₁₂, ..., a₀ - коэффициенты полинома, каждый из которых может принимать одно из двух значений - 0 или 1.

Теорема 1.4 (Жегалкина). Каждая функция из P₂ может быть выражена при помощи полинома по модулю 2.

 Подсчитаем общее число различных полиномов Жегалкина от n переменных. Число m различных конъюнкций равно количеству подмножеств (i₁,i₂,...,i_k) множества {1,2...,n}, то есть m=2ⁿ (Æ соответствует a₀). Каждая конъюнкция имеет коэффициент a_..., который можно выбрать двумя способами (0 либо 1). В соответствии с правилом произведения число различных полиномов от n переменных, которые можно образовать из этих конъюнкций, равно 2^m= (пустому подмножеству конъюнкций соответствует полином 0).

Таким образом, число всех полиномов Жегалкина от n переменных равно числу всех булевых функций от тех же переменных. Отсюда, как следствие, получаем единственность представления функций посредством полиномов Жегалкина. 

Пример. Выразить x₁|x₂ в виде полинома Жегалкина. Ответ. x₁|x₂ = x₁x₂Å1.