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

Т а б л и ц а 4.28 Карта Карно Х 3 Х4 X 3 X 4 X 3 X 4 X 3 X 4 x j x 2 1 1 Х \ Х 2 х , х 2 Х|Х 2 1 1 В свете описанных сверток ясно, что подобную карту нужно свернуть в шар и одновременно склеить четыре единицы, распо­ ложенные в углах. Для полученного квадрата вновь применим тот же алгоритм, сохранив переменные, одинаковые для первой_и последней строк (хД, а также первого и последнего столбцов (х4), объединив их в конъюнкцию. Однако, если есть неуверенность в правильности совершаемых действий, лучше циклически пере­ ставить переменные (в любую сторону) и упрощать по обычным правилам. Один из таких вариантов изображен на рис. 4.13. Горизонтальные аргументы сдвинули на 1 вправо, вертикаль­ ные — на 2 вниз. В данном случае был допущен большой произвол в действиях. Там, где на карте больше единиц, нужно так пере­ ставлять аргументы, чтобы как можно меньше единиц «рассека­ лось» границами карты и не нужно было дальше сворачивать. Рассмотрим еще несколько примеров на упрощение булевых функций с помощью карт_Карно. ПуСТЬ F(X i X2) = Х,Х2 V Х2Х, v х,х2. Составим карту Карно для двух переменных (табл. 4.29). Нанесем на карту Карно единицы. Объединим единицы в к о н ­ туры по два элемента. Так как получилось два контура, один из которых дает х и а второй х2, то упрощенный вариант булевой функции содержит дизъюнкцию двух членов: х, и х2. Попадание единицы в два и более контуров соответствует закону идемпотен- X3X4 X3X4 JC3X4 X3X4 х , х 2 х , х 2 Л Х\Х2 J Х[Х2 Рис. 4.13. Шар на карте Карно 185