2.7.1 Представление лф в совершенной дизъюнктивной форме
Для изложения метода и алгоритма перехода от таблицы задания цифрового автомата к его аналитическому представлению с помощью функции алгебры логики, рассмотрим следующую теорему[1,2]:
Теорема. Любой таблично - заданный ЦА может быть представлен в виде логической функции совершенной дизъюнктивной нормальной формы ( СДНФ)
f (x1,
x2,
…, хn)
= F1
+ F2
+ F3
+ ... + Fn
=
Fi,
где i - номера наборов, на которых функция равна 1, т.е.
- знак всеобщности совершенной дизъюнктивной нормальной формы, объединяющий все минтермы Fi, равные 1.
2.7.2 Дизъюнктивная нормальная форма
Дизъюнктивная нормальная форма (ДНФ) логических функций получается после преобразований совершенной дизъюнктивной нормальной формы, например, минимизации.
Дизъюнктивная нормальная форма (ДНФ) -дизъюнктивное объединение термов, включающее минтермы переменного ранга.
Пример. Записать в аналитическом виде ЛФ заданную таблицей 2.5.
Таблица 2.5-Задание функции
x1 |
x2 |
х3 |
f(x) |
х1 |
x2 |
x3 |
f(x) |
0 0 0 0 |
0 0 1 1 |
0 1 0 1 |
1 0 0 1 |
1 1 1 1 |
0 0 1 1 |
0 1 0 1 |
1 0 0 0 |
Количество всех термов, входящих в аналитическую запись СДНФ равно количеству наборов где f(x) = l.
Тогда запишем функцию таблицы 2.5 в СДНФ:
f(x1, x2,
x3) =
+
x2
x3 + x1
.
Склеивая минтермы 1 и 3, получим ДНФ
f(x1, x2, x3) = ( + x1)+ x2 x3= + x2 x3,
т.к. выражение ( + x1) всегда равно 1.
2.7.3 Представление лф в совершенной конъюнктивной форме
Для получения представлений конъюнктивного типа рассмотрим функции Fi (xl, x2, ... ,xn) = 0
Такие функции называют характеристическими функциями нуля.
Теорема. Любой таблично заданный ЦА может быть представлен в следующей совершенной конъюнктивной нормальной форме (СКНФ)
f(xl,
x2,
... ,xn)
= Fi1
Fi2...·Fik
= & Fi,
i
T0,
где Т0 есть множество номеров наборов на которых функция f(х) обращается в ноль.
Определение. Конъюнктивная нормальная форма (КНФ) - объединение термов, включающее в себя макстермы разных рангов.
Например: (х1 + х2 + )(х1 + х2)(х2 + ).
2.8 Аналитический метод минимизации фл
Определение. Минимальная форма (МКФ и МДФ) представления ФЛ это форма, которая содержит минимальное количество термов и переменных в термах, и не должна допускать последующих упрощений.
Упрощение сложных логических выражений может быть осуществлено на основании применения законов и правил алгебры логики, изложенных выше.
Пример. Пусть задана функция в СДНФ
x1x2x3+x1x2 +x1 x3+x1 + x2x3=
добавим еще один конъюнктивный терм x1x2x3 согласно закону х+х=х, тогда,
=x1x2x3+x1 x2 +x1 x3+x1 +x1x2x3+ x2x3=
используем сочетательное и распределительное свойство конъюнкции и дизъюнкции для 1 и 2, 3 и 4, 5 и 6 минтермов, тогда,
=x1x2(x3+ )+x1 (x3+ )+x2x3(x1+ )=
=x1x2+x1 +x2x3=x1(x2+ )+x2x3=x1+x2x3,
т. к. выражение в скобках равно единице.
В настоящее время существенные результаты в решении задач минимизации получены лишь для базиса НЕ, И, ИЛИ, т.к. этот базис наиболее распространен в технике проектирования ЦА.