Как уменьшить логическое утверждение?
Я почти уверен, что могу вспомнить, что делал что-то подобное на одном из моих курсов на уровне колледжа, и что в этом была какая-то формула, но мой разум подводил меня к тому же.
Дано утверждение: (ИЛИ b ИЛИ d) И (ИЛИ c)
Я уверен, что это может быть уменьшено до: (ИЛИ b ИЛИ ИЛИ c)
Но я не могу вспомнить, как бы я это доказал.
Может быть, это была серия логических таблиц?
9 ответов
Вы не можете уменьшить "( a OR b OR d) и ( a OR c)" до "( a OR b OR d OR c)", поскольку первое не удовлетворено "c=true, a,b,d=false" тогда как последний есть. Таким образом, вы не можете доказать правильное сокращение:)
В общем, есть много способов уменьшить размер булевых формул, и это также вопрос того, что вы хотите оптимизировать (общий размер? Среднее количество оценок условий?). Карты Карно работают только для небольшого числа переменных. Сокращение больших булевых формул до более мелких - это сложная тема, которая является ключевой в, например, автоматическом проектировании логических схем.
Карта Карно - ваш друг здесь:
http://en.wikipedia.org/wiki/Karnaugh_map
Вам, скорее всего, придется построить его в обратном порядке по сравнению с приведенными выше уравнениями, но это хороший инструмент, чтобы сказать вам, можно ли его уменьшить еще больше.
Карты Карно, ключ заключается в том, чтобы "нарисовать" все возможные входные данные и указать их выходные данные. Затем вы можете начать отфильтровывать входные данные, которые не имеют значения для выходных данных, тем самым уменьшая карту. Как только он будет оптимизирован, вы сможете создать из него свою логику.
(ИЛИ b ИЛИ d) И (ИЛИ c)
Это означает, что когда a верно, все верно!
=> a ИЛИ { (b ИЛИ d) И (с)}
=> ИЛИ (В И С) ИЛИ (Д и С)
Я думаю, что результат (или ИЛИ ИЛИ ИЛИ ИЛИ) неверен, но помогите мне, если он неправильный.
СОП минимальная форма:
y = a | b&c | c&d;
POS имеют одинаковую стоимость (количество шлюзов для реализации логической схемы):
y = (a|c)&(a|b|d);
a или {(b ИЛИ d) И c}
Обоснование: если "а", то утверждение верно. иначе вам нужно b или d (чтобы удовлетворить первую часть утверждения) и c (удовлетворяет вторую половину для случаев, когда!a
Используя карты Карно:
Это ИЛИ b ИЛИ d:
\ аб кд \ 00 01 11 10 ---+-----------+ 00 | | X| X| X| 01 | X| X| X| X| 11 | X| X| X| X| 10 | | X| X| X| +-----------+
Это ИЛИ c:
\ аб кд \ 00 01 11 10 ---+-----------+ 00 | | | X| X| 01 | | | X| X| 11 | X| X| X| X| 10 | X| X| X| X| +-----------+
Пересекая их, мы получаем:
\ аб кд \ 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 |
Поскольку (что-то) не является прямоугольником, оно требует двух выражений, которые могут быть либо AND, либо OR вместе, в зависимости от того, как мы хотим приблизиться к нему. Мы будем использовать OR в этом примере, так как это дает более простое выражение.
В этом случае мы можем сгруппировать два X рядом друг с другом, добавив еще два, чтобы заполнить всю строку cd, поэтому cd может быть одним из выражений. Мы также можем сгруппировать два поверх друг друга с двумя справа от них, чтобы сформировать квадрат. Этот квадрат представляет выражение bc, так как a и d варьируются в пределах квадрата.
Таким образом, окончательное выражение - это OR ((c AND d) OR (b AND d)) или a + cd + bd. Намного лучше, не правда ли?
Да, вы можете доказать это. Вы не можете уменьшить его до (ИЛИ b ИЛИ ИЛИ c)
Посмотрите на 3-ю строку ниже. Ваше сокращение не сможет дать правильный ответ.
Просто пропустите это:
ABCD
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
Пока что у меня есть (ИЛИ (???)):(