double arrow

Алгоритм метода Квайна

1) Провести все возможные склеивания минтермов, входящих в СДНФ функции. В результате образуются элементарные конъюнкции ранга (n-1).

2) Так как склеиваться могут только элементарные конъюнкции одного ранга, то в дальнейших склеиваниях минтермы не участвуют, поэтому следует выполнить операции поглощения.

3) Над полученными элементарными конъюнкциями ранга (n-1) повторить операции склеивания и поглощения, образовав элементарные конъюнкции нижнего ранга, и т.д.

4) Процесс заканчивается, когда дальнейшее склеивание оказывается невозможным.

5) Оставшиеся в результате поглощения элементарные конъюнкции являются простыми импликантами функции, а дизъюнкция их есть сокращенная ДНФ функции.

Пример. Найти сокращенную ДНФ функции:

СДНФ функции

Приводим алгоритм метода:

Здесь \/ - отметка поглощения.

Сокращенная ДНФ функции:

Пример. Найти сокращенную ДНФ функции:

СДНФ функции

Проводим операции склеивания и поглощения:

Сокращенная ДНФ функции


Сейчас читают про: