Построение совершенной дизъюнктивной и конъюнктивной нормальных форм
Курсовая работа, 18 Мая 2013, автор: пользователь скрыл имя
Описание работы
Алгебра Буля широко применяется при проектировании и проверке электрических схем, в которых используются реле, работающие по принципу "да - нет", при программировании и проектировании ЭВМ, в операциях с переключателями, сигналами, схемами. В современной математической логике этот раздел значительно усовершенствован и разрабатывается как теория булевых алгебр, в том числе как алгебра множеств, алгебра высказываний и т. п. В области традиционной логики соотношения Алгебры Буля часто используются для иллюстрации и прояснения отношений между объемами понятий.
Содержание работы
Введение……………………………………………………………………………..3 Глава 1. Булева алгебра. 4
1.1 Булевы функции одной переменной 5
1.2 Булевы функции двух переменных 5
1.3 Реализация функций формулами. 6
1.4 Равносильные формулы 7
1.5 Законы булевой алгебры 7
1.6 Полнота системы булевых функций 9
Глава 2. Двойственность функций 10
2.1 Принцип двойственности 10
Глава 3. Совершенная дизъюнктивная нормальная форма, совершенная конъюнктивная нормальная форма, дизъюнктивная нормальная форма и конъюнктивная нормальная форма 12
3.1 СДНФ И СКНФ 12
3.2 ДНФ И КНФ 16
Глава 4. Примеры приведения формул Алгебры Высказываний к КНФ,ДНФ,СКНФ И СДНФ 20
Заключение………………………………………………………………………...23
Список литературы 24
Файлы: 1 файл
kursovaya-moya-diskretnaya.docx
— 313.88 Кб (Скачать файл)Примеры и контр-примеры
Формулы в ДНФ:
Формулы не в ДНФ:
Построение ДНФ
Алгоритм построения ДНФ
1) Избавиться от всех логических
операций, содержащихся в формуле,
заменив их основными:
2) Заменить знак отрицания,
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к
операциям конъюнкции и
Пример построения ДНФ
Приведем к ДНФ формулу
Выразим логические операции → и ↓ через
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
Используя закон дистрибутивности, приводим формулу к ДНФ:
k-дизъюнктивная нормальная форма
k-дизъюнктивная нормальной формой называют дизъюнктивную нормальную форму, в которой каждая конъюнкция содержит ровно k литералов.
Например, следующая формула записана в 2-ДНФ:
Переход от ДНФ к СДНФ( не используя таблицу истинности)
Если в какой-то простой конъюнкции недостает переменной, например, Z, вставляем в нее выражение ,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:
Таким образом, из ДНФ получили СДНФ.
Конъюнктивная нормальная форма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литерало
Примеры и контр-примеры
Формулы в КНФ:
Формулы не в КНФ:
Но эти 3 формулы не в КНФ эквивалентны следующим формулам в КНФ:
Построение КНФ
Алгоритм построения КНФ
1) Избавиться от всех
логических операций, содержащихся
в формуле, заменив их основными:
конъюнкцией, дизъюнкцией, отрицанием.
Это можно сделать, используя
равносильные формулы:
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к
операциям конъюнкции и
Пример построения КНФ:
Приведем к КНФ формулу:
Преобразуем формулу F к формуле не содержащей → :
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
По закону дистрибутивности пол
k-конъюнктивная нормальная форма
k-конъюнктивной нормальной формой называют конъюнктивную нормальную форму, в которой каждая дизъюнкция содержит ровно k литералов.
Например, следующая формула записана в 2-КНФ:
Переход от КНФ к СКНФ
Если в простой дизъюнкции не
хватает какой-то переменной (например
Z,то добавляем в нее выражение
(это не меняет самой дизъюнкции), после
чего раскрываем скобки с использованием распределительн
Таким образом, из КНФ получена СКНФ.
Глава 4.Примеры приведения формул Алгебры Высказываний к
КНФ, ДНФ, СКНФ И СДНФ:
Ниже приведены примеры
Пример 1. Следующую формулу привести к СДНФ двумя способами:
Решение:
1-й способ: с помощью равносильных преобразований:
--ДНФ(А)
Произведем преобразование элементарных конъюнкций:
1-ой:
2-ой:
3-ей:
Получили формулу А в виде:
СДНФ(А)
2 способ: по таблице истинности:
x |
y |
z |
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
Таблица 10. Таблица приведения к СДНФ
Выделяем строки, где формула принимает значение 1,составляем дизъюнкцию конъюнкций и получаем СДНФ:
СДНФ(А)
Пример 2.Следующую формулу привести к СКНФ двумя способами:
Решение:
1-ый способ: с помощью равносильных преобразований:
Преобразуем вторую элементарную дизъюнкцию:
Формула А имеет вид:
СКНФ(А)
2 способ: по таблице истинности:
х |
y |
z |
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
Для значений формулы, равных 0, составляем конъюнкцию дизъюнкций и получаем СКНФ:
СКНФ(А)
Пример 3.Найти СДНФ для всякой тождественно истинной формулы, содержащей: а) одно высказывание б)два высказывания.
Решение:
а) Любую тождественно истинную формулу алгебры высказываний можно представить в виде: . Таким образом, СДНФF
б) Дополним каждое выражение в СДНФ переменной y. Получим
СДНФF
Пример 4. По таблице истинности построить СДНФ F и найти равносильную и более простую форму:
x |
y |
z |
F(x,y,z) |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
Решение: Найдем СДНФF:
СДНФF
Далее упростим ее с помощью равносильных преобразований:
СДНФF
Заключение
В наши дни алгебра высказываний стала важнейшей составной частью математики. Одна из ее задач — это решение всевозможных уравнений, числовые соотношения в которых заменены буквенными. Каждый из нас, наверное, на всю свою жизнь запомнил, как решать уравнения второй и третьей степени с буквенными коэффициентами. Так вот, Буль в своей новой алгебре воспользовался всеми этими формулами и правилами.
Булевы функции находят применение в конструировании и упрощении логических схем. Такие схемы встречаются в электронных устройствах, используемых в компьютерах, калькуляторах, телефонных системах и ряде других устройств.
Буль произвел такую научную революцию, о которой сам не подозревал. То, во что он превратил логику, было в дальнейшем положено в основу построения электронно-вычислительных устройств. Из всей логики именно Булева алгебра получила самое большое практическое применение в технике.
В ходе выполнения курсовой работы была достигнута поставленная цель, где были рассмотрены все основные теоретические вопросы булевой алгебры и алгебры высказываний, а также по этим вопросам были приведены и решены примеры, представлены несколько видов алгоритмов.
оз булеву переменную.
Список литературы:
- Овчинников, В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: учебник для вузов [Текст]/В.А. Овчинников. - М: Изд-во МГТУ им. Н.Э.Баумана, 2001. – 228 с.
- Капитонова, Ю.В. Лекции по дискретной математике [Текст]/Ю.В. Капитонова, С.Л. Кривой. СПб.[и др.]:БХВ-Петербург, 2004.-624 с.
- Белоусов, А.И. Дискретная математика: Учебник для вузов [Текст]/А.И. Белоусов, С.Б. Ткачев. – М: Изд-во МГТУ им. Н.Э. Баумана, 2001. - 744 с.
- Нефедов, В.Н. Курс дискретной математики: учебник для вузов [Текст] / В.Н. Нефедов, В.А. Осипова.-М: Изд-во МАИ, 1992.- 262 с.
- Судоплатов, С.В. Элементы дискретной математики: учеб.[Текст] /С.В. Судоплатов, Е.В. Овчинникова.- М: Инфра-М; Новосибирск: Изд-во НГТУ, 2002. - 240 с.
- Гаврилов, Г.П. Задачи и упражнения по дискретной
математике: учеб. пособие [Текст] / 3-е изд., перераб. - М:Физматлит, 2005. - 416 с.
- festival.1september.ru/
articles/551696 - www.ureman.ural.ru:8000/sdnf.
html - student bank.ru/view.php?id=54804&p=1
- ru.wikipedia.org
- it-starter.ru/content/
dvoistvennost-i- samodvoistvennost-bulevykh- funktsii - www.1vf2004.com/dop_t3r 13 part 1.html
- dic.academic.ru/dic.nsf/ntes/
614/БУЛЕВА - www.sch 861.ru/2-school/3-11-ikt/ikt/
urok/logica 1.html