Главная
страница 1страница 2страница 3

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ


Выпускная работа по


«Основам информационных технологий»



Магистрант

кафедры математической кибернетики механико-математического факультета

Авлочинская Татьяна

Руководители:

доцент Супрун Валерий Павлович,

ст. преподаватель Кожич Павел Павлович

Минск – 2011 г.

Оглавление

Список обозначений ко всей выпускной работе 3

Реферат на тему «Декомпозиция интервальных форм частичных булевых функций на основе решения логических уравнений» 4

Введение 4

Глава 1. Основные понятия и определения теории булевых функций 6

Глава 2. Разработка теоретических основ декомпозиции на основе решения логических уравнений. 10

Глава 3. Программа для решения логических уравнений 18

ЗАКЛЮЧЕНИЕ 27

Список литературы к реферату. 28

Предметный указатель к реферату. 29

Интернет ресурсы в предметной области исследования. 30

Действующий личный сайт в WWW 31

Граф(круг) научных интересов 32

Тестовые вопросы по Основам информационных технологий 33

Презентация магистерской диссертации 34

Список литературы к выпускной работе. 35

Приложение 36

37




Список обозначений ко всей выпускной работе


ДНФ

дизъюнктивная нормальная форма

КНФ

конъюнктивная нормальная форма

ПНФ

полиномиальная (разностная) нормальная форма

SAT (ВЫП)

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

SAT-solver

программа для решения задачи SAT (решатель)

Реферат на тему «Декомпозиция интервальных форм частичных булевых функций на основе решения логических уравнений»

Введение


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

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

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

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

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

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



Глава 1. Основные понятия и определения теории булевых функций


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

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

Для дальнейшего изложения методов и алгоритмов решения логических уравнений необходимо ввести ряд понятий и определений [2].

Переменная  называется булевой переменной. Булевой называется функция , зависящая от булевых переменных и принимающая значение 0 или 1.

Пусть  — булево пространство, построенное над переменными булева вектора . Элементами этого пространства являются -компонентные наборы (векторы)  нулей и единиц. Булева функция, значения 0, 1 которой определены на всех элементах , называется полностью определенной.

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

Вектор  компоненты которого принимают значения из алфавита  называется троичным. Число различных -компонентных троичных векторов равно .

Если  или , то -я компонента вектора называется определенной, в противном случае — неопределенной.

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

При этом интервал  содержит  -компонентных булевых векторов, где  — число неопределенных компонент вектора ).

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

Будем считать, что троичные векторы  и  ортогональны по -й компоненте (), если и только если -я компонента принимает значение  в одном из векторов и значение  — в другом (здесь и далее полагаем, что ).

Векторы  и  называются ортогональными (), если они ортогональны, по крайней мере, по одной из компонент.

Под троичной (булевой) матрицей понимается матрица, элементы которой принимают значения из множества .

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

Конъюнкция переменных, или их отрицаний, взятых не более одного раза, называется элементарной конъюнкцией.

Под дизъюнктивной нормальной формой (ДНФ) функции  понимается дизъюнкция конечного числа элементарных конъюнкций.

Дизъюнкция переменных, или их отрицаний, взятых не более одного раза, называется элементарной дизъюнкцией.

Под конъюнктивной нормальной формой (КНФ) функции  понимается конъюнкция конечного числа элементарных дизъюнкций.

Под полиномиальной нормальной формой (ПНФ) функции  понимается сумма по модулю 2 конечного числа элементарных конъюнкций.

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

Троичной матрицей ДНФ  функции  будем называть троичную матрицу  со следующими свойствами:



  1. Число строк  равно длине ;

  2. -я компонента -й строки  равна , если аргумент  входит в j-е слагаемое  с отрицанием (без отрицания), и -я компонента -й строки принимает неопределенное значение, если аргумент  (или ) отсутствует в -м слагаемом  [2].

Рассмотрим основные определения, связанные с понятием логического уравнения и поиском решения логических уравнений.

Под логическим уравнением будем понимать выражение

,

где  — некоторая формула, задающая булеву функцию.

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

Среди различных вариантов постановки задачи о решении логического уравнения выделим следующие два, которые можно считать основными [1]:



  1. Найти, по крайней мере, один корень уравнения (1.1), неважно какой именно.

  2. Найти все корни уравнения (1.1).

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

Далее в этой работе в основном делается акцент на второй вариант постановки задачи о решении логических уравнений.

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

Набор логических уравнений вида



называется системой логических уравнений.

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

.




следующая страница >>
Смотрите также:
Программа для решения логических уравнений 18
263.8kb.
3 стр.
Программа вступительных испытаний в магистратуру по направлению 010100. 68 Математика Программа обсуждена на заседании кафедры ит
150.53kb.
1 стр.
Решение логических задач средствами алгебры логики Обычно используется следующая схема решения: изучается условие задачи; вводится система обозначений для логических высказываний
137.11kb.
1 стр.
Решение уравнений
72.09kb.
1 стр.
Решение нелинейных уравнений
180.73kb.
1 стр.
Лабораторная работа №4 «решение дифференциальных уравнений в частных производных»
56.72kb.
1 стр.
Об одном точном решении уравнений Эйнштейна для вакуума
43.04kb.
1 стр.
Программа вступительных испытаний, проводимых свфу самостоятельно, для поступающих в свфу в 2013 году по математике
76.42kb.
1 стр.
Решение уравнений
65.62kb.
1 стр.
Квадратные уравнения
79.73kb.
1 стр.
Отчет о выполнении задания по теме "Системы линейных алгебраических уравнений"
51.29kb.
1 стр.
Программа дисциплины «Дополнительные главы дифференциальных уравнений»
230.85kb.
1 стр.