Разложение функции алгебры логики по переменным. СДНФ, СКНФ. Полином Жегалкина.
1. Метод равносильных преобразований. Используется для функций, заданных формулой. Метод состоит в выполнении следующих действий. 1) В формуле все функции, кроме суммы Жегалкина и эквиваленции, выражаются через отрицание, конъюнкцию и дизъюнкцию. Эквиваленция заменяется отрицанием операции 2) Дизъюнкция исключается с помощью закона Моргана: 3) Отрицание исключается с помощью свойства суммы Жегалкина: 4) Раскрываются скобки, приводятся подобные с помощью законов:
Пример. 2. Метод неопределенных коэффициентов. Используется для функций, заданных таблицей. Метод состоит в том, что сначала записывается полином Жегалкина для заданной функции в общем виде с неопределенными коэффициентами, затем эти коэффициенты определяются на основе таблицы значений функции от конъюнкции наименьшего ранга к конъюнкциям больших рангов. Пример. Пусть функция задана таблицей 2.14. Запишем полином Жегалкина для f: f (
f (0,0) = f(1,0) = Аналогично, f(0,1) = f(1,1) =
Теперь можно записать выражение (2.5) с определенными коэффициентами: f ( Теорема.Любая функция алгебры логики представима в виде полинома Жегалкина единственным образом с точностью до порядка следования слагаемых. Разложение функции алгебры логики по переменным. СДНФ, СКНФ. Полином Жегалкина.
Логической степенью переменной х называется выражение
Другими словами, логическая степень – выражение, которое обозначает переменную или ее отрицание.
Из определения логической степени следует, что На основании этого можно определить следующее общее свойство логической степени: xs=1 тогда и только тогда, когда x=s (соответственно xs=0Û x≠s). Рассмотрим набор переменных {x1,..,xn}. Конъюнкцией (дизъюнкцией) над множеством переменных {x1,..,xn} называетсялюбое выражение вида Рангом конъюнкции (дизъюнкции) над множеством переменных {x1,..,xn} называетсяколичество попарно различных переменных в конъюнкции (дизъюнкции). Пример. Рассмотрим набор переменных {x1,x2,x3,x4}. Тогда Конъюнкция (дизъюнкция) над множеством переменных {x1,..,xn} называется элементарной, если все переменные в ней попарно различны. Элементарную конъюнкцию (дизъюнкцию) над множеством переменных {x1,..,xn}, называют совершенной , если она имеет ранг n. Иными словами, совершенная конъюнкция (дизъюнкция) – это такая, в которой присутствуют все переменные из рассматриваемой совокупности, причем по 1 разу. Пример.
Конъюнкцию (дизъюнкцию) над множеством переменных {x1,..,xm} можно обозначать K(D) или Ki(Di). Дизъюнктивной (конъюнктивной) нормальной формой называется формула вида K1ÚK2Ú…ÚKl или Пример.
Дизъюнктивная (конъюнктивная) нормальная форма называется совершенной дизъюнктивной(конъюнктивной) нормальной формой или СДНФ(СКНФ),если каждая конъюнкция (дизъюнкция) в ней является совершенной. Пример. Для набора переменных {x1,x2,x3} Теорема(о разложении функции алгебры логики по m переменным). Каждую функцию алгебры логики f(x1,..,xn) для любого m≤n следующее можно представить в следующей форме :
Это представление называется разложением функции по m переменным x1,..,xn . Доказательство. Подставим вместо переменных x1,..,xn любые конкретные значения a1,..,anÎE2. Тогда в левой части равенства (2.1) получим f(a1,..,an), в правой Тогда рассматриваемое выражение можно преобразовать к виду
Тем самым равенство доказано. Следствие ( разложение функции алгебры логики по всем переменным). Для любой функции алгебры логики, не тождественно равной 0, справедливо разложение:
Это разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции f(x1,..,xn). Доказательство. В равенстве (2.1) положим m=n, получим :
Теорема позволяет функции с большим числом переменных выразить с помощью формул над функциями с меньшим числом переменных.
Пример.
Рассмотрим функцию эквиваленции (табл.2.12). Найдем ее разложение по переменной x1 и по всем переменным. Согласно (2.1), получим
По табл.2.12 функции f(x1,x2) определяем, что f принимает значение 1 на двух наборах (s1,s2) значений переменных – на наборах (0,0) и (1,1). Отсюда, согласно (2.2),
Теорема.Для любой функции алгебры логики, не тождественно равной 1, справедливо следующее разложение:
Это разложение назовем совершенной конъюнктивной нормальной формой (СКНФ) функции f(x1,..,xn). Доказательство. Докажем теорему, используя принцип двойственности.
|
: 
.
.
.
, 
, 
, 
.
= 
= 
= 
= 
= 
= 
.
, 
) = 
(2.5)
, 
)
·0 
·0 
=1 (Значение f (0,0) = 1 выбирается из таблицы).
. Данное утверждение можно пояснить табл.2.11.
, в котором 
Î{x1,..,xn}, j= 
.
( 
) – конъюнкция (дизъюнкция) ранга 3.
– элементарная конъюнкция над множеством переменных {x1,x2,x3,x4}, но не совершенная; 
– совершенная конъюнкция над множеством переменных {x1,x2,x3,x4}.
( D1&D2&… &Dl или 
).
–дизъюнктивная нормальная форма. 
– конъюнктивная нормальная форма.
– совершенная дизъюнктивная нормальная форма, 
– совершенная конъюнктивная нормальная форма.
. Выражение 
равно нулю, если существует i (1≤i≤m), при котором ai≠si (по свойству логической степени и свойству конъюнкции x 
0=0). 
, так как
,а по свойству дизъюнкции 
. Мы видим ,таким образом, что левая и правая части выражения (2.1) совпадают при подстановке вместо переменных любых значений.
.
.
– разложение по переменной x1.
– СДНФ для 
.
.