-словесное описание;

-описание в виде таблиц истинности;

-описание в виде алгебраических выражений;

-описание в виде последовательности десятичных чисел.

Словесное описание ФАЛ может звучать так: "Логическая функция трех переменных равна единице, если все три входные переменные равны "единицам". Данный вид описания наиболее часто применяется для первоначального описания поведения логического устройства.

Описание в виде таблицы истинности представляет собой таблицу, которая содержит все возможные комбинации входных переменных и соответствующие им значения функций. Таблица содержит 2n строк и n + m столбцов. Например, таблица 5.

Х2

"0"

0

0

0

Х1

"0"

0

1

1

Х0

"0"

0

У

0

1

1

Х2

X1

"0"

0

1

1

X0

"0"

1

0

1

y

Таблица 5.

1

0

1

При описании ФАЛ с помощью алгебраических выражений возможны две формы ее записи:

1.Дизъюнктивная нормальная форма(ДНФ), которая представляет собой логическую сумму элементарных логических произведений, в каждое из которых входят входные переменные или их инверсии один раз. ДНФ может быть получена из таблицы истинности. Для этого для значений функции Y =1 записываются элементарные логические произведения. Для таблицы 5 имеем:

Y(X2,XrX0) = X2X1X0 + X2X1X0+X2X;X0 + X2X1X0

2.Конъюнктивная нормальная форма(КНФ), которая представляет собой логическое произведение элементарных логических сумм, в каждую из которых входит входные переменные или их инверсии только один раз. КНФ может быть получена из таблицы истинности. Для этого для значений функции Y=0 записываются элементарные логические суммы входных величин. Для таблицы 5 записываем:

y(x2,x1,x0) = (X2 + x1 + x0) (x2 + x1 + X0) + (X2 + x1 + x0) + (X2 + X1 + X(

Описание ФАЛ в виде последовательности десятичных чисел можно получить из алгебраических выражений ДНФ и КНФ. Например для нашего случая:Y(X2,X1,X0)=S(2,3,5,7);Y(X2,XbX0)=n(0,1,4,6)

Основные теоремы и аксиомы алгебры логики и минимизация ФАЛ. Одним из важнейших положений алгебры логики является принцип двойственно-

сти. Он заключается в том, что операции логического сложения можно заменить операциями логического умножения и наоборот.

Если Xj • X0 = Y, то X + X = Y; если X1 + X0 = Y, то X X = Y

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

Xi

X0

1

1

Y=X1AX0

X1 X0

1

Н

1

X0

Y=X1VX0

1

Y=Xo

а)б)в)

Рис. 116. Реализация операций И(а), ИЛИ(б), НЕ(в) на базе элементов 2ИЛИ-Функционально полной системой логических элементов называется совокупность логических элементов, позволяющая реализовать все 16 логических операций. К таким функционально полным системам относятся системы: И, ИЛИ, НЕ; И, НЕ; ИЛИ, НЕ; И-НЕ. В качестве примера рассмотрим выполнение операций И, ИЛИ, НЕ на элементах ИЛИ-НЕ.

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

X • 1 = X

X + 0 = X X + 1 = 1

X+X=X X + x = 1

X= x

XI+ X0 = X0 + X1

X2 + X1 = X2 X1 X1 X0 + X0 = X0

X1 X0 + X0 = X1 + X0

X • 0 = 0

X• X = X

x • X = 0

(X2 X1)X0 = X2(X1 X0

XI X0 = X1 + X0

(X1 + X0)X0 = X0

(X2 + X1)X0 = X2X0 + X1

(X1 + X0)X0 = X1X0 (X1 + x0)(X1+X0) = х0

Любую логическую схему можно описать и представить в совершенной дизъюнктивной или конъюнктивной нормальной форме. Однако полученная

таким образом схема не является оптимальной с точки зрения ее практической реализации. Поэтому исходные ФАЛ обычно минимизируют. Целью минимизации является уменьшение стоимости ее технической реализации. Критерий минимизации неоднозначен. Наиболее просто задача минимизации решается с использованием карт Вейча. Данный метод минимизации базируется на табличном методе представления ФАЛ при числе переменных меньше пяти.

Карта Вейча - это прямоугольная таблица, число клеток в которой равно 2n и в каждой клетке имеется набор всех входных переменных и их инверсий. На рис.117 приведены карты Вейча для двух, трех и четырех переменных. Алгоритм минимизации ФАЛ сводится к следующему:

1) исходные данные записываются в виде таблицы истинности;

а)

X

б)

X

X

X3 X3

X

3

X

в)

Рис. 117. Карта Вейча для двух переменных(а), трех переменных(б), четырех переменных).

2)составляется карта Вейча, в квадраты которой записываются значения функций из таблицы истинности;

3)все клетки, содержащие 1, объединяются в замкнутые области, причем

X1

X1

X2

X

X2

каждая область должна представлять собой прямоугольник с числом клеток 2k, где k = 0, 1, 2, 3,... Области могут пересекаться и одни и те же клетки могут входить в разные области. Затем производится запись минимизированного выражения в дизъюнктивной нормальной форме.