Цифровые устройства и микропроцессоры

51

S1 = ab + abc + b d , S2 = c(a + b + d)(a + d ).

На рисунке 3.16 приведена карта Карно для пяти переменных.

x3x4x5

Рис. 3.16 – Разметка карты Карно для БФ от пяти аргументов

Сложность применения карт Карно и Вейча от пяти переменных заключается в том, что соседними являются столбцы, расположенные не только рядом, но и на расстоянии друг от друга. На рисунке 3.16, например, это столбцы, отмеченные переменными Х3 Х4 Х5 – 001 и 101, 011 и 111. Для карт от шести переменных появляются такие же соседние строки. Поэтому карты Карно и Вейча

54

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

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

Базис, который называют основным, включает три функции: И, ИЛИ, НЕ – и, соответственно, реализуется тремя логическими элементами.

Базис И-НЕ включает в себя только одну функцию И-НЕ и один логический элемент. Его еще называют универсальным. БФ элемента этого базиса:

f = ab.

На основе этого элемента производятся различные цифровые устройства. Чтобы реализовать любую функцию в этом базисе, необходимо провести преобразования БФ в данный базис. Для этого используются теоремы де Моргана. Например:

f1 = x1x2 + x1x2 = x1x2 + x1x2 = x1x2 x1x2.

Таким образом, в окончательной формуле присутствуют только операции И-НЕ. Схема, реализующая эту БФ, приведена на рисунке 3.19.

Рис. 3.19 – Реализация БФ в базисе И-НЕ

Базис ИЛИ-НЕ включает в себя одну функцию ИЛИ-НЕ и только один логический элемент также называется универсальным. БФ элемента этого базиса:

f = a + b.

Чтобы реализовать любую функцию в этом базисе, необходимо провести преобразования БФ. Преобразование формулы в базис ИЛИ-НЕ:

55

f2 = x1x2 + x1x2 = x1x2 + x1x2 = x1 + x2 + x1 + x2.

Схема, реализующая эту БФ, приведена на рисунке 3.20.

Рис. 3.20 – Реализация БФ в базисе ИЛИ-НЕ

Рассмотрим особенности базисов И-НЕ и ИЛИ-НЕ. Элемент И-НЕ описывается функцией. Таблица истинности этой функции приведена в таблице

3.2.

Таблица 3.2 – Таблица истинности функции F

Если на оба входа элемента И-НЕ подать одну и ту же переменную (первая и четвертая строки таблицы), то в результате получается функция:

f = Х1 Х1 = Х1,

т. е. элемент И-НЕ становится инвертором (рис. 3.21, a). При последовательном соединении двух элементов И-НЕ, как показано на рисунке 3.21, б, схема выполняет функцию И. Таким образом, базис И-НЕ содержит как бы три элемента: И-НЕ, И, НЕ.

Рис. 3.21 – Соединение элементов базиса И-НЕ: инвертор (НЕ) (а); элемент И на двух элементах И-НЕ (б)

Элемент ИЛИ-НЕ описывается функцией f = X1 + X 2. Таблица истинности этой функции приведена в таблице 3.3.

56

Таблица 3.3 – Таблица истинности функции F

Если на оба входа элемента ИЛИ-НЕ подать одну и ту же переменную, то получим функцию: f = X1 + X1 = X1, т. е. элемент ИЛИ-НЕ становится инвертором (рис. 3.22, а). При последовательном соединении двух элементов ИЛИ-НЕ, как показано на рисунке 3.22, б, элемент ИЛИ-НЕ преобразуется в элемент ИЛИ. Таким образом, базис ИЛИ-НЕ содержит как бы три элемента: ИЛИ-НЕ, ИЛИ, НЕ.

Рис. 3.22 – Соединение элементов базиса ИЛИ-НЕ: инвертор (НЕ) (а); элемент ИЛИ на двух элементах ИЛИ-НЕ (б)

Рассмотрим примеры реализации функций в различных базисах. Функция D (ДНФ) в базисе И-НЕ сначала минимизируется, затем перево-

дится в базис, а потом реализуется (рис. 3.23).

D = (1, 2, 4, 5, 6, 7, 8, 14) = x1x2 x3x4 + x1x4 + x2 x3x4 + x1x2 =

= x1x2 x3x4 + x1x4 + x2 x3x4 + x1x2 = x1x2x3x4 + x1x4 + x2x3x4 + x1x2.

58