Теорема. Любая булева функция, не являющаяся константой 0 представима в виде сокращенной ДНФ.
Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет таблицы истинности. Если из сокращенной ДНФ удалить все лишние импликанты, то получается ДНФ, называемая тупиковой.
Заметим, что представление функции в виде тупиковой ДНФ в общем случае неоднозначно.
Выбор из всех тупиковых форм формы с наименьшим числом вхождений переменных дает минимальную ДНФ (МНДФ).
Теорема(теорема Квайна). Если исходя из совершенной ДНФ функции произвести все возможные операции неполного склеивания, а затем элементарного поглощения, то в результате получится сокращенная ДНФ, т. е. дизъюнкция всех простых импликант.
Для получения минимальной ДНФ из сокращенной ДНФ используется матрица Квайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк - простые импликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца.
В тупиковую ДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет все контитуенты единицы, т. е. каждый столбец матрицы Квайна содержит звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. В качестве минимальной ДНФ выбирается тупиковая, имеющая наименьшее число вхождений переменных.
В силу принципа двойственности для булевых алгебр все приведенные понятия и рассуждения очевидным образом можно преобразовать для нахождения минимальных конъюнктивных нормальных форм (МКНФ).
Содержание
1.Постановка задачи
2.Теоретическое описание метода минимизации
3.Краткое описание Maple
4.Краткий обзор пакета Logic
5.Подробное описание функций, используемых в данной работе
6.Минимизация переключательной функции средствами Maple
7.Вывод
8.Заключение
9.Список литературы
1. Берман Г.Н. Сборник задач по курсу математического анализа: Учебное
пособие lдля вузов. -20-е изд. М.: НАУКА. Главная редакция физико
математической литературы, 1985. 384 с.
2. Самоучитель по Maple: www.computerbooks.ru\books\Mathematic\Book-Maple.
3. Справочные материалы математического пакета MAPLE 12.
гда можно добиться, выбрав правильный масштаб целевой функции при условии, что исходные значения коэффициентов заданы рациональными числами).Модели распределения капиталовложений часто можно представи
Курсовая
2006
29
Харьковский Национальный Университет Радиоэлектроники
тодом условного градиента, взяв в качестве начального приближения точку.б) Найти точное решение оптимизационной задачиграфоаналитическим методом и её приближённое решение методом отсекающих плоскостей
Курсовая
2006
36
Харьковский Национальный Университет Радиоэлектроники
ое должно отобразить на экранной форме заданную систему булевых уравнений; предоставляя пользователю самому задавать значение каждой функции, находить все ее решения.В основу алгоритма положим 2-й спо
афоаналитический метод - метод решения задачи условной оптимизации. В теоретической части представлена суть метода Розена, а также основные расчетные формулы. В вычислительной части приведен пример ре
Курсовая
2006
29
Харьковский Национальный Университет Радиоэлектроники
Главная