Содержание
- 2. 2.1. БУЛЕВА АЛГЕБРА И ЕЕ ПРИМЕНЕНИЕ 2.1.1. Определение булевой алгебры
- 3. Название этого раздела математики связано с именем его основателя – Джорджа Буля. БУЛЬ (Boole) Джон английский
- 4. Используя классическое понятие алгебры, булеву алгебру можно определить как систему А=(В,φ1,φ2,…, φn), в которой несущим множеством
- 5. Основные логические операции, - дизъюнкция, конъюнкция и отрицание, - можно интерпретировать как операции, введенные в теории
- 6. Как правило, существует логическая интерпретация элементов множества В: 1 – истинно; 0 – ложно. В ряде
- 7. 2.1.2. Области применения булевой алгебры
- 8. Булева алгебра применяется: 1) как средство алгоритмического описания в языках программирования для определения логических условий; 2)
- 9. Алгебра логики позволяет производить анализ и синтез логических устройств. Анализ – это поиск аналитического выражения, которое
- 10. 2.1.3. Высказывания
- 11. Одним из базовых понятий в булевой алгебре является понятие высказывания. Высказывание – это любое повествовательное предложение,
- 12. Пример. Рассмотрим справедливость утверждений: а) число 4 – четное; b) снег – красный; с) 2*2=5. Значения
- 13. Два высказывания A и B называются эквивалентными, если их значения истинности совпадают. Значение истинности может быть
- 14. 2.2. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ
- 15. 2.2.1. Понятие функции и способы ее задания
- 16. Пусть имеется n двоичных переменных x1, x2, …, xn. Каждая из них в некотором конкретном случае
- 17. Функция f, задающая однозначное отображение множества всевозможных наборов значений двоичных переменных x1, x2, …, xn во
- 18. Способы задания функции. Логическая функция может быть задана: 1) математическим выражением (формулой); 2) таблицей. Таблица является
- 20. Оценим число возможных наборов (число строк входных переменных). Конкретный набор – это вектор значений Количество наборов
- 21. Оценим возможное количество вариантов логических функций от n переменных. Множество вариантов логической функции можно представить как
- 22. Наборы, на которых функция равна единице, называют единичными наборами, а наборы, на которых функция равна нулю,
- 23. Две булевы функции и называют равными, если для всех возможных наборов значений аргументов они принимают одинаковые
- 24. Говорят, что булева функция Существенно зависит от аргумента xi , если , хотя бы для одного
- 25. 2.2.2. Элементарные логические операции
- 26. Из множества логических функций выделяется ряд наиболее простых операций, которые имеют ясную логическую интерпретацию: 1) отрицание
- 27. 2) дизъюнкция (логическое сложение) (читается: " x или y "). Дизъюнкция – это функция, выражающая высказывание,
- 28. 3) конъюнкция (логическое умножение) (читается: " x и y"). Для этой операции применяются также следующие формы
- 29. 4) импликация (читается : “если x, то y”). Функция f4 принимает значение ложно только тогда, когда
- 30. 5) эквивалентность (равнозначность) (читается: “x равно y ”). Функция f5=1 тогда и только тогда, когда значения
- 31. 6) сложение по модулю два (неравнозначность) Функция f6 истинна тогда и только тогда, когда значения аргументов
- 32. 7) штрих Шеффера Операция обратная по отношению к конъюнкции (функция ложна, только если оба аргумента истинны)
- 33. 8) стрелка Пирса Функция f8 обратная к дизъюнкции (f8 истинно, только когда x и y ложны)
- 34. Наиболее важными функциями являются первые три. Остальные могут быть выражены через эти три функции. С использованием
- 35. 2.2.3. Свойства основных логических функций
- 36. Основные логические функции обладают следующими свойствами: 1) коммутативность: 2) ассоциативность: 3) идемпотентность конъюнкции и дизъюнкции:
- 37. 4) дистрибутивность: а) конъюнкции относительно дизъюнкции: б) дизъюнкции относительно конъюнкции: 5) двойное отрицание:
- 38. 6) правило де Моргана: 7) правило склеивания: 8) правило поглощения: ;
- 39. 9) действия с константами: Свойства основных булевых функций доказываются либо путем преобразования выражений, либо на основе
- 40. Пример. Доказать, что С учетом таблиц истинности элементарных логических операций определяем последовательно значения функций, указанных в
- 41. Так как значения функций и на всех наборах совпадают, то эти функции равны.
- 42. 2.2.4. Задание функции формулой. Эквивалентные преобразования логических выражений
- 43. Понятие формулы вводится для формализации представления и записи простого или сложного высказывания. Формула рассматривается как некоторый
- 44. Таким образом, рассмотренные выше выражения, которыми описывались элементарные логические операции и свойства основных логических операций, -
- 45. Пусть имеется множество логических функций, заданных формулами Е={ f1, f2, …, fm }; при этом говорят,
- 46. Пример. Пусть функция задана формулой , и при этом имеет место равенство Тогда новую формулу E
- 47. Полученную формулу вновь представим как исходную, и, полагая далее делаем вновь подстановку. Тогда новая формула над
- 48. Логические операции обладают различным приоритетом, с точки зрения порядка выполнения их в выражении. Принят следующий порядок
- 49. Сопоставляя введенные выше понятия логической функции и формулы, следует иметь ввиду, что логическая функция - это
- 50. Пример. Рассмотрим две формулы: и Несложно показать, что обе формулы представляют одну и ту же функцию,
- 51. Две формулы U и B называются эквивалентными (равносильными), если они реализуют одну и ту же функцию.
- 52. Эквивалентное преобразование осуществляется на основе сопоставления таблиц истинности, либо на основе применения свойств основных логических операций.
- 53. 1.Преобразование формулы, описывающей функцию . Справедливость преобразования доказывается соответствующей таблицей истинности.
- 54. 2.Преобразование формулы, описывающей функцию . Справедливость преобразования доказывается соответствующей таблицей истинности.
- 55. 3. Функция f6 4. Функция f7 = 5. Функция f8 =
- 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. Сущность метода заключается в представлении функции в самом общем виде в ДНФ и введении коэффициентов ai,
- 91. Термы, содержащие k переменных, будем называть термами ранга k. В выражении (2.1) представлены все возможные формы
- 93. Для заданной конкретной функции конкретные значения левой части (2.2) нам известны. Если набор такой, что функция
- 94. Пример. Минимизировать заданное выражение
- 96. 2.4.3. Метод Квайна – Мак Класки
- 97. Метод Квайна. При минимизации методом Квайна исходная функция задается в СДНФ. Сущность метода состоит в поэтапном
- 98. Шаг 1. Нахождение первичных импликант. Все термы сравниваются между собой попарно. Если два терма имеют вид
- 99. Пример. Пусть задано следующее выражение в форме СДНФ
- 101. Шаг 2. Составление таблицы. В колонках записываем термы исходного выражения (они обозначены порядковыми номерами), а в
- 102. Шаг 2. Составление таблицы. В колонках записываем термы исходного выражения (они обозначены порядковыми номерами), а в
- 103. Шаг 3. Нахождение существенных импликант. Если в каком-либо из столбцов таблицы имеется одна метка, то импликанта,
- 105. Шаг 5. Вычеркивание лишних импликант. Если после шага 4 в таблице появятся строки, в которых нет
- 106. Шаг 6. Выбор конечного результата. В результирующее выражение включается совокупность импликант, которые имеют метки во всех
- 107. Метод Мак Класки. Мак Класки предложил модернизировать метод Квайна следующим образом: 1) все термы кодируются в
- 108. 4) при исключении переменной вместо нее записывается прочерк. Порядок формирования минимизированного выражения логической функции такой же,
- 109. 2.4.4. Метод карт Карно
- 110. Карта Карно – это графическое представление таблицы истинности. Она представляет собой совокупность ячеек, определяемых системой вертикальных
- 111. Пример. Функции соответствуют представленные ниже таблица истинности и карта Карно.
- 112. Сущность метода заключается в выделении в карте Карно прямоугольных ячеек (блоков), содержащих одно и то же
- 113. 3) терм, описывающий блок, записывается в форме произведения тех переменных, которые на координатной сетке не изменяют
- 114. При формировании групп для получения минимальных сумм необходимо руководствоваться двумя принципами: 1) группа должна быть как
- 115. Общая последовательность действий при минимизации: 1) в таблице Карно выбирается ячейка с единицей, не являющаяся подмножеством
- 116. Пример. Карте Карно, представленной на рисунке, соответствует функция.
- 117. Пример. Карте Карно, представленной на рисунке, соответствует функция.
- 118. Существует еще один способ записи минимальной формулы на основе метода минимальных произведений (минимальное произведение или минимальная
- 119. 4) при исключении переменной вместо нее записывается прочерк. Минимизация частично определенных булевых функций. В случае, если
- 120. Пример. Карте Карно, представленной на рисунке, соответствует функция.
- 121. 2.5. ПОЛНОТА И ЗАМКНУТОСТЬ МНОЖЕСТВА БУЛЕВЫХ ФУНКЦИЙ 2.5.1. Понятие функционально полной системы
- 122. Система функций называется функционально полной, если любая булева функция может быть записана в виде формул через
- 123. Доказательство. Пуст h – это произвольная функция. В силу полноты B функция h может быть выражена
- 124. Доказанную теорему можно использовать для доказательства полноты двух следующих систем: Известно, что – полная система (это
- 125. Для доказательства полноты S1 и S2 нужно установить, что недостающая относительно S0 операция (в S1 –
- 126. Полной является также система , которая сводится к конъюнктивному базису S1 , т.к. отрицание в может
- 127. 2.5.2. Алгебра Жегалкина
- 128. Алгебра над множеством логических функций с двумя бинарными операциями (конъюнкция и сложение по модулю два) называется
- 129. Полученная формула, имеющая вид суммы произведений, называется полиномом по модулю два или полиномом Жегалкина. Для каждой
- 130. Существует ещё один способ приведения функции к полиному Жегалкина. Запишем предполагаемый результат в виде выражения общего
- 131. 2.5.3. Замыкание и замкнутые классы
- 132. Замыканием множества функции M называют множество всех булевых функций, представляемых в виде формул через функции множества
- 133. 4) при исключении переменной вместо нее записывается прочерк. Теорема о функциональной полноте. Для того чтобы система
- 134. S – замкнутый класс всех самодвойственных функций, т.е. функций, для которых ; L – замкнутый класс
- 135. Существует еще одно, близкое по содержанию определение теоремы о полноте. Теорема Поста. Система является полной тогда,
- 136. Примеры функционально полных базисов. Класс функций N из E2 называется предполным, если он неполный, а для
- 137. Состав систем, которые относятся к базису, можно определить на основе следующей таблицы
- 139. Скачать презентацию