Минимизация ФАЛРефераты >> Математика >> Минимизация ФАЛ
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 | 1 |
| 1 |
Минимизировать функцию:
|
|
|
|
|
| 1 | 1 | 1 | |
| 1 | |||
|
|
|
|