КНФ

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

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

Пример КНФ: [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]

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

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

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

Стрелка Пирса: [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]

Ссылки

• Википедия — свободная энциклопедия
• Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика