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

КНФ

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

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

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

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

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

СКНФ

Совершенная конъюнктивная нормальная форма, СКНФ {англ. perfect conjunctive normal form, PCNF} — это такая КНФ, которая удовлетворяет условиям:

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

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

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

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

$\neg{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}}) $, где $ \sigma_{i} $ обозначает наличие или отсутствие отрицание при $ x_{i} $

Найдём инверсию левой и правой части выражения:

$ f(\vec x) = \neg ({\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}})}) $

Применяя дважды к полученному в правой части выражению правило де Моргана, получаем: $ f(\vec x) = \bigwedge \limits_{f(x^{\sigma_1}, x^{\sigma_2}, \dots ,x^{\sigma_n}) = 0}$ $(\neg{x_1^{\sigma_1}} \vee \neg{x_2^{\sigma_2}} \vee \dots \vee \neg{x_n^{\sigma_n}}) $

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

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

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

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

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

x y z $ \langle x,y,z \rangle $
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 $ \langle x,y,z \rangle $
0 0 0 0 $( x \lor y \lor z)$
0 0 1 0 $( x \lor y \lor \neg{z})$
0 1 0 0 $(x \lor \neg{y} \lor z)$
0 1 1 1
1 0 0 0 $(\neg{x} \lor y \lor z)$
1 0 1 1
1 1 0 1
1 1 1 1

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

$ \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})$

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

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

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