Карты Карно

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

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

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

Чтобы представить БФ на карте, достаточно в те клетки, где функция имеет значение 1, поместить единицы. Тогда в остальных клетках будут содержаться нули. На рис. 2.3 изображена КК для БФ

.

Клетки, в которых записаны 1, называют р -клетками БФ, так как 1 представляет собой произведение всех переменных (некоторые могут быть с отрицанием). Две соседние единицы образуют одномерный р -подкуб (рис. 2.4). Этот одномерный р -подкуб может быть представлен простым произведением, содержащим одну переменную , так как два вхождения 1 в этом подкубе соответствуют и ; таким образом свойство поглощения + = проверено графически. На рис. 2.5 этот принцип применен к БФ от трех переменных, изображенной на рис. 2.3. В соответствии с тремя выделенными подкубами можно упростить БФ следующим образом:

.

В общем случае одномерный р -подкуб соответствует произведению, в котором всегда отсутствует одна переменная (или ее отрицание). Переменную, отсутствующую в произведении, также легко определить по карте, это будет та переменная, которая имеет различные значения для двух единиц соответствующего подкуба. Так, на рис. 2.5 в левом подкубе для левой единицы , а для правой единицы (отсутствует ), в правом подкубе для левой единицы , а для правой единицы (отсутствует ), в вертикальном подкубе для верхней единицы , а для нижней единицы (отсутствует ).

Четыре соседние единицы (рис. 2.6) называют двумерным р -подкубом; каждый из них соответствует произведению без двух переменных (во втором примере все четыре единицы являются соседними, так как карты, как пояснялось выше, можно сворачивать). Опущены те переменные, которые не сохраняют постоянное значение на этом подкубе. Аналогично трехмерные р -подкубы содержат восемь единиц (рис 2.7 ).

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

Принимая во внимание клетки КК, не содержащие единиц, и поступая с ними так же, как с клетками с единицами, можно представлять функции в КНФ. Пример подобного представления для БФ из рис. 2.5 приведен на рис. 2.8.

Таким образом, инверсию можно выразить как

.

На основе правила де Моргана функцию можно представить в виде .

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

Согласно договоренностям, принятым в разделе 1.3, безразличные комбинации будут обозначаться в КК символом d. В любые клетки, имеющие d, для увеличения размеров р -подкубов можно помещать единицы. На рис. 2.9 изображена КК для функции с безразличными значениями, заданной табл. 1.9. Доопределим ее (рис 2.10).

Так как данная БФ имеет три безразличных значения, ее можно доопределить восемью способами. Очевидно, что минимальный вид БФ принимает при доопределении всеми единицами (рис. 2.10, з).

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