5.2 Карта Карно

Мы показали, что любую булеву функцию можно выразить в дизъюнктивной нормальной форме. Однако получаемые выражения довольно громоздки. Здесь мы попытаемся решить задачу об «упрощении» выражения для булевой функции. Под «упрощением» мы подразумеваем эквивалентное выражение, использующее меньше символов, чем исходное. Для этого используются карты Карно – наглядные схемы, предназначенные для обнаружения пар минтермов, которые можно сгруппировать и преобразовать в одно простое выражение.

Рассмотрим n булевых переменных p1,p2,…,pn. Для них существует 2n различных элементарных конъюнкций. Например, для двух булевых переменных р и q элементарными конъюнкциями будут p q , p q , p q ,

p q . Карта Карно — это таблица, каждый элемент которой является

элементарной конъюнкцией. Для переменных р и q карта Карно имеет вид, изображенный на следующем рисунке слева

На правой схеме мы для наглядности внутри ячеек представили соответствующие им элементарные конъюнкции.

Для представления картой Карно булевой функции, записанной в дизъюнктивной нормальной форме, необходимо поместить х (крестик) или 1 (единицу) в прямоугольниках, соответствующих элементарным конъюнкциям (минтермам), входящим в выражение. Например, высказыванию (p q) (~ p ~ q) соответствует карта Карно, изображенная

на следующем рисунке

Когда выражению соответствует карта Карно с двумя соседствующими в строке или в столбце крестиками, тогда его можно упростить, сведя две элементарные конъюнкции к одной, содержащей на одну компоненту меньше (т.е. либо р, либо q не будут присутствовать в выражении). Например, высказывание (p q) (p ~ q), которому соответствует карта

Карно, изображенная на следующем рисунке

эквивалентна p, так как

9

Для булевой функции трех переменных р, q и r карта Карно имеет следующий вид

На следующем рисунке для наглядности в прямоугольники мы вписали элементарные конъюнкции

Здесь ячейки карты Карно соответствуют восьми минтермам, которые можно построить из трех булевых переменных. Например, выражению

будет соответствовать карта Карно, показанная на следующем рисунке

Если два знака (крестика) соседствуют, две элементарные конъюнкции могут быть сведены к одной, содержащей на одну из компонент р, q и r меньше. В данном случае дизъюнкция пары элементарных конъюнкций

(p q ~ r) (~ p q ~ r)≡((q ~ r) p) ((q ~ r) ~ p)≡

≡(q ~ r) (p ~ p)≡ (q ~ r) T ≡ q ~ r

сводится к q ~ r , так что выражение принимает вид

.

Если четыре значка x расположены в прямоугольнике рядом

или

10

тогда четыре элементарные конъюнкции, отмеченные значками, могут быть сведены к одному члену, содержащему только одну из компонент р, q или r. Например, первая карта Карно представляет выражение

(p q r) (p q r) (p q r) (p q r),

которое сводится к ~r. Действительно

(p q r) (p q r) (p q r) (p q r)≡

≡(((p r) q) ((p r) q)) (((p r) q ) ((p r) q ))≡

≡((p r) (q q)) ((p r) (q q))≡

≡((p r) T ) ((p r) T )≡(p r) (p r)≡

≡(r p) (r p)≡ r (p p)≡ r

Вторая карта Карно представляет выражение

(p q r) (p q r) (p q r) (p q r)

которое может быть сведено к р. Действительно

(p q r) (p q r) (p q r) (p q r)≡

≡(((p q) r) ((p q) r)) (((p q) r) ((p q) r))≡

≡((p q) (r r)) ((p q) (r r))≡

≡((p q) T ) ((p q) T )≡(p q) (p q)≡

≡(p q) (p q)≡ p (q q)≡ p T ≡ p

Первый и последний столбец таблицы также считаются соседними (можно считать, что карта «скручена»). Например, карта Карно

представляет выражение (p q r) (p q r) (p q r) (p q r), которое может быть приведено к r. Действительно

(p q r) (p q r) (p q r) (p q r)≡

≡(((q r) p) ((q r) p)) (((q r) p) ((q r) p))≡

≡((q r) (p p)) ((q r) (p p))≡

≡((q r) T ) ((q r) T )≡(q r) (q r)≡

≡(r q) (r q)≡ r (q q)≡ r T ≡ r

Выражение

11

представляется следующей картой Карно

Четыре крестика в левых двух столбцах после упрощения дадут q, и выражение примет вид q (p ~ q ~ r). Благодаря наличию блока из двух

значков в середине первой строки, это выражение можно еще больше упростить, приведя к виду q (p ~ r). Действительно

q(p ~ q ~ r)≡ q (~ q (p ~ r))≡(q ~ q) (q (p ~ r))≡

≡T (q (p ~ r))≡ q (p ~ r)

Фактически в дизъюнкцию минтермов мы два раза включаем конъюнкцию p q ~ r . Это, очевидно, не меняет результата, но позволяет включить этот

минтерм в дизъюнкцию четырех минтермов в двух левых столбцах и в дизъюнкцию двух минтермов, соответствующих клеткам в середине первой строки. Дизъюнкция четырех минтермов упростилась до q, а двух – до p ~ r .

Для булевой функции четырех переменных также можно строить карты Карно и применять аналогичную технику упрощения булевых выражений. Проиллюстрируем этот процесс путем построения карты Карно для четырех булевых переменных р,q,r и s. Такая карта Карно может иметь следующий вид

Здесь в ячейки мы поместили элементарные конъюнкции, им соответствующие, а не крестики, как это следует делать для конкретного выражения. В качестве примера рассмотрим выражение

Размещая соответствующие значки в карте Карно, получаем

12

где вместо крестиков мы поместили в ячейки номера минтерма. Например, минтерм (1) – это p q r s , а минтерм (10) – это p ~ q r s . Все

булево выражение может быть представлено в виде дизъюнкции минтермов

(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)≡ ≡((1) (2) (3) (4) (5) (6) (7) (8)) ((1) (2) (9) (10)) ((10) (11))

Здесь во второй строке мы повторили минтермы (1), (2) и (10) и перегруппировали операнды. Очевидно, от этого булево выражение не изменилось. Но теперь видно, что минтермы (1) – (8) образуют восьмиячеечный блок (назовем его A), минтермы (1), (2), (9), (10) образуют четырехъячеечный блок (назовем его B) и минтермы (10) и (11) образуют двухъячеечный блок C. Тогда все булево выражение можно представить в виде A B C .

Для каждого блока нужно записать булево выражение. Восьмиячеечный блок представляется только одним из аргументов булевой функции. В данном случае блок A представляется переменной q. Четырехъячеечный блок можно описать, используя только две булевых переменные. В нашем случае четырехъячеечный блок B, составленный из ячеек верхней строки, можно описать выражением p s . Двухъячеечный

блок можно описать, используя три булевых переменные. В нашем случае для блока С, составленного из двух правых верхних ячеек, соответствующее выражение имеет вид p ~ q r . Следовательно, исходное высказывание

можно упростить и привести к виду q (p s) (p ~ q r). Для последних двух скобок имеем (p s) (p ~ q r)≡ p (s (~ q r)) и все выражение станет еще на один символ короче q (p (s (~ q r))).

Карту Карно для булевой функции четырех аргументов можно рассматривать как «скрученную» в обоих направлениях, т.е. следует считать, что первый и последний столбцы соседствуют, также как и первая и последняя строка прилегают друг к другу. Тогда, например, четырехъячеечный блок на следующей карте Карно

13