Спирина, М.С. Дискретная математика

CD CD CD CD АВ Л ' \____ АВ V АВ АВ Рис. 4.10. Карта Карно для f (ABCD) = ABCD v ABCD v ABCD v ABCD v v ABCD v ABCD Рассмотрим примеры минимизации булевой функции, содер­ жащей четыре переменные. f(ABCD) = ABCD v ABCD v ABCD v ABCD v ABCD v ABCD. Занесем единицы в соответствующие клетки карты Карно (рис. 4.10). Рассмотрим переменные, заключенные контуром в_квадрат. Среди них есть повторяющиеся в соседних клетках (это А и D) и инвертируемые (это пары В, В и С, С). Повторяющиеся перемен­ ные как общий множитель мы сохраним, а инвертируемые — опу­ стим. Из_ контура, содержащего две единицы, вынесем перемен­ ные А, В, расположенные на одной строке, а также одинаковую для первых двух столбцов переменную С, при этом опустим ин­ вертируемую пару D, D. После этих преобразований булева функ­ ция примет вид: f(ABCD) = _AD_w ABC. _ Проверка: £{ABCD) = ABC{D v_Z>) v ACD(B v В ) v ACD(B v v f i ) = ABC v AD(C v C) = ABC v AD, т.е. результаты минимиза­ ции совпали. Пусть /(Х|Х 2 ХзХ4) = Х 1 Х 2 Х 3 Х 4 v * 1 * 2 * 3*4 V x ’lx2xix4 v х хх2х{хА. Как обычно, занесем единицы в табл. 4.27. Но чередование переменных в строке и столбце ничем не ог­ раничено. Такой порядок был введен для удобства последующего упрощения. Поэтому можно сделать так, чтобы все единицы в Т а б л и ц а 4.27 Карта Карно JC 3 X 4 *3*4 *3*4 X 3 X 4 * 1 * 2 * 1 * 2 1 1 * 1 * 2 1 1 * 1 * 2 183