Получение логической функции из таблицы, описывающей вывод d логической функции

Мне был задан следующий вопрос:

В следующей таблице описываются выходные данные d логического развлечения с тремя входными значениями a, b и c.

 a  b  c  |  d 
----------+----
 0  0  0  |  1 
 0  0  1  |  1 
 0  1  0  |  1 
 0  1  1  |  0 
 1  0  0  |  0 
 1  0  1  |  0 
 1  1  0  |  0 
 1  1  1  |  0

Задайте эту логическую функцию, используя подходящую комбинацию AND, OR, XOR, NOT, NAND, NOR или XNOR.

Почему правильный ответ:

d := (((NOT a) AND (NOT b)) AND (NOT c)) OR
(((NOT a) AND (NOT b)) AND c) OR
(((NOT a) AND b) AND (NOT c))

Мой ответ. (((НЕ а) И (НЕ б)) И (НЕ в))

a   b   c     d
===============
0   0   0     1      
.
. 
.

Как это получается?


boolean-logic truthtable
person methuselah    schedule 03.06.2012    source источник
comment
Расскажите, почему вы считаете, что это неправильно. Так как это домашнее задание, мы хотели бы увидеть некоторые усилия. Не забудьте показать свою работу, пожалуйста :-) Но в качестве подсказки Посмотрите на столбец D и количество OR в ответе.   -  person Preet Sangha    schedule 03.06.2012
comment
Я разработал решение d := (((NOT a) AND (NOT b)) AND (NOT c)), но оно неверно.   -  person methuselah    schedule 03.06.2012
comment
Хорошо, теперь сделайте таблицу, показывающую результат вашей функции в ответе. Я начну с тебя:   -  person Preet Sangha    schedule 03.06.2012
comment
Не публикуйте изображение, содержащее текст. Это недоступно для поиска и грубо по отношению к людям, которые не могут просматривать изображения.   -  person Gilles 'SO- stop being evil'    schedule 03.06.2012
comment
@Жиль извини за это   -  person methuselah    schedule 03.06.2012

Ответы (5)


arrow_upward
2
arrow_downward

Ответ, который вы даете, называется формулировкой сумма произведений (СОП). Посмотрите на три больших термина, соединенных операторами OR:

  • ((NOT a) AND (NOT b)) AND (NOT c))
  • ((NOT a) AND (NOT b)) AND c)
  • ((NOT a) AND b) AND (NOT c)

Теперь посмотрите на таблицу истинности, в которой ровно три строки имеют 1 в столбце d. Каждая из этих трех строк соответствует одному из трех терминов.

Можно составить более краткие ответы, например d := (NOT a) AND (NOT(b AND c)), но они не являются формулировкой суммы произведений, которую вы дали.

person thb    schedule 03.06.2012
comment
Кстати, вы должны внимательно следить за комментариями @PreetSangha. Они, вероятно, помогут вам так же или даже больше, чем мой ответ. Удачи. - person thb; 03.06.2012

arrow_upward
1
arrow_downward

  • Проверьте верхнюю половину таблицы. a должно быть ложным, чтобы fun было истинным.
  • Кроме того, b и c не могут одновременно быть true. Итак, это должно быть !(b && c).
  • Это должно сократить fun до !a && !(b && c)
  • Вы можете применить теорему Де Моргана ко второй части и использовать !b || !c, но даже тогда a должно быть ложным, поэтому: !a && (!b || !c) - это то, что вы получите в итоге.
person dirkgently    schedule 03.06.2012

arrow_upward
1
arrow_downward

Для 3 переменных 8 записей (2^3) представляют исчерпывающую комбинацию всех возможных переменных между 3 переменными a, b, c. Переменная d является (как видно) выходом некоторой функции, скажем, f(x).

Теперь, поскольку 8 записей включают все возможные варианты, мы можем сделать вывод, что вывод d является логическим 1 только тогда, когда возникает конкретная комбинация. Результат 0 во всех остальных случаях.

Поэтому мы просто объединяем все строки, которые имеют результат 1. Результат, который у вас есть, следует за этим.

Процедура проста:

  • Возьмите все строки с выводом как 1.
  • For every row, output an expression which will result into a 1 for the value of the variables.
    • AND every variable. If any variable has the value 0, NOT it before ANDing it.
  • OR все 8 выражений, найденных на шаге выше.
person UltraInstinct    schedule 03.06.2012

arrow_upward
1
arrow_downward

Самый простой способ получить функцию из (полной) таблицы истинности — прочитать только строки с единицей (или нулем) в качестве результата и записать дизъюнктивная (или конъюнктивная) нормальная форма.

В вашей таблице меньше результатов 1, чем 0, поэтому дизъюнктивная нормальная форма будет короче. Как видно из таблицы, d будет равно 1 ровно в 3 случаях:

  • a=0, b=0, c=0
  • a=0, b=0, c=1
  • a=0, b=1, c=0

Просто сложите их вместе, и вы получите: (! = не, & = и, v = или)

d = (!a & !b & !c) v (!a & !b & c) v (!a & b & !c)

Эта форма автоматически исключает все остальные случаи. Вы можете еще упростить эту формулу. Более пристальный взгляд на таблицу истинности показывает, что значение c не имеет значения, если оба a и b равны 0. Таким образом, первые две части можно свернуть, чтобы получить следующую дизъюнктивную форму: (больше не нормальный< /em> форма)

d = (!a & !b) v (!a & b & !c)

Это может стать еще короче, если вы примените дистрибутивность:

d = !a & (!b v (b & !c))

Почти сделано:

d = !a & (!b v b) & (!b v !c)   | applying (x v !x) == 1 and (1 & y) == y
  = !a & (!b v !c)              | applying De Morgan (!a v !b) == !(a & b)
  = !a & !(b & c)

Сделанный.

person Wormbo    schedule 03.06.2012

arrow_upward
1
arrow_downward

Как уже упоминалось ранее, вам следует взглянуть на карту Карно. проверьте это на википедии. На первый взгляд это может показаться немного сложным, но как только вы поймете, просто вывести оптимальное выражение для любой таблицы истинности.

На рисунке ниже показана карта Карно для данной таблицы истинности.

\ AB
C\  00  01  11  10
  \----------------
0 | 1 | 1 | 0 | 0 |
  |----------------
1 | 1 | 0 | 0 | 0 |
   ----------------

Первое, что вам нужно сделать при использовании Karnaugh, это скопировать таблицу истинности на карту. Я дам вам понять, как это сделать.

Следующий шаг — сгруппировать их, в статье в Википедии описано, как это сделать.

Наконец-то выработал решение

Из карты Карно видно, что вывод верен, когда (!A и !B) независимо от значения C, вывод также верен, когда (!A & B & !C).

Следовательно, функция может быть записана как: D = (!A & !B) ИЛИ (!A & B & !C)

альтернативное решение: D = (!A & !C) ИЛИ (!A & !B & C)

person praemdonck    schedule 06.06.2012