Минимизация булевых функций

ТЕМА 3. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ Переменные xi или xi - термы. Полный набор из n термов образует конституенту. 1 Определение. В процессе минимизации некоторые термы из конституент пропадут. Тогда оставшуюся часть дизъюнкта или конъюнкта называют импликантой. Определение. Множество вершин куба, на которых функция равна “1” и которые сами образуют куб, порождают единичный интервал этой функции. 2 Определение. Единичный интервал I a булевой функции называется максимальным, если не найдется единичный интервал I b , включающий I a . Определение. Конъюнкция, соответствующая максимальному единичному интервалу, называется простой импликантой этой функции. 3 Определение. Дизъюнкция всех простых импликант булевой функции называется сокращенной ДНФ этой функции. Пример. Найдем минимальную ДНФ для полностью определенной функции (таблица 1). 4 Метод Квайна Мак-Класски 1 этап минимизации полностью определенной функции Переход от совершенной ДНФ к сокращенной однозначен и осуществляется с помощью попарного сравнения конституент ярусов (номера которых отличаются на единицу). Получим максимальные единичные интервалы (рис. 2). 5 Склеивание ярусов, которые отличаются в одном разряде Рис. 2 6 Максимальные единичные интервалы: 0--; -11 Сокращенная ДНФ: f ( x1, x2 , x3 ) x1 x2 x3 . Второй этап минимизации полностью определенной функции Построение и покрытие таблицы Квайна. Таблица Квайна – двумерная таблица, каждой строке которой соответствует максимальный единичный интервал, столбцу – конституента. 7 На пересечении i -й строки и j -го столбца находится единица, если j -я конституента входит в i -й максимальный интервал, в противном случае в клетке (i, j) ставят "0“ (таблица 2). Минимальная ДНФ = Сокращенная ДНФ = x1 x2 x3 . 8 Вывод: Таким образом, после минимизации, во-первых, сокращается количество переменных от 15 (3 переменные × 5 наборов, где функция равна 1) до 3, во-вторых уменьшается количество операций. 9 Причем в качестве первого аргумента берется значение i -го разряда единичного интервала, в качестве второго – значение j -го разряда нулевого интервала. 11 Пример. Рассмотрим нахождение минимальной ДНФ слабоопределенной функции. f ( x1, x2 ,..., x7 ) 1 этап минимизации слабоопределенной функции Для каждого единичного интервала строится таблица различий. 12 Ядро покрытия образуют две обязательные строки а и е. Максимальный единичный интервал: 0 Простая импликанта: x1x5. 13 Ядро покрытия образуют две обязательные строки b и d. Максимальный единичный интервал: 1 0 Простая импликанта: x2 x4 . 14 Ядро покрытия № 1 образуют две обязательные строки a и e. Ядро покрытия № 2 - обязательная строка g. 15 Максимальные единичные интервалы: ; 1 Простые импликанты: x1x5 ; x6 . Сокращенная ДНФ: f ( x1, x2 ,..., x7 ) . 2 этап минимизации слабоопределенной Функции Переход от сокращенной ДНФ функции к тупиковой ДНФ этой функции. 16 Тупиковая ДНФ булевой функции получается в результате покрытия столбцов строками импликантной таблицы (двумерной таблицы, каждой строке которой соответствует максимальный единичный интервал, столбцу – единичный интервал, а на пересечении i -й строки с j -м столбцом находится 1, если j -й единичный интервал входит в i -й максимальный интервал, в противном случае на пересечении находится 0). 17 Построим для рассматриваемого примера импликантную таблицу (таблица 6). 18 Перебор всех тупиковых ДНФ булевой функции определяет выбор минимальной ДНФ этой функции (по количеству букв, операций). В рассматриваемом примере одна тупиковая ДНФ: ~ f ( x1, x2 ,..., x7 ) . Минимальная ДНФ = тупиковой ДНФ = x1x5 x2 x4 . 19 Метод карты Карно Таблицы карт Карно, n – количество переменных n 2 n 3 20 n 4 n 5 21 n 6 22 Основные правила минимизации: 1. Каждая клетка карты соответствует конституенте. Одну и ту же конституенту можно склеивать с другими конституентами многократно a a a a a a ,a a a a a a . 23 2. Покрытие с помощью правильных конфигураций (горизонтальные и вертикальные прямоугольники, квадраты). 3. Число клеток, входящих в любой прямоугольник, есть 2i , i 1, 2 ... n 1 . 4. 2i смежным клеткам соответствует ранг: r n i - количество переменных в простой импликанте. Смежными клетками считаются и те, которые лежат на границах карты. 5. Соседние две, четыре единицы обводят общим контуром для трех переменных. 24 6. Получение максимальных единичных интервалов, простых импликант, сокращенной ДНФ. 7. Определение таблицы Квайна, как для полностью определенной функции и получение минимальной ДНФ. 25 Примеры (карта Карно для трех переменных) a) r 3 2 1; Простая импликанта: x1 (максимальный единичный интервал 1 - -). Сокращенная ДНФ = минимальной ДНФ = x1 . 26 б) r 3 2 1 Простая импликанта: x3 (максимальный единичный интервал - -0). Сокращенная ДНФ = минимальной ДНФ = x3 . 27 в) r 3 2 1; Простая импликанта: x3 (максимальный единичный интервал - -1). Сокращенная ДНФ = минимальной ДНФ = x3 . 28 г) r 3 1 2; Простая импликанта: x1x3 (максимальный единичный интервал 0 - 0). Сокращенная ДНФ = минимальной ДНФ = x1x3 . 29 д) см. пример (таблица 1) 1. r 3 2 1; Простая импликанта: x1 (0 - -). 2. r 3 1 2; Простая импликанта: x2 x3 (- 11). Сокращенная ДНФ = минимальной ДНФ = x1 x2 x3 . 30 Правило упрощения заполненной карты Карно для четырех переменных. 1. Клетки крайнего левого столбца должны рассматриваться как соседние для клеток крайнего правого столбца; клетки верхней строки - как соседние для клеток нижней строки. 2. Соседние две, четыре или восемь единиц обводят общим контуром. 3. Контур должен быть правильной конфигурации. 31 а) Примеры (карта Карно для четырех переменных) Обл.1.: r 4 2 2 ; простая импликанта: x2 x4 (- 0 -0). Обл.2.: r 4 1 3 ; простая импликанта: x1x2 x4 (01-1). Сокращенная ДНФ = минимальной ДНФ = x2 x4 x1x2 x4 32 б) Обл.1.: r 4 2 2 ; простая импликанта: x3 x4 (- -00) Обл.2.: r 4 2 2 ; простая импликанта: x2 x4 (-1-0) Обл.3.: r 4 2 2 ; простая импликанта: x1x4 (1- -0) Обл.4.: r 4 2 2 ; простая импликанта: x2 x3 (-10-) Обл.5.: r 4 2 2 ; простая импликанта: x1x3 (1-0-) Сокращенная ДНФ = минимальной ДНФ = 33