минимальная ДНФ

[tvims]

Здравствуйте, Уважаемые.

Есть задача "Для булевой функции f(x,y,z) найти методом преобразования минимальную ДНФ. По таблице истинности построить СКНФ. По минимальной ДНФ построить релейно-контактную схему."

Вот моя попытка найти методом преобразования минимальную ДНФ:

`f(x,y,z)=((bar(x vee z)) to y) to (x to y)=bar((bar(x vee z)) to y) vee (x to y)=`
`=bar(bar(bar(x vee z)) vee y) vee (bar(x) vee y)=bar(x vee z vee y) vee bar(x) vee y=`
`=(bar(x) wedge bar(z) wedge bar(y)) vee bar(x) vee y=bar(x) vee y`

Посмотрите, пожалуйста. Куда-то потерялось z?

@темы: Математическая логика, Дискретная математика

Comments

[mad-math]

Ответ у вас правильный.

Но на последнем этапе мне не нравится вот этот момент, где у вас используется закон Де Моргана, но для трех переменных, насколько я знаю, он применяется только к двум переменным: `bar(x vee z vee y) vee bar(x) vee y =(bar(x) wedge bar(z) wedge bar(y)) vee bar(x) vee y`.

Мой выход крайне некрасив, но зато корректен:
`[bar(x vee z vee y) vee bar(x)] vee y = bar((x vee z vee y) wedge x) vee y = bar((x vee z vee y) wedge x wedge bar(y)) =`
`= bar((x wedge bar(y)) vee (x wedge bar(y) wedge z) vee (x wedge bar(y) wedge y)) = bar((x wedge bar(y)) wedge (1 vee z)) = `
`= bar((x wedge bar(y))) = bar(x) vee y`

Могу расписать подробнее, если нужно.

[All_ex]

mad-math, к трём тоже можно... `bar(x vee z vee y) = bar(x vee z) wedge bar(y) = bar(x) wedge bar(z) wedge bar(y)`...

А можно в последнем равенстве сослаться на закон поглощения `(A wedge B) vee A = A` и ассоциативность конъюнкции и дизъюнкции...
`[(bar(x) wedge {bar(z) wedge bar(y)}) vee bar(x) ] vee y = bar(x) vee y`, здесь `A = bar(x), \ \ B = bar(z) wedge bar(y)`

[mad-math]

All_ex, точно, у вас гораздо красивее получается.

[All_ex]

tvims, Посмотрите, пожалуйста. Куда-то потерялось z? - Кстати... она же потерялась в Ваших выкладках (или они не Ваши?)... что означал Ваш вопрос?...

[tvims]

Спасибо за комментарии, Уважаемые.

что означал Ваш вопрос?...

Да я второй год не могу четко понять что такое ДНФ и КНФ. С совершенными еще более-менее, там в каждой элементарной дизъюнкции (конъюнкции) должны быть все переменные или их отрицания (ИЛИ я и это неправильно понимаю???!!!). Поэтому меня немного напугало, что нет z в ответе. Очень радует, что ответ верный. Буду решать задачу дальше.

[All_ex]

Поэтому меня немного напугало, что нет z в ответе. - Может это просто фиктивная переменная...

[tvims]

Правильно ли я оформляю таблицу истинности или ее можно строить по ДНФ?
То есть достаточно последних столбцов таблицы?

[All_ex]

Таблица вроде верная...

[tvims]

То есть мы таблицу истинности составляем по исходной функции. Потому что если по ДНФ, то z совсем в расчет не надо было бы брать?

Исходя из таблицы истинности составляем СКНФ. Берем строки, где значение функции равно нулю. Записываем дизъюнкции по этим строкам. Переменные равные "1" берем с отрицанием, остальные как есть. Соединяем эти дизъюнкции конъюнкциями.
Получилось вот что: `(bar(x) vee y vee z) wedge (bar(x) vee y vee bar(z)` - это СКНФ. Правильно?

[tvims]

Проверьте пожалуйста релейно-контактную схему:

[mad-math]

1) Таблица истинности составляется обычно по исходной функции.
2) СКНФ верная.
3) Я с контактными схемами особо не работал, но похоже, что правильно.

[tvims]

спасибо