Карты Карно. Построение МДНФ с помощью карт Карно

Карта Карно для n переменных содержит 2ⁿ ячеек, каждая из которых соответствует одной из возможных 2ⁿ комбинаций значений n логических переменных x₁,…,x_n. Карта строится в виде матрицы размера 2^n-k на 2^k так, что ее столбцы соответствуют значениям переменных x₁,…,x_k, строки – значениям переменных x_k+1,..,x_n, а соседние ячейки отличаются только значением одной переменной.

У каждой вершины n- куба есть ровно n смежных с ней вершин, т.е. вершин, отличающихся от нее только одной координатой. Поскольку в карте Карно каждая ячейка может иметь не более 4 ячеек, соседних по строке или столбцу, для представления точек, отличающихся только на одну координату, необходимо использовать и более удаленные ячейки.

Булева функция может быть представлена на карте Карно выделением 1-ячеек. Подразумевается, что необозначенные ячейки соответствуют 0-точкам.

Для построения импликант берутся всевозможные наборы 1-ячеек, образующих вершины некоторого k-куба (т.е. 2^k точек таких, что пары соседних отличаются ровно одной координатой). Совпадающие координаты образуют набор (δ₁,…,δ_n-k) и требуемая импликанта имеет вид , где x_j – переменная, соответствующая значению δ_j.

При наглядном размещении простых импликант в карте Карно удается непосредственно находить МДНФ, выбирая те простые импликанты, которые покрывают все единицы и имеют наименьшее возможное число вхождений переменных