02Глава21-22 (Полезная книги), страница 5

В данном случае импликанты AC и являются обязательными. Их сумма покрывает все минтермы, следовательно, тупиковая форма Она единственна и поэтому является минимальной.

Таблица 18.

Пример. Найти минимальную ДНФ функции, используя метод Квайна и метод импликантных матриц:

Сокращенная ДНФ

Импликантная матрица функции дана в табл.19.

Таблица 19

Так как нет столбцов с одной отметкой, то ни одна из импликант не является обязательной. Найдем минимальное количество простых импликант, накрывающее все колонки.

Возможны две тупиковые формы функции:

;

Обе формы содержат одинаковое число букв и, следовательно, обе являются минимальными.

Возможны другие тупиковые формы данной функции, но они не минимальны:

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

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

Карта Вейча для двух переменных (а), для трех (б), для четырех (в), для пяти (г), представляет собой таблицу с определенным порядком следования наборов (в клетках таблицы – номера минтермов соответствующего числа переменных) (рис.3).

Рис.3.

Для удобства пользования картами на полях проставляют значения переменных.

Таблица функции записывается в карту обычным способом 1(0) – в квадратах, соответствующих наборам, где f(x₁ x₂ … x_n)=1(0).

Следует иметь виду, что порядок расположения наборов таков, что при переходе между соседними квадратами по строке или столбцу меняется форма лишь одной переменной в наборе. В этом смысле первая строка карты является соседней с последней, а первый столбец – соседний с последним.

Отсюда возникают возможности проведения операции склеивания, исходя из расположения единиц в карте Вейча.

Правила склеивания с помощью карт Вейча.

Два минтерма склеиваются (рис.4), если они расположены:

1. по соседству – в одной строке или одном столбце (рис.4,а);

2. в противоположных концах одной строки или одного столбца (рис.4,б);

3. в одинаковых местах двух карт (рис.4,в), последнее – для n>4.

рис.4.

Алгоритм метода минимизации с помощью карт Вейча.

1. Нанести функцию на карту.

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

3. Выбираются те комбинации, которые объединяют наибольшее количество единиц и при этом накрывают все единицы карты функции. Они являются простыми импликантами функции.

4. Если только одна импликанта покрывает какую-либо единицу на карте, то эта импликанта является существенной (обязательной).

5. Из совокупности простых импликант выбираются минимальные формы функции.

Метод позволяет получить все возможные МДНФ:

Метод Блека-Порецкого.

Используется для получения сокращенной ДНФ из любой произвольной функции представления [5].

Идея построения сокращенной ДНФ по произвольной ДНФ вытекает из следующего определения: если в ДНФ для данной функции f(x₁ … x_n) входит две конъюнкции вида Ax_i и Bx_i, то имеет место равенство D=D\/AB, где D – ДНФ, эквивалентная функция f.

Алгоритм метода Блека-Порецкого.

1. Провести все возможные склеивания любых двух смежных термов, представляющих соответствующие элементарные конъюнкции, получить L-разрядный троичный набор и построить матрицу ранга n.

2. Над полученными элементарными конъюнкциями ранга (n-1) провести операции склеивания и поглощения, образовать элементарные конъюнкции нижнего ранга и т.д.

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

4. Строится импликантная матрица и определяется максимальное покрытие.

Метод удобен при машинных способах минимизации.

Пример. Найти минимальную форму для заданной функции:

1. Матрица исходных данных 3. Матрица ранга (n-2)

0 0 0 1 2 0 2 1

0 0 1 0 2 0 2 1

0 0 1 1 2 0 1 2

1 0 0 1 2 0 1 2

1 0 1 0

1 0 1 1

2. Матрица ранга (n-1)*

0 0 2 1

2 0 0 1

0 0 1 2

2 0 1 0

2 0 1 1

1 0 2 1

1 0 1 2

4. Вычеркиваем одинаковые строки матрицы ранга (n-2) и получаем

A B C D

2 0 2 1

2 0 1 2

5.

где 0 – инверсия переменной, 1 – переменная, 2 – отсутствует переменная.

§6. Минимальные конъюнктивные нормальные формы булевых функций.

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

Рассмотрим наиболее простой алгоритм поиска МКНФ, использующий выражение МКНФ через инверсию от МКНФ обратной функции.

Обратной функцией f₁(x₁ x₂ … x_n) называется

f ₂(x₁ x₂ … x_n)= f₁(x₁ x₂ … x_n).

Алгоритм метода.

1. исходную функцию представляют в СДНФ;

2. находят СДНФ обратной функции;

3. пользуясь любым из известных методов, находят МДНФ обратной функции;

4. инверсия от МДНФ обратной функции после соответствующих преобразований с использованием формул де Моргана представляет МКНФ исходной функции.

Пример. Найти МКНФ функции:

1. СДНФ

2. Так как обратная функция имеет значение 1 на тех наборах, на которых f(ABC) принимает значение 0, то в СДНФ обратной функции входят те минтермы, которые отсутствуют в СДНФ функции f(ABC):

СДНФ

1. Используем метод карт Вейча для отыскания МДНФ обратной функции (рис.9). Сокращенная ДНФ включает простые импликанты: AC, , BC, .

Из них обязательными является АС и . Функция имеет две минимальные формы:

1. Переходим к МКНФ f(ABC):

Пример. Найти МКНФ функции:

1. Карта Вейча для f(ABC) приведена на рис.10, а.

2. Используем карту Вейча для отыскания МДНФ (рис.10,б).

Функция имеет единственную МДНФ:

1. Находим МКНФ исходной функции:

§7. Минимальные формы не полностью определенных булевых функций.

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

Наборы, на которых функция не определена, называется запрещенными или избыточными.

Форма представления функции существенно зависит от выбора значений ее на избыточных наборах.

Пример. Функция f(ABC) приведена в табл.20.

Таблица 20

A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

f(ABC) 1 0 0 0 - 1 1 -

МДНФ

МДНФ

Рассмотрим общий метод получения МДНФ не полностью определенных булевых функций.

Пусть булева функция f(x₁ x₂ … x_n) не определена на p наборах аргументов. Тогда полностью определенная функция φ(x₁ x₂ … x_n) называется эквивалентной функции f(x₁ x₂ … x_n), если ее значения совпадают со значениями функции f(x₁x₂…x_n) на тех наборах, на которых последняя определена.

Если функция f(x₁ x₂ … x_n) не определена на р наборах, то существует 2^p различных функций, эквивалентных данной.

Задача минимизации не полностью определенных функций сводится к отысканию такой эквивалентной функции φ_i(x₁x₂…x_n), которая имеет простейшую минимальную форму.

Введем эквивалентные функции φ₀(x₁x₂…x_n) и φ₁(x₁x₂…x_n), которые на всех запрошенных наборах функции f(x₁x₂…x_n) принимают значения 0 и 1 соответственно.

Теорема. Минимальная ДНФ не полностью определенной функции f(x₁x₂…x_n) совпадает с дизъюнкцией тех самых коротких импликант функции φ₁(x₁x₂…x_n), которые совместно поглощают все единицы функции φ₀(x₁x₂…x_n) и ни одна из них не является лишней.

Доказательство следующее.

Предположим, что φ_i(x₁x₂…x_n) – некоторая эквивалентная функция. Тогда все минтермы СДНФ φ_i входят в СДНФ функции φ₁. Поэтому любая импликанта функции φ_i(x₁x₂…x_n) будет совпадать с импликантой функции φ₁ или поглощаться ею, т.е. среди импликант функции φ₁ всегда найдется такая, которая поглощает любую импликанту любой эквивалентной функции φ₁. Следовательно, самыми короткими импликантами из всех накрывающих единицы функции f(x₁x₂…x_n) будут импликанты функции φ₁.

Среди всех эквивалентных функций φ₀ имеет минимальное количество минтермов. Следовательно, и количество простых импликант (из набора импликант функции φ₁), необходимых для поглощения минтермов φ₀, будет минимальным. Дизъюнкция самых коротких импликант функции φ₁, которые совместно накрывают все единицы φ₀, представляет МДНФ f(x₁x₂…x_n).

Пример. Найти МДНФ функции:

причем наборы < >, < >, < >, < > являются запрещенными.

Проводим процедуру, описанную в методе Квайна, используя минтермы как функциональных, так и запрещенных наборов функции:

Составляем импликантную матрицу (табл.21), используя минтермы только функциональных наборов функции.

Таблица 21

Минимальная форма исходной функции

Импликанта ACD не поглощает ни один минтерм функциональных наборов, так как образована из тех минтермов функции φ₁, которые в φ₀ не входят.

Пример. Найти МДНФ и МКНФ не полностью определенной функции

Причем наборы , и являются запрещенными.