Изменения

Перейти к: навигация, поиск

Сокращённая и минимальная ДНФ

329 байт добавлено, 07:15, 1 марта 2012
Нет описания правки
=== Карты Карно ===
Построим следующую таблицу <tex>n*\cdot n</tex>, где <tex>n</tex> {{---}} количество переменных:
{| border="1"
|
*Выполняются все возможные операции элементарного поглощения для элементарных конъюнкций длины n-1 (общая часть "p" имеет длину n-1)
*В результате получилось множество элементарных конъюнкций, разделяемых на два подмножества (по длине):
**подмножество элементарных конъюнкций длины <tex>n </tex> (оставшиеся)**подмножество элементарных конъюнкций длины <tex>n-1</tex>*Если множество элементарных конъюнкций длины <tex>n-1 </tex> не пусто, то заново выполняются операции неполного попарного склеивания и элементарного поглощения для конъюнкций длины <tex>n-1 </tex> и т.д.
Алгоритм завершается, когда подмножество является пустым, либо нельзя выполнить ни одной операции неполного попарного склеивания.
После выполнения алгоритма будет получена сокращенная минимальная форма.
|}
На данном шаге все элементарные конъюнкции элементы вида<tex>Ax</tex> или <tex>A \neg x</tex> участвовали в операциях попарного неполного склеивания и были поглощены своими собственными частями. Поэтому простые импликанты элементы сокращённой ДНФ на этом шаге не получены.
{|border="1"
|}
На данном этапе получаем простые импликанты элементы сокращённой ДНФ <tex>\neg x \land \neg z \land \neg w</tex> и <tex>y \land \neg z \land \neg w</tex>
{|border="1"
|-
|}
Обе из элементарных конъюнкций элементарные конъюнкции на данном шаге являются простыми импликантамиэлементами сокращённой ДНФ.
В результате выполнения алгоритма мы получаем следующую сокращённую ДНФ: <tex>(\neg x \land \neg z \land \neg w) \lor (y \land \neg z \land \neg w) \lor (x \land z) \lor (x \land y) </tex>
Переход от сокращённой формы к минимальной:
*Единицы ДНФ, покрываемые элементарными конъюнкциями элементами <tex>Ax</tex> или <tex>A \neg x</tex> обозначаются "+". КонъюнктыПары <tex>Ax</tex> и <tex>A \neg x</tex>, попадающие в ядро помечаются "*".*Единицы функции, которые покрываются только каким-то одним конъюнктом из системы простых импликантэлементов сокращённой ДНФ, помечаются “>”.*Единицы функции, покрываемые ядром, но не покрываемые только каким-то одним конъюнктом из системы простых импликант, элементов сокращённой ДНФ помечаются “>>”.
{|border="1"
<references/>
*[http://ru.wikipedia.org/wiki/%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%9A%D1%83%D0%B0%D0%B9%D0%BD%D0%B0 Минимизация логических функций методом Куайна — Википедия]
*[http://matrixcalc.org/pf1.htmlМетод Квайна]
*[http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%B0%D1%80%D0%BD%D0%BE Карта Карно — Википедия]
*[http://vuz.exponenta.ru/PDF/book/kv.htmlМинимизация булевых функций в классе ДНФ]*[http://tablica-istinnosti.ru/minimizatsiya-dnf-metodom-kvayna.htmlМинимизация ДНФ методом Квайна]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции ]]
20
правок

Навигация