Найти СДНФ путем логических преобразований

[mike007]

$(Y \vee Z) \wedge ((X \vee$ Y) \leftrightarrow Z)$
Из собственных наработок:
СДНФ по таблице: $(X \wedge Y \wedge Z) \vee (X \wedge \bar{Y} \wedge Z) \vee (\bar{X} \wedge Y \wedge Z)$
После стандартных преобразований остаётся $(Y \vee Z) \wedge ((\bar{X} \wedge \bar{Y}) \vee Z) \wedge (\bar{Z} \vee X \vee Y)$. Получить СКНФ отсюда дело плёвое, никак не возьму в толк как найти СДНФ.
Спасибо, пожалуйста!

[Профессор Снэйп]

Пользуясь тождеством $A \wedge (B \vee C) \equiv (A \wedge B) \vee (A \wedge C)$, последовательно раскрывайте скобки. Когда все скобки раскроете (ох, муторное это дело!), получите ДНФ. А уж от неё до СДНФ рукой подать. Пользуясь тождеством $A \equiv (A \wedge B) \vee (A \wedge \overline{B})$, последовательно вводите в каждый дизъюнктивный член недостающие переменные. Количество дизъюнктивных членов от такого действия, скорее всего, немеренно размножится. Затем сокращайте одинаковые и получайте ответ.

[mike007]

Здравствуйте. Извините, что так долго не отвечал, все мысли о дипломе.
Следуя вашим рекомендациям, после раскрытия:
$((Y \vee Z) \wedge (\bar{X} \vee \bar{Y}))$ [← пока трогать не будем] $\vee ((Y \vee Z) \wedge Z) \wedge (\bar{Z} \vee X \vee Y)$ $\equiv ((Y \vee Z) \wedge (\bar{X} \vee \bar{Y})) \vee (X \wedge Y \wedge Z) \vee (X \wedge \bar{Y} \wedge Z) \vee (\bar{X} \wedge Y \wedge Z)$.
Т.е. искомые члены получены, но что делать с брошенным выражением — не понятно.
Используя закон дистрибутивности получим:
$ (\bar{X} \wedge \bar{Y} \wedge Y) \vee (\bar{X} \wedge \bar{Y} \wedge Z)$
В первом случае скобка обратится в 0 по свойству, но вторая ненужная $(\bar{X} \wedge \bar{Y} \wedge Z)$ так и остаётся. По таблице проверил несколько раз, не должно её быть.
Где ошибаюсь? Спасибо.

[mike007]

На всякий случай напишу полный вариант после раскрытия:
$((Y \vee Z) \wedge (\bar{X} \vee \bar{Y})) \vee ((Y \vee Z) \wedge Z) \wedge (\bar{Z} \vee X \vee Y) \equiv$ $((Y \vee Z) \wedge (\bar{X} \vee \bar{Y})) \vee (Z \wedge Y) \vee (Z \wedge Z) \wedge (\bar{Z} \vee X \vee Y) \equiv$ $((Y \vee Z) \wedge (\bar{X} \vee \bar{Y})) \vee (Z \wedge Y) \vee Z \wedge (\bar{Z} \vee X \vee Y) \equiv$$((Y \vee Z) \wedge (\bar{X} \vee \bar{Y})) \vee (Z \wedge Y) \vee (Z \wedge \bar{Z}) \vee (Z \wedge X) \vee (Z \wedge Y) \equiv $$((Y \vee Z) \wedge (\bar{X} \vee \bar{Y})) \vee (X \wedge Y \wedge Z) \vee (X \wedge \bar{Y} \wedge Z) \vee (\bar{X} \wedge Y \wedge Z)$

[Maslov]

mike007,

покажите, пожалуйста, путем каких стандартных преобразований Вы получили

$((X \vee Y) \leftrightarrow Z) \equiv ((\bar X \wedge \bar Y) \vee Z) \wedge (\bar Z \vee X \vee Y))$.

[mike007]

Maslov,

$((X \vee Y) \leftrightarrow Z) \equiv ((X \vee Y) \rightarrow Z) \wedge (Z \rightarrow (X \vee Y)) \equiv$ $(((\bar{X} \wedge \bar{Y}) \vee Z) \wedge (\bar{Z} \vee X \vee Y))$

[Maslov]

Вы извините, мне сложно проверить Ваши выкладки, но у меня получается так:

$(y + z)((x + y) \leftrightarrow z) \equiv $

$(y + z) ((x+y)z + \overline{(x+y)} \bar z) \equiv (y + z)(xz + yz + \bar x \bar y \bar z) \equiv $

$xyz + yyz + \bar x \bar y y \bar z + x z z + y z z + \bar x \bar y \bar z z \equiv $

$xyz + yz + xz \equiv xyz + xyz + \bar xyz + xyz + x\bar y z \equiv xyz + \bar x y z + x \bar y z$

[mike007]

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

[Maslov]

mike007 в сообщении #558030 писал(а):

Сейчас попробую найти тождество для устранения эквиваленции в том виде, в котором получил на лекции.

Это правильное тождество :) У Вас где-то в другом месте ошибочка.

[mike007]

Maslov,
но если эквиваленция и импликация устранены правильно, то ошибка может быть только в раскрытии скобок, верно?
Однако, иного пути раскрыть скобки я не вижу. Можно, кончено, раскрыть сначала 1 и 3 или 2 и 3, но есть ли смысл.

[Maslov]

Нормально все с эквивалентностью и импликацией:

$ (x + y) \leftrightarrow z \equiv ((x + y) \to z) (z \to (x + y)) \equiv (\overline { x + y} + z) ( \bar z + (x + y)) \equiv $

$(\bar x \bar y + z) (x + y + \bar z) \equiv (x \bar x \bar y + \bar x \bar y y + \bar x \bar y \bar z + xz + yz + z \bar z) \equiv \bar x \bar y \bar z + x z + yz$

Просто, скорее всего, перепутали где-то $\lor$ и $\land$.

-- Вс апр 08, 2012 18:59:00 --

Вот этот переход еще распишите, пожалуйста, аккуратненько:

$(Y \vee Z) \wedge ((X \vee Y) \leftrightarrow Z) \equiv$
$ ((Y \vee Z) \wedge (\bar{X} \vee \bar{Y})) \vee ((Y \vee Z) \wedge Z) \wedge (\bar{Z} \vee X \vee Y)$

[mike007]

Maslov в сообщении #558042 писал(а):

$(Y \vee Z) \wedge ((X \vee Y) \leftrightarrow Z) \equiv$
$ ((Y \vee Z) \wedge (\bar{X} \vee \bar{Y})) \vee ((Y \vee Z) \wedge Z) \wedge (\bar{Z} \vee X \vee Y)$

Да, здесь будет $(\bar{X} \wedge \bar{Y})$, видимо ошибся при переносе с листа. Так-то у меня правильно написано.

[Maslov]

А это откуда взялось:
$ ((Y \vee Z) \wedge Z) \wedge (\bar{Z} \vee X \vee Y) \equiv$ $ (Z \wedge Y) \vee (Z \wedge Z) \wedge (\bar{Z} \vee X \vee Y) $

[mike007]

По закону дистрибутивности:
$((Y \vee Z) \wedge Z) \equiv$ $ (Z \wedge Y) \vee (Z \wedge Z) $
Далее $(Z \wedge Z) \equiv Z$
Поэтому остается только
$((Y \vee Z) \wedge (\bar{X} \wedge \bar{Y})) \vee (Z \wedge Y) \vee Z \wedge (\bar{Z} \vee X \vee Y)$

[Maslov]

А скобки Вы там не потеряли вокруг $(Z \land Y) \lor Z$?