| Определение: |
| КНФ (Конъюнктивная Нормальная Форма) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких дизъюнктов. |
Пример КНФ:
[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(\sigma_{1}, \sigma_{2}, ... ,\sigma_{n}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}}) [/math]
Найдём инверсию левой и правой части выражения:
[math] f(\vec x) = \overline{\bigvee\limits_{f(\sigma_{1}, \sigma_{2}, ... ,\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(\sigma_{1}, \sigma_{2}, ... ,\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] |
Алгоритм построения СКНФ по таблице истинности
- В таблице отмечаем наборы переменных, которые приводят логическое выражение в состояние нуля.
- В дизъюнкцию записываем переменную без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.
- Полученные дизъюнкции связываем операциями конъюнкции
Примеры СКНФ для некоторых функций
Стрелка Пирса: [math] x \downarrow y = (\overline{x} \lor y) \land (x \lor \overline{y}) \land (\overline{x} \lor \overline{y})[/math]
Медиана трёх: [math]f(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]
