Содержание
- 2. 4.1 ОСНОВНЫЕ ПОНЯТИЯ ЛОГИКИ ПРЕДИКАТОВ
- 3. В алгебре логики высказывания рассматриваются как единый объект с точки зрения истинности или ложности. Структура и
- 4. Определение. Одноместным предикатом P(x) называется произвольная функция переменной x, определенная на множестве М и принимающая значение
- 5. Определение. Предикатом Р называется n-местная функция, определенная на производном множестве М и принимающая в качестве значений
- 6. Используя функциональную форму записи для предикатов, можно сказать, что предикатом Р(х1, х2, …, хn) называется функция
- 7. Таким образом, n-местный предикат, − это двузначная функция от n аргументов, определенная на произвольном множестве М,
- 8. Возможность описывать с помощью предикатов не только функции, но и отношения, определяется следующим: а) если а1,
- 9. Предикат можно поставить в соответствие и непрерывной функции типа F:Мn→М. Такой функции можно поставить в соответствие
- 10. Таким образом, в общем случае предикат Р – двоичная переменная, то есть переменное высказывание, истинность которого
- 11. Примеры. 1.Рассмотрим утверждение «x – целое число». Введем предикат I, обозначающий отношение «быть целым числом», тогда
- 12. 3. Элементы хi множества М – города. Предикат Р(х) устанавливается таким образом: «х – это столица
- 13. Если вместо переменных в предикат подставить объекты , где М – множество, на котором определено Р,
- 14. Пример(для предикатов определенных в предыдущем примере). Пусть в обоих случаях предикаты определены на множестве R –
- 15. Определение. Для предиката можно выделить множество наборов таких, что , которые, будучи подставленными в предикат P,
- 16. Пример. Для предиката , определенного ранее, множество Ip может быть определено следующим образом:
- 17. Определение. Предикат называется тождественно истинным, если его множество Ip образуют все возможные наборы, которые можно определить
- 18. Определение. Предикат называется тождественно ложным, если его множество Т.к. результат предикатного выражения это значение истина или
- 19. Пример. Рассмотрим предикаты I(x) и S(x,y) из предыдущих примеров. Пусть I и S определены на множестве
- 20. 3) задана вычислительная процедура: «Повторять цикл, пока переменные х и у не станут равными, либо прекратить
- 21. Квантор всеобщности (∀). Пусть P(x) это предикат, определенный на множестве М. Тогда под выражением − понимается
- 22. Квантор существования (∃). Пусть Р(х) это предикат, определенный на множестве М. Тогда под выражением понимается высказывание,
- 23. Пример. Пусть предикат - определен на множестве N.
- 24. Входящие в предикатное выражение переменные могут быть связанными или свободными и это зависит от того, каким
- 25. Пример. Для выражения вида область действия кванторов определена следующим образом: для квантора − , для квантора
- 26. Определение. Вхождение переменной x в формулу называется связанным , тогда и только тогда, когда оно совпадает
- 27. Определение. Переменная свободна в формуле, если хотя бы одно ее вхождение в эту формулу свободно. Отметим,
- 28. Определение. Переменная называется квантифицированной , если она используема в кванторных операциях, т.е. или .
- 29. Пример. Р(х) − х свободная; − х связанная; − х связанная, y свободная; − х и
- 30. 4.2 Логика предикатов как формальная система
- 31. Алфавит. Правила построения формул. Аксиомы. Правила вывода.
- 32. 1. Алфавит. предметные переменные − x, y, z и т.п., которые принимают значение из множества М;
- 33. 2. Правила построения формул. Термом является всякая переменная и всякая функциональная форма. Функциональная форма − это
- 34. Предикатная форма − это предикатная константа, соединенная с соответствующим числом термов. Если Р − предикатная константа
- 35. Атом − это предикатная форма или некоторое равенство (выражение вида s=t, где s и t −
- 36. Определение понятия формулы 1. Атом есть формула. 2. Если А − формула, то − формула. 3.
- 37. 3. Определение аксиом. Выбор системы аксиом в исчислении предикатов может быть осуществлен по-разному. Один из наиболее
- 38. 4. Правила вывода. Правила вывода также полностью заимствуются из логики высказываний, кроме того, к ним добавляются
- 39. Примеры. 1. Утверждение: «Все слоны серые». Вводимые предикаты: слон(x) – «x – слон»; цвет(x,y) – «x
- 40. 2. Утверждение: «Для любого множества x существует множество y такое, что мощность y больше, чем мощность
- 41. 3. Утверждение: «Все кубики, находящиеся на кубиках, которые были сдвинуты или были скреплены с кубиками, которые
- 42. 4.3 Определение значения истинности предикатных формул
- 43. Определение. Две формулы логики предикатов считаются равносильными в области М, если они принимают одинаковые логические значения
- 44. Пусть А(х), А(x,y) и В(х) – предикаты, р – высказывание, тогда правила имеют следующий вид:
- 47. Пример. Доказать тождественную истинность заданного предикатного выражения
- 48. Пример. Доказать тождественную ложность заданного предикатного выражения
- 49. 4.4 Метод резолюций для логики предикатов
- 50. Так как анализ выражений в формальных системах осуществляется в чисто синтаксической форме, без учета семантики, то
- 51. 8888888888888888888888888888888888888888888888888888887 Например, для создания из и необходимо найти подстановку «A вместо x», которая сделает идентичными W1(A)
- 52. Определение. Подстановочным частным случаем называется подстановка в некоторое выражение термов вместо переменных.
- 53. Пример. Для выражения P(x, f(y), B) имеется четыре частных случая подстановки: P(z, f(ω), B) – алфавитная,
- 54. Любую подстановку можно представить с помощью множества упорядоченных пар вида S = {t1/v1, t2/v2, …, tn/vn},
- 55. При выполнении подстановки должны соблюдаться два правила: каждое вхождение переменной заменяется на один и тот же
- 56. Для предыдущего примера подстановки описанные с помощью введенного формализма, имеют следующий вид: 1) S1 = {z/x,
- 57. Для обозначения подстановки часто используется следующая запись. Если S – подстановка, а E – выражение, к
- 58. Определение. Говорят, что множество E={E1, E2 , …, En } унифицируемо, если существует такая подстановка S,
- 59. Пример. Пусть A={P(x, f(y), B), P(x, f(B), B)}, рассмотрим подстановку S={C/x, B/y} , унифицируем и получаем
- 60. Унификация производится при следующих условиях: 1. Если термы – константы, то они унифицируемы тогда и только
- 61. Пример. Рассмотрим дизъюнкты: 1) Q(a, b, c) и Q(a, d, l). Дизъюнкты не унифицируемы. 2) Q(a,
- 62. Если необходимо последовательно выполнить несколько подстановок: S1, S2, то можно записать На этом действии базируется такое
- 63. Если S и S' являются двумя множествами подстановок, то их композиция S и S' (пишется S
- 64. Определение. Композиция подстановок g и s есть функция gs, определяемая следующим образом: (gs) [t]=g[ s[t]], где
- 65. Пример. Пусть задана последовательность подстановок {x/y,w/z}, {v/x}, {A/v, f(B)/w}, они эквивалентны одной подстановке {A/y,f(B)/z}. Последняя подстановка
- 66. Основное требование алгоритма унификации состоит в том, что унификатор должен быть максимально общим, т.е. для любых
- 67. Определение. Если s – произвольный унификатор выражения E, а g – наиболее общий унификатор этого набора
- 68. Определение. Множество рассогласований непустого множества дизъюнктов {E1,…, En} получается путем выявления первой (слева) позиции, на которой
- 69. Пример. Рассмотрим дизъюнкты: {P(x, f(y, z)), P(x, a), P(x, g(h(k(x))))}. Множество рассогласований состоит из термов, которые
- 70. Алгоритм унификации Пусть E – множество дизъюнктов, D – множество рассогласований, k – номер итерации, gk
- 71. Шаг 1. Пусть k=0, gk=e (пустой унификатор), Ek=E.
- 72. Шаг 2. Если для Ek не существует множества рассогласований Dk, то алгоритм завершает работу и gk
- 73. Шаг 3. Если существуют такие элементы vk и tk в Dk, что vk – переменная, не
- 74. Шаг 4. Пусть gk+1=gk { tk / vk}, заменим во всех дизъюнктах Ek переменную vk. на
- 75. Шаг 5. k=k+1. Перейти к шагу 2.
- 76. Пример. Рассмотрим дизъюнкты: E={P(f(a), g(x)), P(y, y)}. Итерация 1. Шаг 1. E0=E, k=0, g0=e. Шаг 2.
- 77. Итерация 2. Шаг 2. D1={g(x),f(a)}. Шаг 3. Так как нет переменной в множестве рассогласований D1, то,
- 78. Обычно унификацию используют для приведения в соответствие различных выражений. Если в одном из выражений подставлены вместо
- 79. Как отмечалось ранее, метод резолюций применим к множеству дизъюнктов. Поэтому рассмотрим последовательность действий, которую необходимо реализовать,
- 80. Пусть задано следующее предикатное выражение: Его следует привести к множеству предложений. На каждом шаге будем приводить
- 81. Шаг 1. Используя правила эквивалентных преобразований, в исходном выражении все логические операции записывают через операции дизъюнкции,
- 82. Шаг 2. Используя правила де Моргана, выполняют преобразования, обеспечивающие применение операции отрицания только к литералам. Пример.
- 83. Шаг 3. Разделение переменных. Так как в пределах области действия квантора можно заменить любую переменную на
- 84. Шаг 4. Исключение кванторов существования. Рассмотрим формулу В этой формуле получается, что все выражение выполняется для
- 85. Если заменить на эту формулу переменную x, то квантор существования можно убрать и переписать выражение в
- 86. Пример. Привести к сколемовской форме следующую формулу: можно заменить переменную x на константу a, переменную u
- 87. Шаг 5. Преобразование выражения в предваренную (префиксную) форму. Так как в формуле кванторы существования отсутствуют, то
- 88. Шаг 6. Приведение матрицы выражения к форме КНФ. Известно, что любая логическая функция может быть представлена
- 89. Применим их к полученному после шага 5 выражению:
- 90. Шаг 7. Исключение кванторов общности. Так как в выражении остались кванторы общности, а их порядок несущественен,
- 91. Шаг 8. Переход от выражения в виде КНФ к множеству предложений. Для этого требуется убрать все
- 92. Шаг 9. Переименование переменных. Символы переменных должны быть изменены так, чтобы каждый появлялся не более чем
- 93. При построении вывода с помощью метода резолюций следует учитывать следующее: 1. Если во множестве присутствуют только
- 94. Пример. Рассмотрим дизъюнкты: C1: P(x)∨ Q(x), C2: Так как аргументы предиката Р в C1 и C2.
- 95. Следовательно, можно получить резольвенту C3’: Q(f(a))∨ R(a). В общем случае, подставив f(x) вместо x в C1,
- 96. Определение. Если два или более предиката (с одинаковым знаком) дизъюнкта C имеют наиболее общий унификатор g,
- 97. Пример. Рассмотрим дизъюнкт C= P(x) ∨ P(f(y)) ∨ В этом дизъюнкте первый и второй предикаты имеют
- 98. Определение. Пусть C1 и C2 – два дизъюнкта, которые не имеют никаких общих переменных. Пусть L1
- 99. Пример. Пусть C1= P(x) ∨ Q(x) и C2= ∨ R(x). Так как x входит в C1
- 100. Пример. Тогда при и получаем резольвенту а при
- 101. Переформулируем теперь уже известный алгоритм метода резолюций применительно к логике предикатов.
- 102. Шаг 1. Если в S есть пустой дизъюнкт, то множество S не выполнимо и алгоритм завершает
- 103. Шаг 2. Найти в исходном множестве S такие дизъюнкты или склейки дизъюнктов C1 и C2, которые
- 104. Шаг 3. Вычислить резольвенту C1 и C2, добавить ее в множество S и перейти к шагу
- 105. Пример 1. Докажем с помощью метода резолюций справедливость следующих рассуждений. Каждый член демократической партии голосует за
- 106. Введем следующие предикаты: C(x) – "x – член демократической партии"; W(x) – "x – голосует за
- 107. Решение:
- 108. Пример 2. Докажем с помощью метода резолюций справедливость следующих рассуждений. Некоторые руководители с уважением относятся ко
- 109. Введем следующие предикаты: C(x) – "x – руководитель"; P(x) – "x – программист"; B(x) – "x
- 110. Тогда посылки, записанные в виде предикатных выражений будут выглядеть так: Заключение примет следующий вид:
- 111. Преобразовав посылки и следствие, которое надо взять с отрицанием, в совокупность дизъюнктов, получим множество предложений, невыполнимость
- 113. Пример 3. Докажем с помощью метода резолюций справедливость следующих рассуждений. Если родитель мужчина, то это отец.
- 114. Введем следующие предикаты: C(x) – "x – сын"; О(x) – "x – отец "; R(x,y) -
- 115. Решение:
- 116. Определение. Сколемовской формой предикатного выражения называется формула логики предикатов, в которой все вхождения переменных, у которых
- 118. Скачать презентацию