Содержание
- 2. Формулы исчисления высказываний Рассмотрим понятие переменной – a, b, c,… x, y,… Будем строить формулы, последовательно
- 3. Логическое следствие и эквивалентность формул Говорят, что формула B является логическим следствием формулы A (запись: A
- 4. Эквивалентное преобразование формул Несколько важных эквивалентностей исчисления высказываний законы булевой алгебры: a ∧ a ⇔ a,
- 5. Исчисление предикатов Распространяем понятие логической формулы на объекты, отличные от истинностных значений И и Л. Строим
- 6. Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики. Логическое следствие и эквивалентность Понятия логического следствия
- 7. Формальные теории Формализовать понятие доказательства, чтобы можно было формальными методами исследовать, насколько достоверен сам математический метод
- 8. Выводимость из гипотез Пусть задан набор гипотез Г = { Г1, Г2,…, Гn } Вывод –
- 9. Формальное исчисление высказываний Будем строить формулы из (логических) констант a, b, c,… с помощью набора логических
- 11. Примеры выводов в формальном исчислении высказываний ├─ (a → a) (a → (b → a)) (A1)
- 12. Теорема о дедукции В формальном исчислении высказываний следующие утверждения равносильны: Г, A ├─ B Г ├─
- 13. Полнота и непротиворечивость формальной теории Интерпретация формальной теории – правило, согласно которому некоторым формулам теории сопоставляется
- 14. Система аксиом теории называется независимой, если ни одну из этих аксиом невозможно вывести из остальных. Формальная
- 15. Теорема 1. Во всякой достаточно богатой формальной теории первого порядка существует такая истинная формула F, что
- 16. Булевы функции.
- 19. Двумерные двоичные векторы можно рассматривать как вершины единичного квадрата в двумерном евклидовом пространстве:
- 20. Векторы α и β связаны отношением ≤, если из вершины α можно пройти в вершину β
- 21. Аналогично, трехмерные векторы соответствуют вершинам куба; векторы α и β связаны отношением ≤, если из вершины
- 22. Пусть – произвольная формула алгебры высказываний, содержащая n переменных. Оценка переменных такой формулы– это упорядоченная последовательность
- 23. Каждой оценке переменных однозначным образом сопоставляется значение истинности u∈{0,1} высказывания, полученного из формулы U после соответствующей
- 24. Таким образом, мы получаем соответствие задающее отображение Такие отображения называют булевыми функциями.
- 25. Непосредственно из определений вытекает, что формулы алгебры высказываний и равносильны в том и только том случае,
- 26. Заметим, что Булевы функции представляют интерес не только в связи с их «логическим» происхождением, но и
- 27. Введем следующие определения. Переменные, пробегающие множество {0,1}, мы будем называть булевыми и обозначать буквами Функция от
- 28. Булевы функции от одной переменной– это отображения Множества {0,1} в себя. Булевы функции от одной переменной
- 29. Булевы функции от двух переменных можно рассматривать как бинарные операции на множестве {0,1}. В следующей таблице
- 31. Комбинируя перечисленные функции (с помощью суперпозиций), можно строить более сложные булевы функции, в том числе и
- 32. ¬x = x→0 = x|x= x↓x= 1⊕x; xy= ¬ (¬x∨¬y) = ¬x↓¬y = (x↓x)↓(y↓y); x∨y= ¬
- 33. Далее для обозначения отрицания будем использовать знак x’=¬x. Двойственной к булевой функции называется функция Принцип двойственности
- 34. Если представлена формулой, содержащей только конъюнкции, дизъюнкции и отрицания, то двойственная функция получается заменой в этой
- 35. Дизъюнктивная нормальная форма (ДНФ). Конъюнктивная нормальная форма (КНФ).
- 36. Пусть функция от трех переменных задана следующей таблицей:
- 37. тогда Каждый из трех дизъюнктивных членов (слагаемых) записанной формулы соответствует набору значений аргументов, для которого функция
- 38. Легко видеть, что описанный способ построения формулы по таблице применим к любой функции, не равной тождественно
- 39. Двойственная конструкция приводит к представлению функции в так называемой совершенной конъюнктивной нормальной форме, сокращенно СКНФ. СКНФ
- 40. Описанный выше способ построения СДНФ и СКНФ опирается на следующую теорему о разложении функции по переменной.
- 41. Доказательство. Докажем первую формулу. Чтобы не загромождать выкладки индексами и многоточиями, ограничимся случаем функции от двух
- 42. Таким образом, левая и правая части доказываемого равенства совпадают на любом наборе значений аргументов. Следовательно, функции
- 43. Последовательно применяя несколько раз (по числу переменных) разложение из предыдущей теоремы, можно получить СДНФ булевой функции.
- 44. Функция представлена в виде дизъюнкции четырех дизъюнктивных членов. Те из них, для которых коэффициент равен нулю,
- 45. Элементарной конъюнкцией (конъюнктом) называют конъюнкцию переменных и/или их отрицаний, в которой каждая переменная встречается не более
- 46. Полные системы булевых функций Система булевых функций называется полной, если любая булева функция может быть выражена
- 47. Поскольку дизъюнкцию можно выразить через конъюнкцию и отрицание, система функций {∧, ’} также полна. Точно так
- 48. Через ⊕ и 1 можно выразить отрицание, так что система Функций {1, ⊕, ⋅} также является
- 49. Пример. Вычислим полином Жегалкина для функции Имеем При выводе использовались равенства
- 50. Существуют полные системы, содержащие всего одну функцию. Отрицание и конъюнкцию можно выразить через стрелку Пирса. Следовательно,
- 51. Таким образом, что установить полноту системы функций можно, показав, как через функции этой системы выражаются функции
- 52. Пример. Покажем что система функций {⋅,∨} неполна. Действительно, отрицание нельзя выразить через дизъюнкцию и конъюнкцию. Допустим
- 53. Тем же свойством обладает и любая сложная функция, составленная из конъюнкции и дизъюнкции. Значит, что противоречит
- 54. Важнейшие замкнутые классы булевых функций. Теорема Поста о полноте Пусть K– некоторый класс булевых функций. Замыканием
- 55. Замыкание любой полной системы функций содержит все булевы функции. Для неполной системы функций это уже не
- 56. Рассмотрим важнейшие замкнутые классы булевых функций. Класс . Класс – это класс всех функций, сохраняющих 0,
- 57. Не входят: тождественная единица; отрицание; импликация. Таблица для функции из класса в первой строке содержит 0,
- 58. Класс . Класс – это класс всех функций, сохраняющих 1, то есть таких функций для которых
- 59. Не входят в : тождественный ноль; отрицание.
- 60. Класс . Класс – это класс всех самодвойственных функций, то есть таких функций f, которые совпадают
- 61. Конъюнкция и дизъюнкция не самодвойственны. В таблице самодвойственной функции значение в последней строке противоположно значению в
- 62. Класс L. Класс L– это класс всех линейных функций, то есть функций, представимых в виде где
- 63. Класс M. Класс M– это класс монотонных функций. Функция называется монотонной, если при Конъюнкция, дизъюнкция монотонны;
- 64. Теперь мы можем сформулировать один из важнейших результатов теории булевых функций– теорему Поста о полноте. Теорема.
- 65. Как было показано, ни один из перечисленных пяти замкнутых классов не является полным(имеются не входящие в
- 66. Имеются булевы функции, не входящие ни в один из классов Любая такая функция в соответствии с
- 68. Скачать презентацию