Днф и сднф в чем разница

For Informatics

$A \or B$ $(A \and B) \or \neg A$ $(A \and B \and \neg C) \or (\neg D \and E \and F) \or (C \and D) \or B$

Приведем к ДНФ формулу : $F = ((X \rightarrow Y) \downarrow \neg (Y \rightarrow Z))$
Выразим логические операции → и ↓ через : $\vee \wedge \neg$

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

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

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

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

Совершенная дизъюнктивная нормальная форма

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

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

В ячейках результата $f(x_1, x_2, x_3)$ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы. Далее рассматриваются значения переменных при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.

$x_1 = 0$
$x_2 = 0$
$x_3 = 0$

Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так: $\overline<x_1>\cdot \overline <x_2>\cdot \overline<x_3>» /></p> <ul> <li><img decoding=$

$x_2 = 0$

$x_3 = 1$

$x_3$ в этом случае будет представлен без инверсии: $\overline<x_1>\cdot \overline <x_2>\cdot x_3″ /><br /> Таким образом анализируются все ячейки <img decoding=$ . Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).
$f(x_1, x_2, x_3) = (\overline<x_1>\and \overline <x_2>\and \overline<x_3>) \vee (\overline <x_1>\and \overline <x_2>\and x_3) \vee (\overline <x_1>\and x_2 \and \overline<x_3>) \vee (x_1 \and x_2 \and \overline<x_3>)» /></p> <h4>Переход от ДНФ к СДНФ</h4> <p><img decoding=$ ,
после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем, так как $Z \vee Z = Z$ по закону идемпотентности). Например:

Днф и сднф в чем разница

For Informatics

Совершенная дизъюнктивная нормальная форма

Добавить комментарий Отменить ответ