СКНФ методом равносильных преобразований

[LarisaK]

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

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

Пробовала сгруппировать:
$(x \wedge y)\vee (\bar x\wedge y\wedge \bar z) = (x \wedge y)\vee (y \wedge \bar z)$ - по формуле Блейка
или
$(\bar x\wedge\bar y\wedge z) \vee (\bar x\wedge y\wedge \bar z) = \bar x \wedge (\bar y \vee z) \wedge (y \vee z) $ - вынесла за скобки и перемножила
но в обоих случаях что делать дальше с оставшимися членами выражения (как сделать конъюнкцию внешней функцией) не понимаю.
Может я вообще все делаю неправильно (третий день бьюсь):(
Задание для заочников, вроде не должно быть сложным, явно не вижу какого-то простого способа. Помогите, плз

[Sender]

LarisaK в сообщении #1185479 писал(а):

вынесла за скобки и перемножила

Собственно, вы на правильном пути.
Вот как бы вы раскрывали скобки, если бы у вас было обычное алгебраическое выражение
$(\bar x+\bar y+ z)(x + y) (x + \bar z)(\bar x+ y+ \bar z)$?

[Sinoid]

Sender в сообщении #1185483 писал(а):

Вот как бы вы раскрывали скобки, если бы у вас было обычное алгебраическое выражение
$(\bar x+\bar y+ z)(x + y) (x + \bar z)(\bar x+ y+ \bar z)$?

Не совсем понятно, зачем здесь раскрытие скобок (в данном случае), если в конечном итоге нужно получить выражение со скобками. А вообще, нужно применить равносильность $P\vee Q\wedge R\cong(P\vee Q)\wedge(P\vee R)$

[Sender]

Sinoid в сообщении #1185507 писал(а):

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

А если в условии заменить все операции на двойственные, изменив вопрос задачи на нахождение СДНФ, тогда понятно?

[arseniiv]

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

-- Ср янв 18, 2017 05:06:25 --

…или найти (гуглом или даже здесь на форуме, притом должна быть достаточно большая вероятность получить его по одному из четырёх запросов вида «СКНФ/СДНФ алгоритм/метод»)

[LarisaK]

arseniiv в сообщении #1185578 писал(а):

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

-- Ср янв 18, 2017 05:06:25 --

…или найти (гуглом или даже здесь на форуме, притом должна быть достаточно большая вероятность получить его по одному из четырёх запросов вида «СКНФ/СДНФ алгоритм/метод»)

под методом подразумевается вот это?
1.Перейти к булевой формуле, т. е. раскрыть импликацию и эквиваленцию.
2. Перейти с помощью закона де Моргана к формуле с «тесными отрица-
ниями, в которой отрицание встречается не выше, чем над переменной.
3. С помощью дистрибутивного закона сделать конъюнкцию внешней опе-
рацией (создать скобки).
4. Привести подобные и опустить тождественно истинные множители.
5. Пополнить элементарные диз юнкции (получившиеся множители) не-
достающими переменными, повторить п. 4 и остановиться.

Если да, то я и застряла на 3 пункте, так как у меня не получается правильно сгруппировать члены выражения. Я ведь правильно понимаю, что их нужно по 2шт группировать (какой с каким) и преобразовывать с помощью дистрибутивного закона, а потом результат преобразовывать дальше?
Смысл-то я понимаю, и кучу примеров с СКНФ уже решила, а на этом застряла:(.

-- 18.01.2017, 21:01 --

Sender в сообщении #1185483 писал(а):

LarisaK в сообщении #1185479 писал(а):

вынесла за скобки и перемножила

Собственно, вы на правильном пути.
Вот как бы вы раскрывали скобки, если бы у вас было обычное алгебраическое выражение
$(\bar x+\bar y+ z)(x + y) (x + \bar z)(\bar x+ y+ \bar z)$?

так бы и раскрывала бы как в обычной алгебре, сначала бы раскрыла - перемножила первую пару скобок, потом вторую пару, потом полученные результаты между собой. То есть, надо делать двойное отрицание?

[Sender]

LarisaK в сообщении #1185702 писал(а):

То есть, надо делать двойное отрицание?

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

И да, просто уточню на всякий случай. Если вы у вас было алгебраическое выражение, представляющее собой произведение трёх скобок, как бы вы их раскрывали?

[LarisaK]

Sinoid в сообщении #1185507 писал(а):

Sender в сообщении #1185483 писал(а):

Вот как бы вы раскрывали скобки, если бы у вас было обычное алгебраическое выражение
$(\bar x+\bar y+ z)(x + y) (x + \bar z)(\bar x+ y+ \bar z)$?

Не совсем понятно, зачем здесь раскрытие скобок (в данном случае), если в конечном итоге нужно получить выражение со скобками. А вообще, нужно применить равносильность $P\vee Q\wedge R\cong(P\vee Q)\wedge(P\vee R)$

я ее вообще-то и применяю, только по-видимому, не там, где надо


ну смотрите, я беру два, например, первых слагаемых
$\bar x\bar yz+xy$ применяю указанную выше равносильность и правило полупоглощения получаю
$(x+\bar y)(x+z)(y+\bar x)(y+z)$
замечательно, ползем дальше.
осталось
$x\bar z+\bar x y \bar z= (x+y)(y+\bar z)(\bar x+\bar z)(\bar z+y)$

и получила я вот такую фигню в результате, которую абсолютно непонятно как преобразовывать дальше (все скобки разные, неужели все это опять перемножать?)
$(x+\bar y)(x+z)(y+\bar x)(y+z)+ (x+y)(y+\bar z)(\bar x+\bar z)(\bar z+y)$

что я делаю неправильно?

-- 18.01.2017, 21:29 --

Sender в сообщении #1185714 писал(а):

LarisaK в сообщении #1185702 писал(а):

То есть, надо делать двойное отрицание?

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

И да, просто уточню на всякий случай. Если вы у вас было алгебраическое выражение, представляющее собой произведение трёх скобок, как бы вы их раскрывали?

я вроде скобки везде ставлю, чтобы приоритеты не нарушать, и что дистрибутивных закона два - тоже понятно.

раскрывала бы по очереди. перемножила бы две первые скобки, результат заключила бы в скобку и домножила бы его на третью скобку, а что можно проще?

[Sender]

Ответьте на вопрос, пожалуйста.

Sender в сообщении #1185714 писал(а):

Если вы у вас было алгебраическое выражение, представляющее собой произведение трёх скобок, как бы вы их раскрывали?

Пардон, не заметил.

-- Ср янв 18, 2017 20:40:15 --

LarisaK в сообщении #1185715 писал(а):

осталось
$x\bar z+\bar x y \bar z= (x+y)(y+\bar z)(\bar x+\bar z)(\bar z+y)$

Вот здесь у вас ошибка.

[Sinoid]

LarisaK в сообщении #1185715 писал(а):

осталось

Так не надо "осталось". Вы первый оставшийся конъюнкт сдизъюнктируйте с

LarisaK в сообщении #1185715 писал(а):

$(x+\bar y)(x+z)(y+\bar x)(y+z)$

И не пишите, пожалуйста, плюсы, во избежание путаницы.

[arseniiv]

Вы же сами предложили обычное алгебраическое выражение. Тут плюсы — просто плюсы, не дизъюнкция.

[Sinoid]

arseniiv в сообщении #1185776 писал(а):

Вы же сами предложили обычное алгебраическое выражение. Тут плюсы — просто плюсы, не дизъюнкция.

Когда?

[Sender]

arseniiv в сообщении #1185776 писал(а):

Вы же сами предложили обычное алгебраическое выражение.

Это я предложил для аналогии, чтобы использовать предположительно имеющиеся у ТС навыки раскрытия скобок для пользы дела. И, похоже, тем самым окончательно это самое дело запутал.

[LarisaK]

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

[Sinoid]

Еще можно посоветовать проверить совпадение таблиц истинности полученного ответа и исходного выражения логическим калькулятором: всяко бывает...