Привести равносильным преобразование к СДНФ и СКНФ

[nat87]

Формулу алгебры высказываний привести равносильными преобразованиями к СДНФ и СКНФ
$(z\leftrightarrow\bar{y})\wedge(x\rightarrow z)\cong((\bar{z}\vee\bar{y})\wedge(y\vee z))\wedge(\bar{x}\vee z)$
Как я понимаю дальше нужно применить закон дистрибутивности и преобразовать форбулу к дизъюкции конъюктивных одночленов, но на практике что то не получается у меня

-- 15.04.2013, 09:52 --

nat87 в сообщении #710353 писал(а):

Формулу алгебры высказываний привести равносильными преобразованиями к СДНФ и СКНФ
$(z\leftrightarrow\bar{y})\wedge(x\rightarrow z)\cong((\bar{z}\vee\bar{y})\wedge(y\vee z))\wedge(\bar{x}\vee z)$
Как я понимаю дальше нужно применить закон дистрибутивности и преобразовать форбулу к дизъюкции конъюктивных одночленов, но на практике что то не получается у меня

Вот до чего я дошла но не уверена правильно ли

$(z\leftrightarrow\bar{y})\wedge(x\rightarrow z)\cong((\bar{z}\vee\bar{y})\wedge(y\vee z))\wedge(\bar{x}\vee z)\cong(\bar{z}\vee(\bar{y}\wedge(y\vee z))\wedge(\bar{x}\vee z)\cong(\bar{z}\vee(\bar{y}\wedge y)\vee(\bar{y}\vee z))\wedge(\bar{x}\vee z)\cong(\bar{z}\vee(0)\vee(\bar{y}\vee z))\wedge(\bar{x}\vee z)\cong(\bar{z}\vee(\bar{y}\vee z))\wedge(\bar{x}\vee z)$

[Deggial]

nat87 в сообщении #710353 писал(а):

$(z\leftrightarrow\bar{y})\wedge(x\rightarrow z)\cong((\bar{z}\vee\bar{y})\wedge(y\vee z))\wedge(\bar{x}\vee z)\cong(\bar{z}\vee(\bar{y}\wedge(y\vee z))\wedge(\bar{x}\vee z)\cong(\bar{z}\vee(\bar{y}\wedge y)\vee(\bar{y}\vee z))\wedge(\bar{x}\vee z)\cong(\bar{z}\vee(0)\vee(\bar{y}\vee z))\wedge(\bar{x}\vee z)\cong(\bar{z}\vee(\bar{y}\vee z))\wedge(\bar{x}\vee z)$

Как минимум не упрощено до конца, поскольку первая скобка упрощаема.
Вы можете проверить свои вычисления построением таблиц истинности, хотя бы для самого первого и самого последнего выражений. Если таблицы разные, значит где-то ошибка. Можно также подставлять частные значения булевых переменных и упрощать - должно получаться одно и то же.
После первого преобразования у Вас уже получилась КНФ, её уже несложно довести до СКНФ.
Второе преобразование у Вас выглядит странно: Вы получаете две скобки и одну махом упрощаете, а вторую, изоморфную первой, не упрощаете. Нелогично. Либо Вы как-то неправильно преобразовали, но случайно получили правильный результат.
Вообще, вторая скобка не при чем - Вы пытаетесь формально найти ДНФ для эквиваленции. Можете искать её отдельно. У Вас должно получиться $y\bar{z}\vee \bar{y}z$.

[nat87]

Deggial в сообщении #710574 писал(а):

nat87 в сообщении #710353 писал(а):

$(z\leftrightarrow\bar{y})\wedge(x\rightarrow z)\cong((\bar{z}\vee\bar{y})\wedge(y\vee z))\wedge(\bar{x}\vee z)\cong(\bar{z}\vee(\bar{y}\wedge(y\vee z))\wedge(\bar{x}\vee z)\cong(\bar{z}\vee(\bar{y}\wedge y)\vee(\bar{y}\vee z))\wedge(\bar{x}\vee z)\cong(\bar{z}\vee(0)\vee(\bar{y}\vee z))\wedge(\bar{x}\vee z)\cong(\bar{z}\vee(\bar{y}\vee z))\wedge(\bar{x}\vee z)$

Как минимум не упрощено до конца, поскольку первая скобка упрощаема.
Вы можете проверить свои вычисления построением таблиц истинности, хотя бы для самого первого и самого последнего выражений. Если таблицы разные, значит где-то ошибка. Можно также подставлять частные значения булевых переменных и упрощать - должно получаться одно и то же.
После первого преобразования у Вас уже получилась КНФ, её уже несложно довести до СКНФ.
Второе преобразование у Вас выглядит странно: Вы получаете две скобки и одну махом упрощаете, а вторую, изоморфную первой, не упрощаете. Нелогично. Либо Вы как-то неправильно преобразовали, но случайно получили правильный результат.
Вообще, вторая скобка не при чем - Вы пытаетесь формально найти ДНФ для эквиваленции. Можете искать её отдельно. У Вас должно получиться $y\bar{z}\vee \bar{y}z$.

$(z\leftrightarrow\bar{y})\wedge(x\rightarrow z)\cong(\bar{x}\wedge y\wedge\bar{z})\vee(\bar{y}\wedge z)\cong(\bar{y}\wedge z)\vee(\bar{x}\wedge y\wedge\bar{z})\cong((\bar{y}\wedge z)\wedge(x\vee\bar{x}))\vee(\bar{x}\wedge y\wedge\bar{z})\cong(\bar{y}\wedge z\wedge x)\vee(\bar{y}\wedge z\wedge\bar{x})\vee(\bar{x}\wedge y\wedge\bar{z})\cong(x\wedge\bar{y}\wedge z)\vee(\bar{x}\wedge\bar{y}\wedge z)\vee(\bar{x}\wedge y\wedge\bar{z})$

$(z\leftrightarrow\bar{y})\wedge(x\rightarrow z)\cong(\bar{x}\wedge y\wedge\bar{z})\vee(\bar{y}\wedge z)$ Вот этот промежуток у меня никак не получается, т.е к ДНФ у меня не выходит привести

-- 15.04.2013, 19:54 --

[лишняя цитата удалена]

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

[Deggial]

nat87, зачем Вы цитируете одно и то же целиком много раз? Для ответа есть кнопка "Ответить". Для редактирования сообщения можно использовать кнопку "Правка".

nat87 в сообщении #710633 писал(а):

Вот этот промежуток у меня никак не получается, т.е к ДНФ у меня не выходит привести

Докажите сначала $z\leftrightarrow\bar{y}\cong y\bar{z}\vee \bar{y}z$.
Кроме того, Вы неявно уже доказали $x\to z\cong \bar{x}\vee z$. Правая часть - дизъюнкция. Эквиваленцию Вы тоже переписываете как дизъюнкцию. Потом просто скомбинируйте $(b\vee c)a=ab\vee ac$.
Т.е. выполняйте преобразования по частям, так легче.

[nat87]

$z\leftrightarrow\bar{y}\cong (z\rightarrow\bar{y})\wedge(\bar{y}\rightarrow z)\cong(z\vee\bar{y})\wedge(y\vee z)$
и тупик

[Deggial]

nat87 в сообщении #710955 писал(а):

$z\leftrightarrow\bar{y}\cong (z\rightarrow\bar{y})\wedge(\bar{y}\rightarrow z)\cong(z\vee\bar{y})\wedge(y\vee z)$

Ага.
Сначала заметим, что формула должна получиться симметричной, поскольку истинностное значение $A\leftrightarrow B$ совпадает с таковым у $A \neq B$, а последнее отношение симметрично.
Ну а потом Вам нужно использовать дистрибутивность одной логической операции относительно другой: $a(b\vee c)=ab\vee ac$, и взять в качестве $a$ первую скобку.

[nat87]

$z\leftrightarrow\bar{y}\cong (z\rightarrow\bar{y})\wedge(\bar{y}\rightarrow z)\cong(z\vee\bar{y})\wedge(y\vee z)\cong(\bar{y}\vee z)\wedge(y\vee z)\cong(\bar{y}\wedge z\wedge y)\vee(z\wedge y\wedge z)$
вот так?????

[Deggial]

nat87 в сообщении #711172 писал(а):

$(z\rightarrow\bar{y})\wedge(\bar{y}\rightarrow z)\cong(z\vee\bar{y})\wedge(y\vee z)\cong(\bar{y}\vee z)\wedge(y\vee z)$

Я повторюсь: у Вас тут неверно преобразовано, конкретно - первая скобка. Надо так: $p\to q\cong \bar{p}\vee q$.

Если эту ошибку не принимать во внимание, то дальше правильно. Кроме того, то, что Вы получили

nat87 в сообщении #711172 писал(а):

$(\bar{y}\wedge z\wedge y)\vee(z\wedge y\wedge z)$

упрощается. Чему равно $p\wedge p$?

[nat87]

$p\wedge p=p$

$z\leftrightarrow\bar{y}\cong (z\rightarrow\bar{y})\wedge(\bar{y}\rightarrow z)\cong(\bar{z}\vee\bar{y})\wedge(y\vee z)\cong(\bar{y}\vee\bar{z})\wedge(y\vee z)\cong(\bar{y}\wedge\bar{z}\wedge y)\vee(\bar{y}\wedge\bar{z}\wedge z)$

Я что-то уже совсем запуталась

[Deggial]

nat87 в сообщении #711360 писал(а):

$z\leftrightarrow\bar{y}\cong (z\rightarrow\bar{y})\wedge(\bar{y}\rightarrow z)\cong(\bar{z}\vee\bar{y})\wedge(y\vee z)\cong(\bar{y}\vee\bar{z})\wedge(y\vee z)\cong(\bar{y}\wedge\bar{z}\wedge y)\vee(\bar{y}\wedge\bar{z}\wedge z)$

$(\bar{y}\vee\bar{z})\wedge(y\vee z)\cong q\wedge(y\vee z)\cong (q\wedge y)\vee (q\wedge z)\cong$ - сделайте теперь обратную подстановку $q=\bar{y}\vee\bar{z}$.

[nat87]

$((\bar{y}\vee\bar{z})\wedge y)\vee((\bar{y}\vee\bar{z})\wedge z)\cong((y\wedge\bar{y})\vee(y\wedge\bar{z}))\vee((z\wedge\bar{y})\vee(z\wedge\bar{z}))\cong(y\wedge\bar{z})\vee(\bar{y}\wedge z)$

-- 17.04.2013, 08:44 --

$((y\wedge\bar{z})\vee(\bar{y}\wedge z))\wedge(\bar{x}\vee z)$

[Sender]

Верно. Теперь зададимся вопросом: какова будет ДНФ для $(a \vee b)\wedge c$?

[nat87]

$(c\wedge a)\vee(c\wedge b)$
ток к моему примеру трудновато сделать главное не запутаться, щас попробую мож что и выйдет))))

[nat87]

$((y\wedge\bar{z})\vee(\bar{y}\wedge z))\wedge(\bar{x}\vee z)\cong((\bar{x}\vee z)\wedge(y\wedge\bar{z}))\vee((\bar{x}\vee z)\wedge(\bar{y}\wedge z))$

$(\bar{x}\vee z)\wedge(y\wedge\bar{z})\cong y\wedge(\bar{z}\wedge(\bar{x}\vee z))\cong y\wedge((\bar{z}\wedge\bar{x})\vee(\bar{z}\wedge z))\cong y\wedge(\bar{z}\wedge\bar{x})\cong\bar{x}\wedge y\wedge\bar{z}$

[Sender]

Так, хорошо. Осталось раскрыть вторую скобку.