Правило объединения клеток

Минимизация (упрощение) функций. Получение МДНФ.

Пусть дана функция в любом виде, построим для нее карты Карно.

Две соседние клетки отличаются только одной переменной, их объединение исключает одну переменную.

Объединение двух пар клеток (четырех клеток) исключает еще одну переменную и т. д.

1. Объединяют 2 соседние клетки и 4 клетки, образующие квадрат.

2. Объединяют клетки или пары клеток, крайние в столбцах или строках.

3. Объединяют полные столбцы или строки, пары рядом расположенных столбцов или строк, а также крайние столбцы и строки.

4. Объединяют клетки, столбцы и строки, симметричные относительно горизонтальных и вертикальных осей.

Для получения МДНФ следует включать в объединения максимальное количество клеток, а число объединений делать минимальным. При этом одна и та же клетка может входить в несколько объединений. Окончательно МДНФ равна дизъюнкции объединений клеток (укороченных неполных конъюнкций).

Карты Карно позволяют получить МДНФ. Если требуется упростить функцию (не обязательно в форме МДНФ), то после получения МДНФ ее можно дополнительно упростить. Пусть МДНФ равна AB+AC, еще более упрощенная форма A(B+C).

Карты Карно позволяют также проводить с функциями и другие операции. Например, пусть даны функции и . Для получения карт Карно F1=f1+f2 или F2=f1*f2 из карт Карно функций f1 и f2 необходимо для каждой клетки провести логическое сложение (для F1) или логическое умножение (для F2) нулей и единиц в картах Карно функций f1 и f2.

Например:

f1: , f2: , f1+f2: , f1*f2: , : , : .

Дата добавления: 2015-05-06