2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Составить и упростить СДНФ и СКНФ
Сообщение06.06.2013, 13:57 
Аватара пользователя
Доброго времени суток.
Прошу совета - верно ли я всё делаю.
Имею задание по Схемотехнике, составить по таблице истинности СДНФ и СКНФ и упростить их.
В дальнейшем по этому необходимо строить цифровые схемы, поэтому желательно не использовать "Исключающее ИЛИ"/"Сложение по модулю 2".

Таблица истинности:
Изображение
1. Составим СДНФ. Берем те строки, где функция равна 1 и пишем в виде дизъюнкции полных совершенных конъюнкций (тобишь в виде сложения произведений).
СДНФ:$ \bar D \bar C \bar B \bar A + \bar D \bar C B \bar A + \bar D \bar C B A + \bar D C \bar B \bar A + \bar D C \bar B A + D \bar C \bar B A + D \bar C B A + D C \bar B A + D C B \bar A + D C B A$

2. Упростим СДНФ.
$\bar D \bar  C \bar A (\bar B + B)+ \bar D C \bar B (\bar A + A) + D \bar C A (\bar B + B) + D C A (\bar B + B) + \bar D \bar C B A + D C B \bar A$ равно
$\bar D \bar C \bar A + \bar D C \bar B + D \bar C A + D C A + \bar D \bar  C B A + D C B \bar A$

Далее
$\bar D \bar C \bar A + \bar D C \bar B + D A (\bar C + C) + \bar D \bar C B A + D C B \bar A$ равно $\bar D \bar C \bar A + \bar D C \bar B + D A + \bar D \bar C B A + D C B \bar A$

И наконец
$\bar D \bar C (\bar A + AB) + \bar D C \bar B + D (A + \bar A C B)$ равно $\bar D \bar C \bar A + \bar D \bar C B + \bar D C \bar B + D A + D C B$

Проверяем программой Logisim:
Изображение
Всё правильно, всё совпало.


3. Составим СКНФ. Берем те строки, где функция равна 0 и пишем в виде произведения сумм, инвертируя переменные. Если 0 - то обычная, если 1 то отрицание.
СКНФ: $(D+C+B+\bar A)\cdot(D+\bar C +\bar B + A)\cdot(D + \bar C +\bar B + \bar A)\cdot(\bar D + C + B +A)\cdot(\bar D + C + \bar B + A)\cdot(\bar D + \bar C + B + A)

4. Упростим СКНФ

$(D+C+B+\bar A)\cdot(D+\bar C+\bar B)\cdot(\bar D+C+B+A)\cdot(\bar D+C+\bar B+A)\cdot(\bar D+\bar C+B+A)$ равно
$(D+C+B+\bar A)\cdot(D+\bar C+\bar B)\cdot(\bar D+C+A)\cdot(\bar D+\bar C+B+A)$ и это равно
$(D+C+B+\bar A)\cdot(D+\bar C+\bar B)\cdot(\bar D+CB+A)$

Где ошибка? Мне сказали, что они должны сойтись, но они не сходятся. В получении и упрощении СДНФ я уверен, в получении СКФН тоже, а вот в упрощении СКНФ - большие сомнения.

Карты Карно не изучались.
Для проверки использую программу Logisim (построение цифровых схем).
Судя по всему, она считает СДНФ и СКНФ по Карно.
Но как добиться того же чисто аналитически? Используя формулы.
Изображение
СДНФ совпало полностью, а вот СКНФ частично - только первые две скобки совпали.

Как аналитически получить СКНФ, как в программе Logisim? и должны ли СДНФ и СКНФ после упрощения "совпасть"?

Или я может чего не так понял? Как бы вы получили и упростили СКНФ?

 
 
 
 Re: Составить и упростить СДНФ и СКНФ
Сообщение06.06.2013, 16:13 
Аватара пользователя
Так разложите обратно, если нужно именно КНФ в итоге.
$(\bar{D} + CB + A) = (\bar{D} + C + A)(\bar{D} + B + A)$

 
 
 
 Re: Составить и упростить СДНФ и СКНФ
Сообщение06.06.2013, 16:40 
Аватара пользователя
Xaositect
О, не знал, что так можно! Спасибо! Это по какому правилу? Поглощение?
Что нужно в итоге - в задании не написано, сказано просто максимально упростить.

А по поводу "СКНФ и СДНФ должны совпасть" можете что-либо сказать? По идее СДНФ и СКНФ это формы одной и той же функции, значит должны как-то совпадать. Я пытался, например, взять двойное отрицание над СКНФ и получить что-то похожее на СДНФ, но не вышло.

 
 
 
 Re: Составить и упростить СДНФ и СКНФ
Сообщение06.06.2013, 16:43 
Аватара пользователя
Izderevny в сообщении #733567 писал(а):
О, не знал, что так можно! Спасибо! Это по какому правилу? Поглощение?
Это я не знаю, как называется, но $(x + y)(x + z) = xx + xy + xz + yz = x + yz$ (в конце поглощение).

Остальное зависит от того, что понимать под словом "упрощение". Например, можно просто раскрыть все скобки в СКНФ и получить ДНФ.

 
 
 
 Posted automatically
Сообщение06.06.2013, 17:37 
Аватара пользователя
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Izderevny, наберите формулы $\TeX$ом, а картинки с формулами уберите (картинки с таблицами оставьте). Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
вернул

 
 
 
 Re: Составить и упростить СДНФ и СКНФ
Сообщение06.06.2013, 19:30 
Аватара пользователя
Спасибо за объяснения, всё верно.

 
 
 
 Re: Составить и упростить СДНФ и СКНФ
Сообщение12.05.2014, 10:58 
Просматривала ход решения ТС и для себя не поняла одно
Почему $(\bar A + AB)=\bar A +B$
Куда девается эта самая А и по какому закону логики.
Помогите пожалуйста новичку, потому как мозг уже кипит...

Заранее благодарна

 
 
 
 Re: Составить и упростить СДНФ и СКНФ
Сообщение12.05.2014, 11:25 
Само соотношение можно просто проверить перебором логических значений $A,B$.
Можно так: $\bar A\vee B = \bar A\vee ((\bar A\vee A)\wedge B) = ...$, дальше раскройте скобки, приведите подобные иным образом, чем было и увидите.

 
 
 
 Re: Составить и упростить СДНФ и СКНФ
Сообщение12.05.2014, 11:40 
Или воспользоваться дистрибутивностью дизъюнкции относительно конъюнкции.

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group