СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице

ДНФ

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

Простая конъюнкция

  • полная, если в неё каждая переменная {или её отрицание} входит ровно 1 раз;
  • монотонная, если она не содержит отрицаний переменных.

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

Пример ДНФ: $f(x,y,z) = (x \land y) \lor (y \land \neg {z})$

СДНФ

СДНФ {Совершенная Дизъюнктивная Нормальная Форма} — это такая ДНФ, которая удовлетворяет условиям:

  • в ней нет одинаковых простых конъюнкций
  • каждая простая конъюнкция полная

Пример СДНФ: $f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})$

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

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

Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона.

$f(\vec{x}) = \neg x_i \wedge f(x_1, \dots ,x_{i-1},0,x_{i+1}, \dots ,x_n) \vee x_i \wedge f(x_1, \dots ,x_{i-1},1,x_{i+1}, \dots ,x_n)$

Данное соотношение легко проверить подстановкой всевозможных значений $x_i$ {$0$ и $1$}. Эта формула позволяет выносить $x_i$ за знак функции. Последовательно вынося $x_1$, $x_2$,.., $x_n$ за знак $f(\vec{x})$, получаем следующую формулу :

$ f(\vec{x}) = \neg x_1 \wedge \neg x_2 \wedge ...\wedge \neg x_{n-1} \wedge \neg x_n \wedge f(0,0,...,0,0)~\vee~$

$\neg x_1 \wedge \neg x_2 \wedge ... \wedge \neg x_{n-1} \wedge x_n \wedge f(0,0,...,0,1) ~\vee~ $ $\dots $ $~\vee~ x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge \neg x_n \wedge f(1,1,...,1,0) ~\vee~ $ $x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge x_n \wedge f(1,1,...,1) $

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

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

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

Пример построения СДНФ для медианы

  1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.

    x y z $\langle x,y,z \rangle$
    0 0 0 0
    0 0 1 0
    0 1 1 0
    0 1 1 1
    1 0 0 0
    1 0 1 1
    1 1 0 1
    1 1 1 1
  2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
    x y z $ \langle x,y,z \rangle $
    0 0 0 0
    0 0 1 0
    0 1 0 0
    0 1 1 1 $(\neg {x} \land y \land z)$
    1 0 0 0
    1 0 1 1 $(x \land \neg {y} \land z)$
    1 1 0 1 $(x \land y \land \neg {z})$
    1 1 1 1 $(x \land y \land z)$
  3. Все полученные конъюнкции связываем операциями дизъюнкции. $ \langle x,y,z \rangle = (x \land y \land z) \lor (\neg {x} \land y \land z) \lor (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})$

Примеры СДНФ для некоторых функций

Стрелка Пирса: $x \downarrow y = (\neg {x} \land \neg {y})$

Исключающее или: $x \oplus y \oplus z = (\overline{x} \land \overline{y} \land z) \lor (\overline{x} \land y \land \overline{z}) \lor (x \land \overline{y} \land \overline{z}) \lor (x \land y \land z)$

Совершенной дизъюнктивной нормальной формой формулы $A(x_1,x_2,…,x_n)$ называется ДНФ, обладающая следующими свойствами:

а} в ней нет одинаковых дизъюнктивных элементов;

б} ни одна элементарная конъюнкция не содержит двух одинаковых высказываний;

в} ни какая элементарная конъюнкция не содержит высказывание вместе с ее отрицанием;

г} в каждой элементарной конъюнкции содержится либо $X_i$, либо $\overline {X}_i$, где $i = 1, n$.

Условие а} – г} являются необходимыми и достаточными для того, чтобы ДНФ стала СДНФ. В свою очередь эти условия дают возможность составить алгоритм получения СДНФ из ДНФ:

1) если какая-нибудь элементарная конъюнкция не содержит высказывание $X_i$, то заменим выражением $B\wedge (X_i\vee \overline{X}_i) \equiv (B\wedge X_i)\vee (B\wedge \overline{X}_i)$;

2) если в полученном выражении окажутся одинаковые элементарные конъюнкции, то лишние опускаются;

3) если в некоторых элементарных конъюнкциях окажутся одинаковые высказывания, то лишние опускаются;

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

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Формула называется дизъюнктивной нормальной формой {ДНФ}, если она является дизъюнкцией неповторяющихся элементарных конъюнкций. ДНФ записываются в виде: $A_1\vee A_2\vee ...\vee A_n$ , где каждое $A_n$ — элементарная конъюнкция.

Формула $A$ от $k$ переменных называется совершенной дизъюнктивной нормальной формой {СДНФ}, если:

  1. $A$ является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция $k$ переменных $x_1,x_2,…,x_k$, причем на $i$-м месте этой конъюнкции стоит либо переменная $x_i$ либо ее отрицание;

  2. Все элементарные конъюнкции в такой ДНФ попарно различны.

Например: $A = x_1 \wedge$ НЕ $x_2 \vee x_1 \wedge x_2$

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

Она является примером однозначного представления булевой функции в виде формульной {алгебраической} записи.

Теорема о СДНФ: Пусть $f(x_1 x_2, …, x_n)$ – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию $f$.

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

  • В таблице истинности отмечаем наборы переменных, на которых значение функции $f = 1$.
  • Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание.
  • Все полученные конъюнкции связываем операциями дизъюнкции.