1-2-3

Нормальные формы Оптимизация ДНФ

Существование СДНФ

Теорема. Для любой булевой функции f : Bn ! B имеет место

f (x1; x2; : : : ; xn) = _ x1 1 & x2 2 & : : : & xn n :

( 1;2;:::n)2Bn:f ( 1;2;:::n)=1

Доказательство (продолжение). Пусть п.ч. равна 1. Тогда для некоторого ( 1; 2; : : : n) 2 Bn, такого, что

f ( 1; 2; : : : n) = 1, имеем

x1 1 & x2 2 & : : : & xn n = 1

Значит для каждого i = 1; n значение xi i = 1, а это возможно только при xi = i . Таким образом,

f (x1; x2; : : : ; xn) = 1:

Нормальные формы Оптимизация ДНФ

Существование СКНФ

Теорема. Для любой булевой функции f : Bn ! B имеет место

f (x1; x2; : : : ; xn) = & (x 1 _x 2 _ _x n ):

( 1;2;:::n)2Bn:f ( 1;2;:::n)=0 1 2 n

Нормальные формы Оптимизация ДНФ

Существование СКНФ

Теорема. Для любой булевой функции f : Bn ! B имеет место

f (x1; x2; : : : ; xn) = & (x 1 _x 2 _ _x n ):

( 1;2;:::n)2Bn:f ( 1;2;:::n)=0 1 2 n

Доказательство. Пусть f (x1; x2; : : : ; xn) = 0. Тогда при

1 = x1; 2 = x2; : : : ; n = xn имеем

x1 1 _ x2 2 _ _ xn n = 0 _ 0 _ _ 0 = 0:

Поэтому правая часть (п.ч.) равна 0.

Нормальные формы Оптимизация ДНФ

Существование СКНФ

Теорема. Для любой булевой функции f : Bn ! B имеет место

f (x1; x2; : : : ; xn) = & (x 1 _x 2 _ _x n ):

( 1;2;:::n)2Bn:f ( 1;2;:::n)=0 1 2 n

Доказательство (продолжение). Пусть п.ч. равна 0. Тогда для некоторого ( 1; 2; : : : n) 2 Bn, такого, что

f ( 1; 2; : : : n) = 0, имеем

x1 1 _ x2 2 _ _ xn n = 0

Значит для каждого i = 1; n значение xi i = 0, а это возможно только при xi = i . Таким образом,

f (x1; x2; : : : ; xn) = 0:

Нормальные формы Оптимизация ДНФ

Вес ДНФ

IВесом ДНФ называется количество литералов, входящих в ДНФ.

Нормальные формы Оптимизация ДНФ

Вес ДНФ

IВесом ДНФ называется количество литералов, входящих в ДНФ.

IНапример, вес ДНФ

x1 & x2 & x3 _ x2 & x3 _ x1 & x2

равен

Нормальные формы Оптимизация ДНФ

Вес ДНФ

IВесом ДНФ называется количество литералов, входящих в ДНФ.

IНапример, вес ДНФ

x1 & x2 & x3 _ x2 & x3 _ x1 & x2

равен 7.

Нормальные формы Оптимизация ДНФ

Вес ДНФ

IВесом ДНФ называется количество литералов, входящих в ДНФ.

IНапример, вес ДНФ

x1 & x2 & x3 _ x2 & x3 _ x1 & x2

равен 7.

IЗадача. По данной булевой функции f найти ее ДНФ с наименьшим весом.

Нормальные формы Оптимизация ДНФ

Вес ДНФ

IВесом ДНФ называется количество литералов, входящих в ДНФ.

IНапример, вес ДНФ

x1 & x2 & x3 _ x2 & x3 _ x1 & x2

равен 7.

IЗадача. По данной булевой функции f найти ее ДНФ с наименьшим весом. (Такая ДНФ называется минимальной.)

Нормальные формы Оптимизация ДНФ

Импликанты

I Элементарный конъюнкт

называется импликантом булевой функции f (x1; x2; : : : ; xn), если

K = 1 =) f (x1; x2; : : : ; xn) = 1

для всех x1; x2; : : : ; xn 2 B: