Разложение функции алгебры логики по переменным. СДНФ, СКНФ. Полином Жегалкина.

1. Метод равносильных преобразований. Используется для функций, заданных формулой. Метод состоит в выполнении следующих действий.

1) В формуле все функции, кроме суммы Жегалкина и эквиваленции, выражаются через отрицание, конъюнкцию и дизъюнкцию. Эквиваленция заменяется отрицанием операции : .

2) Дизъюнкция исключается с помощью закона Моргана: .

3) Отрицание исключается с помощью свойства суммы Жегалкина: .

4) Раскрываются скобки, приводятся подобные с помощью законов:

, , , .

Пример. = = = = = = .

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

Пример. Пусть функция задана таблицей 2.14. Запишем полином Жегалкина для f:

f ( , ) = (2.5)

Табл. 2.14
		f( , )

f (0,0) = ·0 ·0 ·0 =1 (Значение f (0,0) = 1 выбирается из таблицы).

f(1,0) = ·0 ·1 ·0 =0 =0 1=0 =1.

Аналогично, f(0,1) = ·0 ·0 ·1 =0 =0 1=0 =1.

f(1,1) = ·1 ·1 ·1 =1 =1

1 1 1=1 =0.

Теперь можно записать выражение (2.5) с определенными коэффициентами: f ( , ) = 1.

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

Разложение функции алгебры логики по переменным. СДНФ, СКНФ. Полином Жегалкина.

Логической степенью переменной х называется выражение

Другими словами, логическая степень – выражение, которое обозначает переменную или ее отрицание.

Из определения логической степени следует, что . Данное утверждение можно пояснить табл.2.11.

На основании этого можно определить следующее общее свойство логической степени: x^s=1 тогда и только тогда, когда x=s (соответственно x^s=0Û x≠s).

Рассмотрим набор переменных {x₁,..,x_n}.

Конъюнкцией (дизъюнкцией) над множеством переменных {x₁,..,x_n} называетсялюбое выражение вида , в котором Î{x₁,..,x_n}, j= .

Рангом конъюнкции (дизъюнкции) над множеством переменных {x₁,..,x_n} называетсяколичество попарно различных переменных в конъюнкции (дизъюнкции).

Пример. Рассмотрим набор переменных {x₁,x₂,x₃,x₄}.

Тогда ( ) – конъюнкция (дизъюнкция) ранга 3.

Конъюнкция (дизъюнкция) над множеством переменных {x₁,..,x_n} называется элементарной, если все переменные в ней попарно различны.

Элементарную конъюнкцию (дизъюнкцию) над множеством переменных {x₁,..,x_n}, называют совершенной , если она имеет ранг n.

Иными словами, совершенная конъюнкция (дизъюнкция) – это такая, в которой присутствуют все переменные из рассматриваемой совокупности, причем по 1 разу.

Пример.

– элементарная конъюнкция над множеством переменных {x₁,x₂,x₃,x₄}, но не совершенная; – совершенная конъюнкция над множеством переменных {x₁,x₂,x₃,x₄}.

Конъюнкцию (дизъюнкцию) над множеством переменных {x₁,..,x_m} можно обозначать K(D) или K_i(D_i).

Дизъюнктивной (конъюнктивной) нормальной формой называется формула вида K₁ÚK₂Ú…ÚK_l или ( D₁&D₂&… &D_l или ).

Пример.

–дизъюнктивная нормальная форма. – конъюнктивная нормальная форма.

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

Пример. Для набора переменных {x₁,x₂,x₃} – совершенная дизъюнктивная нормальная форма, – совершенная конъюнктивная нормальная форма.

Теорема(о разложении функции алгебры логики по m переменным).

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

(2.1)

Это представление называется разложением функции по m переменным x₁,..,x_n .

Доказательство. Подставим вместо переменных x₁,..,x_n любые конкретные значения a₁,..,a_nÎE₂. Тогда в левой части равенства (2.1) получим f(a₁,..,a_n), в правой . Выражение равно нулю, если существует i (1≤i≤m), при котором a_i≠s_i (по свойству логической степени и свойству конъюнкции x 0=0).

Тогда рассматриваемое выражение можно преобразовать к виду

, так как

,а по свойству дизъюнкции . Мы видим ,таким образом, что левая и правая части выражения (2.1) совпадают при подстановке вместо переменных любых значений.

Тем самым равенство доказано.

Следствие ( разложение функции алгебры логики по всем переменным).

Для любой функции алгебры логики, не тождественно равной 0, справедливо разложение:

.

(2.2)

Это разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции f(x₁,..,x_n).

Доказательство. В равенстве (2.1) положим m=n, получим :

.

Теорема позволяет функции с большим числом переменных выразить с помощью формул над функциями с меньшим числом переменных.

Пример.

Рассмотрим функцию эквиваленции (табл.2.12). Найдем ее разложение по переменной x₁ и по всем переменным.

Согласно (2.1), получим

– разложение по переменной x₁.

По табл.2.12 функции f(x₁,x₂) определяем, что f принимает значение 1 на двух наборах (s₁,s₂) значений переменных – на наборах (0,0) и (1,1). Отсюда, согласно (2.2),

– СДНФ для .

Теорема.Для любой функции алгебры логики, не тождественно равной 1, справедливо следующее разложение:

.

(2.3)

Это разложение назовем совершенной конъюнктивной нормальной формой (СКНФ) функции f(x₁,..,x_n).

Доказательство. Докажем теорему, используя принцип двойственности.