Булевы функции. Основные формулы булевой алгебры. Аналитическая запись булевых функций в булевом базисе. Дешифраторы. Мультиплексоры, страница 10

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

В некоторых случаях МДНФ инверсной функции проще, чем МДНФ исходной функции. Пример:

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

Обычно, при необходимости получения минимального выражения в базисе Пирса или Шеффера функцию минимизируют в булевом базисе, а затем, используя правила де Моргана, преобразуют функцию.

Пример: запишем функции  и  в базисе Шеффера:

;

.

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

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

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

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

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

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

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

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

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

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

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

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