Автор работы: Пользователь скрыл имя, 18 Мая 2013 в 14:03, курсовая работа
Алгебра Буля широко применяется при проектировании и проверке электрических схем, в которых используются реле, работающие по принципу "да - нет", при программировании и проектировании ЭВМ, в операциях с переключателями, сигналами, схемами. В современной математической логике этот раздел значительно усовершенствован и разрабатывается как теория булевых алгебр, в том числе как алгебра множеств, алгебра высказываний и т. п. В области традиционной логики соотношения Алгебры Буля часто используются для иллюстрации и прояснения отношений между объемами понятий.
Введение……………………………………………………………………………..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) Избавиться от всех логических
операций, содержащихся в формуле,
заменив их основными:
2) Заменить знак отрицания,
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к
операциям конъюнкции и
Приведем к ДНФ формулу
Выразим логические операции → и ↓ через
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
Используя закон дистрибутивности, приводим формулу к ДНФ:
k-дизъюнктивная нормальной формой называют дизъюнктивную нормальную форму, в которой каждая конъюнкция содержит ровно k литералов.
Например, следующая формула записана в 2-ДНФ:
Если в какой-то простой конъюнкции недостает переменной, например, Z, вставляем в нее выражение ,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:
Таким образом, из ДНФ получили СДНФ.
Конъюнктивная нормальная форма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литерало
Формулы в КНФ:
Формулы не в КНФ:
Но эти 3 формулы не в КНФ эквивалентны следующим формулам в КНФ:
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к
операциям конъюнкции и
Преобразуем формулу F к формуле не содержащей → :
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
По закону дистрибутивности пол
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
Заключение
В наши дни алгебра высказываний стала важнейшей составной частью математики. Одна из ее задач — это решение всевозможных уравнений, числовые соотношения в которых заменены буквенными. Каждый из нас, наверное, на всю свою жизнь запомнил, как решать уравнения второй и третьей степени с буквенными коэффициентами. Так вот, Буль в своей новой алгебре воспользовался всеми этими формулами и правилами.
Булевы функции находят применение в конструировании и упрощении логических схем. Такие схемы встречаются в электронных устройствах, используемых в компьютерах, калькуляторах, телефонных системах и ряде других устройств.
Буль произвел такую научную революцию, о которой сам не подозревал. То, во что он превратил логику, было в дальнейшем положено в основу построения электронно-вычислительных устройств. Из всей логики именно Булева алгебра получила самое большое практическое применение в технике.
В ходе выполнения курсовой работы была достигнута поставленная цель, где были рассмотрены все основные теоретические вопросы булевой алгебры и алгебры высказываний, а также по этим вопросам были приведены и решены примеры, представлены несколько видов алгоритмов.
оз булеву переменную.
Список литературы:
математике: учеб. пособие [Текст] / 3-е изд., перераб. - М:Физматлит, 2005. - 416 с.
Информация о работе Построение совершенной дизъюнктивной и конъюнктивной нормальных форм