Минимизация булевых функций. Минимизирующие карты Карно. Метод Куайна-МакКласки
Ясно, что при разработке логических схем, немаловажной является задача минимизации количества используемых элементов (другими словами, логических операций).
В связи с этим, возникает задача минимизации логических функций в некотором классе формул. В частности, в классах ДНФ и КНФ.
Минимальная ДНФ Такая ДНФ, которая содержит наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей ДНФ. Минимальная КНФ Такая КНФ, которая содержит наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей КНФ.
Процесс нахождения минимальных форм, собственно, и называется минимизацией. В простых случаях, для минимизации достаточно тождественных преобразований. В более сложных – используются специальные алгоритмы.
Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ, является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя членами, содержащими одинаковые переменные, вхождения которых (с отрицанием и без) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например:
\[ \;\overline
Аналогично для КНФ:
\[ (\;\overline
Возможность поглощения следует из очевидных равенств
Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск членов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей.
Минимизирующие карты Карно
Графический способ минимизации булевых функций. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как построенная соответствующим образом таблица истинности функции.
Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.
Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.
В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.
Булевы функции \(N\) переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе \(2^N\) различных элементарных членов.
Элементарные члены СДНФ или СКНФ образуют структуру, топологически эквивалентную \(N\) -мерному кубу. Действительно, если рассматривать набор значений функции \(x_1,\,\ldots,\,x_N\) как \(N\) -мерный вектор \(\
Например, для функции двух переменных, заданной таблицей истинности:
Источник
Что значит минимизация булевой функции
В предыдущем разделе мы познакомились с различными типами ДНФ и научились их находить визуально по матрице Грея. Перейдем к изучению формальных методов построения сокращенной, безызбыточных, минимальных и кратчайших ДНФ булевой функции, заданной совершенной или произвольной ДНФ.
Интерес к кратчайшим и минимальным ДНФ основан на их оптимальности (по длине и рангу соответственно), которая положительно проявляется, по крайней мере, в следующих двух случаях. Во-первых, с оптимальными ДНФ легче оперировать, то есть вычислять значения функции, строить матрицу Грея и подставлять в другие формулы. Во-вторых, оптимальные ДНФ более предпочтительны для построения по ним схем из логических элементов: дизъюнкторов, конъюнкторов и инверторов.
Пример. Рассмотрим мажоритарную функцию.
Нарисуем схемы по совершенной и кратчайшей ДНФ. Логические элементы изобразим в виде соответственно обозначенных прямоугольников.
Схема, построенная по кратчайшей ДНФ (справа), оказалась проще: она содержит меньше элементов. •
Интерес к сокращенной ДНФ вызван тем, что она является промежуточной при построении кратчайших, минимальных и безызбыточных ДНФ.
Безызбыточные ДНФ интересны как сами по себе, так как часто оказываются близкими к оптимальным, так и тем, что среди них находятся все минимальные и простые кратчайшие ДНФ.
Определение. Минимизировать булеву функцию это значит построить ее кратчайшую или минимальную ДНФ или все кратчайшие или все минимальные ДНФ (постановка задачи уточняется дополнительно).
Рассмотрим двухэтапный подход к минимизации булевой функции, основанный на теоремах о кратчайшей и минимальных ДНФ (подраздел 9.2), утверждающих, что все минимальные и хотя бы одна из кратчайших ДНФ состоят из простых импликант.
Первый этап: найдем все простые импликанты функции, то есть конъюнкции ее сокращенной ДНФ.
Второй этап: из сокращенной ДНФ выделим конъюнкции искомых ДНФ (кратчайших или минимальных).
Далее наряду с языком ДНФ будем использовать язык интервалов как более наглядный при визуальном решении и более удобный при компьютерной реализации алгоритмов. Напомним аналогию между рядом понятий (относящихся к одной и той же булевой функции) на упомянутых языках.
Источник
Минимизация булевых функций
Аналитические методы минимизации
Используя законы булевой алгебры, можно получить для одной и той же логической функции множество эквивалентных представлений. Чем проще аналитическое выражение функции, тем экономичнее и проще ее практическая реализация на интегральных микросхемах. Сложность булевой функции определяется ее рангом, т.е. количеством переменных в ее конъюнктивных или дизъюнктивных членах.
Представление булевой функции в Сов ДНФ в большинстве случаев не является минимальным.
Используя операции поглощения и склеивания, его можно существенно упростить. Часто используется неполное склеивание, при котором оба члена, участвовавших в склеивании (или один из них), могут повторно склеиваться с другими оставшимися членами Сов ДНФ.
В процессе минимизации важно отыскать смежные конституенты, которые отличаются только одним аргументом (в одну конституенту аргумент входит с инверсией, а в другую – без нее).
Две смежные конституенты, склеиваясь, образуют импликанту рангом на единицу ниже, чем исходные конституенты.
Используя, например, неполное склеивание последней коституенты в Сов ДНФ функции F 1 последовательно с остальными, приходим к следующему выражению:
Процесс многоступенчатого склеивания приводит к импликантам, которые не склеиваются с другими. Такие импликанты называют простыми. Форма записи булевой функции в ДНФ, состоящая только из простых импликант, называется сокращенной дизъюнктивной нормальной формой (Сокр ДНФ).
В некоторых случаях в Сокр ДНФ могут содержаться лишние импликанты, которые могут быть исключены без изменения значения функции.
Одним из методов отыскания лишних импликант является метод испытания членов: чтобы испытать некоторый член функции, следует исключить его из Сокр ДНФ и подставить в оставшееся выражение такие значения аргументов, которые обращают исключенный член в единицу. Если при такой подстановке оставшееся выражение окажется тождественно равным единице, то испытуемый член является лишним.
Найдем для примера тупиковую форму Сокр ДНФ
.
Испытаем член AC. AC = 1, если A = 1 и C = 1. Подставим в оставшееся выражение 
A = 1 и C = 1, получим
.
При B = 0 F(A, B, C) = 1·1 Ъ 0·0 = 1, но при 
F(A, B, C) = 0·1 Ъ 0·0 = 0. Следовательно, член AC не лишний.
Испытаем член BC, равный 1 при B = 0, C = 1. При этом
.
Последнее выражение равно 1 как при A = 1, так и при A = 0. Поэтому член 
– лишний.
Испытание члена 
по этой же методике показывает, что он не является лишним, в итоге тупиковая форма исходной функции имеет вид:
.
Минимизация булевых функций с помощью карт Карно
Для минимизации функций относительно небольшого числа переменной (не более шести) наиболее простым и наглядным является графический метод, использующий карты Карно.
Карта Карно – это прямоугольник, разбитый на квадраты, число которых равно числу наборов рассматриваемой функции, т. е. 2 n . Клетки размечаются так, чтобы наборы, для которых возможны смежные конституенты, оказались бы в соседних клетках.
При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. Например, для функции двух переменных А и В (рис. 5) карта Карно имеет вид
Единицы, представленные в клетках, обозначают конституенты единицы рассматриваемой функции. Отыскание минимальной ее формы сводится к определению варианта, при котором все конституенты единицы накрываются (охватываются контурами покрытия) наименьшим числом наиболее коротких импликант. Объединение клеток на карте эквивалентно выполнению операции склеивания.
Всегда нужно стремиться к минимальному количеству контуров и максимальной площади каждого из них, руководствуясь следующими правилами:
площадь контура покрытия должна быть S k = 2 m-i клеток, где 
– целое число, m – число переменных. Если, например, m = 3, то S k = 1, 2, 4, или 8 клеток;
число сокращаемых переменных N перем. = log 2 S k , т.е. при S k = 1 не сокращается ни одна переменная, при S k = 2 сокращается одна переменная и т.д.
В примере на рис. 5 пара единиц верхней строки охватывается импликантой Ā (т.е. обе клетки ) имеют общий аргумент Ā). Пара единиц правого столбца накрывается импликантой B, как общей для обеих клеток. Следовательно, минимальная ДНФ функции F(A,B) = Ā Ъ B.
Если имеется несколько вариантов объединения конституент контурами, то можно получить несколько различных эквивалентных минимальных ДНФ функции, одна из которых выбирается для реализации в цифровом устройстве.
Карту Карно удобно использовать и для минимизации функций, заданных в алгебраической форме, например,
.
Карта Карно, состоящая из 2 3 = 8 клеток, может быть размечена, как показано на рис. 6.
При охвате единиц контурами склеивания карту Карно можно сворачивать в цилиндр, как вдоль горизон-тальной, так и вертикальной оси. В результате все четыре единицы, расположенные в углах Карты, охватываются контуром с общей импликан-той 
. Такой минимизации соответствует выражение
.
Минимизация недоопределенных функций
Недоопределенность функции означает, что запрещенные наборы никогда не появятся в процессе работы устройства. Значит, такую функцию можно произвольно доопределить, установив ее значения на запрещенных наборах, и это не отразится на работе устройства, но обчит его реализацию.
Пусть необходимо минимизировать булеву функцию, заданную картой Карно (рис. 7).
Если группировать единицы в контурах только по исходному заданию (рис. 7, а), то минимальная форма функции будет иметь вид:
.
После доопределения функции (рис. 7, б), ее минимальная ДНФ (заметим, что это будет уже другая полностью определенная функция j ) оказывается предельно простой
.
Функция j , значения которой совпадают со значениями заданной функции F на тех наборах, где F определена, называется эквивалентной.
Таким образом, задача минимизации недоопределенной функции сводится к отысканию такой эквивалентной функции, которая имеет простейшую форму.
При синтезе комбинационных схем всегда возникает вопрос выявления опасных состязаний. С этой целью на практике пользуются простым и удобным формальный критерием Хаффмена: статические опасные состязания в устройстве с минимизированной структурой могут иметь место, если на карте Карно при охвате соседних клеток контурами склеивания окажутся хотя бы две соседние клетки, не покрытые контуром.
Поэтому устранение опасных состязаний достигается возвращением импликант, которые оказались лишними при переходе от сокращенной к тупиковой ДНФ.
Источник
Минимизация булевых функций
Аналитические методы минимизации
Используя законы булевой алгебры, можно получить для одной и той же логической функции множество эквивалентных представлений. Чем проще аналитическое выражение функции, тем экономичнее и проще ее практическая реализация на интегральных микросхемах. Сложность булевой функции определяется ее рангом, т.е. количеством переменных в ее конъюнктивных или дизъюнктивных членах.
Представление булевой функции в Сов ДНФ в большинстве случаев не является минимальным.
Используя операции поглощения и склеивания, его можно существенно упростить. Часто используется неполное склеивание, при котором оба члена, участвовавших в склеивании (или один из них), могут повторно склеиваться с другими оставшимися членами Сов ДНФ.
В процессе минимизации важно отыскать смежные конституенты, которые отличаются только одним аргументом (в одну конституенту аргумент входит с инверсией, а в другую – без нее).
Две смежные конституенты, склеиваясь, образуют импликанту рангом на единицу ниже, чем исходные конституенты.
Используя, например, неполное склеивание последней коституенты в Сов ДНФ функции F 1 последовательно с остальными, приходим к следующему выражению:
Процесс многоступенчатого склеивания приводит к импликантам, которые не склеиваются с другими. Такие импликанты называют простыми. Форма записи булевой функции в ДНФ, состоящая только из простых импликант, называется сокращенной дизъюнктивной нормальной формой (Сокр ДНФ).
В некоторых случаях в Сокр ДНФ могут содержаться лишние импликанты, которые могут быть исключены без изменения значения функции.
Одним из методов отыскания лишних импликант является метод испытания членов: чтобы испытать некоторый член функции, следует исключить его из Сокр ДНФ и подставить в оставшееся выражение такие значения аргументов, которые обращают исключенный член в единицу. Если при такой подстановке оставшееся выражение окажется тождественно равным единице, то испытуемый член является лишним.
Найдем для примера тупиковую форму Сокр ДНФ
.
Испытаем член AC. AC = 1, если A = 1 и C = 1. Подставим в оставшееся выражение 
A = 1 и C = 1, получим
.
При B = 0 F(A, B, C) = 1·1 Ъ 0·0 = 1, но при 
F(A, B, C) = 0·1 Ъ 0·0 = 0. Следовательно, член AC не лишний.
Испытаем член BC, равный 1 при B = 0, C = 1. При этом
.
Последнее выражение равно 1 как при A = 1, так и при A = 0. Поэтому член 
– лишний.
Испытание члена 
по этой же методике показывает, что он не является лишним, в итоге тупиковая форма исходной функции имеет вид:
.
Минимизация булевых функций с помощью карт Карно
Для минимизации функций относительно небольшого числа переменной (не более шести) наиболее простым и наглядным является графический метод, использующий карты Карно.
Карта Карно – это прямоугольник, разбитый на квадраты, число которых равно числу наборов рассматриваемой функции, т. е. 2 n . Клетки размечаются так, чтобы наборы, для которых возможны смежные конституенты, оказались бы в соседних клетках.
При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. Например, для функции двух переменных А и В (рис. 5) карта Карно имеет вид
Единицы, представленные в клетках, обозначают конституенты единицы рассматриваемой функции. Отыскание минимальной ее формы сводится к определению варианта, при котором все конституенты единицы накрываются (охватываются контурами покрытия) наименьшим числом наиболее коротких импликант. Объединение клеток на карте эквивалентно выполнению операции склеивания.
Всегда нужно стремиться к минимальному количеству контуров и максимальной площади каждого из них, руководствуясь следующими правилами:
площадь контура покрытия должна быть S k = 2 m-i клеток, где 
– целое число, m – число переменных. Если, например, m = 3, то S k = 1, 2, 4, или 8 клеток;
число сокращаемых переменных N перем. = log 2 S k , т.е. при S k = 1 не сокращается ни одна переменная, при S k = 2 сокращается одна переменная и т.д.
В примере на рис. 5 пара единиц верхней строки охватывается импликантой Ā (т.е. обе клетки ) имеют общий аргумент Ā). Пара единиц правого столбца накрывается импликантой B, как общей для обеих клеток. Следовательно, минимальная ДНФ функции F(A,B) = Ā Ъ B.
Если имеется несколько вариантов объединения конституент контурами, то можно получить несколько различных эквивалентных минимальных ДНФ функции, одна из которых выбирается для реализации в цифровом устройстве.
Карту Карно удобно использовать и для минимизации функций, заданных в алгебраической форме, например,
.
Карта Карно, состоящая из 2 3 = 8 клеток, может быть размечена, как показано на рис. 6.
При охвате единиц контурами склеивания карту Карно можно сворачивать в цилиндр, как вдоль горизон-тальной, так и вертикальной оси. В результате все четыре единицы, расположенные в углах Карты, охватываются контуром с общей импликан-той 
. Такой минимизации соответствует выражение
.
Минимизация недоопределенных функций
Недоопределенность функции означает, что запрещенные наборы никогда не появятся в процессе работы устройства. Значит, такую функцию можно произвольно доопределить, установив ее значения на запрещенных наборах, и это не отразится на работе устройства, но обчит его реализацию.
Пусть необходимо минимизировать булеву функцию, заданную картой Карно (рис. 7).
Если группировать единицы в контурах только по исходному заданию (рис. 7, а), то минимальная форма функции будет иметь вид:
.
После доопределения функции (рис. 7, б), ее минимальная ДНФ (заметим, что это будет уже другая полностью определенная функция j ) оказывается предельно простой
.
Функция j , значения которой совпадают со значениями заданной функции F на тех наборах, где F определена, называется эквивалентной.
Таким образом, задача минимизации недоопределенной функции сводится к отысканию такой эквивалентной функции, которая имеет простейшую форму.
При синтезе комбинационных схем всегда возникает вопрос выявления опасных состязаний. С этой целью на практике пользуются простым и удобным формальный критерием Хаффмена: статические опасные состязания в устройстве с минимизированной структурой могут иметь место, если на карте Карно при охвате соседних клеток контурами склеивания окажутся хотя бы две соседние клетки, не покрытые контуром.
Поэтому устранение опасных состязаний достигается возвращением импликант, которые оказались лишними при переходе от сокращенной к тупиковой ДНФ.
Источник
