Основные положения булевой алгебры презентация
Содержание
- 2. 2.1. БУЛЕВА АЛГЕБРА И ЕЕ ПРИМЕНЕНИЕ 2.1.1. Определение булевой алгебры
- 3. Название этого раздела математики связано с именем его основателя – Джорджа
- 4. Используя классическое понятие алгебры, булеву алгебру можно определить как систему
- 5. Основные логические операции, - дизъюнкция, конъюнкция и отрицание, - можно интерпретировать
- 6. Как правило, существует логическая интерпретация элементов множества В: 1 –
- 7. 2.1.2. Области применения булевой алгебры
- 8. Булева алгебра применяется: 1) как средство алгоритмического описания в языках программирования
- 9. Алгебра логики позволяет производить анализ и синтез логических устройств. Анализ
- 10. 2.1.3. Высказывания
- 11. Одним из базовых понятий в булевой алгебре является понятие высказывания. Высказывание
- 12. Пример. Рассмотрим справедливость утверждений: а) число 4 – четное; b)
- 13. Два высказывания A и B называются эквивалентными, если их значения истинности
- 14. 2.2. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ
- 15. 2.2.1. Понятие функции и способы ее задания
- 16. Пусть имеется n двоичных переменных x1, x2, …, xn. Каждая
- 17. Функция f, задающая однозначное отображение множества всевозможных наборов значений двоичных переменных
- 18. Способы задания функции. Логическая функция может быть задана: 1) математическим выражением
- 20. Оценим число возможных наборов (число строк входных переменных). Конкретный набор –
- 21. Оценим возможное количество вариантов логических функций от n переменных. Множество вариантов
- 22. Наборы, на которых функция равна единице, называют единичными наборами, а наборы,
- 23. Две булевы функции
- 24. Говорят, что булева функция Существенно зависит от аргумента xi ,
- 25. 2.2.2. Элементарные логические операции
- 26. Из множества логических функций выделяется ряд наиболее простых операций, которые имеют
- 27. 2) дизъюнкция (логическое сложение)
- 28. 3) конъюнкция (логическое умножение)
- 29. 4) импликация
- 30. 5) эквивалентность (равнозначность)
- 31. 6) сложение по модулю два (неравнозначность)
- 32. 7) штрих Шеффера
- 33. 8) стрелка Пирса
- 34. Наиболее важными функциями являются первые три. Остальные могут быть выражены через
- 35. 2.2.3. Свойства основных логических функций
- 36. Основные логические функции обладают следующими свойствами: 1) коммутативность:
- 37. 4) дистрибутивность: а) конъюнкции относительно дизъюнкции: б)
- 38. 6) правило де Моргана: 7) правило склеивания:
- 39. 9) действия с константами: Свойства
- 40. Пример. Доказать, что С учетом таблиц истинности элементарных логических
- 41. Так как значения функций и на всех наборах совпадают,
- 42. 2.2.4. Задание функции формулой. Эквивалентные преобразования логических выражений
- 43. Понятие формулы вводится для формализации представления и записи простого или сложного
- 44. Таким образом, рассмотренные выше выражения, которыми описывались элементарные логические операции и
- 45. Пусть имеется множество логических функций, заданных формулами Е={ f1, f2, …,
- 46. Пример. Пусть функция задана формулой
- 47. Полученную формулу вновь представим как исходную, и, полагая далее делаем
- 48. Логические операции обладают различным приоритетом, с точки зрения порядка выполнения их
- 49. Сопоставляя введенные выше понятия логической функции и формулы, следует иметь ввиду,
- 50. Пример. Рассмотрим две формулы:
- 51. Две формулы U и B называются эквивалентными (равносильными), если они реализуют
- 52. Эквивалентное преобразование осуществляется на основе сопоставления таблиц истинности, либо на основе
- 53. 1.Преобразование формулы, описывающей функцию
- 54. 2.Преобразование формулы, описывающей функцию
- 55. 3. Функция f6 4. Функция f7
- 56. Формулы, из которых построена некоторая исходная формула, называются подформулами. Чаще всего
- 57. 2.2.5. Двойственные функции
- 58. Логическая функция ,
- 59. Теорема 2.1. Если некоторая формула Ф реализует функцию f, то формула
- 60. В частном случае из теоремы 2.1 вытекает следующее правило. Если формула
- 61. Можно сформулировать следующие принципы двойственности для формул: 1) если две формулы
- 62. 3) если две формулы эквивалентны, то будут эквивалентны и формулы, полученные
- 63. 2.3. СПЕЦИАЛЬНЫЕ РАЗЛОЖЕНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ 2.3.1. Конъюнктивная и дизъюнктивная нормальные
- 64. Любая функция булевой алгебры может быть представлена некоторыми формулами специального вида.
- 65. Элементарной конъюнкцией (ЭК) называют конъюнкцию нескольких переменных или их отрицаний.
- 66. Если заданная функция уже представлена некоторой формулой, то путем эквивалентных преобразований
- 67. 2) если в выражении над несколькими элементами имеются знаки отрицания, то
- 68. Упрощение логических формул на основе применения понятий тождественно истинных и тождественно
- 69. Утверждение 2. Для того чтобы элементарная конъюнкция была тождественно ложной, необходимо
- 70. Указанные два утверждения используются для упрощения выражений следующим образом: В случае
- 71. Пример. Установить характер истинности формулы
- 72. 2.3.2. Совершенно нормальные конъюнктивная и дизъюнктивная формы
- 73. Понятие совершенно нормальных конъюнктивных и дизъюнктивных форм. Пусть имеется n переменных:
- 74. Элементарная дизъюнкция, сформированная в соответствии с указанными требованиями, образует логическую конструкцию
- 75. Совершенной дизъюнктивной нормальной формой (СДНФ) логической функции называют представление её
- 76. Каждая логическая функция может быть представлена единственным образом в совершенной дизъюнктивной
- 77. Приведение функции к совершенно нормальной форме называют ее разложением по всем
- 78. 1. Логическая формула приводится к
- 79. Если отсутствуют несколько переменных, то операцию нужно повторить для всех отсутствующих
- 80. При приведении к совершенной конъюнктивной нормальной форме последовательность действий остается той
- 81. Существует еще один метод приведения функции к совершенной нормальной форме. Выражение
- 82. Пример. Рассмотрим пример приведения заданной логической функции к форме СДНФ, с
- 84. Пример. Рассмотрим пример приведения заданной логической функции к форме СКНФ, с
- 86. 2.4. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ 2.4.1. Понятие минимизации
- 87. Задача минимизации булевой функции состоит в построении такой ДНФ (или КНФ)
- 88. Для минимизации булевых функций в целях получения самых простых выражений используется
- 89. 2.4.2. Метод неопределенных коэффициентов
- 90. Сущность метода заключается в представлении функции в самом общем виде в
- 91. Термы, содержащие k переменных, будем называть термами ранга k. В выражении
- 93. Для заданной конкретной функции конкретные значения левой части (2.2) нам известны.
- 94. Пример. Минимизировать заданное выражение
- 96. 2.4.3. Метод Квайна – Мак Класки
- 97. Метод Квайна. При минимизации методом Квайна исходная функция задается в СДНФ.
- 98. Шаг 1. Нахождение первичных импликант. Все термы сравниваются между собой попарно.
- 99. Пример. Пусть задано следующее выражение в форме СДНФ
- 101. Шаг 2. Составление таблицы. В колонках записываем термы исходного выражения (они
- 102. Шаг 2. Составление таблицы. В колонках записываем термы исходного выражения (они
- 103. Шаг 3. Нахождение существенных импликант. Если в каком-либо из столбцов таблицы
- 105. Шаг 5. Вычеркивание лишних импликант. Если после шага 4 в таблице
- 106. Шаг 6. Выбор конечного результата. В результирующее выражение включается совокупность импликант,
- 107. Метод Мак Класки. Мак Класки предложил модернизировать метод Квайна следующим образом:
- 108. 4) при исключении переменной вместо нее записывается прочерк. Порядок формирования минимизированного
- 109. 2.4.4. Метод карт Карно
- 110. Карта Карно – это графическое представление таблицы истинности. Она представляет собой
- 111. Пример. Функции соответствуют представленные
- 112. Сущность метода заключается в выделении в карте Карно прямоугольных ячеек (блоков),
- 113. 3) терм, описывающий блок, записывается в форме произведения тех переменных, которые
- 114. При формировании групп для получения минимальных сумм необходимо руководствоваться двумя принципами:
- 115. Общая последовательность действий при минимизации: 1) в таблице Карно выбирается ячейка
- 116. Пример. Карте Карно, представленной на рисунке, соответствует функция.
- 117. Пример. Карте Карно, представленной на рисунке, соответствует функция.
- 118. Существует еще один способ записи минимальной формулы на основе метода минимальных
- 119. 4) при исключении переменной вместо нее записывается прочерк. Минимизация частично определенных
- 120. Пример. Карте Карно, представленной на рисунке, соответствует функция.
- 121. 2.5. ПОЛНОТА И ЗАМКНУТОСТЬ МНОЖЕСТВА БУЛЕВЫХ ФУНКЦИЙ 2.5.1. Понятие
- 122. Система функций называется функционально полной, если любая булева функция может быть
- 123. Доказательство. Пуст h – это произвольная функция. В силу полноты B
- 124. Доказанную теорему можно использовать для доказательства полноты двух следующих систем:
- 125. Для доказательства полноты S1 и S2 нужно установить, что недостающая относительно
- 126. Полной является также система , которая
- 127. 2.5.2. Алгебра Жегалкина
- 128. Алгебра над множеством логических функций с двумя бинарными операциями (конъюнкция и
- 129. Полученная формула, имеющая вид суммы произведений, называется полиномом по модулю два
- 130. Существует ещё один способ приведения функции к полиному Жегалкина. Запишем предполагаемый
- 131. 2.5.3. Замыкание и замкнутые классы
- 132. Замыканием множества функции M называют множество всех булевых функций, представляемых в
- 133. 4) при исключении переменной вместо нее записывается прочерк. Теорема о функциональной
- 134. S – замкнутый класс всех самодвойственных функций, т.е. функций, для которых
- 135. Существует еще одно, близкое по содержанию определение теоремы о полноте. Теорема
- 136. Примеры функционально полных базисов. Класс функций N из E2 называется предполным,
- 137. Состав систем, которые относятся к базису, можно определить на основе следующей
- 138. Символом «+» обозначается факт непринадлежности функции к замкнутому классу. Согласно теореме
- 139. Скачать презентацию
Слайды и текст этой презентации
Скачать презентацию на тему Основные положения булевой алгебры можно ниже: