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

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

х1 у1

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

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

Рис.1. Обобщенная схема логического устройства.

Зависимость выходных переменны у, выраженная через совокупность входных переменных х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.