9.2.1. ТАБЛИЦА КАРНО

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

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

Таблица 9.4 (см. скан) Таблица истинности для функции И

Таблица 9.5 (см. скан) Таблица Карно для функции И

Таблица Карно является лишь упрощенной формой записи таблицы истинности, поэтому, на ее основании можно

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

Таблица 9.6 (см. скан) Таблица истинности и соответстиующаи ей таблица Карио

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

Для ячейки, расположенной правее, следует записать

Когда наконец будет составлена логическая сумма всех произведений, помимо других в ней встретится и такой фрагмент:

Он упрощается следующим образом:

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

Таким образом, в этом примере логическое произведение для группы В, состоящей из двух ячеек, равно

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

Для столбца состоящего из четырех ячеек, можно записать

Для контура С, имеющего квадратную форму и состоящего также из четырех элементов, получим следующее логическое произведение:

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

Для дизъюнктивной нормальной формы сразу найдем максимально упрощенный результат: