30. Основные определения исчисления предикатов
Предикат
– это высказывательная функция,
определенная на некотором множестве
М, то есть такая n-местная
функция Р, которая каждому упорядоченному
набору
элементов множества М сопоставляет
некоторое высказывание, обозначаемое
[20].
Предикат – фундаментальное понятие математической логики, являющееся условием, сформулированным в терминах некоторого точного логико-математического языка. Предикат содержит обозначения для произвольных объектов – переменные. При замещении переменных именами объектов предикат задает точно определенное высказывание.
Предикат, имеющий одну переменную, называется свойством, а предикат с двумя переменными – отношением.
Исчисление предикатов первого порядка – формальный язык, выражающий разнообразные утверждения.
Правильно построенные формулы (ППФ) –допустимые выражения исчисления предикатов. Элементы формул: предикатные символы, символы переменных, функциональные символы, символы констант, символы логических операций.
Система продукций – обобщение вычислительного формализма, использующего предикаты и оперирующее понятиями: структура, класс, объект, свойства, правила.
Пример:
-
предикат, который имеет значение
«истина», если
.
Если
,
то предикат возвратит значение «ложь».
31. Высказывания. Кванторы и их свойства
Исчисление предикатов использует специальные операторы – кванторы, которые могут быть двух видов:
-
квантор общности,
-
квантор существования.
Связанная переменная в ППФ – квантифицированная переменная. Свободная переменная – не квантифицированна.
Высказывание – ППФ, у которой все переменные связанные.
Первый порядок исчисления предикатов не допускает квантификации предикатных и функциональных символов.
Пример высказывания и соответствующей ППФ [11]:
=
«Все слоны серые».
В данном примере свойство «Слон(х)» определяет возможность отношения «Цвет(х,Серый».
Свойства кванторов:
.
.
.
.
.
.
Пример интерпретации первого свойства:
Не существует ни одного слона, боящегося мышей. = Все слоны не боятся мышей.
Пример представления высказывания в исчислении предикатов:
Все кубики, находящиеся на кубиках, которые были сдвинуты или были скреплены с кубиками, которые сдвигались, также были сдвинуты: |
|
.
32. Правила вывода. Унификация
Назначение правил вывода: на основе множества ППФ получить новые корректные ППФ. Известно большое количество правил вывода, среди которых наиболее часто применяемыми являются следующие правила:
Правило вывода
1:
.
Модус поненс - операция, создающая ППФ
W2
из ППФ вида W1
и W1
W2.
Это правило интерпретируется так: если
истинно утверждение
,
и из
следует
,
то утверждение
тоже истинно.
Правило вывода 2:
Транзитивность оператора импликации.
Правило вывода 3:
Слияние утверждений
и
.
Правило вывода 4:
Резолюция двух ППФ.
Правило вывода 5: Специализация - создает ППФ W(А) из ППФ (x)W(х),
где А - любой символ константы.
Унификация –
процесс поиска подстановочных термов
на место переменных. Обозначение
подстановок:
,
где
-
новая переменная,
-
заменяемая переменная.
-
подстановка s
применяется к каждому элементу множества
ППФ
.
Назначение унификации – приведение
ППФ к заданному виду.
Множество ППФ
называется
унифицируемым,
если существует подстановка s
такая, что
.
Такая подстановка называется унификатором.
Применение унификатора сворачивает
унифицируемое множество в один элемент.