7.1. Разложение Шеннона

Рассмотрим следующее разложение булевой функции f(x₁, …, x_n) по переменной x_i.

Разложение Шеннона. f(x₁, …, x_n) = x_i f(x₁, …, x_i-1,1,x_i+1, …, x_n) x _i f(x₁, …, x_i-1,0,x_i+1, …, x_n).

Доказательство (не умаляя общности, для i=1). При x₁=0 имеем:

f(0,x₂, …, x_n)=0f(1,x₂, …, x_n) 0 f(0,x₂, …, x_n)=f(0,x₂, …, x_n).

При x₁=1 имеем:

f(1,x₂, …, x_n)=1f(1,x₂, …, x_n) 1 f(0,x₂, …, x_n)=f(1,x₂, …, x_n).

Следовательно, разложение верно. •

Определение. Сомножитель f(x₁, …, x_i-1,1,x_i+1, …, x_n) называется коэффициентом разложения функции f(x₁, …, x_n) по переменной x_i при x_i, а сомножитель f(x₁, …, x_i-1,0,x_i+1, …, x_n) – коэффициентом разложения функции f(x₁, …, x_n) по переменной x_i при x _i.

Пример. Булеву функцию f(x,y,z)= y xz yz разложим по переменной x:

y xz yz=x (y 1z yz) x (y 0z yz)=

[ упростим коэффициенты разложения на основе свойств 0 и 1 для конъюнкции ]

=x (y z yz) x (y 0 yz)=

[ продолжим упрощение коэффициента при x на основе свойства 0 для эквивалентности a 0 = a при a=y ; напомним, что способ получения таких свойств был рассмотрен в подразделе 4.4 ]

=x (y z yz) x (y yz),

в результате имеем следующие коффициенты разложения, зависящие лишь от y и z:

y z yz – коэффициент разложения функции f(x,y,z) по переменной x при x,

y yz – коэффициент разложения функции f(x,y,z) по переменной x при x . •