ДНФ

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

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

Определение:

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

Определение:

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

Определение:

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

Определение:

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

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

Теорема:

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

Доказательство:

[math]\triangleright[/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] Данное соотношение легко проверить подстановкой всевозможных значений [math]x_i[/math](0 и 1). Эта формула позволяет выносить [math]x_i[/math] за знак функции. Последовательно вынося [math]x_1[/math], [math]x_2[/math],.., [math]x_n[/math] за знак [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] Т.к применение данного соотношения к каждой из переменных увеличивает количество дизъюнктивных членов в два раза, то для функции от [math]n[/math] переменных мы имеем [math]2^n[/math] дизъюнктивных членов. Каждый из них соответствует значению функции на одном из [math]2^n[/math] возможных наборов значений n переменных. Если на некотором наборе [math]f(\vec{x})=0[/math], то весь соответствующий дизъюнктивный член также равен 0 и из представления данной функции его можно исключить. Если же [math] f(\vec{x})=1[/math], то в соответствующем дизъюннктивном члене само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.

[math]\triangleleft[/math]

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

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