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

1 1 1 данном случае оказались рядом. Для этого достаточно отождествить, т.е. «склеить», отмеченные на рис. 4.11 жирной линией стороны. Фактически это соответствует свертыванию карты в вертикальный ци­ линдр, в котором левый край совмещается с правым (также отмечено жирной лини­ ей). При их совмещении единицы первого и последнего столбцов окажутся соседни­ ми и для них можно будет применить алго­ ритм склеивания. Таким образом, и без мысленного сво­ рачивания карты можно циклически пере­ ставлять аргументы в строках и столбцах. Из всей четверки единиц по вертикали со­ хранится общая переменная второй и тре­ тьей строк х2, а по горизонтали — общая переменная первого и последнего столбцов х,: f ( x ix2xix4) = х2* 4 . Такие нестандартные приемы минимизации булевых выраже­ ний упрощают саму процедуру _и экономят время. Пусть f ( x xX2XyX4) = Х |Х 2 Х 3 Х4 V Х ,Х 2^ з Х 4 v X ^ X jF V X 3W 4 = x 2 F 3 . Рис. 4.11. Иллюстрация склейки карты Карно в цилиндр для_ Дхрсрс з х Д = хрс2х 3 x 4 v V Х ,Х2Х3Х4 V Х |Х 2Х3Х4 V v Х |Х 2х 3х 4 Карта Карно для этой функции представлена на рис. 4.12. Аналогично предыдущему случаю здесь удобно переставить переменные в столбце, что соответствует свертыванию карты в горизонтальный цилиндр. В этом примере контуры объединены «через край» при сверты­ вании карты Карно в горизонтальный цилиндр так, чтобы совмес­ тились верхний и нижний края карты и образовался квадрат. В пер­ вой и последней строках сохраняется общая переменная г 2, а в первом и втором столбцах — общая переменная xj. Их конъюнк­ ция и является ответом. Пусть / ( Х | Х 2Х>Х4 ) = Х ,Х 2 Х 3Х4 V Х (Х 2Х 3Х4 V Х | Х 2Х 3 Х4 V X |X 2X 3X4 = X , Х 2 Х4 V V X iX 2X 4 = Х 2Х 4 . Нанесем единицы на карту (табл. 4.28). *3*4 *3*4 *3*4 *3*4 т А / Л * 1 *2 1 1 1 Х,Х 2 1 1 _ 1 ___ * 1 *2 V W Рис. 4.12. Горизонтальный цилиндр на карте Карно 184