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

Цель минимизации – получить логическую функцию, эквивалентную заданной, но содержащую минимальное число соответствующих логических переменных. Методов минимизации существует достаточно много, но мы рассмотрим только наиболее часто используемые на практике.

Алгебраическое упрощение – это один из способов минимизации логических функций, в котором используются теоремы и законы булевой алгебры.

Алгоритм минимизации заключается в нахождении и группировании пары «соседних» наборов переменных с целью сокращения одной переменной по закону склеивания. Этот процесс продолжается до тех пор, пока не останется ни одной пары соседних наборов. Окончательное логическое выражение упрощается с помощью теорем склеивания или поглощения.

Однако алгебраическое упрощение обычно используется для несложных определенных функций. При большом числе переменных и для неполных функций этот метод практически неприемлем.

Минимизация методом Квайна–МакКласски используется при большом числе переменных и малом числе фиктивных состояний булевых функций. Это табличный метод, основанный на последовательном склеивании соседних наборов. Алгоритм этого метода достаточно простой и поэтому удобен для программной реализации [10].

Минимизация методом матриц Карно применяется в случаях, когда исходная функция содержит не более шести – семи логических переменных.

Возможности использования матриц Карно для минимизации булевых функций зависят от умения выделять группы клеток матрицы с одинаковыми состояниями функций, представляющих собой соседние состояния переменных. Такие группы соседних симметричных клеток называются подкубами. Таким образом, подкуб – это набор клеток матрицы с одинаковыми состояниями функции, в котором одна или более переменных имеют постоянное значение. Число клеток в подкубе должно быть равно 2^k, где k = 0, 1, 2, 3,.... Следовательно, подкубы могут быть одно-, двух-, четырехклеточными и т.д. При выделении одноклеточного подкуба ни одна переменная не исключается, поскольку одна клетка матрицы определяется одним полным набором; при выделении двухклеточного подкуба исключается одна переменная; при четырехклеточном исключаются две переменные и т.д. Подкубы являются симметричными сплошными или разнесенными прямоугольниками. При выделении подкубов руководствуются следующими правилами.

1. Клетки матрицы с одинаковыми значениями функции (только единичные или только нулевые) должны быть обязательно включены хотя бы в один подкуб.

2. Подкуб должен объединять возможно большее число клеток матрицы (из ряда 2^k) с одинаковым значением функции.

3. Размеры подкуба можно увеличивать за счет включения в них пустых (фиктивных) клеток матрицы.

4. Одна и та же клетка матрицы может быть включена в разные подкубы, если это способствует их расширению.

5. Число подкубов должно быть минимальным.

Рис. 2.2 Рис. 2.3

Следующим после выделения подкубов этапом минимизации является составление логических формул. Здесь следует рассмотреть два варианта:

а) выделение подкубов по логическим единицам;

б) выделение подкубов по логическим нулям.

При выделении подкубов по единицам логическая формула будет иметь вид МДНФ. Элементарная минимальная конъюнкция для каждого подкуба определяется переменными, которые не изменяют своего состояния в данном подкубе. Значения переменных записываются соответственно их состоянию в клетках матрицы. Полученные по всем подкубам конъюнкции дизъюнктируют, получая при этом МДНФ.

При выделении подкубов по нулям логическая формула получится в виде МКНФ. В этом случае для каждого подкуба составляется элементарная минимальная дизъюнкция, причем значения переменных, имеющих по данному подкубу постоянное состояние, инвертируют. Далее элементарные дизъюнкции конъюнктируют, получая МКНФ.

Так, для известной нам булевой функции (табл. 2.1) матрицы Карно и выделенные в них подкубы представлены на рис. 2.2 и 2.3.

Выделяя подкубы по единицам, получаем МДНФ: Y =d ++, то же – по нулям, получаем МКНФ: Y = (+ d) (+) (+). Обычно выбирают тот вариант, в котором меньшее число переменных.

Контрольные задания

1. Преобразуйте выражение с целью упрощения.

2. Преобразуйте последовательно левую и правую части уравнения с целью доказательства заданного тождества:

.

3. Найдите значения каждой из следующих булевых функций при а = 1; b = 0; c = 0; d = 1: ; ; ; .

4. Докажите справедливость тождеств:

; ; .

5. Запишите все функции двух переменных в совершенных дизъюнктивной и конъюктивной нормальных формах.

6. Приведите заданную функцию к совершенным дизъюнктивной и конъюктивной нормальным формам .

7. Преобразуйте выражение , разложите на конституенты нуля и единицы, представьте таблицей состояний и матрицей Карно.

8. Логическую функцию преобразуйте и представьте, используя теорему де Моргана с помощью только функции Вебба и только штриха Шеффера.

9. Произведите упрощение логического выражения, используя законы логики Буля. С помощью таблиц истинности сравните упрощенное выражение с исходным: .

10. Произведите аналитическим путем преобразования и упрощение левой и правой частей тождества с целью его доказательства:

.

11. Произведите минимизацию булевых функций, заданных десятичными эквивалентами, методами Квайна – МакКласски, Гаврилова – Копыленко и по матрицам Карно. Сравните результаты минимизации.

Y₁ = {3,4,5,7,11,17,19,23,24,26,27}; Y_Ф = {1,2,6,8,10,12,13,16,21,22}.

Дата добавления: 2014-01-07