Лекция №3. Минимизация булевых функций
 Скачать 400.58 Kb.
|
|
1 Лекция №3 по математической логике и теории алгоритмов Тема: Минимизация булевых функций. Существует немало методов минимизации логических функций, однако наибольший интерес представляют те, которые могут быть формализованы, а соответственно запрограммированы без соответствующих сложностей. Широкое внедрение вычислительной техники и систем управления во все сферы человеческой деятельности и усложнение задач, решаемых этими системами, требуют разработки новых и совершенствования существующих методов логического проектирования цифровых устройств. Логическое проектирование при этом понимается в широком смысле, основанное на методах минимизации логических функций, которое включает не только статику систем, т.е. их структуру и функциональные связи, но и анализ динамики как на уровне структуры, а также на уровне переходных процессов, связанную с изменением переменных и временными характеристиками элементов. В связи с этим исследования, направленные на развитие методов минимизации логических функций, обеспечивающих упрощение, улучшение основных характеристик, а также снижение времени и стоимости разработки внедрения системы никогда не потеряют своей актуальности. Определение 1. Длиной элементарной конъюнкции называется количество переменных в ней. Определение 2. Длиной дизъюнктивной нормальной формы называется сумма длин, входящих в неё. Определение 3. Элементарные конъюнкции называются соседними, если они имеют одинаковую длину и отличаются на одну переменную (в одной элементарной конъюнкции присутствует переменная, а в другой её отрицание). Определение 4. Дизъюнктивная нормальная форма минимальной длины, тождественно равной данной булевой функции, называется ее минимальной дизъюнктивной нормальной формой (МДНФ). Определение 5. Дизъюнктивная нормальная форма, не допускающая склеек, называется тупиковой. Очевидно, что у любой булевой функции существует минимальная дизъюнктивная нормальная форма, так как из всех длин l = 1, 2, 3..., равных ей дизъюнктивных нормальных форм, всегда 2 можно выбрать минимальную. К сожалению, единственность отсутствует: многие булевы функции имеют несколько МДНФ одинаковой длины. Существуют различные способы минимизации булевых функций. 1. Метод непосредственных преобразований. Преобразования логической формулы к минимальной дизъюнктивной нормальной форме разбивается на 2 этапа: 1. Пусть удалось выделить в ДНФ множитель вида x x , тогда, заменив его единицей, можно уменьшить длину ДНФ. Эта процедура называется склейкой по переменной х. Чтобы обнаружить склейку в ДНФ, необходимо найти в ней соседние элементарные конъюнкции. С помощью соседних элементарных конъюнкций получается склейка. Иногда она бывает минимальной, но чаще минимизацию можно продолжить. 2. С помощью сокращающих логических тождеств возможно ещё уменьшить длину тупиковой дизъюнктивной нормальной формы. К ним относятся: а) x xy x - закон поглощения; б) y x y x x - закон сокращения. Пример. Совершенная дизъюнктивная нормальная форма задана в двоичном виде 0000 0001 0010 0101 0110 0111 1000 1001 1010. Привести ее к минимальной дизъюнктивной нормальной форме. Р еш ен и е 1. Запишем булеву функцию в виде формулы, после чего применим процедуру склейки. t yz x yt x t z y z y t yz x yt x t z y z y x x t yz x z y x yt x t z y z y x t yz x t t z y x t z z y x t z y x x t t z y x t z y x t z y x t z y x yzt x t yz x t z y x t z y x t z y x t z y x 2. Получена тупиковая ДНФ. Применим закон сокращения. ) ( ) ( ) ( ) ( yz x yt x t y z y z t y x t z y t z t y x t z z y t yz x yt x t z y z y Полученная дизъюнктивная нормальная форма является минимальной (МДНФ), так как дальнейшие упрощения невозможны. 3 П р и м е р . Привести булеву функцию z yz x ) ( к минимальной дизъюнктивной нормальной форме. Решение. Приведем булеву функцию к ДНФ: ) ( ) ( ) ( ) ( z x z y x yz xz z z y x yz xz z yz x z yz xz z yz x z yz x z yz x z yz x z yz x Применив закон поглощения, получаем МДНФ булевой функции: z x yz xz z x z y x yz xz 2. Карты Карно. Карты Карно являются одним из наиболее удобных способов минимизации. Они впервые появились в одной из статей Мориса Карно в 1953 году. Это специальные таблицы, дающие возможность упростить процесс поиска минимальной формы булева выражения с помощью графического представления 6 n . Они имеют вид прямоугольника, разделённого на n 2 клеток, в каждой из которых – двоичный n – мерный набор значений функции ) , , ( 1 n x x f f из таблицы истинности. Для 2 n карта Карно имеет вид таблицы, состоящей из 4 2 2 клеток: 2 1 x x 2 1 x x или 00 10 2 1 x x 2 1 x x 01 11 Логическая функция ) , ( 2 1 x x f f на карте Карно представлена совокупностью клеток, заполненных единицами (1) или пустотами (0), если известны её значения при всем наборе аргументов, т.е. известна таблица истинности или СДНФ. При 3 n карты Карно имеют вид таблицы, с 4 2 8 2 3 клетками: Изменение 3 2 x x Изменение 1 x 3 2 1 x x x 3 2 1 x x x 3 2 1 x x x 3 2 1 x x x 3 2 1 x x x 3 2 1 x x x 3 2 1 x x x 3 2 1 x x x Для построения минимальной ДНФ производится «склеивание» единиц. Склеиваются только соседние клетки, которые отличаются значением одной переменной. Процесс сводится к объединению в группы единичных клеток Карно. При этом общие переменные сохраняются, а различные опускаются. 4 Рассмотрим более подробно процедуру минимизации с помощью карт Карно. Алгоритм «склеивания» с помощью карт Карно имеет следующий вид: 1. Привести булеву функцию к СДНФ. 2. Нанести единицы на карту Карно. 3. Объединить соседние единицы контурами, охватывающим m 2 клеток, где , 2 , 1 , 0 m При этом может оказаться, что единица попадает одновременно в два контура. Если контур охватывает более одной пары единиц одновременно, то предпочтительно его не дробить на пары, а рассматривать как единый целый контур, например, квадрат. 4. Провести упрощения, т.е. исключить члены, дополняющие друг друга до 1 внутри контура, следя за тем, чтобы переменные внутри контура были связаны операцией конъюнкции. 5. Объединить оставшиеся члены (по одному в каждом контуре) функцией ИЛИ, т.е. дизъюнкцией. 6. Записать полученное упрощенное булево выражение в ДНФ. При заполнении карт Карно необходимо обратить внимание на порядок заполнения строк и столбцов значениями переменных. Последовательность значений переменных должна сохраняться неизменной. При таком заполнении каждые две соседние клетки отличаются лишь значением одной переменной. Нарушение порядка заполнения строк или столбцов не запрещается, но может не дать ожидаемого результата. Рассмотри примеры минимизации булевых функций с помощью карт Карно. Пример. Пусть xyz z xy yz x z y x z y x f ) , , ( Решение. Нанесём единицы на карту и обведем сначала попарно двумя контурами: y x y x y x y x z 1 1 z 1 1 Такое действие соответствует заключению в скобки слагаемых yz x z y x и xyz z xy . Вынося за скобки одинаковые конъюнкции, в скобках получаем дизъюнкцию противоположных значений одной из переменных. В данном примере этому шагу соответствуют 5 конъюнкции z z y x и z z xy . Поэтому объединение двух соседних единиц всегда приводит к закону инверсии, согласно которому дизъюнкция противоположных значений переменной равна 1. Поэтому при записи ответа после применения карты Карно переменные, заключенные в общий контур, связываются конъюнкцией (как и общий множитель при вынесении за скобки), а такие отдельные конъюнкции, т.е. различные контуры, объединяются между собой дизъюнкцией. Если записать полученный результат, то, очевидно, к нему вновь можно применить то же правило: y y x x xy y x z y x f ) , , ( Однако в данном примере удобнее рассмотреть целиком весь квадрат из четырех единиц и сравнить переменные, записанные на горизонтальных и вертикальных клетках. y x y x y x y x z 1 1 z 1 1 Очевидно, общие множители сохранятся после упрощения (ведь их можно было вынести за скобки), а инвертируемые уйдут согласно закону инверсии. Поэтому целесообразнее опустить инвертируемые пары x x и z z , а в ответе сохранить общую для всех клеток переменную y Рассмотрим пример минимизации булевой функции, содержащей четыре переменных. Пример. Пусть ) , , , ( t z y x t z y x t z y x t z y x t z y x t z y x t z y x f Решение. Занесем единицы в соответствующие клетки карты Карно: t z t z t z t z y x 1 1 y x 1 1 y x y x 1 1 Рассмотрим переменные, заключенные контуром в квадрат. Среди них есть повторяющиеся в соседних клетках (это x и t ) и 6 инвертируемые (это пары y y, и z z, ). Повторяющиеся переменные как общий множитель мы сохраним, а инвертируемые – опустим. Из контура, содержащего две единицы, вынесем переменные y x, , расположенные на одной строке, а также одинаковую для первых двух столбцов переменную z , при этом опустим инвертируемую пару t t, . После этих преобразований булева функция примет вид: z y x t x t z y x f ) , , , ( Пример. Пусть ) , ( y x y x y x y x f Решение. Составим карту Карно для двух переменных. y y x 1 x 1 1 Нанесем на карту Карно единицы. Объединим единицы в контуры. Так как получилось два контура, один из которых дает x , а другой y , то упрощенный вариант булевой функции содержит дизъюнкцию двух членов: x и y . Попадание единицы в два и более контуров соответствует закону идемпотентности x x x , поэтому каждое слагаемое (элементарная конъюнкция) может быть представлено столько раз, сколько нужно для упрощения. При этом они группируются с другими слагаемыми, с которыми попали в один контур, независимо. Фактически сделано следующее: y x x y y y x y x x y x y x y x Получили ) , ( y x y x f |