Конспект лекций по дискретной математикеРефераты >> Математика >> Конспект лекций по дискретной математике
КДНФÞСДНФÞ{ТДНФ}Þ{МДНФ}
Распространение терминологии в отношении нулевого покрытия определяется на понятии импликанта как соответствие импликанте и на системе импликант.
ПРИМЕР: (минимизация булевой функции методом Квайна-Мак-Класки)
1) f4(x)=V(0,1,5,7,8,10,12,14,15)
(f=1)
f4(x)=&(2,3,4,6,9,11,13)
(f=0)
На этапе получения множества максимальных кубов целесообразно разделить множество ноль - кубов (К°(f)) на ряд подмножеств ,отличающихся количеством единиц .
В операцию склеивания в этом случае могут вступать только кубы ,относящиеся к соседним подмножествам ,то есть отличающиеся на единицу
ì 000X ü
ï X000 ÷ K°(f)=C°(f)
ï 0X01 ÷
Z(f)= í 01X1 ý Sa=36
ê X111 ú Sb=45
ê 111X ú
î 1XX0 þ
K1(f)=C1(f) Sa=10*3=30
Sb=40
Z(f)=C3(f) Sa=20
Sb=27
При минимизации не полностью определенной булевой функции множество максимальных кубов определяется на объединении множества существенных вершин и безразличных наборов в целях получения кубов наибольшей размерности .
2) Определение ядра покрытия .
Выполнение этого этапа реализуется с помощью таблицы покрытий .
Kаждая строка таблицы - максимальный куб(простая импликанта).
Каждый столбец - существенная вершина булевой функции (безразличные наборы не включаются).
Элементы этой таблицы отражают отношение покрытия ,то есть на пересечении i-ой строки и j-ого столбца ставится некоторая отметка в том случае если i-ый максимальный куб покрывает j-ую вершину .
Таблицу покрытий иногда называют импликантной таблицей с учетом того ,что каждый максимальный куб соответствует простой импликанте а существенные вершины конституантам
единицы(нуля).
Существенные вершины
макс. Кубы |
0000 |
0001 |
0101 |
0111 |
1000 |
1010 |
1100 |
1110 |
1111 | |
A |
000X |
* |
* |
| |
| |
| |
| | |||
B |
X000 |
* |
| * |
| |
| |
| | ||||
C |
0X01 |
* |
* |
| |
| |
| |
| | |||
D |
01X1 |
* |
* |
| |
| |
| |
| | |||
E |
X111 |
* |
| |
| |
| |
| |
* | |||
F |
111X |
| |
| |
| |
| |
* | ||||
1XX0 |
| * |
| * |
| * |
| * | ||||||
a |
b |
c |
d |
| |
| |
| |
| |
e |
Для полностью определенной булевой функции количество меток в каждой строке равно числу ноль - кубов покрываемых кубом данной строки .Для не полностью определенной функции количество меток в строке зависит от количества безразличных наборов покрываемых данным кубом .Для нахождения кубов ,принадлежащих ядру покрытия в таблице ищутся столбцы с единственной меткой .Строка ,которой принадлежит эта метка определяет куб ядра .
Т(f)={1XX0}
3) Определение множества минимальных покрытий .
На этом этапе из множества максимальных кубов не принадлежащих ядру покрытия ,выделяются такие минимальные подмножества ,с помощью каждого из которых покрываются оставшиеся вершины (не покрытые ядром) .
Реализацию этого этапа целесообразно производить с использованием упрощенной таблицы.
В упрощенной таблице вычеркнуты все кубы принадлежащие ядру и вершины покрываемые ядром.
Для решения задачи 3-го этапа можно использовать один из 3-х методов или их комбинацию:
1) Метод простого перебора
2) Метод Петрика
3) Дальнейшее упрощение.
1)На данном этапе целесообразно ввести обозначение максимальных кубов и существенных вершин.