Как сократить логическое утверждение?

Question

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

Учитывая заявление:( a OR b OR d ) И ( a OR c )

Я почти уверен, что это можно сократить до:( а ИЛИ b ИЛИ d ИЛИ c )

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

Может быть, это была серия логических таблиц?

Answer 1

Вы не можете уменьшить "(a OR b OR d) AND (a OR c)" до "(a OR b OR d OR c)", потому что первое не удовлетворяется "c=true, a,b,d=false" , тогда как последнее есть.Так что вы тоже не сможете доказать правильность сокращения :)

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

Answer 2

Карты Карно?Сокращение логических выражений?

Answer 3

Карта Карно здесь ваш друг:

http://en.wikipedia.org/wiki/Karnaugh_map

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

Answer 4

Карты Карно, ключевой момент заключается в том, чтобы «нарисовать» все возможные входные данные и указать их выходные данные.Затем вы можете начать фильтровать входные данные, которые не влияют на выходные данные, тем самым уменьшая карту.Как только он будет оптимизирован, вы сможете создавать на его основе свою логику.

Answer 5

( a OR b OR d ) И ( a OR c )

Это означает, что когда а верно, все верно!

=> a OR { (b OR d) AND (c) }

=> a ИЛИ ( b И C) ИЛИ ( d и C )

Я думаю, что результат (a OR b OR d OR c) неправильный, но помогите мне, если он неправильный.

Answer 6

а или {(б ИЛИ d) И с}

Аргументация:Если «а», то утверждение верно.в противном случае вам понадобится b или d (чтобы удовлетворить первую часть оператора) и c (удовлетворит вторую половину для случаев, когда !a

Answer 7

С использованием Карты Карно:

Это ИЛИ b ИЛИ d:

 \ab
cd\ 00 01 11 10
---+-----------+
00 |  | X| X| X|
01 | X| X| X| X|
11 | X| X| X| X|
10 |  | X| X| X|
   +-----------+

Это ИЛИ c:

 \ab
cd\ 00 01 11 10
---+-----------+
00 |  |  | X| X|
01 |  |  | X| X|
11 | X| X| X| X|
10 | X| X| X| X|
   +-----------+

Пересекая их, получаем:

 \ab
cd\ 00 01 11 10
---+-----------+
00 |  |  | X| X|
01 |  |  | X| X|
11 | X| X| X| X|
10 |  | X| X| X|
   +-----------+

Очевидно, это ИЛИ (что-то), где (что-то) есть:

    00 01
11 | X| X|
10 |  | X|

Поскольку (что-то) не является прямоугольником, для него требуются два выражения, которые могут быть объединены либо оператором И, либо ИЛИ, в зависимости от того, как мы хотим к этому подойти.В этом примере мы будем использовать OR, поскольку оно дает более простое выражение.

В этом случае мы можем сгруппировать два X рядом друг с другом, добавив еще два, чтобы заполнить всю строку cd, чтобы cd мог быть одним из выражений.Мы также можем сгруппировать их друг над другом так, чтобы двое находились справа от них, чтобы сформировать квадрат.Этот квадрат представляет собой выражение bc, поскольку и a, и d изменяются в пределах квадрата.

Итак, окончательное выражение a ИЛИ ((c И d) ИЛИ (b И d)), или а + компакт-диск + др.Гораздо приятнее, не так ли?

Answer 8

Минимальная форма СОП:

y = a | b&c | c&d;

POS имеют одинаковую стоимость (количество вентилей для реализации логической схемы):

y = (a|c)&(a|b|d);

Answer 9

Да, вы можете это доказать.Вы не можете уменьшить его до (a OR b OR d OR c)

Посмотрите на третью строку ниже.Ваше сокращение не сможет дать правильный ответ.

Просто запустите его:

А Б В Г
0 0 0 0 = 0
0 0 0 1 = 0
0 0 1 0 = 0
.
.
.
1 0 0 0 = 1
1 0 0 1 = 1

Пока что у меня есть (A OR (???)) :(