4. Определение дополнения функции

Дополнение булева выражения может быть получено заменой переменной ее дополнением в соответствующем двойственном выражении. Например, для двойственная форма имеет вид

а дополнение или инверсия функции

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

Теперь рассмотрим базисные функции И или ИЛИ. Функция, двойственная по отношению к функции ,

.

Д ополнение функции получают заменой переменных их дополнениями в двойственной форме

.

Р ис. 1.15. Таблица истинности, подтверждающая, что является инверсией

Рис. 1.16. Дополняющие друг друга схемы.

Аналогично, функцию, двойственную по отношению к определяют как

,

и дополнение функции f имеет вид

.

Т аким образом дополнение функции И - это функция ИЛИ, операндами которой являются дополнения переменных, присутствующих в И; и наоборот, дополнение функции ИЛИ - это функция И, операндами которой являются дополнения переменных, присутствующих в ИЛИ. Процедура дополнения функций И и ИЛИ иллюстрируется с помощью электронных схем (рис. 1.17).

Рис. 1.17. Дополнения функций И и ИЛИ:

а - дополнение функции И; б - дополнение функции ИЛИ

Так как дополненной функции, f = АВ является функция и , то, следовательно,

.

Аналогично, поскольку дополнение f = A + B задаётся в виде и , то, следовательно,

.

Эти два выражения являются двумя формами теоремы де Моргана.

В более общем виде теорема, де Моргана записывается

Теоремы перестановки, сочетания и распределения

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

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

Теорема согласования

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

.

Значения f’ равны соответствующим значениям f для всех возможных комбинаций значении переменных А, В и С. Таблицы истинности для f и f' приведены на рис. 1.18. Просмотр столбцов таблицы для f и f' показывает, что значения этих функций идентичны для всех возможных значений переменных А, В и С.

Равенство f = f' может быть доказано и алгебраически:

,

однако и, следовательно,

.

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

Рис. 1.18. Доказательство теоремы согласования с помощью таблицы истинности

Например, для

терм согласования имеет вид АВ. Добавляя его к f, получаем .

Применяя теорему поглощения, устанавливаем, что терм лишний и что его можно исключить. Тогда .

Важно отметить, что длина терма АВ меньше длины удаленного терма .

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

5. Р - и S - термы. Канонические формы

Конъюнкцией (Р-термом) п переменных называется логическое произведение всех п переменных, в котором любая переменная может быть представлена также своим дополнением. В случае двух переменных А и В существуют четыре возможные комбинации переменных (рис. 2.1). Каждой такой комбинация соответствует свой Р-терм, который может быть получен следующим образом. Рассмотрим первую строку таблицы, представленной на рисунке. Для нее А = 0, В = 0 и, следовательно, . Искомый Р-терм формируем из таких значений переменных, которые делают значение Р-терма равным 1, следовательно, . Оставшиеся три Р-терма получаем тем же самым путем.

Рис. 2.1. P- и S-mepмы двух переменных

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

Так как и для А = 0 и В=0, то для А=0 и В=0. Таким образом, могут быть получены еще три S-терма. Для трех переменных А, В и С существует восемь возможных комбинаций переменных и, следовательно, существует восемь Р-термов и восемь S-термов. В случае п переменных существует возможных комбинаций значений этих переменных и, следовательно, существует Р-термов и S-термов. Ясно, что число Р- и S-тepмов быстро растет с ростом n.

Сформулируем одно важное свойство Р-термов: сумма всех Р-термов равна единице, т. е.

.

Здесь используется операция булевого сложения. Уравнение, двойственное по отношению к вышеприведенному, имеет вид

,

где операция умножения является булевым умножением.

В случае двух переменных логическую сумму всех P-термов определяем так:

Выражение, двойственное для суммы, имеет вид

и представляет собой произведение всех возможных сумм термов для двух переменных.

Канонические формы

Если булева функция записывается в виде суммы Р-термов или произведения S-термов, то говорят, что она представлена в канонической форме. Так, функция

представлена в канонической S-P форме, а функция

в канонической P-S форме.