7-Тема. Практическое занятие

7-Тема. Практическое занятие.
БУЛЕВЫ ФУНКЦИИ. УПРОЩЕНИЕ ВЫРАЖЕНИЙ БУЛЕВЫХ ФУНКЦИЙ. КАРТА КАРНО

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

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

).
Это выражение — дизъюнктивная нормальная форма. Его можно упростить следующим образом:


= по законам коммутативности
и ассоциативности


—по закону дистрибутивности
= так как

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

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

В случае булевых функций трех переменных , и карта Карно представляет собой таблицу с двумя строками и четырьмя столбца­ми (рис. 7.2). Столбцы обозначены дизъюнкциями, которые можно получить из двух переменных и и их отрицаний, а строки — переменной и ее отрицанием .