КНФ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (переименовал СКНФ в КНФ)
Строка 15: Строка 15:
 
Пример КНФ:
 
Пример КНФ:
 
<tex>f(x,y) = (x \lor y) \land (y \lor \overline{z})</tex>
 
<tex>f(x,y) = (x \lor y) \land (y \lor \overline{z})</tex>
 
КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу: <tex>a (b\lor c)\to a b\lor a c</tex>, которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило <tex>a\lor b c\to (a \lor b)(a \lor c)</tex>, выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.
 
 
Например КНФ <tex>\to</tex> ДНФ: <tex>(x \lor y) \land (y \lor \overline{z}) = (x \land y) \lor y \lor (x \land \overline{z}) \lor (y \land \overline{z}) = y \land (x \lor 1 \lor \overline{z}) \lor (x \land \overline{z}) = (x \land \overline{z}) \lor y</tex>
 
 
Например ДНФ <tex>\to</tex> КНФ: <tex> (x \land \overline{z}) \lor y = (x \lor y) \land (y \lor \overline{z}) </tex>
 
  
 
== СКНФ ==  
 
== СКНФ ==  

Версия 06:06, 21 декабря 2011

КНФ

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

Элементарная дизъюнкция

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


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

Пример КНФ: [math]f(x,y) = (x \lor y) \land (y \lor \overline{z})[/math]

СКНФ

Определение:
СКНФ (Совершенная Конъюнктивная Нормальная Форма) — это такая КНФ, которая удовлетворяет условиям:
  • в ней нет одинаковых элементарных дизъюнкций
  • в каждой дизъюнкции нет одинаковых переменных
  • каждая элементарная дизъюнкция содержит каждый из аргументов функции.

Пример СКНФ: [math]f(x,y,z) = (x \lor \overline{y} \lor z) \land (x\lor y \lor \overline{z})[/math]


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

Поскольку инверсия функции [math]\overline{f}(\vec x)[/math] равна единице на тех наборах, на которых [math]f(\vec x)[/math] равна нулю, то СДНФ для [math]\overline{f}(\vec x)[/math] можно записать следующим образом: [math] \overline{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}}) [/math], где [math] \sigma_{i} [/math] обозначает наличие или отсутствие отрицание при [math] x_{i} [/math]

Найдём инверсию левой и правой части выражения: [math] f(\vec x) = \overline{\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}})} [/math]

Применяя дважды к полученному в правой части выражению правило де Моргана, получаем: [math] f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (x_{1}^{\overline{\sigma_{1}}} \vee x_{2}^{\overline{\sigma_{2}}} \vee ... \vee x_{n}^{\overline{\sigma_{n}}}) [/math]

Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, то теорема доказана.
[math]\triangleleft[/math]

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

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

Пример построения СКНФ

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

x y z [math]med(x,y,z)[/math]
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

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

x y z [math]med(x,y,z)[/math]
0 0 0 0 [math]( x \lor y \lor z)[/math]
0 0 1 0 [math]( x \lor y \lor \overline{z})[/math]
0 1 0 0 [math](x \lor \overline{y} \lor z)[/math]
0 1 1 1
1 0 0 0 [math](\overline{x} \lor y \lor z)[/math]
1 0 1 1
1 1 0 1
1 1 1 1

3. Все полученные дизъюнкции связываем операциями конъюнкции.

[math]med(x,y,z) = ( x \lor y \lor z) \land (\overline{x} \lor y \lor z) \land (x \lor \overline{y} \lor z) \land ( x \lor y \lor \overline{z})[/math]

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

Стрелка Пирса: [math] x \downarrow y = (\overline{x} \lor y) \land (x \lor \overline{y}) \land (\overline{x} \lor \overline{y})[/math]

Исключающее или: [math] 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)[/math]

Ссылки