Т. А. Сливина математическая логика и теория алгоритмов

§ 2. Понятие формулы логики предикатов. Значение формулы логики
предикатов

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

1) p, q, r, … – переменные высказывания, которые принимают значения 0 или 1;
2) x, y, z, … – предметные переменные, которые принимают значения из некоторого множества М. x⁰, y⁰, z⁰, … – предметные константы, т. е. значения предметных переменных;
3) Р(·), F(·), … – одноместные предикаты,
Р(·,·, …,), F(·,·, …,) – n-местные предикаты,
Р⁰(·), Р⁰(·,·,…,) – постоянные предикаты;
4) Символы логических операций: ;
5) Символы кванторных операций:
6) Вспомогательные символы: скобки ( ), запятые.
Определение формулы логики предикатов.
1. Каждое высказывание как переменное, так и постоянное, является формулой.
2. F(x₁, x₂, …, x_n) является формулой, если F(·,·, …,) – есть n-местный предикат (переменный или постоянный), а x₁, x₂, …, x_n – предметные переменные или постоянные.
3. Если А и В формулы, то А В, А В, А В – тоже формулы. Причем, переменные, которые в исходных формулах были свободными, остаются свободными, а связанные – остаются связанными.
4. Если А – формула, то – тоже формула.
5. Если А(х) – формула, в которую х входит свободно, то высказывания и являются формулами, причем переменная х входит в них связанно.
Все остальные высказывания, не удовлетворяющие 1–5, не являются формулами.
Примеры формул.
q, P(x), P(x) Q(x⁰, y),
Не является формулой следующее выражение: Здесь нарушено условие п. 3, так как в это выражение переменная х входит связанно и свободно (P(x)).
Замечание. Всякая формула алгебры логики высказываний является формулой логики предикатов.
Формула логики предикатов может принимать логическое значение, если задано множество М, на котором определены, входящие в эту формулу предикаты.
Логическое значение формулы зависит от:

1. 
   значений, входящих в формулу переменных высказываний;
   
2. 
   значений свободных переменных из множества М;
   
3. 
   значений предикатных переменных.
   

При конкретных значениях, каждого из трех видов переменных, формула логики предикатов примет значение «и» или «л», (0, 1).
Например, рассмотрим формулу
(1)
в которой двухместный предикат Р(х,у) определен на множестве ММ, где М = {0, 1, 2, …, n, …}.
В формулу (1) входит переменный предикат Р(х,у), предметные переменные х, у, z, две из которых у и z – связанные кванторами, ах – свободная.
Возьмем за конкретное значение предиката Р(х,у) фиксированный предикат Р°(х,у): «х<у», а свободной переменной х придадим значение х°=5М. Тогда при значениях у, меньших х°=5 предикат Р°(х°,у) принимает значение ложь, а импликация Р(х, у)  Р(у,z) при всех zМ принимают значение истина, то есть высказывание имеет значение «истина».