ДНФ

Канонические формы логических формул

Любая логическая формула задает некоторую булеву функцию. Но для всякой булевой функции можно привести бесконечно много формул ее представляющих. Одной из задач алгебры логики является построение канонических форм(т.е формул построенных по определенному правилу).

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

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

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

Формула [math]f(\vec{x})[/math] от n переменных называется совершенно дизъюктивной нормальной формой(СДНФ), если она обладает следующими свойствами :

1. [math]f(\vec x)[/math] является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция n переменных [math]x_1[/math], x₂,...,x_n, причем на i-ом месте этой конъюнкции стоит i-ый терм.
2. Все элементарные конъюнкции в такой ДНФ попарно различны.

Теорема об СДНФ

Теорема : Для любой булевой функции [math]f(\vec{x})[/math], не равной тождественному нулю, существует СДНФ, ее задающая.

Док-во : Для любой булевой функции выполняется следующее соотношение

[math]f(\vec{x}) = \overline x_i \wedge f(x_1,..,x_{i-1},0,x_{i+1},..,x_n) \vee x_i \wedge f(x_1,..,x_{i-1},1,x_{i+1},x_n)[/math]

Данное соотношение легко проверить подстановкой всевозможных значений x_i(0 и 1). Эта формула позволяет выносить x_i за знак функции. Последовательно вынося x₁, x₂,.., x_n за знак [math]f(\vec{x})[/math], получаем следующую формулу : [math] f(\vec{x}) = \overline x_1 \wedge \overline x_2 \wedge ...\wedge \overline x_{n-1} \wedge \overline x_n \wedge f(0,0,...,0,0)~\vee~[/math]

[math]\overline x_1 \wedge \overline x_2 \wedge ... \wedge \overline x_{n-1} \wedge x_n \wedge f(0,0,...,0,1) ~\vee~[/math]

[math]... [/math]

[math]~\vee~ x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge \overline x_n \wedge f(1,1,...,1,0) ~\vee~[/math]

[math]x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge x_n \wedge f(1,1,...,1) [/math]

Т.к применение данного соотношения к каждой из переменных увеличивает количество дизъюнктивных членов в два раза, то для функции от n переменных мы имеем 2ⁿ дизъюнктивных членов. Каждый из них соответствует значению функции на одном из 2ⁿ возможных наборов значений n переменных. Если на некотором наборе [math]f(\vec{x})=0[/math], то весь соответствующий дизъюнктивный член также равен 0 и из представления данной функции его можно исключить. Если же [math] f(\vec{x})=1[/math], то в соответствующем дизъюннктивном члене само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.

Алгоритм построения СДНФ по таблице истинности

1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.
2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
3. Все полученные конъюнкции связываем операциями дизъюнкции.