1-2-3

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

Булевы функции

IB = f0; 1g.

IБулева функция функция f : Bn ! B:

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

Литералы

I Литерал любая переменная x или ее отрицание x.

(

x если = 1

I x =

xесли = 0:

I = 1 и = 0 для всех 2 B:

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

Литералы

I Литерал любая переменная x или ее отрицание x.

(

x если = 1

I x =

xесли = 0:

I= 1 и = 0 для всех 2 B:

IТаким образом, x = 1 тогда и только тогда, когда x = .

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

Литералы

I Литерал любая переменная x или ее отрицание x.

(

x если = 1

I x =

xесли = 0:

I= 1 и = 0 для всех 2 B:

IТаким образом, x = 1 тогда и только тогда, когда x = .

IА также, x = 0 тогда и только тогда, когда x 6= , то есть x = .

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

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

IКонъюнкция нескольких литералов называется элементарным конъюнктом

IПримеры x2 & x4, x1 & x2 & x3.

IЭлементарный конъюнкт нзывается полным, если он содержит все рассматриваемые переменные.

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

Элементарные дизъюнкты

IДизъюнкция нескольких литералов называется элементарным дизъюнктом

IПримеры x2 _ x4, x1 _ x2 _ x3.

IЭлементарный дизъюнкт нзывается полным, если он содержит все рассматриваемые переменные.

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

Дизъюнктивные нормальные формы

IДизъюнкция нескольких элементарных конъюнктов называется дизъюнктивной нормальной формой (ДНФ).

IПример x2 & x4 _ x1 & x2 & x3.

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

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

Конъюнктивные нормальные формы

IКонъюнкция нескольких элементарных дизъюнктов называется конъюнктивной нормальной формой (КНФ).

IПример (x2 _ x4) & (x1 _ x2 _ x3).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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