Исчисление предикатов: язык, формулы и правила вывода

Высказывание «все студенты сдали экзамен» сообщает больше, чем просто одно значение «истина» или «ложь»: оно говорит об объектах, их свойствах и связи между ними. Исчисление предикатов позволяет записать эту структуру и проверить, какие заключения следуют из принятых посылок. Оно используется в математических доказательствах, спецификациях программ и описании отношений в базах знаний.
Ниже можно проверить небольшой пример. В области ровно три объекта, у каждого есть свойство . Перемещайте ползунок: он задаёт, у скольких из них нет свойства . Если хотя бы один такой объект существует, утверждение «все обладают » нарушено.
От высказываний к предикатам
В исчислении высказываний целые предложения обозначают буквами и соединяют связками. Например, из и следует , независимо от внутреннего устройства предложений. Но если обозначить одной буквой фразу «каждый студент сдал экзамен», внутри неё уже нельзя выделить студента и его результат.
Предикат выражает свойство объекта или отношение объектов. Пусть означает « - студент», а - « сдал экзамен». Тогда утверждение записывается так:
Читаем: для любого объекта , если он студент, то он сдал экзамен. Областью может быть, например, множество участников курса. В формуле учитываются и те участники, кто не является студентом: для них условие импликации ложно, поэтому сама импликация истинна. Формула не утверждает, что студенты вообще существуют.
Исчисление предикатов первого порядка квантифицирует по объектам области, а не по самим свойствам и отношениям. Например, можно сказать «для каждого человека», но запись «для каждого свойства» уже выходит за рамки обычной логики первого порядка. Точный набор символов зависит от выбранного формального языка.
Из чего состоит формула
Алфавит языка включает переменные , логические связки , кванторы и скобки. В конкретной задаче добавляют нелогические символы: предикаты, константы и, при необходимости, функции.
Терм обозначает объект: им может быть переменная , константа или выражение , если - символ функции. Предикат применяется к нужному числу термов: описывает свойство, а - отношение двух объектов. Это атомарные формулы. Из них по правилам построения получают более сложные формулы, например .
В записи переменная связана квантором, а остаётся свободной. Значение такой открытой формулы зависит от выбора . Если связать и её, получится замкнутая формула: . Она уже выражает утверждение об области целиком. Скобки показывают, какая часть формулы находится в области действия квантора; без них легко прочитать запись неверно.
В примерах с кванторами важно также сохранять порядок: «каждый знает кого-то» не обязательно означает «есть один человек, которого знают все». Отдельный разбор этих различий есть в статье про кванторы всеобщности и существования.
Как формализовать условие задачи
Пусть в группе есть студенты и преподаватели. Запишем фразу: «Каждый студент, изучающий логику, сдал экзамен». Сначала выбираем область - все участники курса. Затем задаём предикаты : « студент», : « изучает логику», : « сдал экзамен».
Союз «и» внутри условия объединяет два требования к одному объекту. Импликация связывает их с результатом. Запись означала бы другое: каждый участник курса одновременно студент, изучает логику и сдал экзамен. Она намного сильнее исходной фразы.
Существование студента, который изучает логику и сдал экзамен, выражается иначе: . Здесь конъюнкция необходима: импликация внутри квантора существования могла бы оказаться истинной даже для объекта, который не студент. После перевода полезно прочитать формулу обратно обычными словами и проверить, не добавили ли мы лишнее условие.
Проверка на конечной области
Рассмотрим область . Пусть истинно для всех трёх объектов, а - только для первого и второго. Мы проверяем формулу подстановкой каждого объекта. При и обе части импликации истинны. При условие истинно, а следствие ложно, поэтому импликация ложна.
На схеме ниже итог каждого случая вынесен в отдельный столбец. Достаточно одного исключения, чтобы всеобщая формула оказалась ложной в этой интерпретации. Если с помощью ползунка убрать единственный контрпример, все три импликации станут истинными и формула тоже станет истинной в выбранной области.

Здесь мы проверили конкретную конечную модель. Это не доказательство того, что формула истинна или ложна во всех возможных областях. О том, как значения символов и сама область задают смысл формулы, подробнее рассказывает статья об интерпретации формулы.
Пример вывода из посылок
Проверка истинности в модели и формальный вывод отвечают на разные вопросы. Для вывода выпишем две посылки: и . Требуется получить . В системе естественного вывода достаточно двух переходов:
- Из получаем по правилу устранения квантора всеобщности: подставляем терм вместо .
- Из и заключаем по правилу устранения импликации, или modus ponens.
Первый шаг переводит общее правило к конкретному объекту, второй применяет полученную импликацию. Подстановка должна быть допустимой: свободные переменные подставляемого терма не должны случайно попасть под действие другого квантора. Иначе смысл формулы изменится из-за захвата переменной.
Обратный переход требует осторожности. Из нельзя заключить : факт об одном объекте не доказывает утверждение обо всех. В правилах введения всеобщего квантора используют произвольный объект при специальных ограничениях на открытые допущения. Аналогично, из существования объекта со свойством нельзя без дополнительных условий приписать это свойство заранее выбранному объекту.
Следование, доказуемость и контрмодель
Запись означает семантическое следование: в каждой интерпретации, где истинны все посылки множества , истинна и формула . Запись говорит о синтаксическом выводе из по правилам выбранной системы. Для стандартных корректных и полных систем логики первого порядка эти понятия совпадают; смысл этого результата объясняется в статье о теореме Гёделя о полноте.
Чтобы опровергнуть предполагаемое следование, достаточно построить контрмодель: интерпретацию, в которой все посылки истинны, а заключение ложно. Например, из одного нельзя вывести . Возьмём область из одного объекта и положим, что и для него ложны. Посылка истинна благодаря ложному условию импликации, но заключение ложно.
При поиске ошибки не обязательно сразу перебирать большие структуры. Начните с одного или двух объектов, зафиксируйте истинность посылок и попробуйте сделать заключение ложным. Успех доказывает, что вывод неверен; неудача на нескольких маленьких моделях сама по себе ещё не доказывает его правильность.
Где применяется такой язык
В программировании формулы помогают явно записывать требования к данным. Например, утверждение «у каждого заказа есть покупатель» можно представить отношением между заказами и покупателями. При этом нужно отдельно определить, какие объекты входят в область и что означает отношение: сама формула не проверит корректность данных в системе. Если правило нарушено, конкретный заказ без покупателя становится понятным контрпримером.
В математике на языке предикатов формулируют определения и теоремы. Знакомое утверждение о натуральных числах «для каждого числа найдётся большее» использует отношение порядка и два квантора. При его записи важно, что большее число может зависеть от исходного; требование одного числа, большего всех натуральных, было бы совсем другим утверждением.
Формальный язык полезен и при проверке рассуждений на естественном языке. Сначала выделяют посылки, затем вводят обозначения и сравнивают предполагаемое заключение с тем, что действительно можно вывести. Однако выбор предикатов уже является интерпретацией исходной задачи: если перевод потерял существенное условие, корректное доказательство будет относиться к другой формулировке. Поэтому последний шаг - вернуться от символов к исходному тексту и проверить соответствие.
Частые ошибки
- Забывать область. Одни и те же символы могут описывать разные объекты и отношения; без интерпретации нельзя оценить конкретную формулу.
- Путать импликацию и конъюнкцию. «Все студенты сдали» ограничивает студентов; она не делает каждого объекта студентом.
- Считать пример доказательством общего утверждения. Проверка трёх объектов работает только для выбранной модели.
- Обобщать с особого объекта. не гарантирует для остальных объектов.
- Менять местами кванторы. При двух переменных порядок может изменить зависимость выбора и смысл формулы.
FAQ
Чем предикат отличается от высказывания?
Высказывание в заданной интерпретации имеет значение истинности. Предикат с переменной задаёт свойство или отношение; открытая формула получает значение после назначения объектов её свободным переменным.
Можно ли доказать всеобщую формулу проверкой примеров?
В конкретной конечной области - да, если проверены все её объекты. Для утверждения обо всех интерпретациях нескольких примеров недостаточно: нужен общий аргумент или формальный вывод.
Зачем нужны правила вывода, если есть модели?
Правила дают конечное доказательство из посылок. Модели помогают объяснить смысл формул и находить контрпримеры к неверным выводам.
Коротко
Исчисление предикатов объединяет язык объектов, свойств и отношений с логическими связками и кванторами. Формализация начинается с выбора области и значений символов; затем формулу можно проверить в модели или вывести из посылок. В примере с тремя объектами один объект с истинным и ложным опровергает утверждение в данной модели.
Читайте также

Система натурального вывода: правила и примеры
Система натурального вывода по шагам: правила введения и устранения связок, временные допущения, построение доказательства и типичные ошибки в логике.

Булев куб: вершины, рёбра и расстояние Хэмминга
Булев куб простыми словами: как двоичные наборы становятся вершинами, когда они соседствуют, сколько в кубе рёбер и как найти расстояние между вершинами.

Частично упорядоченное множество: примеры и диаграмма
Разбираем частично упорядоченное множество: свойства отношения, сравнимые элементы, диаграмму Хассе и отличие максимального элемента от наибольшего на примерах.

Доминирующее множество в графе: определение и примеры
Как проверить доминирующее множество графа и найти число доминирования: разбираем путь из шести вершин, полный перебор, жадный подход и типичные ошибки.

Гиперграф: что это такое и как его построить
Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.

Контекстно-свободная грамматика: правила и примеры
Контекстно-свободная грамматика простыми словами: терминалы и нетерминалы, вывод слова, дерево разбора, неоднозначность и применение при анализе синтаксиса.