Способы записи ФАЛ

Рассмотрим некоторое логическое устройство, на входе которого присутствует n-разрядное двоичное число (двоичный код), а на выходе – m-разрядный код. Для математического описания работы устройства необходимо определить зависимость каждой из m выходных переменных у от входного двоичного кода.

х1 у1

х2 Логическое у2

хn устройство уm

Зависимость выходных переменны у, выраженная через совокупность входных переменных х1,х2,…хn с помощью операций алгебры логики, носит название функции алгебры логики (ФАЛ). Понятие ФАЛ является базовым в алгебре логики. Для описания ФАЛ используются различные формы: словесная, табличная, алгебраическая, последовательность десятичных чисел и кубических комплексов.

Пример словесного описания для функции 3 ИЛИ: логическая функция трех переменных равна единице, если одна из переменных равна единице.

Описание ФАЛ из предыдущего примера в виде таблицы истинности:

Таблица для описания функции n переменных содержит 2ⁿ строк. Соответственно функция n аргументов имеет 2ⁿ наборов переменных. Количество столбцов равно сумме чисел n+m. В данном случае (всего одна выходная переменная): 3+1=4 столбца.

Описание ФАЛ в виде последовательности десятичных чисел легко понять на примере. Возьмем за основу таблицу истинности предыдущего примера. Первое значение у=1 функция имеет на наборе 001. Переводят этот двоичный код в десятичный –1. Следующая единица: 010 2, и т.д. Полученная ФАЛ записывается в следующем виде:

у(х1,х2,х3) = S(1,2,3,4,5,6,7).

На некоторых этапах разработки логических устройств удобно ФАЛ представлять координатным (графическим) способом. При небольшом количестве аргументов (n<6), наиболее распространенным из них является метод карт Карно. Карта Карно представляет собой двухкоординатную таблицу – несколько видоизмененную таблицу истинности. 2ⁿ наборов, представленных соседними клетками, отличаются значением только одной переменной.

Правила построения Карно следующие:

1)Количество клеток равно количеству строк таблицы истинности.

2)Слева и сверху располагаются значения аргументов. Порядок размещения аргументов таков, что в двух соседних по горизонтали и вертикали клетках отличается значение только одного аргумента (поэтому соседними считаются и клетки, находящиеся на противоположных краях таблицы).

3)В клетки заносятся соответствующие значения ЛФ.

На рис.3 приведена карта Карно для функции 3 ИЛИ.

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

Различают две формы написания ФАЛ алгебраическим выражением ДНФ и КНФ.

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

у(х1,х2,х3) = х1 х 2+х1х3+х1х2 х 3

При проектировании устройств чаще имеют дело с совершенной дизъюнктивной нормальной формой (СДНФ). Получают СДНФ из таблиц истинности следующим образом:

- для каждого набора входных переменных на котором ФАЛ равна единице записывают конституенты единицы - элементарные конъюнкции, причем переменные, равные нулю, записывают с инверсией.

- логически суммируют полученные конституенты единицы.

Запись СДНФ для функции 3 ИЛИ сделаем, воспользовавшись ее табличным представлением.

у(х1,х2,х3) = х 1 х 2х3+ х 1х2 х 3+ х 1х2х3+х1 х 2 х 3+

+х1 х 2х3+х1х2 х 3+ х1х2х3

Вторая форма записи ФАЛ – это конъюнктивная нормальная форма (КНФ).

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

Аналогично, существует совершенная конъюнктивная нормальная форма (СКНФ).

Получают СКНФ из таблиц истинности следующим образом:

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

- логически перемножают полученные конституенты нуля.

Запись СКНФ для функции 3 ИЛИ сделаем, воспользовавшись ее табличным представлением.

у(х1,х2,х3) = х1+х2+х3.