Структуры данных и модели вычислений

         

Язык предикатов - часть 3


Аналогичное замечание справедливо и для двухместных предикатов.

Правила образования формул

  1. Если — -местный предикатный символ, а — термы, то выражение является формулой (атомарной).
  2. Если и — формулы, то выражения , , и являются формулами.
  3. Если — формула, а — переменная, то выражения , являются формулами.

Замечания

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

    в атомарные подформулы формулы называются связанными.

  2. Переменная, имеющая вхождение в атомарную подформулу формулы , не находящуюся в области действия соответствующего квантора, называется свободной переменной формулы . Конечно, одна и та же переменная может иметь как связанные, так и свободные вхождения в формулу.
  3. Формула, не имеющая переменных со свободными вхождениями, называется предложением.
  4. Формулы, в которых имеются свободные вхождения переменных, трактуются как высказывательные формы, а предложения — как высказывания, истинностная оценка которых зависит от интерпретации входящих в них предикатных и функциональных символов в соответствии со смыслом логических связок и кванторов.

Пример.

Пусть нелогическая сигнатура состоит из трех символов , где — двухместный предикат, — одноместная функция, — двухместная функция, тогда выражение

очевидно, будет формулой. Поскольку в этой формуле нет свободных переменных, то она является предложением.

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

  • — точка, являющаяся серединой отрезка ,
  • — точка, симметричная точке

    относительно некоторой точки,

  • — предикат, означающий равенство точек и .

При такой интерпретации нелогических символов , приведенная выше формула есть утверждение о том, что середина отрезка симметрична середине отрезка с концами, симметричными точкам .

Очевидно, что это утверждение истинно.


Рис. 14.1. 

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




Содержание  Назад  Вперед