КНФ
| Определение: |
| Простой дизъюнкцией (англ. inclusive disjunction) или дизъюнктом (англ. disjunct) называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза. |
Простая дизъюнкция
- полная, если в неё каждая переменная (или её отрицание) входит ровно один раз;
- монотонная, если она не содержит отрицаний переменных.
| Определение: |
| Конъюнктивная нормальная форма, КНФ (англ. conjunctive normal form, CNF) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов. |
Пример КНФ:
[math]f(x,y,z) = (x \lor y) \land (y \lor \neg{z})[/math]
СКНФ
| Определение: |
Совершенная конъюнктивная нормальная форма, СКНФ (англ. perfect conjunctive normal form, PCNF) — это такая КНФ, которая удовлетворяет условиям:
- в ней нет одинаковых простых дизъюнкций
- каждая простая дизъюнкция полная
|
Пример СКНФ:
[math]f(x,y,z) = (x \lor \neg{y} \lor z) \land (x\lor y \lor \neg{z})[/math]
| Теорема: |
Для любой булевой функции [math]f(\vec{x})[/math], не равной тождественной единице, существует СКНФ, ее задающая. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Поскольку инверсия функции [math]\neg{f}(\vec x)[/math] равна единице на тех наборах, на которых [math]f(\vec x)[/math] равна нулю, то СДНФ для [math]\neg{f}(\vec x)[/math] можно записать следующим образом:
[math]\neg{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}}) [/math], где [math] \sigma_{i} [/math] обозначает наличие или отсутствие отрицание при [math] x_{i} [/math]
Найдём инверсию левой и правой части выражения:
[math] f(\vec x) = \neg ({\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}})}) [/math]
Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
[math] f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (\neg{x_{1}^{\sigma_{1}}} \vee \neg{x_{2}^{\sigma_{2}}} \vee \ldots \vee \neg{x_{n}^{\sigma_{n}}} ) [/math]
Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, не равной тождественному нулю, то теорема доказана. |
| [math]\triangleleft[/math] |
Алгоритм построения СКНФ по таблице истинности
- В таблице истинности отмечаем те наборы переменных, на которых значение функции равно [math]0[/math].
- Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть [math]0[/math], то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
- Все полученные дизъюнкции связываем операциями конъюнкции.
Пример построения СКНФ для медианы
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно [math]0[/math].
| x |
y |
z |
[math] \langle x,y,z \rangle [/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. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть [math]0[/math], то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
| x |
y |
z |
[math] \langle x,y,z \rangle [/math] |
|
| 0 |
0 |
0 |
0 |
[math]( x \lor y \lor z)[/math]
|
| 0 |
0 |
1 |
0 |
[math]( x \lor y \lor \neg{z})[/math]
|
| 0 |
1 |
0 |
0 |
[math](x \lor \neg{y} \lor z)[/math]
|
| 0 |
1 |
1 |
1 |
|
| 1 |
0 |
0 |
0 |
[math](\neg{x} \lor y \lor z)[/math]
|
| 1 |
0 |
1 |
1 |
|
| 1 |
1 |
0 |
1 |
|
| 1 |
1 |
1 |
1 |
|
3. Все полученные дизъюнкции связываем операциями конъюнкции.
[math] \langle x,y,z \rangle = ( x \lor y \lor z) \land (\neg{x} \lor y \lor z) \land (x \lor \neg{y} \lor z) \land ( x \lor y \lor \neg{z})[/math]
Примеры СКНФ для некоторых функций
Стрелка Пирса: [math] x \downarrow y = (\neg{x} \lor {y}) \land ({x} \lor \neg {y}) \land (\neg {x} \lor \neg {y}) [/math]
Исключающее или: [math] x \oplus y \oplus z = (\neg {x} \lor \neg {y} \lor z) \land (\neg {x} \lor y \lor \neg {z}) \land (x \lor \neg {y} \lor \neg {z}) \land (x \lor y \lor z)[/math]
Медиана 5 аргументов:
[math] \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land \\ (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor \overline{x_2} \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor \overline{x_2} \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor \overline{x_5}) [/math]
См. также
Источники информации
