Упрощение булевой алгебры

Мне нужно привести это логическое выражение к его простейшей форме. Учитывая, что простейшая форма содержит 3 термина и 7 литералов.

Выражение:

x'yz + w'x'z + x'y + wxy + w'y'z

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

Любая помощь будет оценена по достоинству.


boolean algebra boolean-logic
person xbonez    schedule 14.04.2010    source источник
comment
Что означает x' по сравнению с просто x? Это производная? Или что-то другое?   -  person RBarryYoung    schedule 14.04.2010
comment
в булевой алгебре x 'не является (x). например, если x=0, то x'=1.   -  person xbonez    schedule 14.04.2010
comment
Извините, я научился использовать нотацию типа Copi (Not A = ~A), а не Черч (¬A) или стиль пост-апострофа (A').   -  person RBarryYoung    schedule 14.04.2010
comment
Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что он касается булевой алгебры и математики, а не непосредственно программирования или кодирования.   -  person Pang    schedule 13.07.2017

Ответы (6)


arrow_upward
1
arrow_downward

Я немного заржавел с булевой алгеброй, но я думаю, что понял, как это сделать. Я позволю вам сделать работу, но вот основные шаги:

1) Сгруппируйте термины с помощью y и уберите все, что можно, в скобках. После повторного расширения это оставит вас с четырьмя терминами и десятью литералами.

2) Удалите лишний термин, оставив вам три термина и семь литералов.

Подсказка: сначала я нашел ответ с помощью карты Карно, а затем использовал обычную булевую алгебру, чтобы найти решение :-)

person David Johnstone    schedule 14.04.2010
comment
Согласованный! Читать, используя K-карту в первую очередь. ;-) +1 за этичное мошенничество. - person Peter K.; 14.04.2010

arrow_upward
5
arrow_downward

Попробуйте поместить его на Карту Карно.

person Peter K.    schedule 14.04.2010
comment
+1 K-Maps действительно просты, и как только вы к ним привыкнете, вы сможете легко уменьшить любую логическую функцию из четырех или менее переменных. - person BlueRaja - Danny Pflughoeft; 14.04.2010
comment
Карты Карно отлично подходят для этого. Я только что сам решил эту проблему, и она немного упрощается. - person David Johnstone; 14.04.2010
comment
да, мы только начинаем изучать K-карты, но этот HW требует от нас использовать булевую алгебру, а не K-карты - person xbonez; 14.04.2010
comment
@xbonez: Но K-карты ЯВЛЯЮТСЯ булевой алгеброй или, по крайней мере, другим способом ее визуализации. Ага! HW = Домашняя работа, а не HW = Аппаратное обеспечение. Понимаю. Что ж, советую посмотреть, что вам говорит К-карта о том, как делать алгебру. - person Peter K.; 14.04.2010

arrow_upward
3
arrow_downward

сокращение Куайна-МакКласки — один из самых эффективных инструментов для этого, хотя это может быть трудоемким.

person Ignacio Vazquez-Abrams    schedule 14.04.2010

arrow_upward
0
arrow_downward

Так:

х'у + шху + ш'у'z

person RBarryYoung    schedule 14.04.2010
comment
Как правило, мы не просто даем ответы на домашние вопросы, но я думаю, это нормально, потому что на самом деле вы можете упростить это больше, чем это (при условии, что я не сделал ошибку, что не всегда безопасно делать): - ) - person David Johnstone; 14.04.2010
comment
Да, я почти уверен, что мой ответ еще в одном шаге от завершения. :-) - person RBarryYoung; 14.04.2010
comment
Вау, я действительно ошибся в своем ответе - я сделал ошибку в своей K-карте. Этот ответ правильный, но его можно уменьшить, удалив ровно один литерал, оставив 3 термина и 7 литералов по мере необходимости. - person BlueRaja - Danny Pflughoeft; 14.04.2010
comment
к сожалению, нам не разрешено использовать K-карты в этом конкретном HW. мы должны использовать булеву алгебру. и я понимаю, что вы, ребята, не даете ответы на вопросы HW, и это разумно, но я на самом деле пытался решить этот вопрос часами, и мы даже спросили нашу ТА по чтению, и она тоже не могла понять это - person xbonez; 14.04.2010
comment
Если вы собираетесь решить эту задачу, используя только законы булевой алгебры, вам предстоит непростая задача. Я бы попробовал дважды отрицать все выражение, но я даже не знаю, сработает ли это... - person BlueRaja - Danny Pflughoeft; 14.04.2010
comment
Ну, я зашел так далеко, используя только булеву алгебру. Четыре переменные — это всего 16 возможных ветвей, так что это не так уж и сложно. - person RBarryYoung; 14.04.2010
comment
Подводя итог: я дал полезный ответ (устранил 40% исходной сложности), я не нарушил правило домашнего задания, потому что я не завершил исходный вопрос (имеет 8 вместо 7 констант) и потому что я не показал мою работу (которая, очевидно, потребуется от ОП), я сделал ее полностью с использованием метода, указанного для задачи (булевой алгебры), и ОП подтвердил ее правильность. Если что-то из этого неверно, пожалуйста, дайте мне знать. Однако, если это резюме верно, то, пожалуйста, сообщите, почему никто, включая ОП, не считает, что оно заслуживает одобрения? - person RBarryYoung; 14.04.2010
comment
@RBarryYoung: с четырьмя переменными существует 16 возможных количественных оценок, которые могут быть оценены как истинные или ложные в соответствии с данным выражением, что означает, что существует 65536 возможных выражений. Я думаю, это довольно сложно. - person BlueRaja - Danny Pflughoeft; 14.04.2010
comment
@BlueRaja: На самом деле это будет 3 ^ 16, потому что переменные также могут быть инвертированы в терминах. Но в любом случае, это НЕ подход к логическому анализу, потому что вы можете оценить эффективность терминов отдельно от всего выражения (из-за того, как работает ИЛИ по сравнению с И для логической оценки). Вы определенно делаете это слишком сложно. - person RBarryYoung; 15.04.2010
comment
@RBarryYoung: существует только 2 ^ 16 логических функций от четырех переменных (как следует из того факта, что существует только 2 ^ 16 возможных K-карт). Отрицание одной из функций 2^16 даст вам еще одну из функций 2^16. Вы также не можете, как вы говорите, оценивать термины изолированно - сам ваш ответ является примером того, где литерал можно удалить, только просмотрев все три термина. - person BlueRaja - Danny Pflughoeft; 15.04.2010
comment
Раджа: Хорошо, ты абсолютно прав. Я, должно быть, пересчитал в уме все из ваших предполагаемых 65 536 вариантов, сам того не осознавая, и случайно решил эту задачу. Большое спасибо за то, что вы исправили меня, чтобы я не думал, что знаю, как решить эту проблему, которую я уже решил. - person RBarryYoung; 19.04.2010

arrow_upward
0
arrow_downward

Можем ли мы использовать группы?

w'z(x' + y') + y(x' + w)
person 500 - Internal Server Error    schedule 15.04.2010
comment
(Дайте мне знать, если вы хотите знать, как я туда попал) - person 500 - Internal Server Error; 15.04.2010

arrow_upward
0
arrow_downward 

X'YZ + W'X'Z + X'Y + WXY + W'Y'Z
=  X'Y+W'X'Z+WXY+W'Y'Z      by absorption
=  WY+X'Y+W'X'Z+W'Y'Z       by absorption
=  W'Y'Z+WY+X'YZ+X'Y        by consensus
=  W'Y'Z+WY+X'Y         by absorption

Использование инструмента на http://www.logicminimizer.com/

person Mika    schedule 21.04.2013