русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2015-08-31; просмотров: 1808; Нарушение авторских прав


 

Обозначим через множество всех наборов из 0 и 1. Его можно рассматривать как множество всех вершин единичного -мерного куба, который в дальнейшем будем называть просто -мерным кубом, а наборы – вершинами куба. На рис. 1. представлена проекция 3-мерного куба на плоскость.

 

° 111

 

011 ° ° 101 °110

 

001° ° 010 ° 100

 

° 000

Рис. 1

 

Пусть – фиксированная система чисел из 0 и 1 такая, что . Множество всех вершин куба таких, что

,

называется -мерной гранью, то есть имеем подмножество :

.

Очевидно, что -мерная грань является -мерным подкубом куба .

Число -мерных граней куба равно .

Число называют рангом грани и обозначают . Таким образом, сумма размерности и ранга грани равна . Размерности граней куба (ранги) могут изменяться в пределах от 0 до . Нульмерные грани ( ) – это вершины куба ; одномерные грани называют ребрами; грань размерности – это сам куб .

Куб и совокупность его граней образуют топологический объект, называемый кубическим комплексом. Относительно этого достаточно сложного объекта многие вопросы остаются нерешенными до настоящего времени. Например, неизвестно каково минимальное множество вершин, обладающим тем свойством, что в этом множестве есть по крайней мере один представитель от каждой -мерной грани (задача Лупанова о «протыкании» граней).

Сопоставим каждой функции алгебры логики подмножество вершин , в которых эта функция равна 1:

.

При этом булевым операциям над функциями будут соответствовать теоретико-множественные операции над подмножествами . Следующая таблица устанавливает соответствие между аналитическими и геометрическими объектами.

 

Таблица 1. Соответствие аналитических и геометрических объектов

Аналитический объект Геометрический объект
Двоичные слова длины Вершины -мерного куба
Булева функция Подмножество вершин
Элементарная конъюнкция -грань куба
Формулы Соотношения
Д. н. ф. Объединение граней
Представление функции д. н. ф. Покрытие гранями

 



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

 

 

 


Рис. 2

Первое покрытие состоит из четырех точек (нульмерных граней) и ребра (одномерной грани), второе – из трех ребер (одномерных граней).

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

Сформулируем геометрическую задачу о покрытии, эквивалентную задаче о минимизации булевой функции.

Дано подмножество вершин единичного -мерного куба. Найти покрытие этого подмножества содержащимися в нем гранями с наименьшим рангом.

Переход от аналитического к геометрическому языку в ряде случаев помогает быстро найти МДНФ. Например, для функции из рассмотренного выше примера гранями, содержащимися в , являются одномерные (покрывают две вершины) и нульмерные (покрывают одну вершину) грани. Множество состоит из 6 вершин, поэтому его покрытие включает не менее трех граней. Следовательно, ДНФ – минимальная.



<== предыдущая лекция | следующая лекция ==>
Понятие ДНФ. Проблема минимизации булевых функций | Определение тупиковой ДНФ


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.003 сек.