Содержание
- 2. Определение Формальная система представляет собой совокупность чисто абстрактных объектов, не связанных с внешним миром, в которой
- 3. Всякая формальная система строится на основе формализованного языка (как средства формирования и изложения выражений, имеющих смысл
- 4. В формальной теории все формулы доказываются. Под теоремой в формальной системе понимают высказывание, истинное в данной
- 5. Доказательство – это способ получения одних выражений из других с помощью операций над символами и построения
- 6. Неопределяемые термины – это те термины и понятия, смысл и содержание которых считается уже известным, и
- 7. Обычно это утверждения, правильность которых не вызывает сомнения, и они принимаются как очевидные истины. Такие выражения
- 8. Определение формальной системы осуществляется в следующем порядке: 1. Задается конечное множество символов, которые образуют алфавит формальной
- 9. 3. Устанавливается множество аксиом, т.е. формул, истинность которых не требует доказательства. Обычно к ним относят те
- 10. В общем случае эти правила могут быть представлены в следующем виде что означает: из множества истинных
- 11. Определение Формальным доказательством, или просто доказательством, называется последовательность формул такая, что каждая формула является либо аксиомой,
- 12. Задаваемые при описании формальной системы правила вывода называют также правилами вывода заключений, т.е. они позволяют определить,
- 13. Различают два типа правил вывода. 1. Правила, применяемые к формулам, рассматриваемым как единое целое, в этом
- 14. 2. Правила, которые могут применяться к любой отдельной части формулы, причем сами эти части являются формулами,
- 15. Определение Правило подстановки заключается в замещении всех вхождений какой-либо переменной на формулу из формальной системы, которая
- 16. Пример Рассмотрим формальную систему следующего вида: Алфавит = {a, b, w}. Формулы − символ или последовательность
- 17. Символы с1 и с2 не принадлежат алфавиту формальной системы (ФС), они служат посредниками для формализации правил
- 18. Из определения ФС вытекает и способ получения допустимых формул, т.е. формул, выводимых согласно правилу вывода путем
- 19. Определение Формальная система называется разрешимой, если существует хорошо определенный способ действия, который за конечное число шагов
- 20. Определение Интерпретация представляет собой распространение исходных положений какой-либо формальной системы на реальный мир. Интерпретация придает смысл
- 21. Теоремы формальной системы, будучи интерпретированы, становятся после этого утверждениями в обычном смысле слова, и в этом
- 22. Следует отметить, что при интерпретации речь идет о замыкании или логическом завершении математического подхода, который в
- 23. 1. Математик изучает реальность, конструируя некоторое абстрактное представление о ней, т.е. некоторую формальную систему. 2. Строится
- 24. 3. Происходит возвращение к начальной точке всего построения и осуществляется интерпретация теорем, полученных при формализации.
- 25. Замечание Изучение аксиом и теорем как абстрактных выражений, представленных в некоторой форме, называется синтаксическим изучением аксиоматических
- 26. Формальную теорию часто называют исчислением. Под исчислением понимают формальное представление теории, которое позволяет оперировать с объектами
- 27. 1. Проблема противоречивости. Логическое исчисление называется непротиворечивым, если в нем недоказуемы никакие две формулы, из которых
- 28. 3. Проблема независимости аксиом. Для начала введем понятие независимой аксиомы. Аксиома называется независимой, если она не
- 29. §4. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
- 30. Определение Исчисление высказываний (ИВ), т.е. логика высказываний – это формальная система, интерпретацией которой является алгебра высказываний.
- 31. Как и любая формальная система, исчисление высказываний строится на основе четырех основных процедур: 1. Задания алфавита.
- 32. Алфавит, который состоит из символов трех категорий: а) бесконечное счетное множество высказываний (или переменных высказываний), которые
- 33. Формулы в исчислении высказываний однозначно получаются с помощью правил, которые описываются базисом и индуктивным шагом: базис:
- 34. Пример. Если x, y, z − формулы в соответствии с правилом базиса, то (x->y), (x&z) и
- 35. С введением понятия формулы вводится и понятие подформулы или части формулы, делается это следующим образом. Подформулой
- 36. Пример. Пусть задана формула , определим ее подформулы и глубину их вложенности.
- 37. Кроме табличной формы каждая правильная формула может быть представлена в виде дерева, ветви которого – исходные
- 38. Для упрощения записи формул ИВ используются те же соглашения, что и в алгебре логики, которые позволяют
- 39. Существует несколько вариантов подбора аксиом как исходных тождественно истинных формул. Эти наборы эквивалентны в том смысле,
- 41. Тождественную истинность аксиом можно проверить либо прямым вычислением значения формулы на каждом наборе, либо приведением их
- 42. Пример
- 43. Правила вывода устанавливают отношения на множестве формул исчисления высказываний. Правила вывода обычно представляются как отношения на
- 44. В исчислении высказываний используется два правила вывода: правило заключения (modus ponens). Если A и − это
- 45. 2) правило подстановки. где - это формулы, − попарно различные переменные высказывания; через запись обозначен результат
- 46. Справедливость правил вывода исчисления высказываний подтверждается применением методов булевой алгебры. В частности, тождественную истинность выводимой формулы
- 47. Кроме двух приведенных выше правил вывода, можно получить и другие правила, позволяющие строить новые доказуемые формулы.
- 48. Правило сложного заключения. Если − формулы и − теорема, то формула B − также теорема. Правило
- 49. Правило силлогизма (замыкания). Если и − теоремы, то также теорема, иначе Правило композиции. Если теорема, то
- 50. Правила вывода можно рассматривать и как результат логического анализа некоторых человеческих рассуждений. Рассмотрим примеры для приведенных
- 51. Правило заключения ИСХОДНЫЕ ПОСЫЛКИ. Если данный многоугольник правильный (А=1), то в него можно вписать окружность (А
- 52. Правило силлогизма ИСХОДНЫЕ ПОСЫЛКИ. Если треугольник равнобедренный (А = 1), то две его стороны равны (В
- 53. Как отмечалось выше, формулы исчисления высказываний можно интерпретировать как формулы алгебры высказываний (АВ). Для этого следует
- 54. Однако формализма, реализованного в АВ, не всегда достаточно для реализации построения доказательств в ИВ, поэтому существует
- 55. Определение. Формула выполнима, если она может принимать значение «истина» (например, ) Определение. Формула невыполнима, если ни
- 56. Определение. Тавтологиями называются общезначимые формулы. Если формула А≡1, т.е. А – тавтология, то это можно записать
- 57. Определение (Логический вывод на основе множества гипотез). Пусть E – это множество формул, тогда запись означает,
- 58. Определение. Принцип дедукции состоит в следующем. Формула A является логическим следствием конечного множества Е тогда и
- 59. В силу того, что для высказываний справедливы все свойства логических операций, которые были определены в алгебре
- 60. Действительно, если А есть логическое следствие гипотез ,то, учитывая сформулированный выше принцип дедукции, можно считать справедливой
- 61. МЕТОДЫ, ИСПОЛЬЗУЕМЫЕ ДЛЯ ОПРЕДЕЛЕНИЯ ОБЩЕЗНАЧИМОСТИ ФОРМУЛ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
- 62. Алгоритм редукции. Этот алгоритм позволяет доказывать общезначимость формул исчисления высказываний путем приведения к абсурду. Рассмотрим на
- 63. Предположим, что при некоторой интерпретации эта формула принимает значение «ложь». Из определения функции импликации известно, что
- 64. Применив ранее использованные рассуждения к первой строке, получим следующие значения переменных: Если подставить полученные значения во
- 65. Пример. Используя алгоритм редукции, доказать общезначимость следующей формулы: Пусть при некоторой интерпретации Это возможно только, если
- 66. Тогда из первой формулы следует, что возможна одна из следующих комбинаций значений переменных a и b:
- 67. Из второй формулы следует это означает, что возможны следующие значения c и a:
- 68. Из имеем c=1, b=0. Это единственно допустимые для c и b значения, при которых формула принимает
- 69. Метод резолюций. Для порождения логических следствий будет использована очень простая схема рассуждений. Пусть A, B и
- 70. В том частном случае, когда X – высказывание, а A и B – дизъюнкты, это правило
- 71. Так как левая часть последнего равенства представляет собой конъюнкцию, для его выполнения достаточно доказать равенство нулю
- 72. Применение метода резолюций предусматривает порождение новых дизъюнктов на основе следующей леммы, в основе которой лежит правило
- 73. Для доказательства приведенных выше утверждений о выполнимости формулы С необходимо, как отмечалось выше, доказать, что хотя
- 74. Таким образом, принцип резолюций заключается в использовании того факта, что множество дизъюнктов S не выполнимо, если
- 75. Метод резолюций выгодно отличается от других методов тем, что он дает возможность использовать средства автоматического доказательства,
- 76. Определение. Литера − это элементарное высказывание или его отрицание. Например, . Определение. Дизъюнкт или элементарная дизъюнкция
- 77. Так как для того, чтобы выражение в форме КНФ было тождественно истинным, необходимо и достаточно, чтобы
- 78. Итак, невыполнимость формул, из которых формируется конечное множество дизъюнктов S, доказывается с помощью следующего алгоритма. Шаг
- 79. Шаг 2. Построение резольвенты. Выбираем l, S1, S2, такие, что и и вычисляем резольвенту r. Если
- 80. Шаг 3. Обновление множества дизъюнктов. Заменяем множество дизъюнктов , т.е. добавляем к существующим дизъюнктам новый дизъюнкт
- 81. Пример. Доказать, используя метод резолюций, невыполнимость следующего множества дизъюнктов . Пронумеруем дизъюнкты. Это делается для того,
- 82. Порождаем логические следствия, при порождении следствия будем указывать, номера участвовавших в построении дизъюнктов:
- 83. Замечание. Алгоритм проверки невыполнимости недетерминирован. Вообще говоря, возможен не один вариант выбора значений для l, S1
- 84. Свойство 1. Если множество S не содержит ни одной пары дизъюнктов, допускающих резольвенту, то оно выполнимо
- 85. Пример. Доказать, используя метод резолюций, что S является логическим следствием множества гипотез H, где , а
- 86. Для доказательства того, что H |= S необходимо и достаточно доказать невыполнимость следующего множества дизъюнктов
- 87. Пример. Пусть дано множество утверждений, сформулированных на естественном языке, и некоторое заключение, которое из них следует.
- 88. Введем следующие обозначения для высказываний: g – встать рано; d – играть в преферанс; с –
- 89. Следствие примет вид . При построении доказательства по дедукции в качестве механизма воспользуемся методом эквивалентных преобразований
- 90. Теперь построим доказательство, используя метод резолюций. Для этого приведем имеющиеся гипотезы к форме дизъюнктов: Отрицание следствия
- 92. Скачать презентацию