Основные способы задания двоичных функций

Скачать 0.52 Mb.

Название	Основные способы задания двоичных функций
страница	3/4
Дата публикации	15.03.2015
Размер	0.52 Mb.
Тип	Лекция

100-bal.ru > Математика > Лекция

1 2 3 4

Лекция №5

5.1 Минимизация двоичных функции.

Пусть двоичная функция f представлена в виде ДНФ:

(5.1.1)

Определение 5.1.2: ?????????? представления (5.1.1) булевой функции f называется число операций «» и «» в записи (5.1.1).

Замечание 5.1.3: Операции «отрицания» в определении 5.1.2 не учитываются.

Определение 5.1.4: Задача минимизации для функции f заключается в нахождении заданий функции f в виде ДНФ, у которых сложности минимальны. Такие ДНФ называются минимальными (МДНФ).

Определение 5.1.5: Импликантами двоичной функции f называются элементарные конъюнкции, входящие во всевозможные ДНФ функции f. Импликанта функции f называется простой, если все элементарные конъюнкции, полученные из неё удалением некоторых переменных, не являются импликантами функции f.

Утверждение 5.1.6: Пусть . Следующие утверждения эквивалентны:

является импликантой функции f;
;
.

Доказательство: Покажем эквивалентность первых двух утверждений. Если – импликанта и – та ДНФ, в которую входит , например, , то

.

Обратно, если – некоторая ДНФ, то в силу тождества конъюнкцию можно дописать в качестве (k+1)-ой импликанты в эту ДНФ не нарушая равносильности.

Эквивалентность утверждений 2 и 3 следует из тождеств:

,

.

Утверждение доказано.

Утверждение 5.1.7: В минимальной ДНФ функции f () все импликанты являются простыми.

Доказательство: Пусть - минимальная ДНФ функции f. Предположим, что импликанта не простая. Тогда её можно представить в виде произведения двух элементарных конъюнкций от разных переменных, одна из которых, например, также является импликантой функции f. Согласно утверждению 5.1.6:

, или иначе

.

Таким образом, получено противоречие с минимальностью исходной ДНФ.

Утверждение доказано.

Из этого утверждения вытекает, что задачу минимизации в классе ДНФ можно решать в два этапа.

1-ый этап: Находят все простые импликанты функции f. Дизъюнкция всех простых импликант функции f называется сокращённой ДНФ этой функции.

Замечание 5.1.8: Сокращённая ДНФ функции f действительно является ДНФ для f, поскольку, повторяя доказательство утверждения 5.1.7 можно в произвольной ДНФ функции f заменить все импликанты на простые.

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

5.2 Геометрическая интерпретация минимизации ДНФ.

Зададим двоичную функцию на n-мерном двоичном кубе. Как было отмечено ранее, при таком задании элементарным конъюнкциям ранга k соответствуют такие множества вершин, графы связности которых имеют вид (k-n)-мерных кубов. Поскольку дизъюнкции элементарных конъюнкций соответствует объединение множеств вершин таких подкубов, то каждой ДНФ функции f соответствует некоторое покрытие множества M_f единичных вершин функции f (области истинности) подмножествами, имеющими в качестве графов связности подкубы. Простым импликантам функции f будут соответствовать подкубы максимальных размерностей, покрывающие вершины из M_f.

Соответственно, первая задача (1-ый этап) решается перечислением всех максимальных подкубов, содержащихся в графе связности множества M_f.

Вторая задача (2-ой этап) заключается в нахождении минимальных (по числу подкубов) покрытий множества M_f максимальными подкубами.

Рассмотрим пример. Пусть двоичная функция f (x₁, x₂, x₃, x₄) имеет геометрическое задание, изображённое на рис. 5.2.1:

1011

X₃
X₄

0010

1100

0100

1110

1010

0110

0101

1001

1101

X₂

0011

0001

0111

1111

Рисунок 5.2.1

0000

1000

X₁

Граф связности такой функции имеет вид:

1110

0111

0011

1110

1000

1010

1100

1110

Выпишем сокращённую ДНФ, записывая простые импликанты в том же порядке, в каком они изображены в графе связности:

Легко видеть, что тупиковыми будут две ДНФ:

,

,

соответствующие покрытиям:

Минимальной будет только вторая тупиковая ДНФ.

1 2 3 4

Похожие:

	1. Функции, их свойства и графики Числовая функция. Способы задания... ...		Урок по теме «Модуль действительного числа» Здравствуйте, ребята! Сегодня на уроке мы постараемся повторить всё, что мы узнали о модуле числа, основные способы решения уравнений,...
	Конспект урока возрастание и убывание функций. Экстремумы. (Тема... Цель урока: ввести понятия возрастания и убывания функций, экстремумов функций, научить применять эти понятия при чтении и построении...		Решение д Общий член последовательности имеет вид В этой главе вводится понятие числовой последовательности, изучаются основные способы задания числовой последовательности, главное...
	Приложение №2 Вопросы к промежуточной аттестации Хирургическая обработка рук различными способами. Способы обработки операционного поля, хирургического инструментария, шовного материала....		2. место дисциплины в структуре образовательной программы Для реализации поставленных целей в курсе рассматриваются основные положения оптимизации налогов, изучаются методы налогового планирования,...
	“ Альтернативные источники энергии” Также описаны основные группы рисков, характерные, на современном этапе, для мировой экономики. Приведены основные проблемы развития...		Урок изучения нового материала Цель. Закрепить определение и свойства тригонометрических функций. Назначение тригонометрических функций, необходимость их возникновения....
	Радиофизический факультет Содержание дисциплины «Теория функций комплексного переменного» направлено на ознакомление студентов с теорией аналитических функций,...		Программа по формированию навыков безопасного поведения на дорогах... Цель: формирование знаний о конфликте и его функций. Определение путей предупреждения конфликтных ситуаций и способы их решения,...
	Общая трудоемкость дисциплины Содержание дисциплины «Теория функций комплексного переменного» направлено на ознакомление студентов с теорией аналитических функций,...		Расчёт коэффициента передачи по току низкочастотного фильтра В данной курсовой работе рассматриваются методы анализа линейных цепей (классификация методов, их применение) и способы их линеаризации,...
	Т. Эдисон. Цель Тема Дискретная случайная величина, способы ее задания. Числовые характеристики. Функция распределения и ее свойства. 19		Рабочая программа дисциплины Тема Дискретная случайная величина, способы ее задания. Числовые характеристики. Функция распределения и ее свойства. 19
	Цуканова Ольга Анатольевна Тема Дискретная случайная величина, способы ее задания. Числовые характеристики. Функция распределения и ее свойства. 19		Урок по теме: «Математическое моделирование» Тема Дискретная случайная величина, способы ее задания. Числовые характеристики. Функция распределения и ее свойства. 19

Школьные материалы