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

КНФ

Простой дизъюнкцией { англ. 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)$

Далее:

Механические приложения криволинейного интеграла 1-го рода

Формулы. Равенство функций и эквивалентность формул. Основные эквивалентности

Поверхностный интеграл второго рода и его свойства

Вычисление двойного интеграла. Двукратный интеграл

Равносильные формулы алгебры высказываний

Класс $L$. Теорема о замкнyтости класса $L$

Замена переменных в двойном интеграле. Двойной интеграл в полярных координатах

Вычисление двойного интеграла

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

Частные случаи векторных полей

Механические приложения двойного интеграла

Выражение площади плоской области через криволинейный интеграл

Односторонние и двусторонние поверхности. Ориентация поверхности

Свойства криволинейного интеграла второго рода

Механические и физические приложения поверхностного интеграла первого рода

Огравление $\Rightarrow $