Логика предикатов.

Алфавит языка логики предикатов включает следующие группы символов:

- предметные константы: a, b, c, …;

- предметные переменные: x, y, z, …;

- функциональные символы: f, g, h, …;

- предикатные символы: P, Q, R, …;

- логические связки:, &, v, →, ↔;

- кванторы:

Кроме того, для задания порядка операций могут использоваться скобки.

Множество D объектов, о которых ведется рассуждение, называется областью интерпретации языка логики предикатов. Предметные константы соответствуют конкретным элементам множества D, а предметы переменные могут принимать значения множества D.

Функциональные символы соответствуют функциям, заданным на области интерпретации. Функциональный символ вместе со списком аргументов образует функциональную форму. Например, если D – множество чисел, то функциональная форма f(x, y) может интерпретироваться как двуместная функция сложения чисел: x+y.

Термом является всякая предметная константа, предметная переменная либо функциональная форма. Аргументами функциональной формы могут быть любые термы, например f(a, x, g(c, z)).

Понятие формул в логике предикатов определяется следующим образом:

- всякий атом есть формула;

- если А и В – формулы, то А, А& В, АvВ, А→ В, А↔ В также формулы;

- если А – формула и х – переменная, то - формулы;

- других формул нет

Квантор всеобщности соответствует словосочетанию «для всех», т.е. формула вида интерпретируется как высказывание: «Для всех объектов области интерпретации выполняется свойство Р». Квантор существования соответствует слову «существует». Например, формула вида интерпретируется как высказывание: «Существует пара объектов в области интерпретации, которые находятся в отношении Q».

Квантор вместе с переменной называется квантификацией. Область действия некоторой квантификации есть формула, к которой применяется эта функция.

Для того, чтобы записать некоторое утверждение на языке логики предикатов необходимо:

- зафиксировать множество объектов, о которых идет речь, как область интерпретации;

- выделить функциональные связи и отношения (свойства), упоминаемые в данном утверждении и сопоставить им функциональные и предикатные символы соответствующей местности;

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