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

с помощью диаграмм Вейча.

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

При минимизации следует руководствоваться следующими правилами:

1) Строится и размечается прямоугольная таблица, число клеток которой равно числу возможных наборов аргументов.

2) В клетки таблицы заносятся значения булевой функции. При поиске клеточки таблицы аргумент набора равный 0 берется без отрицания, а равный 1 – с отрицанием. В найденную клетку записывают значение функции.

3) Обводят контурами все 0 с соблюдением следующих правил:

- контур должен быть прямоугольным;

- внутри контура не должно быть единиц;

- при обводке следует получить минимальное число контуров максимальной площади;

- число нулей в контуре должно быть равно степени числа 2 (1, 2, 4, 8, 16,…);

- одна и та же клетка, заполненная нулем может входить в несколько контуров;

- при обводке следует учитывать, что самая верхняя и самая нижняя строки таблицы являются соседними. Соседними являются также крайний левый и крайний правый столбцы.

- количество контуров должно быть как можно меньше, а площадь контуров – как можно больше.

4) Записывают минимальное выражение как функцию Пирса над логическими выражениями, которые описывают контура таблицы. Логическое выражение для контура представляет собой операцию Пирса от аргументов. Для поиска логического выражения для контура выясняют, от каких аргументов он зависит. Если все нули контура приписаны к аргументу , то в логическое выражение этот аргумент входит. Если все единицы контура помечены инверсией аргумента, то в выражение вписывается . Если в контуре есть нули, помеченные и нули, помеченные , то в описание контура этот аргумент не входит.

ВАЖНО! При минимизации в базисах Шеффера и Пирса действуют два дополнительных правила:

Если контур занимает половину таблицы, то над аналитическим описанием этого контура ставится дополнительное отрицание;

Если в таблице только один контур, то над ним также следует поставить дополнительное отрицание.

Естественно, если в таблице только один контур, и он занимает половину таблицы, то над ним ставятся два дополнительных отрицания.

Пример: минимизировать в базисе Пирса функции:

, , , .

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

Минимизация булевых функций большого числа аргументов.

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

Рассмотрим идею простейшего метода минимизации функций произвольного числа аргументов, который легко программируется и пригоден для минимизации не полностью определенных булевых функций. Используя эту идею легко получить алгоритмы минимизации булевых функций не только в МДНФ и МКНФ, но и в базисах Пирса и Шеффера.

В начале рассмотрим получение МДНФ.