Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

Минимизация функций алгебры логики



 Другие рефераты
Механические колебания в дифференциальных уравнениях Минимизация ФАЛ Минимизация функций нескольких переменных. Метод спуска Многогранники

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

Если в процессе склейки образуется форма R, содержащая члены  вида  [pic]  и
[pic]то для нее  справедливо  выражение  [pic],  что  позволяет  добавить  к
исходной форме R несколько членов  вида  пар  [pic]  и  [pic]и  после  этого
продолжить минимизацию.
Пример:
[pic][pic]
[pic]
Мы получили минимальную СНФ.

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

 Пример:
[pic]
|       |[pic]  |[pic]  |[pic]  |[pic]  |[pic]  |[pic]  |[pic]  |[pic]  |
|0      |0      |0      |0      |00     |00     |00     |000    |1      |
|1      |0      |0      |1      |00     |01     |01     |001    |0      |
|2      |0      |1      |0      |01     |00     |10     |010    |1      |
|3      |0      |1      |1      |01     |01     |11     |011    |0      |
|4      |1      |0      |0      |10     |10     |00     |100    |1      |
|5      |1      |0      |1      |10     |11     |01     |101    |0      |
|6      |1      |1      |0      |11     |10     |10     |110    |0      |
|7      |1      |1      |1      |11     |11     |11     |111    |1      |

[pic]
Итак, получим [pic]
      Метод Квайна     (1.3)
Суть метода сводится  к  тому,  чтобы  преобразовать  ДСНФ  в  МДНФ.  Задачи
минимизации  по  методу  Квайна  состоит  в  попарном  сравнении  импликант,
входящих в  ДСНФ  с  целью  выявления  возможности  склеивания  по  какой-то
пременной так:
[pic]
Таким образом, можно понизить ранг термов.  Процедура  производится  до  тех
пор, пока не остается  ни  одного  терма,  допускающего  склейки  с  другим.
Причем склеивающиеся термы помечаются *.
Определение: Непомеченные термы называются первичными импликантами.
Полученное логическое выражение не всегда оказывается  минимальным,  поэтому
исследуется возможность дальнейшего упрощения.
Для этого:
1. Составляются таблицы,  в  строках  которых  пишутся  найденные  первичные
импликанты, а в столбцах указываются термы первичной ФАЛ.
2. Клетки этой таблицы отмечаются в том случае,  если  первичная  импликанта
входит в состав какого-нибудь первичного терма.
3. Задача упрощения сводится к  нахождению  такого  минимального  количества
импликант, которые покрывают все столбцы.
Алгоритм метода Квайна (шаги):
1. Нахождение первичных импликант.
 Исходные термы  из  ДНФ  записывают  в  столбик  и  склеиваю  сверху  вниз.
Непомеченные импликанты переходят в функции на этом шаге.
2. Расстановка меток избыточности.
 Составляем таблицу, в которой строки  –  первичные  импликанты,  столбцы  –
исходные термы. Если некоторый min-терм содержит первичный импликант, то  на
пересечении строки и столбца ставим метку.
3. Нахождение существенных импликант.
  Если в каком-либо столбце есть только одна метка, то  первичный  импликант
соответствующей строки является существенным.
4. Строка,  содержащая  существенный  импликант  и  соответствующие  столбцы
вычеркиваются.
Если  в  результате  вычеркивания   столбцов   появятся   строки   первичных
импликант, которые  не  содержат  метки  или  содержат  одинаковые  метки  в
строках, то такие первичные импликанты  вычеркиваются.  В  последнем  случае
оставляем одну меньшего ранга.
5. Выбор минимального покрытия.
Из таблицы, полученной на  шаге  3  выбирают  такую  совокупность  первичных
импликант, которая включает метки во всех столбцах по крайней мере по  одной
метке в каждом. При нескольких  возможных  вариантах  отдается  предпочтение
покрытию с минимальным суммарным числом элементов в импликантах,  образующих
покрытие.
6. Далее результат записывается в виде функции.
Пример:
[pic]
Шаг 1.
|Термы 4го ранга          |Термы 3го ранга          |Термы 2го ранга          |
|[pic]  * 1               |[pic]                    |[pic]                    |
|[pic] * 3                |[pic]                    |[pic]                    |
|[pic]  * 4               |[pic]  * 1               |                         |
|[pic]  * 1               |[pic]  * 2               |                         |
|[pic]  * 2               |[pic]                    |                         |
|[pic]  * 2               |[pic]  * 2               |                         |
|[pic]  * 3               |                         |                         |
|[pic]  * 4               |[pic]                    |                         |
|                         |[pic]                    |                         |
|                         |[pic]  * 1               |                         |

Шаг 2.
|       |[pic]  |[pic]  |[pic]  |[pic]  |[pic]  |[pic]  |[pic]  |[pic]  |
|[pic]  |V      |       |       |V      |       |       |       |       |
|[pic]  |V      |       |       |       |       |V      |       |       |
|[pic]  |       |       |V      |V      |       |       |       |       |
|[pic]  |       |       |       |       |V      |V      |       |       |
|[pic]  |       |       |       |       |V      |       |       |V      |
|[pic]  |       |V      |V      |       |       |       |V      |V      |

Шаг 4 пропускаем.
Шаг 5.
Выбираем те min-термы, при записи которых, МДНФ функции минимальна.
Шаг 6.
[pic]
Недостаток метода Квайна – необходимость полного по парного  сравнения  всех
min-термов на этапе нахождения первичных импликант.
      Идея модификации метода Квайна – метод Квайна-Мак-Класки.     (1.4)
1. Каждая конъюнкция в ДСНФ представляется своим двоичным набором.
2. Вся совокупность номеров наборов разбивается на группы в  зависимости  от
числа единиц, имеющихся в  номерах  наборов  (0-группа,  1-группа,  2-группа
и.т.д.).
3. Сравниваются две группы, отличающиеся на одну единицу.
4. В результате сравнения в номере набора, имеющего большее число единиц  на
позиции, где обнаружится разница на одну единицу ставится прочерк.
5. В процессе преобразования возникают новые сочетания (n-группы).
6.  Процесс  преобразования  длится  до  тех  пор,  пока  возможна  операция
склеивания.
7. Элементы преобразованных групп являются первичными импликантами,  которые
вместе с номерами исходных наборов образуют таблицы разметок.
8. В остальном эти методы совпадают  с  единственным  уточнением  –  если  в
результате таблицы разметок ни одна из строк не покрывает  единицу  столбца,
то надо выбрать номер столбца набора из предыдущей группы преобразований.
Определение: n-группа – это такой набор аргументов функции, что  число  всех
аргументов равных единице равно n, причем значении функции равно 1.
Пример:
[pic]
Составим таблицу исти
1234
скачать работу


 Другие рефераты
Алгебраические числа
Куба
Даосизм и Конфуцианство
Даосизм и его влияние на китайскую культуру


 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ