Слайд 2Метод Квайна
Способ представления функции в ДНФ или КНФ с минимальным количеством членов
![Метод Квайна Способ представления функции в ДНФ или КНФ с минимальным количеством](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/880449/slide-1.jpg)
и минимальным набором переменных.
Преобразование функции можно разделить на два этапа:
на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;
на втором этапе — переход от сокращённой формы к минимальной форме.
Слайд 3Первый этап (получение сокращённой формы)
![Первый этап (получение сокращённой формы)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/880449/slide-2.jpg)
Слайд 5Пример
Пусть есть таблица истинности:
![Пример Пусть есть таблица истинности:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/880449/slide-4.jpg)
Слайд 7Второй этап (табличный)
Рассмотренный выше пример уже удовлетворяет определению минимальной формы, однако далеко
![Второй этап (табличный) Рассмотренный выше пример уже удовлетворяет определению минимальной формы, однако](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/880449/slide-6.jpg)
не всегда после первого этапа сокращённая форма совпадает с минимальной.
Ещё могут оставаться члены, чьё удаление не изменяет конечный результат.
На данном этапе требуется удалить лишние переменные.
Слайд 10Обработка импликантной матрицы
Мы вновь получили дизъюнкцию простых импликант, на этот раз в
![Обработка импликантной матрицы Мы вновь получили дизъюнкцию простых импликант, на этот раз](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/880449/slide-9.jpg)
количестве пяти штук.
Чтобы получить минимальную форму, воспользуемся импликантной матрицей.
Столбцы в ней соответствуют членам СДНФ, а строки — членам сокращённой формы.
Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами:
Слайд 11Импликанты, не подлежащие исключению, образуют ядро.
Такие импликанты определяются по вышеуказанной матрице.
Для
![Импликанты, не подлежащие исключению, образуют ядро. Такие импликанты определяются по вышеуказанной матрице.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/880449/slide-10.jpg)
каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой.
Исключить все остальные члены сокращённой формы, однако, нельзя, так как это может привести к превращению какой-либо другой импликанты в нелишнюю.
Слайд 12Выбор остальных импликант, что войдут в минимальную форму, сводится к нахождению минимального
![Выбор остальных импликант, что войдут в минимальную форму, сводится к нахождению минимального](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/880449/slide-11.jpg)
набора неядровых импликант, которые покроют столбцы, не перекрываемые ядровыми.
Применительно к рассматриваемому случаю это будут третий и четвёртый столбец.
То, что можно исключить остальные импликанты, легко проверяется. На соответствующих наборах мы получаем значение 1, которая получается и на удалённых импликантах.