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

Привет, Вы узнаете о том , что такое минимизация булевых функций, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое минимизация булевых функций , настоятельно рекомендую прочитать все из категории Теория конечных автоматов.

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

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

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

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

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

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

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

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

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

3. Об этом говорит сайт https://intellect.icu . Размеры подкуба можно увеличивать за счет включения в них пустых (фиктивных) клеток матрицы.

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. Произведите минимизацию булевых функций, заданных десятичными эквивалентами, методами Квайна – МакКласски, Гаврилова – Копыленко и по матрицам Карно. Сравните результаты минимизации.

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

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