Разложение функции по переменным

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

м x, если s=0

xs = н

о x, если s=1.

Теорема 2 (Разложение в дизъюнкцию). Любую функцию f(x1,...,xm) для любого n (1 Ј n Ј m) можно представить в виде

f(x1,...,xm) = x1s1 &... & xnsn & f(s1,...,sn,xn+1,...,xm)

Доказательство. Покажем, что для любого набора значений переменных (x1,...,xn,xn+1,...,xm) значения левой и правой частей совпадают. Возьмём фиксированный набор (x1,...,xn,xn+1,...,xm). Рассмотрим выражение x1s1 &... & xnsn. Если одно из значений xisi равно 0, то и всё выражение равно 0. Тогда и выражение x1s1 &... & xnsn & f(s1,...,sn,xn+1,...,xm) равно 0. Единице же выражение x1s1 &... & xnsn равно только в том случае, если s1 = x1,..., sn = xn. При этом f(s1,...,sn,xn+1,...,xm) = f(x1,...,xn,xn+1,...,xm) Таким образом, значение правой части всегда равно равно f(x1,...,xm), то есть значению левой части.

Теорема 3 (Разложение в конъюнкцию). Любую функцию f(x1,...,xm) для любого n (1 Ј n Ј m) можно представить в виде

f(x1,...,xm) = x1s1 Ъ... Ъ xnsn Ъ f(s1...,sn,xn+1,...,xm)

Разложения по всем переменным дают суперпозицию конъюнкции, дизъюнкции и отрицания.

Следствие 1 (Совершенная дизъюнктивная нормальная форма).

Любая функция f может быть представлена в следующей форме:*

f(^x1,...,x_m) = ^x1^s1 &... & x_ms_m & f(^s1,...,s_m) = *

= ^x1^s1 &... & x_ms_m

Следствие 2 (Совершенная конъюнктивная нормальная форма).

Любая функция f может быть представлена в следующей форме:*

f(^x1,...,^xm) = ^x1^s1 Ъ... Ъ ^xm^sm

Таким образом, любая булева функция может быть представлена суперпозицией конъюнкции, дизъюнкции и отрицания. Разложение по всем переменным в дизъюнкцию называется совершенной дизъюнктивной нормальной формой функции, а в конъюнкцию – совершенной конъюнктивной нормальной формой.*

Совершенная дизъюнктивная и конъюнктивная нормальная формы дают способ представления булевой функции через суперпозицию конъюнкции, дизъюнкции и отрицания если у нас есть таблица значений функции.

Чтобы получить совершенную дизъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 1 и записать для каждого из них конъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 – то переменную надо взять с отрицанием, если 1 – без отрицания. Из получившихся конъюнкций надо построить дизъюнкцию.

Чтобы получить совершенную конъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 0 и записать для каждого из них дизъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 – то переменную надо взять без отрицания, если 1 – с отрицанием. Из получившихся дизъюнкций надо построить конъюнкцию.