Разложение булевых функций по переменным. Сднф.

В ведём обозначение: x^σ= x,σ=1,

¬x, σ=0 x^σ=1x=σ

Функция вида x1^σ·x2^σ2·…·xσ^σk= xi^σ называется элементарной конъюнкцией, где - const

Функция вида называется элементарной дизъюнкцией, где - const

Теорема (о разложении булевых функций по переменным).Любую булеву функцию от n-переменных f(x1,x2,…,xn) можно представить в виде f(x1,x2,…,xn)=∪x1^σ1·x2^σ2·…·xk^σk·f(σ1,σ2,…,σk,x(k+1),…,xn)(1)

(σ1,σ2,…,σk)

Соотношение (1) назывется разложением булевой функции по первым k переменным. Для доказательства достаточно показать, что при подстановки любого набора в соотношение (1) дает тождество.

Возьмём произвольный набор n и подставим в соотношение (1).

F(α1,α2,…,αn)=∪α1^σ1,α2^σ2,…,αk^σkf(σ1,σ2,…,σk,αk+1,…,αn)

(σ1,…,σk)

В этой сумме отличными от нуля будут только те слогаемые, для которых i=i(i=1,…,k). Такое слогаемое единственное и оно имеет вид α1^α1·α2^α2·…·αk^αk·f(α1,…,αk,α(k+1),…,αn)=f(α1,…,αn). Это верно для любого n.

Следствия

1)Разложение булевой функции по одной переменной имеет вид: f(x1,…,xn)=∪x1^σ1·f(σ1,x2,…,xn)=

σ1

x1^1·f(1,x2,…,xn)∪ x1^0·f(0,x2,…,xn)= x1·f(1,x2,…,xn)∪¬х1·f(0,x2,…,xn).

2)Разложение булевой функции по всем n переменным имеет вид: f(x1,x2,…,xn)(2)=∪x1^σ1,…,xn^σnf(σ1,σ2,…,σn)=∪x1^σ1·x2^σ2·…·xn^σn(3)

(σ1,…,σn) (σ1,…,σn)f(σ1,…,σn)=1

Разложение (3) — совершенная дизъюнктивно нормальная форма.

Теорема. Любую булевую ф-цию, не тождественную 0(f≠0) можно представить в виде СКНФ.

Обоснование. Если ф-ция тождественная 0, f=0, то её можно представить f=x·(¬x). Если ф-ция не тожд. 0, то её можно представить в виде совершенной дизъюнктивно-нормальной формы (СДНФ).

Теорема является конструктивной, то есть позволяет для любой ф-ции построить ф-лу, реализующую её над этим снож ({&,∪,-}).

Построение СДНФ по таблице истинности:

1.Выделяем те наборы, на которых ф-ция принимает значение1.

2.По каждому такому набору строим элементарную конъюнкцию.

3.Полученные элементарные конъюнкции складываем.