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

Минимизация ФАЛ

авим таблицу истинности:
|[pic]          |[pic]          |[pic]          |[pic]          |[pic]          |
|0              |0              |0              |0              |1              |
|0              |0              |0              |1              |1              |
|0              |0              |1              |0              |1              |
|0              |0              |1              |1              |1              |
|0              |1              |0              |0              |1              |
|0              |1              |0              |1              |1              |
|0              |1              |1              |0              |1              |
|0              |1              |1              |1              |1              |
|1              |0              |0              |0              |1              |
|1              |0              |0              |1              |1              |
|1              |0              |1              |0              |0              |
|1              |0              |1              |1              |1              |
|1              |1              |0              |0              |0              |
|1              |1              |0              |1              |0              |
|1              |1              |1              |0              |0              |
|1              |1              |1              |1              |1              |

Запишем n-группы:
0-Группа: 0000
1-Группа: 0001, 0010, 0100, 1000
2-Группа: 0011, 0101, 0110, 1001
3-Группа: 0111,1011
4-Группа: 1111
Теперь сравним группы с номерами n и n+1:
0-Группа: 000-, 00-0, 0-00, -000
1-Группа: 00-1, 0-01, -001, 001-, 0-10, 010-,01-0, 100-
2-Группа: 0-11, -011, 01-1, 011-, 10-1
3-Группа: -111, 1-11
Еще раз сравним (при этом прочерки должны быть на одинаковых позициях):
0-Группа: 00--, 0-0-, -00-
1-Группа: 0--1, -0-1, 0-1-, 01—
2-Группа: --11
И еще раз сравним:
0-Группа: 0---
Запишем таблицу исходных min-термов, где функция равна 1:
|0000 |0001 |0010 |0011 |0100 |0101 |0110 |0111 |1000 |1001 |1011 |1111 |     |
|V    |V    |V    |V    |V    |V    |V    |V    |     |     |     |     |0--- |

Выделим минимальное число групп, покрывающих

Для проверки составим таблицу истинности

|               |1000           |1001           |1011           |1111           |
|-00-           |V              |V              |               |               |
|-0-1           |               |V              |V              |               |
|-111           |               |               |V              |V              |

      Метод минимизирующих карт (для ДСНФ и КСНФ). (1.5)
Одним из способов графического представления булевых функций  от  небольшого
числа переменных являются карты  Карно.  Их  разновидность  –  карты  Вейча,
которые строятся как развертки кубов на плоскости,  при  этом  вершины  куба
представляются клетками карты, координаты которых совпадают  с  координатами
соответствующих вершин куба.
Для ДСНФ единицы  ставятся  в  клетке,  соответствующей  номеру  набора,  на
котором значение функции равно единице, а ноль не ставится,  а  для  КСНФ  –
наоборот.

Диаграмма для двух логических переменных (для ДСНФ):
[pic]



Для трех переменных:
[pic]
Карты Карно используются для ручной минимизации функций алгебры  логики  при
небольшом   количестве   переменных.   Правило    минимизации:    склеиванию
подвергаются 2,4,8,16,[pic] клеток и клетки, лежащие на границе карты.
При числе переменных 5 и больше отобразить графически функцию в виде  единой
плоской карты невозможно. Тогда строят комбинированные карты,  состоящие  из
совокупности более простых карт. Процедура минимизации заключается  тогда  в
том, что сначала находится минимальная форма  4-х  мерных  кубов  (карт),  а
затем,  расширяя  понятие  соседних   клеток,   отыскивают   min-термы   для
совокупности карт. Причем соседними клетками  являются  клетки,  совпадающие
при совмещении карт поворотом вокруг общего ребра.



|                 |[pic]             |[pic]           |
|[pic]            |[pic]             |[pic]           |
|[pic]            |[pic]             |[pic]           |

Пример: Минимизировать ФАЛ от двух переменных: [pic]
|                 |[pic]             |[pic]           |
|[pic]            |1                 |1               |
|[pic]            |1                 |                |

[pic]
Минимизировать функцию: [pic]
|               |[pic]          |[pic]          |[pic]          |[pic]          |
|[pic]          |1              |1              |1              |               |
|[pic]          |               |1              |               |               |
|               |[pic]          |[pic]          |[pic]          |[pic]          |

[pic]
Минимизация логических функций, заданных в базисе [pic].
Метод  неопределенных  коэфициентов  применим   для   минимизации   функций,
заданных в различных базисах. Пусть функция [pic]  является  ПСНФ,  операция
[pic]имеет особенности, отличающие ее от операции дизъюнкции.
1)[pic]
2)[pic]
3) [pic]
Минимизация при этом усложняется, так как ее основными  критериями  являются
минимальные ранги каждого терма и их  минимальное  количество,  при  этом  в
ходе минимизации в базисе [pic]  нецелесообразно  приравнивать  к  нулю  все
коэффициенты на наборах где [pic], т.к. в наборах,  где  функция  [pic]могут
остаться  термы  высокого  ранга.  Поэтому  особой  разницы  между   выбором
нулевого или единичного значения функции нет.
Количество коэффициентов, остающихся в нулевых строках должно  быть  четным,
а в единичных – нечетным.  Лучше  всего  рассматривать  единичные  строки  и
оставлять  те  коэффициенты   минимального   ранга,   которые   чаще   всего
повторяются в этих строках. В общем случае для получения  минимальной  формы
выполняют следующие действия:
1) Подсчитывают, сколько раз в единичных строках встречаются  термы  первого
ранга и оставляют из них те, которые встречаются максимальное число раз.
2) Находят нулевые строки, в которых встречаются оставленные в  первом  шаге
термы и их не обнуляют.
3) Рассматривая нулевую строку, в которой остался  одни  единичные  термы  и
находят в ней еще единичный терм, встречающийся  максимальное  число  раз  в
единичных строках, в которых еще не было оставлено ни одного терма и.т.д.
Метод Квайна-Мак-Класки может быть применим при  минимизации  этого  базиса,
при этом кроме эффективных значений функции, где  [pic]включаются  некоторые
min-термы, где  [pic].  Метод  Квайна-Мак-Класки  применим  для  минимизации
базисов стрелки пирса и штриха Шеффера.
      Не полностью определенные ФАЛ           (1.6)
Определение: не  полностью  определенные  ФАЛ  от  n  переменных  называется
функции, заданные на множестве наборов меньше чем [pic].
Если  количество  неопределенных  наборов  равно  m   то   путем   различных
доопределений можно получить [pic] различных функций.
Пример: доопределить функцию [pic]
Где символ * означает "может быть".
Доопределим *=0
1)[pic]
Доопределим *=1
2) [pic]
Если доопределять *=0 или *=1 то получим минимальный вариант:
3)[pic]
Пример показывает, что доопределение функции существенно влияет на  конечный
результат  минимизации.  При  доопределении  [pic]  можно  руководствоваться
правилом: МДНФ не полностью определенных функций получается  как  дизъюнкция
наиболее коротких по числу букв импликант функции [pic] на  всех  наборах  и
функциях, которые в совокупности покрывают все импликативные СНФ, и  [pic]на
всех наборах, где функция не определена.
Пример: найти минимальную форму для [pic]
Составим таблицу истинности:

|[pic]          |[pic]          |[pic]          |[pic]          |[pic]          |
|0              |0              |0              |0              |1              |
|0              |0              |0              |1              |*              |
|0              |0              |1              |0              |*              |
|0              |0              |1              |1              |0              |
|0              |1              |0              |0              |*              |
|0              |1              |0              |1              |0              |
|0              |1              |1              |0              |1              |
|0              |1              |1              |1              |*              |
|1              |0              |0              |0              |*              |
|1              |0              |0              |1              |1              |
|1              |0              |1              |0              |0              |
|1              |0              |1              |1              |*              |
|1              |1              |0              |0              |0              |
|1              |1              |0              |1              |*              |
|1              |1              |1              |0              |1              |
|1              |1              |1              |1              |*              |

1) доопрделим *=1 и получим минимальный вид функции[pic]
[pic]
Доопрделим *=0
[pic]
Оптимальное  доопрделение  функций  соответствующее  минимальному   покрытию
может быть найдено по методу Квайна.
|               |[pic]          |[pic]          |[pic]          |[pic]          |
|[pic]          |               |               |V              |               |
|[pic]          |V              |               |V              |               |
|[pic]          |               |V              |               |V              |
|[pic]          |               |               |V              |               |

В  результате  получится  минимальный  вид  функции  вида:  [pic]ее  таблица
единичных значений тогда будет: [pic]
      Временные булевы функции.   (1.7)
Определение: Временная булева  функция  –  логическая  функция  вида  [pic],
принимающ
1234
скачать работу

Минимизация ФАЛ

 

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

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


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