Слайд 2Метод Квайна
Способ представления функции в ДНФ или КНФ с минимальным количеством членов
и минимальным набором переменных.
Преобразование функции можно разделить на два этапа:
на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;
на втором этапе — переход от сокращённой формы к минимальной форме.
Слайд 3Первый этап (получение сокращённой формы)
Слайд 5Пример
Пусть есть таблица истинности:
Слайд 7Второй этап (табличный)
Рассмотренный выше пример уже удовлетворяет определению минимальной формы, однако далеко
не всегда после первого этапа сокращённая форма совпадает с минимальной.
Ещё могут оставаться члены, чьё удаление не изменяет конечный результат.
На данном этапе требуется удалить лишние переменные.
Слайд 10Обработка импликантной матрицы
Мы вновь получили дизъюнкцию простых импликант, на этот раз в
количестве пяти штук.
Чтобы получить минимальную форму, воспользуемся импликантной матрицей.
Столбцы в ней соответствуют членам СДНФ, а строки — членам сокращённой формы.
Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами:
Слайд 11Импликанты, не подлежащие исключению, образуют ядро.
Такие импликанты определяются по вышеуказанной матрице.
Для
каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой.
Исключить все остальные члены сокращённой формы, однако, нельзя, так как это может привести к превращению какой-либо другой импликанты в нелишнюю.
Слайд 12Выбор остальных импликант, что войдут в минимальную форму, сводится к нахождению минимального
набора неядровых импликант, которые покроют столбцы, не перекрываемые ядровыми.
Применительно к рассматриваемому случаю это будут третий и четвёртый столбец.
То, что можно исключить остальные импликанты, легко проверяется. На соответствующих наборах мы получаем значение 1, которая получается и на удалённых импликантах.