Карты Карно

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

Карта Карно для n переменных служит эффективным средством иллюстративного представления n-куба. Она содержит 2ⁿ ячеек, каждая из которых соответствует одной из 2ⁿ возможных комбинаций значений п логических переменных х₁, х₂, ..., x_п.

Карта строится в виде матрицы размера 2^п-1 на 2^k так, что ее столбцы соответствуют значениям переменных х₁, х₂, ..., x_k, строки — значениям переменных х_k+1, х_k+2, ..., x_п, а соседние ячейки (как по вертикали, так и по горизонтали) отличаются только значением одной переменной.

	00…0	00…1	…xk+1…xk…	10…0
00…0
00…1
xk+1…xk
10…0

На рис. 6.6 приведены карты Карно для функций трех и четырех переменных соответственно. В этих картах все ячейки, отмеченные скобкой x_i (по строке и столбцу), представляют входные комбинации с х_i = 1, а в неотмеченных строках и столбцах ячейки соответствуют комбинациям с х_i = 0 (см. рис- 6.6 а, на котором разными способами изображена одна и та же карта).

Пример. На рис. 6.6а ячейка а соответствует набора 001 значений переменных х₁, х₂, х₃. Отметим, что для каждой функции может быть построено несколько различных карт. На рис. 6.6б изображены две карты Карно для функции четырех переменных. Первая карта соответствует разбиению переменных {{х₁, х₂}, { х₃, х₄ }}, а вторая — {{ х₁}, { х₂, х₃, х₄ }}.

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

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

На рис. 6.7 изображена карта, представляющая булеву функцию f(x,y z) , для которой

f(0,0,0) = f(1,1,0) = f(1,1,1) = f(1,0,1)= 0,

f(0,1,0) = f(1,0,0)= f(0,0,1) = f(0,1,1) = 1.

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

Пример 6.7.1. Точки b и с на рис. 6.6б лежат в 1-кубе, который определяет конъюнкт . Точки {d,е,f,g} образуют 2-куб, представляющий импликанту х₁ х₄.

Определение простых импликант функции сводится к нахождению всех k-кубов, которые не содержатся в кубах более высокого порядка.

Пример 6.7.2. Простые импликанты для карты Карно, приведенной на рис. 6.7, равны , , .

18

03.07.2025