Diskretnaya_matematika_1_semestr

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

Пусть f(x1,…,xn)-произвольная булева ф-ция. Представим f* в виде совершенной ДНФ:f*(x1,…,xn)=∪x1^σ1·x2^σ2·…·xn^σn

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

Воспользуемся тождеством f**=f. Найдём двойственные ф-ции в обеих частях.

f(x1,…,xn)=&(x1^σ1∪x2^σ2∪…∪xn^σn)

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

Воспользуемся определением двойственности: f*(σ1,…,σn)=¬¬f(¬σ1,…,¬σn)=&(x1^σ1∪x2^σ2∪…∪xn^σn)=

(σ1,…,σn):f(¬σ1,…,¬σn)=0

=&(x1^¬α1∪x2^¬σ2∪…∪xn^¬αn) (4)

(α1,…,αn):f(α1,…,αn)=0

Представление (4) называется совершенной конъюнктивной нормальной формой.

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

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

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

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

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