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