Рефераты / Математика /

Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

Минимизация ФАЛ Совершенно нормальные формы хотя и дают однозначные представления функции, но являются очень громоздкими. Реализация СНФ программно или схемотехнически является избыточной, что ведет к увеличению программного кода, поэтому существуют методы упрощения логической записи минимизации. Определение: Преобразование логических функций с целью упрощения их аналитического представления называются минимизацией. Существуют два направления минимизации: 1. Кратчайшая форма записи (цель минимизировать ранг каждого терма). При этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ. 2. Получение минимальной формы записи (цель получение минимального числа символов для записи всей функции сразу). При этом следует учесть, что ни один из способов минимизации не универсален! Существуют различные методы минимизации: 1. Метод непосредственных преобразований логических функций. (1.1) При применении данного метода: а) Записываются ДСНФ логических функций б) Форма преобразуется и упрощается с использованием аксиом алгебры логики. При этом, в частности, выявляются в исходном ДСНФ так называемые соседние min-термы, в которых есть по одной не совпадающей переменной.

По отношению к соседним min-термам применяется закон склейки, значит ранг min-терма понижается на единицу. Определение: Min-термы, образованные при склеивании называются импликантами. Полученные после склейки импликанты по возможности склеивают до тех пор, пока склеивание становится невозможным. Определение: Несклеивающиеся импликанты называются прослойками. Определение: Формула, состоящая из простых импликант тупиковая. Пример: 00010011010101111000101011001110 Если в процессе склейки образуется форма R, содержащая члены вида и то для нее справедливо выражение , что позволяет добавить к исходной форме R несколько членов вида пар и и после этого продолжить минимизацию. Пример:

Мы получили минимальную СНФ.

Метод неопределенных коэффициентов. (1.2) Суть метода состоит в преобразовании ДСНФ в МДНФ. На основании теоремы Жигалкина любую ФАЛ можно представить в виде (рассмотрим на примере трех переменных):

Алгоритм определения коэффициентов: 1. Исходное уравнение разбить на систему уравнений, равных числу строк в таблице истинности. 2. Напротив каждого выражения поставить соответствующее значение функции. 3. Выбрать строку, в которой значение функции и приравнять все к нулю. 4. Просмотреть строки, где функция имеет единичное значение, и вычеркнуть все коэффициенты, встречающиеся в нулевых строках. 5. Проанализировать оставшиеся коэффициенты в единичных строках. 6. Используя правило, что дизъюнкция равна 1 если хотя бы один из , выбрать min-термы минимального ранга. Причем отдавать предпочтение коэффициентам, встречающимся в нескольких уравнениях одновременно. 7. Записать исходный вид функции. Метод неопределенных коэффициентов применим для дизъюнктивной формы и непригоден для конъюнктивной.

Пример:

0000000000000110010001010010201001001001013011010111011041001010001001510110110110106110111010110071111111111111

Итак, получим Метод Квайна (1.3) Суть метода сводится к тому, чтобы преобразовать ДСНФ в МДНФ. Задачи минимизации по методу Квайна состоит в попарном сравнении импликант, входящих в ДСНФ с целью выявления возможности склеивания по какой-то пременной так:

Таким образом, можно понизить ранг термов. Процедура производится до тех пор, пока не остается ни одного терма, допускающего склейки с другим. Причем
Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ