Минимизация ДНФ методом Квайна

Содержание

Слайд 2

Метод Квайна

Способ представления функции в ДНФ или КНФ с минимальным количеством членов

Метод Квайна Способ представления функции в ДНФ или КНФ с минимальным количеством
и минимальным набором переменных.
Преобразование функции можно разделить на два этапа:
на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;
на втором этапе — переход от сокращённой формы к минимальной форме.

Слайд 3

Первый этап (получение сокращённой формы)

Первый этап (получение сокращённой формы)

Слайд 4

Получение сокращённой формы

Получение сокращённой формы

Слайд 5

Пример

Пусть есть таблица истинности:

Пример Пусть есть таблица истинности:

Слайд 6

Результаты упрощения

Результаты упрощения

Слайд 7

Второй этап (табличный)

Рассмотренный выше пример уже удовлетворяет определению минимальной формы, однако далеко

Второй этап (табличный) Рассмотренный выше пример уже удовлетворяет определению минимальной формы, однако
не всегда после первого этапа сокращённая форма совпадает с минимальной.
Ещё могут оставаться члены, чьё удаление не изменяет конечный результат.
На данном этапе требуется удалить лишние переменные.

Слайд 8

Пример

Пример

Слайд 9

Получение СДНФ

Получение СДНФ

Слайд 10

Обработка импликантной матрицы

Мы вновь получили дизъюнкцию простых импликант, на этот раз в

Обработка импликантной матрицы Мы вновь получили дизъюнкцию простых импликант, на этот раз
количестве пяти штук.
Чтобы получить минимальную форму, воспользуемся импликантной матрицей.
Столбцы в ней соответствуют членам СДНФ, а строки — членам сокращённой формы.
Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами:

Слайд 11

Импликанты, не подлежащие исключению, образуют ядро.
Такие импликанты определяются по вышеуказанной матрице.
Для

Импликанты, не подлежащие исключению, образуют ядро. Такие импликанты определяются по вышеуказанной матрице.
каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой.
Исключить все остальные члены сокращённой формы, однако, нельзя, так как это может привести к превращению какой-либо другой импликанты в нелишнюю.

Слайд 12

Выбор остальных импликант, что войдут в минимальную форму, сводится к нахождению минимального

Выбор остальных импликант, что войдут в минимальную форму, сводится к нахождению минимального
набора неядровых импликант, которые покроют столбцы, не перекрываемые ядровыми.
Применительно к рассматриваемому случаю это будут третий и четвёртый столбец.
То, что можно исключить остальные импликанты, легко проверяется. На соответствующих наборах мы получаем значение 1, которая получается и на удалённых импликантах.
Имя файла: Минимизация-ДНФ-методом-Квайна.pptx
Количество просмотров: 40
Количество скачиваний: 0