П3.2. Получение совершенной дизъюнктивной (CДНФ) и совершенной конъюнктивной (СКНФ) нормальных форм записи ФАЛ

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

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

· логически суммируют полученные произведения.

Пример П3.1. Записать СДНФ для ФАЛ, заданной таблицей истинности,

Фактически СДНФ это логическая сумма конституент единицы, заданной ФАЛ.

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

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

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

Пример П3.2. Записать СКНФ для ФАЛ, заданной таблицей истинности на предыдущей странице,

П3.3. Минимизация ФАЛ

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

При большом числе переменных для минимизации ФАЛ используется специальное программное обеспечение. При небольшом числе переменных (не более 5) хорошие результаты дают табличные методы, работающий без привлечения ЭВМ.

Рассмотрим один из этих методов – метод карт Вейча. Данный метод предполагает использование специальных прямоугольных таблиц, построенных на основе таблиц истинности. Для описания этого метода введем понятие соседних кодов.

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

На рис. П3.1 приведены карты Вейча для двух, трех и четырех переменных.

Рассмотрим метод заполнения карт Вейча. Искомый код определяется пересечением строк и столбцов, озаглавленных соответствующими переменными. Например, для таблицы, показанной на рис. П3.1 а, верхняя левая клетка (отмеченная звездочкой) соответствует коду . Для таблицы, показанной на рис. П3.1 б, нижняя правая клетка (отмеченная звездочкой) соответствует коду . Для рисунка П3.1 в нижняя левая клетка (отмеченная звездочкой) соответствует коду .

В качестве примера рассмотрим минимизацию ФАЛ, описанной выше в таблице истинности. Заполненная карта Вейча, соответствующая данной таблице, приведена на рис. П3.2. При минимизации ФАЛ можно использовать либо ее единичные, либо нулевые значения. При объединении единичных значений ФАЛ получают выражение для самой функции, а при объединении нулевых значении – выражение для функции, инверсной исходной. Минимизация ФАЛ выполняется по следующему алгоритму: · на карте Вейча ФАЛ выделяют прямоугольные области объединяющие клетки с выбранным значением функции «лог 1» или «лог. 0». Каждая область должна содержать 2 ^k клеток, где k - целое число (0, 1, 2,…). Выделенные области могут пересекаться, т. е. одна клетка может входить в несколько различных областей; · каждая из выделенных областей описывается произведением переменных, которые для этой области остаются неизменными. Каждое произведение должно содержать n – k переменных;

· из полученного множества выбирают минимальное число максимально больших областей, включающих все клетки с выбранным значением ФАЛ;

· логически суммируют выбранные произведения.

Полученное выражение является минимальной дизъюнктивной ФАЛ.

Воспользуемся приведенной методикой для минимизации вышеприведенной функции. Произведем объединение областей с единичными значениями функции. Имеем три области (см. рис. П3.3). Для области I неизменными остаются переменные X 1 и X 0. Для области II - постоянны переменные Х 2 и Х0. Для области III – неизменны Х 2 и Х 1. Суммируя произведения неизменных переменных для каждой из выделенных областей, получим минимальную дизъюнктивную форму искомой ФАЛ в виде:

В правильности полученной ФАЛ можно убедиться, подставляя в неё различные комбинации входных переменных. Например, для входного кода 001 имеем ¸ что соответствует приведенной таблице истинности.

Объединяя клетки, содержащие нулевые значения функции, так же получим три области. Это область I, для которой неизменны переменные и , область II для которой неизменны и и область III с неизменными и . Суммируя произведения переменных для каждой области получим ФАЛ, инверсную заданной:

.

Подставив, для проверки, в полученную ФАЛ входной код 001 найдем:

или F (X) = 0.

Интересно отметить, что в рассмотренном примере область II была получена объединением клеток, расположенных на противоположных краях таблицы. Это следует из основного правила построения таблицы. Коды рядом расположенных клеток должны быть соседними, т. е. отличаться только в одном разряде. Нижней правой клетке рассматриваемой таблицы соответствует код 000, а левой нижней клетке – код 010, т. е. они соседние. Поэтому реально рассматриваемая таблица является объемной фигурой и представляет собой поверхность цилиндра (рис. П3.5)

Тоже самое можно сказать и о таблице 4-х переменных. Здесь соседним кодам попарно соответствуют как нижняя и верхняя строки таблицы, так и правый и левый крайние ее столбцы. Поэтому таблица ФАЛ 4-х переменных как бы размещена на поверхности тора. На рис. П3.6 показаны возможные варианты объединения в области клеток карты Вейча 4-х переменных. Вполне очевидно, что распределение переменных по клеткам на плоском варианте карты Вейча может не совпадать с приведенным выше. Например, клетки, соответствующие переменной Х 0, можно поменять местами с клетками, соответствующим переменной Х 3. .Но всегда должен выполняться основной принцип заполнения карты – рядом расположенные клетки (по горизонтали и вертикали) должны соответствовать соседним кодам. П3.4. Приведение ФАЛ к заданному базису логических элементов Для реализации ФАЛ произвольной сложности достаточно иметь элементы, выполняющие три основные логические операции. Это операция И (дизъюнкция), ИЛИ (конъюнкция) и НЕ (отрицание). Такая совокупность логических элементов называется функционально полнойсовокупностью логических элементов. Используя принцип двойственности, согласно которому логические операции И и ИЛИ могут быть взаимно преобразованы, функционально полную систему логических элементов можно уменьшить до двух элементов. Это совокупности элементов И и НЕ или ИЛИ и НЕ. На практике, нашли применение элементы, которые совмещают две функции. Это элементы И-НЕ и ИЛИ-НЕ. Согласно вышесказанному, один такой элемент является функционально полной системой логических элементов и на его основе можно построить логическое устройство произвольной сложности.

Приведение ФАЛ к заданному базису логических элементов означает приведение его к заданному типу элементов (И-НЕ или ИЛИ-НЕ), причем число входов этих элементов так же должно быть заданным.

Таким образом, проблема приведения ФАЛ к заданному базису логических элементов распадается на две самостоятельные задачи:

· приведения ФАЛ к заданному типу логических элементов (операций);

· приведение числа входов элемента к заданному.