Минимизация дизъюнктивной нормальной формы
Конъюнкция двух булевых переменных. Литерал как любая формула вида x, где x — произвольная переменная. Минимизация системы функций. Поиск простых импликантов исходной системы. Построение матрицы покрытия и ее сокращение. Дизъюнктивная нормальная форма.
| Рубрика | Математика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 21.06.2014 |
| Размер файла | 32,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Оглавление
- 1. Дизъюнктивная нормальная форма
- 2. Алгоритм построения СДНФ
- 3. Тупиковая ДНФ
- 4. Минимизация булевых функций в классе ДНФ
1. Дизъюнктивная нормальная форма
Конъюнкция и дизъюнкция
Определение 1: Конъюнкцией (или логическое умножение) двух булевых переменных называется следующая функция . конъюнкция дизъюнктивный матрица
Определение 2: Дизъюнкцией (логическое сложение) двух булевых переменных называется следующая функция .
Дизъюнктивная нормальная форма (ДНФ)
Определение 3: Литерал -- любая формула вида x или xЇ, где x -- произвольная переменная. Литерал обозначается как x.
Т.е. литерал -- обозначение самого переменного или его отрицания.
Определение 4: Переменная или называется литералом (или буквой).
Определение 5: Конъюкция литералов, встречающихся не более чем по одному разу, называется элементарной конъюнкцией. Число букв входящих в неё называется её рангом. Элементарная конъюнкция называется полной относительно рассматриваемой булевой функции, если её ранг равен числу переменных данной функции.
Определение 6: Дизъюнкция конечного множества элементарных конъюнкций называется дизъюнктивной нормальной формой(ДНФ). Число элементарных конъюнкций, образующих дизъюнктивную нормальную форму(ДНФ) называется длиной ДНФ. ДНФ содержащая только полные элементарные конъюнкции называется совершенной ДНФ (или СДНФ). Любую логическую формулу А можно представить в виде ДНФ, а затем ДНФ в виде СДНФ.
2. Алгоритм построения СДНФ
Легко построить СДНФ, представляющую произвольную булеву функцию, заданную в табличной форме. Для этого достаточно выделить наборы , на которых функция принимает значение 1, и для каждого из них ввести в СДНФ полную элементарную конъюнкцию, где любая переменная присутствует с отрицанием, если , и без отрицания, если .
Очевидно, для любой булевой функции , кроме константы 0, существует единственная СДНФ (с точностью до порядка литералов и конъюнкций). Поэтому данная форма представления булевой функции является канонической.
3. Тупиковая ДНФ
Тупиковой ДНФ (ТДНФ) функции f называется такая ДНФ ее простых импликант, из которых нельзя выбросить ни одного импликанта, не изменив функции f.
Теорема: Всякая минимальная ДНФ некоторой функции является ее тупиковой ДНФ.
Для получения МДНФ функции f необходимо построить все ТДНФ функции f и выбрать те из них, которые содержат минимальное число букв.
4. Минимизация булевых функций в классе ДНФ
Задача минимизации системы булевых функций в классе ДНФ заключается в поиске такой системы ДНФ для заданной системы булевых функций, которая содержала бы минимальное число конъюнкций, на которых заданы ДНФ всех функций системы. Такую систему ДНФ будем называть кратчайшей. При решении этой задачи существенную роль играют понятия импликанты и простой импликанты .
Импликантой булевой функции называется такая элементарная конъюнкция литералов булевых переменных , если на любом наборе значений переменных , на котором равнa 1, значение функции также равно 1.
Простой импликантой называется такая импликанта, которая перестает быть импликантой при удалении из нее любого символа.
Классические методы решения поставленной задачи основаны на предварительном получении множества всех простых импликант заданной системы булевых функций и последующим выделением из него некоторого подмножества, которое и будет представлять решение. Нахождение кратчайшей системы ДНФ можно свести к поиску безызбыточных (тупиковых) систем ДНФ, из которых выбирается кратчайшая система ДНФ. Нахождение кратчайшей системы ДНФ может привести к слишком громоздким вычислениям, поэтому в разработанном алгоритме осуществляется поиск меньшей по числу конъюнкций тупиковой системы ДНФ среди найденных решений.
Алгоритм минимизации
Алгоритм минимизации системы полностью определенных булевых функций состоит из 3 этапов. Предполагается, что функции исходной системы заданы в виде совершенных ДНФ, поэтому если система функций задана в другом виде, то первоначально ее надо привести к системе совершенных ДНФ (СДНФ).
Этап 1. Поиск всех простых импликант исходной системы СДНФ булевых функций.
Этап 2. Построение матрицы покрытия и ее сокращение.
Этап 3. Поиск тупиковых систем ДНФ.
Размещено на Allbest.ru
...Подобные документы
Многие переменные, минимизация их функций. Точки максимума и минимума называются точками экстремума функции. Условия существования экстремумов функции многих переменных. Квадратичная форма, принимающая, как положительные, так и отрицательные значения.
реферат [70,2 K], добавлен 05.09.2010Определение констант нуля и установление эквивалентности линейных функций при помощи таблицы истинности. Нахождение минимальной дизъюнктивной нормальной формы функции с помощью метода неопределенных коэффициентов. Преобразование функции методом Квайна.
контрольная работа [335,2 K], добавлен 05.07.2014Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.
курсовая работа [278,1 K], добавлен 21.02.2009Представление булевой функции в виде дизъюнктивной нормальной формы. Выражение всех логических операции в формуле через конъюнкции, дизъюнкции и отрицания. Сокращение количества слагаемых, входящих в формулу и количества переменных, входящих в слагаемое.
контрольная работа [1,3 M], добавлен 06.05.2013Поиск собственных чисел и построение фундаментальной системы решений. Исследование зависимости жордановой формы матрицы А от свойств матрицы системы. Построение фундаментальной матрицы решений методом Эйлера, решение задачи Коши и построение графиков.
курсовая работа [354,7 K], добавлен 14.10.2010Построение диаграммы псевдографа, матрицы инцидентности и матрицы соседства вершин. Восстановление дерева по вектору с помощью алгоритма Прюфера. Построение таблицы истинности для функции и совершенной конъюнктивной и дизъюнктивной нормальной форм.
контрольная работа [181,9 K], добавлен 25.09.2013Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.
контрольная работа [178,2 K], добавлен 20.01.2011Понятия зависимой, независимой переменных, области определения функции. Примеры нахождения области функции. Примеры функций нескольких переменных: линейная, квадратическая, функция Кобба-Дугласа. Построение графика и линии уровня функции двух переменных.
презентация [104,8 K], добавлен 17.09.2013Алгоритм построения многочлена Жегалкина по совершенной дизъюнктивной нормальной форме. Диаграмма Эйлера-Венна, изображение универсального множества и подмножества. Проверка самодвойственности, монотонности и линейности логической функции двух переменных.
контрольная работа [227,5 K], добавлен 20.04.2015Общая схема методов спуска. Метод покоординатного спуска. Минимизация целевой функции по выбранным переменным. Алгоритм метода Гаусса-Зейделя. Понятие градиента функции. Суть метода наискорейшего спуска. Программа решения задачи дискретной оптимизации.
курсовая работа [90,8 K], добавлен 30.04.2011Логическая переменная в алгебре логики. Логические операции: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Основные законы алгебры логики. Правила минимизации логической функции (избавление от операций импликации и эквивалентности).
курсовая работа [857,2 K], добавлен 16.01.2012Определение формулы исчисления высказываний, основные цели математической логики. Построение формул алгебры высказываний. Равносильность формул исчисления высказываний, конъюнктивная и дизъюнктивная нормальная форма. Постановка проблемы разрешимости.
контрольная работа [34,3 K], добавлен 12.08.2010Понятие, основные свойства элементарных булевых функций и соотношения между ними. Формулировка принципа двойственности. Совершенные дизъюнктивная и конъюнктивная нормальные формы. Многочлен (полином) Жегалкина. Суперпозиция и замыкание класса функций.
презентация [24,4 K], добавлен 05.02.2016Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.
учебное пособие [1,3 M], добавлен 20.08.2014Основные понятия алгебры логики. Дизъюнктивные и конъюнктивные нормальные формы. Сущность теоремы Шеннона. Булевы функции двух переменных. Последовательное и параллельное соединение двух выключателей. Свойства элементарных функций алгебры логики.
контрольная работа [345,3 K], добавлен 29.11.2010Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
курсовая работа [701,9 K], добавлен 27.04.2011Понятие функции нескольких переменных. Аргументы, частное значение и область применения функции. Рассмотрение функции двух и трех переменных. Предел функции нескольких переменных, теорема. Главная сущность непрерывности функции нескольких переменных.
реферат [86,3 K], добавлен 30.10.2010Графическая интерпретация множеств и операций над ними. Математическая логика, булева алгебра. Совершенная конъюнктивная нормальная форма. Равносильные формулы и их доказательство. Полнота системы булевых функций. Логика предикатов, теория графов.
лекция [253,7 K], добавлен 01.12.2009Сущность и математическое обоснование булевой функции, ее назначение и пути решения. Порядок составления таблицы истинности для определенного количества переменных. Связь всех дизъюнкций в конъюнкцию. Разработка и листинг программы представления.
курсовая работа [837,6 K], добавлен 27.04.2011Основные правила решения системы заданных уравнений методом Гаусса с минимизацией невязки и методом простых итераций. Понятие исходной матрицы; нахождение определителя для матрицы коэффициентов. Пример составления блок-схемы метода минимизации невязок.
лабораторная работа [264,1 K], добавлен 24.09.2014