КНФ, ДНФ, СДНФ, СКНФ

[stx]

Добрый день!

Задание такое:
Определить КНФ, ДНФ, СДНФ, СКНФ для формулы логики высказываний: $\[F = \overline {(Y \supset Z)} \sim \overline {(Z \supset X)} \]$

Записываю формулу в таком виде $\[F = \neg (Y \supset Z) \sim \neg (Z \supset X)\]$
Начинаю с КНФ.
$\[F \equiv \neg (\neg Y \vee Z) \sim \neg (\neg Z \vee X) \equiv \]$
$\[ \equiv (\neg (Y \supset Z) \supset \neg (Z \supset X))\& (\neg (Z \supset X) \supset \neg (Y \supset Z)) \equiv \]$
$\[ \equiv (\neg (Y \supset Z)\& \neg (Z \supset X)) \vee ((Z \supset X)\& (Y \supset Z)) \equiv \]$
$\[ \equiv ((Y\& \neg Z)\& (Z\& \neg X)) \vee (\neg (Z\& \neg X)\& \neg (Y\& \neg Z)\]$
Что делать дальше не понимаю. Попытки решить приводят к монструозному виду

[Sonic86]

0) Предлагаю Вам писать вместо $\&$ умножение, либо его совсем не писать, а отрицание элементарных переменных $\neg D$ писать как $\bar{D}$, кроме того, конъюнкция ассоциативна - скобочки можно не писать. Если все это сделать, то формула будет более обозреваемой. Хотя дело Ваше.
1) Последнюю формулу легко упростить - посмотрите на нее внимательно.
2) КНФ приводится к СКНФ добавлением отсутствущих переменных в виде $W\vee \bar{W}$. Можно также СКНФ получить по таблице истинности, как с СДНФ. КНФ и ДНФ двойственны друг другу - можете всем этим невозбранно пользоваться.

[stx]

Отрицание записываю как $\[\neg Z\]$, а не $\[\overline Z \]$, т.к. проще смотреть по формулам в учебнике именно в таком виде.

Попробую по шагам.

$\[\ ((Y\& \neg Z)\& (Z\& \neg X)) \vee (\neg (Z\& \neg X)\& \neg (Y\& \neg Z) \equiv$
$\[ \equiv (Y\& \neg Z\& Z\& \neg X) \vee \neg ((Z\& \neg X) \vee (Y\& \neg Z))\]$

Как еще упростить не понимаю.

[Sonic86]

Как Вы думаете, чему равно $Z\vee \neg Z$?
Кстати, я преобразования не проверил. Можете проверить себя составлением таблицы истинности исходной и конечной формулы.

[stx]

Sonic86 в сообщении #792465 писал(а):

Как Вы думаете, чему равно $Z\vee \neg Z$?
Кстати, я преобразования не проверил. Можете проверить себя составлением таблицы истинности исходной и конечной формулы.

$\[Z \vee \neg Z = Z\]$

Полагаю, что начал немного не с того.
По свойству эквивалентности отрицание можно было снять в самом начале.

$\[F = \overline {(Y \supset Z)} \sim \overline {(Z \supset X)} \equiv (Y \supset Z) \sim (Z \supset X) \equiv \]$
$\[ \equiv ((Y \supset Z)\& (Z \supset X)) \vee (\neg (Y \supset Z)\& \neg (Z \supset X)) \equiv \]$
$\[ \equiv (Y\& Z) \vee (\neg Z\& \neg X) \vee (\neg \neg (Y\& \neg Z)\& \neg \neg (Z\& \neg X)) \equiv \]$
$\[ \equiv (Y\& Z) \vee (\neg Z\& \neg X) \vee (Y\& \neg Z\& Z\& \neg X) \equiv \]$
$\[ \equiv (Y\& Z) \vee (\neg Z\& \neg X) \vee (Y\& Z\& \neg X)\]$

Что ещё можно сделать?

[arseniiv]

stx в сообщении #792473 писал(а):

$\[Z \vee \neg Z = Z\]$

Проверьте это таблицей истинности!

-- Пн ноя 25, 2013 19:16:04 --

Хотя это меньше даст, чем следующее размышление: замените мысленно $Z$ на $\neg Z$. Получится $\neg Z \vee \neg\neg Z = \neg Z$, т. е. $\neg Z \vee Z = Z \vee \neg Z = \neg Z$. Получается, что $Z = \neg Z$ — а такого не бывает. Значит, $Z \vee \neg Z \ne Z$.

-- Пн ноя 25, 2013 19:18:52 --

…и так же не равно $\neg Z$. Т. к. значение этой формулы больше от значений никаких переменных не зависит, остаются два варианта — тождественная истинность или тождественная ложность. И один из них, основываясь на свойствах дизъюнкции, выбрать можно. (Хотя его и так должно было быть видно сразу.)

[stx]

Ошибся.
По таблицам для дизъюнкции $\[Z \vee \neg Z = 1\]$, а для конъюнкции $\[Z \vee \neg Z = 0\]$

Так понимаю, что единицу можно не писать? Т.е. следующее выражение должно выглядеть так:
$\[ (Y\& Z) \vee (\neg Z\& \neg X) \vee (Y\& \neg Z\& Z\& \neg X) \equiv \]$
$\[ \equiv (Y\& Z) \vee (\neg Z\& \neg X) \vee (Y\& \neg X)\]$

Или в другом виде записи:
$\[(Y \wedge Z) \vee (\neg Z \wedge \neg X) \vee (Y \wedge \neg X)\]$

Дальше упрощается или можно считать, что КНФ получилось?

[Sonic86]

stx в сообщении #792610 писал(а):

Так понимаю, что единицу можно не писать?

С чего вдруг? Надо писать. Просто потом другими преобразованиями она исключается. Найдите $1\vee W, 1\wedge W, 0\vee W, 0\wedge W$.

stx в сообщении #792610 писал(а):

а для конъюнкции $\[Z \vee \neg Z = 0\]$

$Z\wedge \neg Z = 0$.

stx в сообщении #792610 писал(а):

$\[ (Y\& Z) \vee (\neg Z\& \neg X) \vee (Y\& \neg Z\& Z\& \neg X) \equiv \]$
$\[ \equiv (Y\& Z) \vee (\neg Z\& \neg X) \vee (Y\& \neg X)\]$

Вот как раз преобразовали неправильно последнюю скобку, сделайте по шагам.

stx в сообщении #792610 писал(а):

Или в другом виде записи:
$\[(Y \wedge Z) \vee (\neg Z \wedge \neg X) \vee (Y \wedge \neg X)\]$

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

[stx]

Sonic86 в сообщении #792750 писал(а):

stx в сообщении #792610 писал(а):

$\[ (Y\& Z) \vee (\neg Z\& \neg X) \vee (Y\& \neg Z\& Z\& \neg X) \equiv \]$
$\[ \equiv (Y\& Z) \vee (\neg Z\& \neg X) \vee (Y\& \neg X)\]$

Вот как раз преобразовали неправильно последнюю скобку, сделайте по шагам.

stx в сообщении #792610 писал(а):

Или в другом виде записи:
$\[(Y \wedge Z) \vee (\neg Z \wedge \neg X) \vee (Y \wedge \neg X)\]$

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

Воспользуюсь свойством: $\[A \& 1 \equiv A\]$

Преобразую скобку так:
$\[(Y\& \neg Z\& Z\& \neg X) \equiv (Y\& 1\& \neg X) \equiv (Y\& \neg X)\]$
Или в таком виде: $\[(Y \wedge \neg X)\]$

Пробую получить КНФ по шагам.
$\[(Y\& Z) \vee (\neg Z\& \neg X) \vee (Y\& \neg X) \equiv Y\& (Z \vee \neg X) \vee (\neg Z\& \neg X)\]$

Что делать дальше не понимаю.

[Sonic86]

stx в сообщении #792831 писал(а):

Преобразую скобку так:
$(Y\& \neg Z\& Z\& \neg X) \equiv (Y\& 1\& \neg X)$

Еще раз, обращая Ваше внимание:

Sonic86 в сообщении #792750 писал(а):

$Z\wedge \neg Z = 0$.

Ну или $\neg Z\& Z = 0$.

stx в сообщении #792831 писал(а):

Пробую получить КНФ по шагам.
$\[(Y\& Z) \vee (\neg Z\& \neg X) \vee (Y\& \neg X) \equiv Y\& (Z \vee \neg X) \vee (\neg Z\& \neg X)\]$

Да, 1-й шаг правильно, можете продолжать, пока все внешние дизъюнкции не исчезнут (у Вас она одна осталась). Только для преобразования необязательно искать совпадающий литерал в 2-х скобках (если Вы так делали) - можно в лоб делать: $P\vee (Q\& R)=(P\vee Q)\& (P\vee R)$ - $\vee$ исчезает, остается $\&$.

А начинать с СКНФ, СДНФ Вас не прикалывает никак, да?