Содержание
- 2. Элементарная классическая логика. Семантика логических знаков. Введение: Высказывания и формы высказываний. Тема 1: Логические союзы. Тема
- 3. Высказыванием называют предложение, выражающее суждение. Если суждение, составляющее содержание (смысл) некоторого высказывания, истинно, то о данном
- 4. Слова: не; неверно, что; и; или; если..., то; тогда и только тогда, когда; либо..., либо; несовместно;
- 5. Существуют формы высказываний с двумя предметными переменными (с двумя пробелами); например, х старше у (...старше -...);
- 6. Если в форме высказывания, содержащей несколько предметных переменных, осуществить подстановку только для одной из них, то
- 7. В формализованном языке элементарной логики базовым понятием является понятие высказывания. - предложение есть понятие грамматическое, т.е.
- 8. Союз "и" (может быть "да", "но", "а" в значении "и") называется конъюнкцией. Союз "или" принято называть
- 9. Из двух высказываний можно построить одно, типа "если..., то...", которое называется импликацией. Высказывание, непосредственно следующее за
- 10. Логика высказываний может быть построена так. Прежде всего для этого сначала введем понятие языка логики высказываний,
- 11. Понятие правильно построенного высказывания (ППВ): 1. Всякая пропозициональная буква есть (простое) высказывание (ППВ). 2. Если А
- 12. Определение формулы логики высказываний: - пропозициональная переменная есть формула; - если А произвольная формула, то [читается:
- 13. Точный смысл (семантика) логических знаков может быть разъяснен с помощью специальных таблиц, в которых зафиксировано, при
- 14. Рассмотрим таблицы формул, содержащих в качестве главного логического знака различные логические союзы. Отрицание Семантическая таблица отрицания.
- 15. Так как каждая из формул А и В может быть истинной или ложной, то возможны четыре
- 16. Формула А\/В истинна тогда и только тогда, когда истинна по крайней мере одна из формул А
- 17. Формула (А -› В) ложна тогда и только тогда, когда формула А истинна, а В ложна,
- 18. Формула (А ↔ В) истинна либо когда формулы А и В обе истинны, либо когда они
- 19. Формула (А В) истинна, когда А ложно, но В истинно, или когда А истинно, но В
- 20. Перевод формул к логическим союзам «и», «не», «или» . 1. Нужно выявить все элементарные высказывания, которые
- 21. Исчисление истинностных значений логических формул. Тождественно-истинные и тождественно-ложные формулы. Введение: Исчисление истинностных значений логических формул. Тема
- 22. Исчисление истинностных значений логических формул осуществляется с помощью семантических таблиц для соответствующих логических союзов. Исчисление истинностных
- 23. Вычисление логического значения формулы по заданным логическим значениям ее переменных удобно проводить следующим образом. Выпишем формулу
- 24. Существуют формулы, которые при любых наборах логических значений переменных получают в заключительном столбце таблицы логическое значение
- 25. Каждая тождественно-истинная формула выражает логический закон. Формула p->р есть известный логический закон тождества, а формула р
- 26. Таким образом, существуют формулы, которые истинны при любых логических значениях своих переменных. Некоторые свойства тождественно-истинных формул:
- 27. Существуют также формулы, которые при любых наборах логических значений переменных получают в заключительном столбце своей таблицы
- 28. Двойственность логических формул. Равносильные формулы. Введение: Двойственность логических формул. Равносильные формулы. Тема 1: Закон двойственности. Тема
- 29. Знаки ↔ и - являются двойственными знаками. Определение Пусть А формула, в которую не входит знак
- 30. То же самое имеет место в отношении таблиц для эквивалентности и строгой дизъюнкции; таблица формулы (А↔В)
- 31. Если А* и В* - формулы, двойственные соответственно формулам А и В и если А равносильно
- 32. Определение : Формула А называется самодвойственной, если А равносильно А*. Определение : Формула А называется несамодвойственной,
- 33. Иногда различные по своей структуре формулы таковы, что одинаковым наборам логических значений переменных во входных столбцах
- 34. Отношение равносильности имеет следующие свойства: во-первых, рефлексивно, т. е. А равносильно А; во-вторых, симметрично, т. е.
- 35. А\/В равносильно В\/А; А\/(В\/С) равносильно (А\/В)\/С Данные равносильности свидетельствуют о коммутативности и ассоциативности дизъюнкции. А\/(В/\С) равносильно
- 36. Данные равносильности свидетельствуют о дистрибутивности дизъюнкции относительно конъюнкции и дистрибутивности конъюнкции относительно дизъюнкции. А/\А равносильно А
- 37. ~ И равносильно Л ~ Л равносильно И А↔И равносильно А А↔Л равносильно А/\И равносильно А
- 38. Понятие нормальной формы. Введение: Понятие нормальной формы. Тема 1: Процедура приведения к нормальной форме. Тема 2:
- 39. Определение : Формула логики высказываний имеет нормальную форму, если она: а) не содержит знаков ?, ↔
- 40. Любую формулу А, не имеющую нормальной формы, можно конечным числом применений правила замены преобразовать в формулу
- 41. Каждая формула логики высказываний принадлежит к одному из трех следующих классов: истинная при всех логических значениях
- 42. Если в результате ее применения к формуле ~ А, выяснится, что ~ А тождественно-истинная формула, то
- 43. Разрешающая процедура заключается в: приводим формулу к нормальной форме; в формуле, приведенной к нормальной форме, выделяем
- 44. К формулам а) и б), если это возможно, снова применяем пункты 2) - 4), а затем
- 45. Укажем простой метод, позволяющий по виду формулы, приведенной к некоторой стандартной форме, судить о том, тождественно-истинна
- 46. Для того чтобы формулу привести к КНФ, необходимо вначале с помощью известной процедуры привести ее к
- 47. Таким образом, по виду некоторой формулы в КНФ можно судить о том, тождественно-истинна она или нет.
- 48. Для того чтобы привести формулу к СКНФ, необходимо: известным уже способом привести ее к КНФ; на
- 49. Сокращенной КНФ данной формулы называется такая ее КНФ, которая удовлетворяет следующим условиям: ни в одном конъюнктивном
- 50. Для того чтобы привести формулу к сокращенной КНФ, нужно: привести ее к КНФ; из всех одинаковых
- 51. Формулы логики высказываний наряду с КНФ могут иметь дизъюнктивную нормальную форму (ДНФ). Условимся называть элементарной конъюнкцией
- 52. Определение Совершенной дизъюнктивной нормальной формой (СДНФ) некоторой формулы называется такая ее ДНФ, которая удовлетворяет следующим условиям:
- 53. всем тем дизъюнктивным членам, в которых отсутствует какая-нибудь из содержащихся в данной формуле переменных Е, на
- 54. Определение Сокращенной ДНФ данной формулы называется такая ее ДНФ, которая удовлетворяет следующим условиям: ни в одном
- 55. если среди дизъюнктивных членов ДНФ имеются два таких, что один содержит некоторую переменную, а другой -
- 56. Логическое следование. Естественный вывод в логике высказываний. Введение: Логическое следование. Тема 1: Понятие логического вывода. Тема
- 57. Пусть A1, A2. ..., An и В - формулы, a -E1, E2, ..., Em - совокупность
- 58. Формула В называется в этом случае логическим следствием (заключением) формул A1, A2, ..., An, а формулы
- 59. Метод сокращенных таблиц - в качестве начального предположения будет выступать то, что искомое высказывание не является
- 60. Как формы выражения логических законов, тождественно-истинные формулы, или логические тождества, используются для обоснования правил логического следования.
- 61. При n = О считаем, что формула, построенная по данной схеме кратной импликации, совпадает с формулой
- 62. В логике правила следования записываются в виде фигур рассуждения A1, ... A2, ..., An С которые
- 63. Таким образом, для проверки корректности некоторой фигуры рассуждения нужно образовать кратную импликацию, сделав посылки фигуры а
- 64. Логический вывод обозначается следующим знаком: " ├ ". Формула следующего вида: P1,P2,.....,Pn ├ Q, означает, что
- 65. Правило ВД, состоящее из двух фигур, означает, что дизъюнкция следует из формулы, совпадающей с одним из
- 66. Применяя правила следования, мы можем из исходных формул, называемых посылками, или допущениями, получать (выводить) новые формулы,
- 67. Прямое доказательство формулы (кратной импликации) вида A1->(A2->...(An->C)...) строится: 1. На любом шаге построения можно написать: одну
- 68. Косвенное доказательство формулы строится согласно следующему предписанию. На любом шаге построения можно написать: одну из формул
- 69. Слабое косвенное доказательство формулы A1->(A2-> ... (An->С) ... ) строится согласно следующему предписанию. На любом шаге
- 70. если для окончания косвенного доказательства требуется получение последовательности формул, содержащей пару противоречащих формул, и не требуется,
- 71. Правило построения сильного косвенного доказательства. Сильное косвенное доказательство формулы A1->(A2->...(An->C)..) строится согласно следующему предписанию. На любом
- 72. При построении исчисления высказываний гильбертовского типа выбирают конечный запас логических тождеств или конечный запас эффективно определенных
- 73. А единственным правилом вывода служит МП. Доказательство в системе Н формулы F строится согласно следующему предписанию.
- 74. Доказательство формулы F считается построенным, если в соответствии с пунктами 1) - 2) получена последовательность формул,
- 75. Непротиворечивость логической системы можно определить следующим образом: система называется непротиворечивой, если в ней недоказуемы некоторая формула
- 76. Логическую систему называют разрешимой теорией, если для нее существует эффективный метод, позволяющий конечным числом достаточно простых
- 77. Покажем , что система N естественного вывода семантически полна, отложив установление ее семантической корректности. Будем говорить,
- 78. Логика - это наука о способах доказательства. Выясним, в чем, собственно, состоит различие в построении доказательств
- 79. Введем еще два метасимвола: вместо объектной конъюнкции " /\ " будем использовать субъектный символ метаконъюнкции -
- 80. Клауза есть именно формальная запись доказываемого предложения. Вместо букв в ней можно подставить объектные высказывания, и
- 81. Однако исходная клауза по сравнению с другими подобными формами, имеет определенные преимущества и, в частности, используется
- 82. В качестве основной аксиомы логики высказываний, выражающей отношение порядка, мы возьмем клаузу А,В А, . Построение
- 83. Закона о единице записывается как: А, 1 А , Закон транзитивности : А→В, В→С А→С, Построение
- 84. Противоположным к аксиоматическому является конструктивный метод доказательства, основанный на таблицах истинности. Построение доказательств в логике высказываний.
- 85. Правило отделения: А, А→В В Принцип резолюций целиком заменяет аксиому порядка, поскольку сама эта аксиома может
- 86. Доказательный вывод в натуральном исчислении строится как упорядоченная цепь преобразований, связанных с удалением или введением логических
- 87. Во всех десяти правилах перед символом метаимпликации " " может стоять любой перечень посылок Р. Так,
- 88. Доказательство: 1. А, А→В В, (УИ) 2. А, А→ (УИ) 3. А, А→В, А→ B В(1,
- 89. Модуль 6. Исчисление предикатов. Символизация естественного языка. Тема 1: Понятие предиката, предикатного выражения и кванторов. Тема
- 90. Понятие предиката, предикатного выражения и кванторов. В грамматике предикат (сказуемое) есть то слово (или несколько слов)
- 91. Выражение "для всякого x" называется квантором общности. Мы считаем "для каждого x" и "для всех x"
- 92. Исчисление предикатов. Общая формулировка Для каждого n = 0, 1, 2, ... дано некоторое число n
- 93. Если А и В - элементы данного множества, то элементами его будут и ~ (А), (А)
- 94. Вхождение переменной в формулу называется связанным, если оно находится в области действия квантора, использующего эту переменную,
- 95. Исчисление предикатов. Общезначимость. Примем, что простой формуле Р(y1, y2, ... yn) приписывается истинностное значение, связанное с
- 96. Тождественно истинные формулы логики предикатов. Напомним, что как и в логике высказываний, формула, имеющая на выходе
- 97. Логическое следование. Основное определение понятия логического следования для логики предикатов. Формула В есть логические следствие формул
- 98. Естественный вывод в логике предикатов. Подстановкой в формулу А переменной у вместо переменной х называется замещение
- 99. Естественный вывод в логике предикатов. ВС А (х-у) Е х А УС Е х А А(х
- 100. Правило ВВ называется введением всеобщности, правило ВС - введением существования, и, наконец, правило УС -удаление существования.
- 101. При построении доказательства правило УС применяется, если выполняются следующие условия: собственная переменная данного правила не входит
- 102. Правило ВВ Оно позволяет переходить от предложения, выражающего условие, к общему предложению, если от параметра данного
- 103. Специфические законы логики предикатов. С помощью сформулированных выше правил естественного вывода доказываются следующие формулы, которые выражают
- 104. Специфические законы логики предикатов. 13. Е х (А & В)-> (Е х А & Е х
- 106. Скачать презентацию