ВУЗ:
Составители:
Рубрика:
19
Разложение булевых функций по переменным.
Теорема 4.2. (о разложении функций по переменным). Каждую
функцию алгебры логики f(x
1
,…,x
n
) при любом m,1
≤
m
≤
n, можно
представить в следующей форме:
),...,,,...,(),...,,,...,(
,..,
n1mm1m1n1mm1
xxfxxxxxxf
m1
m1
++
∨=
δδ
δδ
δδ
,
(4.1)
где дизъюнкция берется по всем возможным наборам
значений переменных x
1
,…,x
m
.
Это представление называется разложением функции по m
переменным x
1
,…,x
m
.
Доказательство.
Теорема доказывается подстановкой в обе
части равенства (4.1) произвольного набора (
n1mm1
α
α
α
α
,...,,,...,
+
)
всех n переменных.
Левая часть (4.1) дает f(
α
1
,…,
α
n
).
Правая -
),...,(),...,,,...,(
),...,,...,(
,...,
n1n1mm1m1
n1mm1m1
ff
f
m
1
m
1
m1
αααααααα
ααδδαα
α
α
δ
δ
δδ
==
=∨
+
+
В качестве следствия получим два специальных случая
разложения.
Следствие 4.1.
Разложение по k-ой переменной
),...,,,,...,(),...,,,,...,(
),...,,,,...,(
n1k1k1kn1kk1k1k
n1kk1k1
xx0xxfxxx1xxfx
xxxxxf
+−+−
+−
∨=
=
Следствие 4.2.
Разложение по всем n переменным
).,...,(),...,(
,...,
n1n1n1
fxxxxf
n1
n1
δδ
δδ
δδ
∨= Но 0f
n1
=),...,(
δ
δ
либо .),,( 1f
n1
=
δ
δ
… Cледовательно, при 0xxf
n1
≡
/
),...,( оно
может быть преобразовано к виду
,),...,(
),...,(
,...,,...,
n
1
n1
n1
n
1
n1
n1
1f
n1n1
xxfxx
δδ
δδ
δδ
δδ
δδ
δδ
=
∨=∨ т.е.
n
1
n1
n1
n1
1f
n1
xxxxf
δ
δ
δδ
δδ
=
∨=
),...,(
,...,
),...,(
- СДНФ.
Страницы
- « первая
- ‹ предыдущая
- …
- 17
- 18
- 19
- 20
- 21
- …
- следующая ›
- последняя »
