Метод карт Карно для нахождения минимальной ДНФ

n = 4

Карта Карно – плоскостная интерпретация 4-мерного булева куба.

00

Считаем, что левый край склеен с правым, а верхний – с нижним.

Если таблицу Карно свернуть таким образом, то получится тор (torus - геометрическая фигура, напоминающая бублик).

Правила поиска интервалов.

1. Интервалом ранга 1 могут быть 2 соседних строки (2 соседних столбца)

2. Интервалом ранга 2 может быть вся строка, весь столбец или квадрат 2х2.

3. Интервалом ранга 3 – любые 2 соседние по горизонтали и вертикали клетки.

4. Одна отдельно взятая вершина будет интервалом ранга 4.

Алгоритм – тот же самый.

Лекция 6: «Метод Квайна – Мак-Клоски для нахождения минимальной ДНФ»

Этот метод удобен для нахождения минимальной ДНФ функции от любого числа переменных.

Определение. Элементарная конъюнкция K₁ покрывает ЭК K₂, если каждая переменная, входящая в K₁, входит и в K₂.

__ __ __

X₁X₃ – покрытие X₁X₂X₃X₄

N_k1 É  N_k2

K₂ = K₁K

K – конъюнкция из других переменных.

__ _ _ __ _ _

X₁X₃ V X₁X₂X₃X₄ = X₁X₃ (1 V X₂X₄) = X₁X₃ – поглощение

Склеивание двух ЭК

_

Kx V Kx = K

Идея метода Квайна (алгоритм)

1. Выписываются все элементарные конъюнкции из СДНФ функции.

2. Проводятся все возможные склеивания между этими ЭК. Полученные новые ЭК сохраняются вместе со старыми.

3. Между ними снова проводим все возможные склеивания до тех пор, пока это возможно. В результате среди ЭК появятся все простые импликанты функции.

4. Проводим поглощение между всеми получившимися ЭК, то есть оставляем только те ЭК, которые не покрываются никакими другими.

5. В результате получаются только простые импликанты. Их дизъюнкция является сокращенной ДНФ. Дальше все идет в соответствии с тривиальным алгоритмом минимизации.