Программа минимизации ДНФ - Помощь студентам

arris90 · 06.04.2011, 00:03

Здравствуйте товарищи! Есть такая проблема в качестве диплома дали задание написать программу, по минимизации ДНФ(Дизъюнктивно Нормальной Формы), программа должна минимизировать любой введенный днф до 20 переменных. но ладно дело написать программу еще смогу, но сам алгоритм программы я не знаю как написать... Не могу себе представить в программном виде это... Очень большая просьба помочь с этим... Так же еще сказано что то про решение "тупиковых" днф. если что есть скайп arrissss90

Mandrivnyk · 06.04.2011, 00:25

Минимизация систем полностью определенных булевых функций может производиться по алгоритму, аналогичному алгоритму метода Квайна с небольшими отличиями. Алгоритм минимизации следующий:
1) Построить полное множество А элементарных конъюнкций минимизируемой системы функций, считая, что вначале каждая из функций системы представлена в СДНФ. Каждой конституенте единицы множества А присвоить признак, содержащий номера функций системы, в которые входит рассматриваемая конституента.
2) Произвести минимизацию СДНФ функции f, конституентами единицы которой являются все элементы множества A. При выполнении склеивания двух конституент единицы каждой вновь образуемой элементарной конъюнкции присвоить признак, состоящий из номеров функций, общих для двух склеиваемых конституент единицы. Последнее справедливо и для двух склеиваемых элементарных конъюнкций с признаками. Если признаки склеиваемых конституент единицы не содержат общих номеров, то склеивание не производится. Поглощение производится только для элементарных конъюнкций с одинаковыми признаками. Полученные в результате склеивания и поглощения конъюнкции называются простыми импликантами системы функций.
3) Построить импликантную матрицу функции f, аналогичную матрице Квайна с той разницей, что для каждой конституенты единицы выделяется столько столбцов, сколько различных номеров функций со- держит ее признак. Покрытие матрицы импликантами производится аналогично методу Квайна.

arris90 · 08.04.2011, 20:37

Тогда еще парочка вопросов, просьба ответить понятливо, ибо в интернете об этом написано очень заумно.
1)Что такое операция удаления элементарной конъюнкции?
2)Что такое операция удаления буквы? как это происходит?
3)Как проверить эквивалентность начальной и конечной(минимизированной) ДНФ?
ПС. очень прошу о помощи.

Вадим Мошев · 08.04.2011, 20:47

Цитата:

3)Как проверить эквивалентность начальной и конечной(минимизированной) ДНФ?

Просто составьте таблицу истинности для исходной и полученной ДНФ, если на всех двоичных наборах значения функции совпадают, то они эквивалентны.

06.04.2011, 00:03	#1
arris90 Новичок Джуниор Регистрация: 05.04.2011 Сообщений: 2	Программа минимизации ДНФ Здравствуйте товарищи! Есть такая проблема в качестве диплома дали задание написать программу, по минимизации ДНФ(Дизъюнктивно Нормальной Формы), программа должна минимизировать любой введенный днф до 20 переменных. но ладно дело написать программу еще смогу, но сам алгоритм программы я не знаю как написать... Не могу себе представить в программном виде это... Очень большая просьба помочь с этим... Так же еще сказано что то про решение "тупиковых" днф. если что есть скайп arrissss90

06.04.2011, 00:25	#2
Mandrivnyk Software Developer Участник клуба Регистрация: 01.03.2011 Сообщений: 1,098	Минимизация систем полностью определенных булевых функций может производиться по алгоритму, аналогичному алгоритму метода Квайна с небольшими отличиями. Алгоритм минимизации следующий: 1) Построить полное множество А элементарных конъюнкций минимизируемой системы функций, считая, что вначале каждая из функций системы представлена в СДНФ. Каждой конституенте единицы множества А присвоить признак, содержащий номера функций системы, в которые входит рассматриваемая конституента. 2) Произвести минимизацию СДНФ функции f, конституентами единицы которой являются все элементы множества A. При выполнении склеивания двух конституент единицы каждой вновь образуемой элементарной конъюнкции присвоить признак, состоящий из номеров функций, общих для двух склеиваемых конституент единицы. Последнее справедливо и для двух склеиваемых элементарных конъюнкций с признаками. Если признаки склеиваемых конституент единицы не содержат общих номеров, то склеивание не производится. Поглощение производится только для элементарных конъюнкций с одинаковыми признаками. Полученные в результате склеивания и поглощения конъюнкции называются простыми импликантами системы функций. 3) Построить импликантную матрицу функции f, аналогичную матрице Квайна с той разницей, что для каждой конституенты единицы выделяется столько столбцов, сколько различных номеров функций со- держит ее признак. Покрытие матрицы импликантами производится аналогично методу Квайна. Болтовня ничего не стоит. Покажите мне код. (c) Linus Torvalds Помог ответ? -- Поставьте отзыв. Выражения особой благодарности в рублевом эквиваленте отправлять сюда --> R269634919062

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Выбрать оптимальный тарифный план с точки зрения минимизации затрат (Паскаль)	ZavriK	Паскаль, Turbo Pascal, PascalABC.NET	2	05.04.2011 07:59
Задача минимизации дисбаланса на линии сборки (задача минимакса)	LenZab	Microsoft Office Excel	13	13.03.2011 22:51
сравнение двух днф	Zln	Помощь студентам	0	11.05.2010 16:42

08.04.2011, 20:37	#3
arris90 Новичок Джуниор Регистрация: 05.04.2011 Сообщений: 2	Тогда еще парочка вопросов, просьба ответить понятливо, ибо в интернете об этом написано очень заумно. 1)Что такое операция удаления элементарной конъюнкции? 2)Что такое операция удаления буквы? как это происходит? 3)Как проверить эквивалентность начальной и конечной(минимизированной) ДНФ? ПС. очень прошу о помощи.