<< Пред. стр. 4 (из 7) След. >>
Список литературы по разделу
8
6
8
5
2 0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1 0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1 0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1 0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1 0
1
0
1
0
0
0
1
1
1
0
1
1
1
1
1 0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0 0
1
0
0
1
0
0
1
0
0
0
0
1
1
0
0
Срабатывание реагирующего органа на сигнал Х3 дает работу команду на поворот руки на 180 для правильной ориентации детали и сигнал Х1 — на загрузку станка с патроном большего диаметра. Сигнал Х2 обеспечивает загрузку второго станка. Каждая конституента единицы в Х1 и Х2 сообщает системе управления станка соответствующий номер технологии обработки.
В прикладном значении, проблема выбора формы представления логических функций сводится к задаче выбора набора стандартных логических элементов, из которых будет строится реальная схема устройства управления (автомата). Сложность автомата с точки зрения номенклатуры и количества применяемых в схеме элементов существенно зависит от вида функций, выбранных в качестве базиса. Если, например, за базис выбраны функции отрицания, дизъюнкции и конъюнкции, то любая функция алгебры логики может быть представлена в СДНФ или СКНФ и после этого реализована на стандартных элементах. Уменьшение числа логических операций, входящих в базис функционально полной системы, сокращает номенклатуру стандартных логических элементов в схеме. Снижение общего количества элементов, необходимых для реализации логической функции, ведет к повышению надежности работы схемы управляющего устройства, уменьшению её габаритов, сложности, стоимости и пр. Одним из основных путей получения таких экономных схем является преобразование и приведение логических функций к минимальной форме.
2.2 Минимизация функций алгебры логики
Любая функция алгебры логики может быть записана в виде СДНФ или СКНФ. Такая запись в ряде случаев является неэкономной. Рассмотрим следующий пример.
Пример 2.7 Пусть задана СДНФ функции
f (x1, х2, х3) = х1 х2 х3 v х1 х2 х3 v х1 х2 х3 v x1 x2 x3 v х1 х2 х3.
Преобразуем эту СДНФ следующим образом. Добавим еще один конъюнктивный член х1 х2 х3. Это добавление не меняет данной функции, так как
x v х= х;
f (x1, х2, х3) = х1 х2 х3 v х1 х2 х3 v х1 х2 х3 v x1 x2 x3 v х1 х2 х3 v х1 х2 х3.
Теперь преобразуем это выражение, используя сочетательное и распределительное свойства конъюнкции и дизъюнкции:
f (x1, х2, х3) = х1 х2( х3 v х3 ) v х1 х2 (х3 v x3) v х1 х2( х1 v х1).
Используя свойство дизъюнкции х v х ? 1 (2), получаем:
f (x1, х2, х3) = х1 х2 v х1 х2 v х2 х3
Аналогично предыдущему выполняем дальнейшие преобразования:
f (x1, х2, х3) = х1( х2 v х2) v х2 х3 ? x1 v x2 x3
Из примера видна неэкономность совершенных нормальных форм для представления функций алгебры логики. Проблема простейшего представления функций сводится к проблеме выбора базиса и проблеме наиболее экономного представления функций в этом базисе. В настоящее время существенные результаты в решении задачи минимизации получены лишь для базиса, состоящего из отрицания, конъюнкции и дизъюнкции. Именно этот базис в основном и будет рассматриваться в дальнейшем.
Как указывалось ранее минимальной дизъюнктивной нормальной формой булевой функции называется ДНФ, содержащая наименьшее число букв (по отношению ко всем другим ДНФ, представляющим заданную булеву функцию).
Нахождение такой минимальной формы булевых функций представляет собой проблему минимизации, которая является основной для практических приложений алгебры логики, а также построения экономичных схем вычислительной техники (цифровых автоматов). В общей постановке данная задача пока не решена, однако имеются алгоритмы частичного аналитического или графического решения проблемы минимизации [4], [5], [6].
Аналитические методы минимизации
Аналитически формулу, представленную в ДНФ, можно путем равносильных преобразований упрощать многократным применением операций склеивания (18) и (19), поглощения (16) и (17) и зависимости (15). В результате приходят к такому аналитическому выражению, когда дальнейшие преобразования оказываются уже невозможными, то есть получают так называемую тупиковую форму.
Дизъюнктивная нормальная форма называется тупиковой, если при удалении из неё любой конъюнкции получаемая в результате ДНФ не является эквивалентной исходной.
Тупиковая форма может быть не единственной. Чтобы убедиться в том, что данная тупиковая форма является минимальной, необходимо найти все тупиковые формы и сравнить их по числу входящих в них букв.
Пусть, например, функция у задана в СДНФ:
y = х1 х2 х3 v х1 х2 х3 v х1 х2 х3 v x1 x2 x3 v х1 х2 х3.
Группируя члены формулы 1-2, 3-4 и применяя свойства склеивания
(18), (19) получаем:
y = (х1 х2 х3 v х1 х2 х3) v (х1 х2 х3 v x1 x2 x3) v х1 х2 х3 ? х1 х2 v х1 х2 v х1 х2 х3
При другом способе группирования:
y = х1 х2 х3 v( х1 х2 х3 v х1 х2 х3) v (x1 x2 x3 v х1 х2 х3 )? х1 х2 х3 v х2 х3 v х1 х2
Обе тупиковые формы не являются минимальными. Чтобы получить
минимальную форму, нужно повторить в исходной формуле одно слагаемое
(9). В первом случае таким слагаемым может быть х1 х2 х3, тогда
y = х1 х2 v х1 х2 v (х1 х2 х3 v x1 x2 x3) ? х1 х2 v х1 х2 v х2 х3
Если для первого же случая группирования добавить x1 x2 x3,получим:
y = х1 х2 v х1 х2 v (х1 х2 х3 v x1 x2 x3) ? х1 х2 v х1 х2 v х1 х3
Перебрав все возможные варианты, можно убедиться, что две последние формы являются минимальными. Работа с формулами на таком уровне подобна "блужданию в потемках". Поиск минимальных форм становится более целенаправленным, если использовать понятие импликанты,
Булева функция g(х1 , х2,.., х3) называется импликантой булевой функции f(х1 , х2,.., х3), если для любого набора переменных, на котором g = 1, справедливо f 1.
Например, пусть булева функция f задана таблицей истинности 2.6:
Таблица 2.6 — Таблица истинности функции и ее импликант
х1 х2 х3 f g1 g2 g3 g4 g5 g6 g7
0
0
0
0
1
1
1
1 0
0
1
1
0
0
1
1 0
1
0
1
0
1
0
1 0
0
0
1
0
0
1
1 0
0
0
0
0
0
0
1 0
0
0
0
0
0
1
0 0
0
0
0
0
0
1
1 0
0
0
1
0
0
0
0 0
0
0
1
0
0
0
1 0
0
0
1
0
0
1
0 0
0
0
1
0
0
1
1
Запишем из таблицы 2.6 в аналитической форме функцию f и все ее импликанты в СДНФ:
f = х1 х2 х3 v х1 х2 х3 v х1 х2 х3 =g7
g1 = х1 х2 х3;
g2 = х1 х2 х3;
g3 = х1 х2 х3 v х1 х2 х3 ? х1 х2 (х3 v х3 )?х1 х3;
g4 = х1 х2 х3;
g5 = х1 х2 х3 v х1 х2 х3 ? х2 х2 (х1 v х1 )?х2 х3;
g6 = х1 х2 х3 v х1 х2 х3.
Импликанта g булевой функции f; являющаяся элементарной конъюнкцией, называется простой, если ни какая часть импликанты g не является импликантой функции f.
В нашем случае: импликанты g3 = х1 х3 и g5 = х2 х3 являются простыми импликантами функции f. Импликанты g1 ,g2, g4, g6 не являются простыми, так как их части являются импликантами функции f.
Для получения минимальной ДНФ могут быть использованы следующие правила:
1. Дизъюнкция любого числа импликант булевой функции / также является импликантой этой функции.
2. Любая булева функция f эквивалентна дизъюнкции всех своих простых импликант. Такая форма представления булевой функции называется сокращенной ДНФ.
В рассматриваемом примере простых импликант всего две: g3 и g5. Следовательно, сокращенная ДНФ функции f имеет вид:
f = g3 v g5? х1 х2 v х2 х3
Из таблицы 2.6 функции f видно, что простые импликанты g3 и g5 в совокупности покрывают своими единицами все единицы этой функции.
Получение сокращенных ДНФ является начальным этапом отыскания минимальных форм булевых функций. В сокращенную ДНФ входят все простые импликанты булевой функции. Иногда из сокращенной ДНФ можно убрать одну или несколько простых импликант, не нарушая равнозначности исходной функции. Такие простые импликанты называют лишними. Исключение лишних простых импликант из сокращенных ДНФ — второй этап минимизации.
Сокращенная ДНФ булевой функции, в которой отсутствуют лишние простые импликанты является тупиковой.
Тупиковые ДНФ булевой функции f, содержащие минимальное число букв, являются минимальными. Но так как булева функция может иметь несколько тупиковых ДНФ, то минимальных ДНФ тоже может быть несколько.
Кроме рассмотренных известны и другие аналитические методы минимизации булевых функций, в частности: метод Квайна — Мак — Класки, алгебраический метод С. Петрика, метод Блейка — Порецкого и др. [5], [6].
Метод Квайиа — Мак-Класки
При минимизации по методу Квайна предполагается, что минимизируемая функция задана в СДНФ. Элементарные конъюнкции ранга и, входящие в СДНФ минимизируемой функции, называют минитермами ранга и. Метод Квайна состоит из последовательного выполнения следующих этапов:
1. Нахождение первичных импликант. Все минитермы данной функции сравнивают между собой попарно. Если минитермы mi и mj таковы, что они имеют вид ахi и axi, то выписывается конъюнкция а, являющаяся минитермом (n — 1)- го ранга. Минитермы n- го ранга, для которых произошло склеивание, отмечаются звездочкой *. После построения всех минитермов (п-1)- го ранга вновь сравнивают их попарно, выписывают минитермы (n-2)- гo ранга и отмечают склеиваю)циеся минитермы (и — 1)- го ранга и т. д. Этап. заканчивается, когда вновь полученные минитермы i-го ранга уже не склеиваются между собой. Все не отмеченные минитермы называются первичными или простыми импликантами.
Пример 2.8
f (x1, х2, х3, х4) = х1 х2 х3 х4 v х1 х2 х3 х4 v х1 х2 х3 х4 v x1 x2 x3 х4 v х1 х2 х3 х4 v
v х1 х2 х3 х4 v х1 х2 х3 х4 v х1 х2 х3 х4.
Минитермы 4-го ранга:
х1 х2 х3 х4*, х1 х2 х3 х4 *, х1 х2 х3 х4 *,
х1 х2 х3 х4 *, х1 х2 х3 х4 *, х1 х2 х3 х4*, х1 х2 х3 х4 .
Образуем минитермы 3-го ранга:
Минитермы 4-го ранга:
х1 х3 х4, х2 х3 х4 , х1 х2 х3*, х2 х3 х4*,
х1 х2 х4 , х2 х3 х4 *, х1 х2 х4*, х1 х3 х4 *, х1 х2 х3*.
Теперь находим минитермы 2-ro ранга:
х2 х3
Так как дальнейшее склеивание невозможно, то этап получения простых импликант закончен. Простыми импликаитами являются следующие минитермы:
х1 х3 х4, х2 х3 х4 , х1 х2 х4,
х1 х2 х4 , х2 х3 х4, х2 х3.
2.Расстановка меток. Для данной функции
f (x1, х2, …, хn) =vi ?i
где ?i — простые импликанты, полученные на первом этапе. Соотношение (2.42) определяет СДНФ для данной функции. Для нахождения минимального покрытия интервалами максимального ранга необходимо теперь произвести выбрасывание некоторого количества первичных импликант. На этапе расстановки меток составляется таблица, число строк которой равно числу полученных первичных импликант минимизируемой функции. Число столбцов совпадает с числом минитермов СДНФ. Если в некоторый минитерм СДНФ входит какая-либо из первичных импликант, та на пересечении соответствующего столбца и строки ставится метка.
Пример 2.8 (продолжение). Составим таблицу с метками для рассматриваемой функции, в которой будет шесть строк и восемь столбцов.
v
v
v
v
v v
v
<< Пред. стр. 4 (из 7) След. >>
Список литературы по разделу