Ekzamen-Дисмат

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

В ведём обозначение:

x, σ=1

<=> x=σ

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

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

Теорема (о разложении булевых функций по переменным)

Любую булеву функцию можно представить в виде (1)

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

В этой сумме отличными от нуля будут только те слогаемые, для которых ai=si. Такое слогаемое только одно и оно имеет вид

. Это верно для любого n.

Следствия

1)Разложение булевой функции по одной переменной:

2)Разложение булевой функции по всем n переменным имеет вид

Это СДНФ — совершенная дизъюнктивно нормальная форма

f=f(x1,...,xn); f представим в виде СДНФ.

f**=f

ai=si

СКНФ

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