Дизъюнктивная нормальная форма
Особенности дизъюнктивной нормальной формы (ДНФ) в булевой логике — нормальной формы, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Использование в формуле закона двойного отрицания, закона де Моргана, закона дистрибутивности.
| Рубрика | Математика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 16.02.2020 |
| Размер файла | 14,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РТ ГАПОУ «АРСКИЙ ПЕДАГОГИЧЕСКИЙ КОЛЛЕДЖ им. Г. ТУКАЯ»
Реферат
Дизъюнктивная нормальная форма
Выполнил студент: Валиев А.Р.
Руководитель: Сафина А.Р.
Арск, 2019 год
Введение
Дизъюнктивная нормальная форма (ДНФ) в булевой логике -- нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ. Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.
Глава 1. Примеры и контрпримеры
Формулы в ДНФ:
Закон де Моргана:
Глава 2. Построение ДНФ
2.1 Алгоритм построения ДНФ
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
2.2 Пример построения ДНФ
Приведем к ДНФ формулу:
Выразим логические операции > и v через:
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
Используя закон дистрибутивности, приводим формулу к ДНФ:
дизъюнктивная нормальная форма
Глава 3. k-дизъюнктивная нормальная форма
k-дизъюнктивная нормальной формой называют дизъюнктивную нормальную форму, в которой каждая конъюнкция содержит ровно k литералов.
Например, следующая формула записана в 2-ДНФ:
Глава 4. Переход от ДНФ к СДНФ
Если в какой-то простой конъюнкции недостает переменной, например, Z, вставляем в нее выражение:,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем).
Таким образом, из ДНФ получили СДНФ.
Список использованных источников
1. Ю.И. Галушкина, А.Н. Марьямов: Конспект лекций по дискретной математике - 2-е изд., испр. - М.: Айрис-пресс, 2008. - 176 с
Размещено на Allbest.ru
...Подобные документы
Представление булевой функции в виде дизъюнктивной нормальной формы. Выражение всех логических операции в формуле через конъюнкции, дизъюнкции и отрицания. Сокращение количества слагаемых, входящих в формулу и количества переменных, входящих в слагаемое.
контрольная работа [1,3 M], добавлен 06.05.2013Определение констант нуля и установление эквивалентности линейных функций при помощи таблицы истинности. Нахождение минимальной дизъюнктивной нормальной формы функции с помощью метода неопределенных коэффициентов. Преобразование функции методом Квайна.
контрольная работа [335,2 K], добавлен 05.07.2014Нормальное распределение на прямой, нормальная кривая. Влияние параметров нормального распределения на форму нормальной кривой. Вероятность отклонения в заданный интервал нормальной случайной величины. Вычисление вероятности заданного отклонения.
курсовая работа [1,7 M], добавлен 06.12.2012Теорема Бернулли как простейшая форма закона больших чисел. Предельные теоремы теории вероятностей и объяснение природы устойчивости частоты появлений события. Качественные и количественные утверждения закона больших чисел, его практическое применение.
курсовая работа [75,2 K], добавлен 17.12.2009Понятие вероятности, математического ожидания, закона больших чисел, динамика их развития. Введение аксиоматического определения понятия вероятности математического ожидания. Теоремы Бернулли и Пуассона как простейшие формы закона больших чисел.
дипломная работа [388,7 K], добавлен 23.08.2009Особенности нормальной формы линейного преобразования. Изучение собственных и присоединенных векторов линейного преобразования. Выделение подпространства, в котором преобразование А имеет только одно собственное значение. Анализ инвариантных множителей.
курсовая работа [37,6 K], добавлен 21.02.2010Графическая интерпретация множеств и операций над ними. Математическая логика, булева алгебра. Совершенная конъюнктивная нормальная форма. Равносильные формулы и их доказательство. Полнота системы булевых функций. Логика предикатов, теория графов.
лекция [253,7 K], добавлен 01.12.2009Определение вероятности случайного события, с использованием формулы классической вероятности, схемы Бернулли. Составление закона распределения случайной величины. Гипотеза о виде закона распределения и ее проверка с помощью критерия хи-квадрата Пирсона.
контрольная работа [114,3 K], добавлен 11.02.2014Булевы алгебры – решетки особого типа, применяемые при исследовании логики (как логики человеческого мышления, так и цифровой компьютерной логики), а также переключательных схем. Минимальные формы булевых многочленов. Теоремы абстрактной булевой алгебры.
курсовая работа [64,7 K], добавлен 12.05.2009Определение формулы исчисления высказываний, основные цели математической логики. Построение формул алгебры высказываний. Равносильность формул исчисления высказываний, конъюнктивная и дизъюнктивная нормальная форма. Постановка проблемы разрешимости.
контрольная работа [34,3 K], добавлен 12.08.2010Формулировка и графическая интерпретация закона Вейса. Вывод возможных граней кристалла. Простые формы кристалла, кратность точечной группы. Закрытые и открытые простые формы, их особенности и характеристика. Образец типовой записи группы симметрии.
презентация [363,4 K], добавлен 23.09.2013Оценивание параметров закона распределения случайной величины. Точечная и интервальная оценки параметров распределения. Проверка статистической гипотезы о виде закона распределения, нахождение параметров системы. График оценки плотности вероятности.
курсовая работа [570,4 K], добавлен 28.09.2014Литералы рассуждения и вопрос об их отрицаниях. Математическая модель отрицания для рассуждения, содержащего связную совокупность суждений. Отрицания в математической логике и дополнения в алгебре множеств. Интерпретации формул математической логики.
контрольная работа [40,8 K], добавлен 03.09.2010Обработка результатов информации по транспортным и технологическим машинам методом математической статистики. Определение интегральной функции нормального распределения, функции закона Вейбула. Определение величины сдвига к началу распределения параметра.
контрольная работа [488,5 K], добавлен 05.03.2017Построение диаграммы псевдографа, матрицы инцидентности и матрицы соседства вершин. Восстановление дерева по вектору с помощью алгоритма Прюфера. Построение таблицы истинности для функции и совершенной конъюнктивной и дизъюнктивной нормальной форм.
контрольная работа [181,9 K], добавлен 25.09.2013Принцип минимакса как основа целесообразного поведения игроков в антагонистической игре. Порядок разыгрывания в некооперативной игре в нормальной форме. Принцип оптимальности стратегий для нее. Представление игры в развернутой и в нормальной форме.
реферат [241,5 K], добавлен 20.10.2012Основные формы мышления: понятия, суждения, умозаключения. Сочинение Джорджа Буля, в котором подробно исследовалась логическая алгебра. Значение истинности (т.е. истинность или ложность) высказывания. Логические операции инверсии (отрицания) и конъюнкции.
презентация [399,6 K], добавлен 14.12.2016Формулировка основного закона динамики. Понятие и основные характеристики прямолинейного движения, формы и особенности его задания. Схема формирования и решения дифференциальных уравнений движения. Примеры решения типовых задач по данной тематике.
презентация [1,7 M], добавлен 26.09.2013История открытия нормального закона, его применение в науке и технике. Вероятность попадания случайной величины, подчиненной нормальному закону, на заданный участок. Нормальная функция распределения. Геометрическая интерпретация вероятного отклонения.
контрольная работа [506,3 K], добавлен 21.04.2019Основные этапы развития булевой алгебры и применение минимальных форм булевых многочленов к решению задач, в частности, с помощью метода Куайна - Мак-Класки. Применение минимизирования логических форм при проектировании устройств цифровой электроники.
курсовая работа [58,6 K], добавлен 24.05.2009
