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

таблица истинности или СДНФ. При п = 3 карты Карно имеют вид таблицы с 23 = 8 = 2 • 4 клетками (табл. 4.25). Т а б л и ц а 4.25 Карта Карно для булевых функций трех переменных Изменение х 2х 3 ____ __ Изменение Х[ *1*2*3 Х|Х}Хч *1*2*3 *1*2*3 *1*2*3 *1*2*3 *1*2*3 *1*2*3 Для п = 4 карты Карно имеют 24= 16 = 4 4 клеток (табл. 4.26). Т а б л и ц а 4.26 Карта Карно для булевых функций четырех переменных Изменение Х \Х2 Изменение х3х4 * 1 *2*3*4 *1*2*з*4 Х 1 Х 2 Х 3 Х 4 *1*2*3*4 *1*2*3*4 W 3 X 4 *l*2*i*4 Х 1 Х 2 Х 3 Х 4 xix2x3x4 Х 1 Х 2 Х 3 Х 4 Х 1 Х 2 Х 3 Х 4 *1*2*3*4 Х 1 Х 2 Х 3 Х 4 Х 1 Х 2 Х 3 Х 4 XiX 2 X 3 X 4 * 1 * 2 *з * 4 Для построения минимальной ДНФ производится «склеива­ ние» единиц. Склеиваются только соседние клетки, которые от­ личаются значением одной переменной. Процесс сводится к объ­ единению в группы единичных клеток карт Карно. При этом об ­ щие переменные сохраняются, а различные опускаются. Рассмотрим более подробно процедуру минимизации с помо­ щью карт Карно. Алгоритм «склеивания» с помощью карт Карно имеет следующий вид. 1. Привести булеву функцию к ДНФ. 2. Нанести единицы на карту Карно. 3. Объединить соседние единицы контурами, охватывающими 2т клеток, где т = 0, 1, 2, 3. При этом может оказаться, что еди­ ница попадает одновременно в два контура. Если контур охваты­ вает более одной пары единиц одновременно, то предпочтитель­ нее его не дробить на пары, а рассматривать как единый целый контур, например квадрат. 4. Провести упрощения, т.е. исключить члены, дополняющие друг друга до 1 внутри контура, следя за тем, чтобы переменные внутри контура были связаны операцией конъюнкции. 5. Объединить оставшиеся члены (по одному в каждом конту­ ре) функцией ИЛИ, т.е . дизъюнкцией. 181