20
правок
Изменения
Нет описания правки
=== Визуализация гиперкубами ===
[[Файл:Гиперкуб.PNG||right|рис. 1]]
Этот способ работает при количестве переменных не больше трёх (в противном необходимо вводить четвёртое или следующие за ним измерения для представления фигур).
Сначала мы рисуем куб в системе отсчёта Oxyz (названия координатных осей соответствуют названиям переменных). Затем каждую вершину обрабатываем следующим образом:
*В противном случае мы помещаем в вершину закрашенный белый кружок.
Например, для такой ДНФ: <tex>(X \wedge \neg Y \wedge Z) \vee (X \wedge Y \wedge Z) \vee (\neg X \wedge Y \wedge Z) \vee (\neg X \wedge Y \wedge \neg Z) \vee ( X \wedge Y \wedge \neg Z)</tex> мы получим следующий гиперкуб (риссм. 1рисунок)
Далее обработка гиперкуба идёт следующим образом:
пока у нас есть незакрашенные вершины, мы выбираем грань, либо вершину, либо ребро, на которых больше всего закрашенных чёрным вершин и ещё не обработанных вершин.
*Если множество элементарных конъюнкций длины n-1 не пусто, то выполняются шаги со второго для конъюнкций длины n-1 и т.д.
Алгоритм завершается, когда подмножество является пустым, либо нельзя выполнить ни одной операции неполного попарного склеивания.
После выполнения алгоритма будет получена сокращенная минимальная форма.
Переход от сокращённой формы к минимальной осуществляется с помощью импликантной матрицыспециальной таблицы.Члены СДНФ заданной функции вписываются в столбцы, а в строки — простые импликанты, то есть члены сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантамиэлементами сокращённой формы.
Для получения минимальной формы достаточно выбрать из членов сокращённой формы, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих членов, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра.
Рассмотрим метод Квайна на примере:
Функция от четырёх аргументов задана следующей таблицей:
{|border="1"
|Набор <tex>xyzw</tex>
|-
|}
Проведём операции неполного склеивания и поглощения:
{|border="1"
|-
|}
{|border="1"
|-
|}
На данном шаге все импликанты участвовали в операциях попарного неполного склеивания и были поглощены своими собственными частями. Поэтому простые импликанты на этом шаге не получены.
{|border="1"
|-
|}
{|border="1"
|-
|}
На данном этапе получаем простые импликанты <tex>\neg x \land \neg z \land \neg w</tex> и <tex>y \land \neg z \land \neg w</tex>
{|border="1"
|-
|}
Обе из элементарных конъюнкций на данном шаге являются простыми импликантами.
В результате выполнения алгоритма мы получаем следующую сокращённую ДНФ: <tex>(\neg x \land \neg z \land \neg w) \lor (y \land \neg z \land \neg w) \lor (x \land z) \lor (x \land y) </tex>
Переход от сокращённой формы к минимальной:
*Единицы ДНФ, покрываемые импликантами обозначаются "+". Импликанты, попадающие в ядро помечаются "*".
*Единицы функции, которые покрываются только какой-то одной импликантой из системы простых импликант, помечаются “>”.
*Единицы функции, покрываемые ядром, но не покрываемые только какой-то одной импликантой из системы простых импликант, помечаются “>>”.
{|border="1"
|}
На основе этой таблицы получим ядро <tex>(\neg x \land \neg z \land \neg w) \lor (x \land z) \lor (x \land y) </tex>, которое является также и минимальной ДНФ.
