Карты Карно. 4 страница
Метод кубических покрытий. Исходным является комплекс кубов C0 такой, что все единицы и неопределенные значения функции покрыты кубами из C0, а нули не покрыты. Т.е. C0 состоит из 0-кубов, соответствующих единицам и неопределенным значениям функции. C0={ 000000, 000001, 000010,000011, 000100, 000110,001000, 001100, 001110,001111, 010010, 010011,010100, 010101, 010110,010111, 011000, 011001,011010, 011011,011101,011110, 011111, 100000,100001, 100010, 100011,101000, 101001, 101100,101101, 101110,110000,110001, 110010, 110011,110101, 110110, 110111,11000, 111001, 111011,111100, 111101, 111110,111111} На множестве C0 выполняем операцию ‘*’ между всеми кубами, результат заносим в таблицу (т.к. операция коммутативная, то достаточно заполнить половину таблицы). Все кубы, которые не образовали ни одного 1-куба, являются импликантами нулевого ранга и образуют Z0. На следующем шаге работаем с множеством C1 – множеством всех 1-кубов, полученных на предыдущем шаге. Повторяем операцию ‘*’ на C1, выбирая множество импликант первого ранга Z1 (1-кубов, не образовавших ни одного 2-куба). Так действуем, пока множество Ci не пустое. В таблицах импликанты множества Zi выделены цветом. Для нахождения МДНФ необходимо выделить множество экстремалей, т.е. импликант, покрывающих обособленные вершины (вершины, покрытые единственной импликантой). Для нахождения обособленных вершин будем последовательно вычитать из куба е множества Z все остальные кубы; если результат вычитания не пустой, то е – кандидат на экстремаль. Если результат вычитания покрывает хотя бы одно единичное значение функции, то е – экстремаль нулевого ранга. На следующем шаге удаляем из множество Z все экстремали нулевого ранга, получаем Z1; удаляем из множества единичных значений функции L единицы, покрытые экстремалями нулевого ранга, получаем L1. Повторяем вычитание и извлекаем экстремали первого ранга. Так делаем, пока не будут покрыты все единицы функции. В таблицах экстремали отмечены цветом. Следует отметить, что перед вычитанием будем упорядочивать множество импликант, т.е. если кубы разной размерности покрывают одинаковые наборы единиц функции, то из рассмотрения удаляем куб меньшей размерности; если первый куб покрывает те же единицы функции, что и второй куб, плюс еще какие-то, то удаляем второй куб.
Кубы
Кубы
Кубы
|
