Контрольная работа: Булевы функции

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

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

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

7.1.Метод Квайна

Метод Квайна основывается на применении двух основных соотношений.

1. Соотношение склеивания

где А — любое элементарное произведение.

2. Соотношение поглощения

Справедливость обоих соотношений легко проверяется.

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

Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью.

Для доказательства достаточно показать, что произвольная простая импликанта р = может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания): по всем недостающим переменным исходной функции f, получаем совокупность Sконституент единицы. При склеивании всех конституент из Sполучим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество Sконституент обязательно присутствует в совершенной ДНФ функции fпоскольку р — ее импликанта.

Минимизация по методу Квайна выполняется по следующему алгоитму:

1. Выполняются все склеивания в СДНФ.

2. Выполняются все поглощения.

3. Результирующая функция проверяется на возможность дальнейшего склеивания и поглощения.

4. После получения сокращенной ДНФ строится импликантная матрица, по которой находятся “лишние” импликанты.

Пример. Пусть имеется булева функция, заданная таблицей истинности (табл 9). Ее СДНФ имеет вид:

f= ÚÚÚÚÚ

Для удобства изложения пометим каждую конституенту единицы из СДНФ функции fкаким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной х3) и с конституентой 3 (по переменной х2 ) конституента 2 с конституентой 4 и т. д. В результате получаем:

1-2:

1-3:

2-4:

3-4:

4-6:

5-6:

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

Далее производим склеивания получаемых элементарных произведений. Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания: