Дизъюнктивная нормальная форма
Особенности дизъюнктивной нормальной формы (ДНФ) в булевой логике — нормальной формы, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Использование в формуле закона двойного отрицания, закона де Моргана, закона дистрибутивности.
| Рубрика | Математика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 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
