Как получить скнф из кнф

«Учебник по дискретной математике ДНФ, СДНФ, КНФ, СКНФ»

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций.

Например, выражение является ДНФ.

Например, выражение является ДНФ, но не СДНФ. Выражение является СДНФ.

Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ и СКНФ. Приведем точные формулировки.

Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание).Например, выражение – простая дизъюнкция,

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций (например выражение – КНФ).

Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одинаковом порядке.

Например, выражение является СКНФ.

Приведем алгоритмы переходов от одной формы к другой. Естественно, что в конкретных случаях (при определенном творческом подходе) применение алгоритмов бывает более трудоемким, чем простые преобразования, использующие конкретный вид данной формы:

а) переход от ДНФ к КНФ

Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:

Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;

б) переход от КНФ к ДНФ

Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)

Таким образом, получили ДНФ.

Обратный переход (от СДНФ к ДНФ) связан с проблемой минимизации ДНФ. Подробнее об этом будет рассказано в разд. 5, здесь же мы покажем, как упростить ДНФ (или СДНФ) по правилу Блейка. Такая ДНФ называется сокращенной ДНФ;

в) сокращение ДНФ (или СДНФ) по правилу Блейка

Применение этого правила состоит из двух частей:

— если среди дизъюнктных слагаемых в ДНФ имеются слагаемые , то ко всей дизъюнкции добавляем слагаемое К₁К₂. Проделываем эту операцию несколько раз (можно последовательно, можно одновременно) для всех возможных пар слагаемых, а затем, применяем обычное поглощение;

— если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например,

Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ , после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):

в) переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, z, вставляем в нее выражение ,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:

г) переход от КНФ к СКНФ

Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной (например, z, то добавляем в нее выражение (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):

Таким образом, из КНФ получена СКНФ.

Заметим, что минимальную или сокращенную КНФ обычно получают из соответствующей ДНФ.

Переход от КНФ к СКНФ

Author24 — интернет-сервис помощи студентам

Переход от КНФ к СКНФ
Добрый день! Пните в нужную сторону, как сделать переход от ДНФ к СДНФ: x\vee \bar\vee xy .

Переход от СКНФ к КНФ
Подскажите плс, как перейти от СКНФ к КНФ в данном случае: (x- v y v z-)*(x v y- v z) Я.

Приведение к КНФ и СКНФ
Привет! Подскажите, пожалуйста, в чем ошибка? Делал по аналогии с примером на Википедии Необходимо.

КНФ,СДНФ,СКНФ
1.Докажите,что формула(не х -> не y)<->(x->y) является тавтологией 2. Найти СДНФ и СКНФ формулы.

476 / 279 / 90
Регистрация: 15.11.2013
Сообщений: 530

1. То, что у вас написано, — ни разу не КНФ.

2. От КНФ к СКНФ можно перейти разными способами

а. Нарисовать по КНФ таблицу истинности и по ней написать СКНФ.

б. К каждому члену КНФ приписать слагаемое, состоящее из произведений всемозможных переменных, не входящих в этот член (все переменные — в прямом и инверсном вхождении), потом раскрыть скобки.

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Преобразование КНФ в СКНФ
Помогите решить. Преобразовать КНФ в СКНФ, построить диаграмму Вейча. \left(x \vee y \right).

КНФ, ДНФ, СДНФ, СКНФ
Всем привет! Задание такое: Определить КНФ, ДНФ, СДНФ, СКНФ для формулы логики высказываний.

ДНФ, СДНФ, КНФ, СКНФ
Всем привет! f = x1 -> x2x3 Надо перевести эту формулу в ДНФ, СДНФ, КНФ, СКНФ Помогите, кто.

Или воспользуйтесь поиском по форуму:

For Informatics

$\neg A \wedge (B \vee C)$ $(A \vee B) \wedge (\neg B \vee C \vee \neg D) \wedge (D \vee \neg E)$ $A \wedge B$

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

$A \rightarrow B = \neg A \vee B$ $A \leftrightarrow B = (\neg A \vee B) \wedge (A \vee \neg B)$

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

$\neg (A \vee B) = \neg A \wedge \neg B$ $\neg (A \wedge B) = \neg A \vee \neg B$

3) Избавиться от знаков двойного отрицания.

4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.

Пример построения КНФ

Приведем к КНФ формулу

$F = ( X \rightarrow Y ) \wedge (( \neg Y \rightarrow Z ) \rightarrow \neg X )$

Преобразуем формулу F к формуле не содержащей → :

$F = ( \neg X \vee Y ) \wedge ( \neg ( \neg Y \rightarrow Z ) \vee \neg X ) = ( \neg X \vee Y ) \wedge ( \neg ( \neg \neg Y \vee Z ) \vee \neg X )$

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

$F = ( \neg X \vee Y) \wedge ((\neg Y \wedge \neg Z) \vee \neg X)$

По закону дистрибутивности получим КНФ:

$F = (\neg X \vee Y) \wedge (\neg X \vee \neg Y) \wedge (\neg X \vee \neg Z)$

СКНФ

Соверше́нная конъюнкти́вная норма́льная фо́рма (СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных дизъюнкций
в каждой дизъюнкции нет одинаковых пропозициональных переменных
каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности. Возьмем таблицу истинности для 4 четырех переменных:

$x_1$	$x_2$	$x_3$	$x_4$	$f(x_1, x_2, x_3, x_4)$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

$f(x_1, x_2, x_3, x_4)$

В ячейках строки́ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля.

Четвёртая строка содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:

$x_1 = 0$
$x_2 = 0$
$x_3 = 1$
$x_4 = 1$

$x_1 \vee x_2 \vee \overline<x_3> В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так: \vee \overline» /> <h2>Получить СДНФ, СКНФ из ДНФ и КНФ. Помогите с решением</h2> Исходная формула: (x→(y∧¬z))→(x≡z) ДНФ (X ∧ ¬ Y) ∨ (X ∧ Z) ∨ (¬X ∧ ¬Z) КНФ (X ∨ ¬Z) ∧ ( ¬ Y ∨ Z ∧ ¬X) Нужно построить аналитически СДНФ и СКНФ из ДНФ и КНФ. Лучший ответ Так элементарно же всё. Например, что этому конъюнкту (X ∧ ¬ Y) не хватает до совершенства? В нем нет переменной Z. Так добавьте ее туда, не изменяя значение самого конъюнкта. Для этого нужно домножить X ∧ ¬ Y на единицу, которую выразить через Z. X ∧ ¬ Y∧(Z + ¬Z) = (X∧¬ Y∧Z) + (X ∧¬ Y∧¬Z) В результате один несовершенный конъюнкт породил два совершенных. И так далее. Для построения СКНФ идея аналогичная. К сумме X ∨ ¬Z нужно добавить 0, который выражаем как произведение переменной Y и ¬Y. rasslaBONESПрофи (638) 3 года назад rasslaBONESПрофи (638) 3 года назад То есть нужно к каждой скобке добавить недостающую переменную? Некий Загадочный Просветленный (43027) Каждая скобка без переменной породит две скобки, где будет переменная и ее отрицание. <div class='yarpp yarpp-related yarpp-related-website yarpp-template-list'>  <div>Похожие публикации:</div><ol> <li><a href=$ Winload exe как восстановить

Xsplit gamecaster что это

Как переименовать проект в intellij idea

Как перемешать символы в строке python