Содержание
- 2. Метод Квайна Метод Квайна — способ представления функции в ДНФ или КНФ с минимальным количеством членов
- 3. Преобразование функции можно разделить на два этапа: на первом этапе осуществляется переход от канонической формы (СДНФ
- 4. Первый этап (получение сокращённой формы). Предположим, что заданная функция представлена в СДНФ. Выполним все возможные операции
- 5. а) Формула склеивания б) Формула неполного склеивания в) Формула поглощения
- 6. В результате СДНФ приводится к СкДНФ.
- 7. Минимальная форма формулы (МДНФ ) получается на основе импликантной матрицы путем нахождения минимального покрытия этой матрицы.
- 8. Импликанта – это элементарная конъюнкция СкДНФ. Конституента единицы – это элементарная конъюнкция СДНФ. Импликантная матрица –
- 9. Подмножество строк матрицы M является ее покрытием, если в подматрице, образованной этими строками нет нулевых столбцов.
- 10. Пример 1. Пусть
- 11. Тогда 1-я и 2-я строки не покрывают матрицу M: а 1-я и 3-я строки – являются
- 12. ПРИМЕР. Найдем МДНФ формулы:
- 13. Во-первых, осуществим всевозможные склеивания
- 14. В результате СкДНФ имеет вид:
- 15. А импликантная матрица имеет вид
- 16. По данной импликантной матрице можно выбрать следующие МДНФ
- 17. Метод минимизирующих карт. Алгоритм метода минимизирующих карт включает в себя следующие этапы: Вычеркнем из таблицы (минимизирующей
- 18. Отметим конъюнкции, оставшиеся единственными на строке. Вычеркнем строки, в которых присутствуют такие же конъюнкции. Всеми возможными
- 19. ПРИМЕР. Дана СДНФ
- 20. Для данной СДНФ таблица всевозможных сочетаний переменных (минимизирующая карта), имеет вид: * - помечены строки, не
- 21. Из таблицы вычеркнем те строки, которые не содержат конституенты СДНФ, а также конъюнкции этих строк, содержащиеся
- 22. В результате получим:
- 23. После всевозможного перебора остаются следующие МДНФ:
- 24. Метод минимизации с помощью карт Вейча.
- 25. Алгоритм метода карт Вейча включает в себя следующие этапы: Заданная формула приводится к СДНФ. Составляется карта
- 26. Единицы, стоящие по вертикали и горизонтали, объединяются (по 2 , по 4 , по 8 и
- 27. Карты Вейча удобны при поиске МДНФ функций двух, трех и четырех переменных.
- 28. Пример для n=2. Функция задана
- 30. Пример для n=3. Функция задана
- 31. Пример для n=4. Функция задана СДНФ
- 34. Скачать презентацию