|
|
| Лекция: Минимизация ФАЛ |
Шаг 2.
Шаг 4 пропускаем.
Шаг 5.
Выбираем те min-термы, при записи которых, МДНФ функции минимальна.
Шаг 6.
Недостаток метода Квайна – необходимость полного по парного сравнения всех
min-термов на этапе нахождения первичных импликант.
Идея модификации метода Квайна – метод Квайна-Мак-Класки. (1.4)
1. Каждая конъюнкция в ДСНФ представляется своим двоичным набором.
2. Вся совокупность номеров наборов разбивается на группы в зависимости от
числа единиц, имеющихся в номерах наборов (0-группа, 1-группа, 2-группа
и.т.д.).
3. Сравниваются две группы, отличающиеся на одну единицу.
4. В результате сравнения в номере набора, имеющего большее число единиц на
позиции, где обнаружится разница на одну единицу ставится прочерк.
5. В процессе преобразования возникают новые сочетания (n-группы).
6. Процесс преобразования длится до тех пор, пока возможна операция склеивания.
7. Элементы преобразованных групп являются первичными импликантами, которые
вместе с номерами исходных наборов образуют таблицы разметок.
8. В остальном эти методы совпадают с единственным уточнением – если в
результате таблицы разметок ни одна из строк не покрывает единицу столбца, то
надо выбрать номер столбца набора из предыдущей группы преобразований.
Определение: n-группа – это такой набор аргументов функции, что
число всех аргументов равных единице равно n, причем значении функции равно 1.
Пример:
Составим таблицу истинности:
| 
| 
| 
| 
| | 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)
Одним из способов графического представления булевых функций от небольшого
числа переменных являются карты Карно. Их разновидность – карты Вейча,
которые строятся как развертки кубов на плоскости, при этом вершины куба
представляются клетками карты, координаты которых совпадают с координатами
соответствующих вершин куба.
Для ДСНФ единицы ставятся в клетке, соответствующей номеру набора, на котором
значение функции равно единице, а ноль не ставится, а для КСНФ – наоборот.
Диаграмма для двух логических переменных (для ДСНФ):
Для трех переменных:
Карты Карно используются для ручной минимизации функций алгебры логики при
небольшом количестве переменных. Правило минимизации: склеиванию подвергаются
2,4,8,16, клеток и
клетки, лежащие на границе карты.
При числе переменных 5 и больше отобразить графически функцию в виде единой
плоской карты невозможно. Тогда строят комбинированные карты, состоящие из
совокупности более простых карт. Процедура минимизации заключается тогда в
том, что сначала находится минимальная форма 4-х мерных кубов (карт), а
затем, расширяя понятие соседних клеток, отыскивают min-термы для
совокупности карт. Причем соседними клетками являются клетки, совпадающие при
совмещении карт поворотом вокруг общего ребра.
Страницы: 1, 2, 3, 4, 5, 6
|
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|
