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

Практически 100%-ая копия полюбившегося многим инстаграм, идеально подойдет для портфолио, презентации работ своим клиентам или как отклик на понравившуюся вакансию. Молодой ресурс, но администраторы оперативно реагируют на предложения и вопросы.

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

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

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

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

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

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

Упрощение логических функций

Замыкание. Свойства замыкания. Теорема о сведении к заведомо полной системе

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

Теорема Остроградского

Решение задач с помощью алгебры высказываний

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

Замена переменных в тройном интеграле

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

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

Примеры применения цилиндрических и сферических координат

📎📎📎📎📎📎📎📎📎📎