Пример 4.1. 1. P(x) º "x делится на 2",

1. P(x) º "x делится на 2",

Q(x) º "x делится на 3",

P(x)&Q(x) º "x делится на 6".

2. S(x,y) º "x = y ",

ØS(x,x) É S(x,y) - предикат истинен при любых x и y.

Наряду с применением логических связок с предикатами можно выполнять иоперации квантификации или "связывания квантором переменную".

Определение. Квантор общности. Пусть P(x) - предикат, тогда формула "x P(x) обозначает высказывание, которое истинно тогда и только тогда, когда для всех xÎM предикат P(x) - истинен. "xP(x) читается как "для всех x P(x)". Формула "x P(x) от x не зависит - вместо x нельзя подставить никакую предметную константу. Символ " называется квантором общности или универсальным квантором.

Формула "xP(x) на обычном языке передается также и следующими способами:

P(x) при произвольном x;

P(x), каково бы ни было x;

для каждого x (верно) P(x);

всегда имеет место P(x);

каждый обладает свойством P;

все удовлетворяет P.

Определение. Квантор существования. Пусть P(x) - предикат, тогда формула $x P(x) обозначает высказывание, которое истинно тогда и только тогда, когда найдется такой xÎM, что предикат P(x) - истинен. $x P(x) читается как "существует такой x, что P(x)". Формула $x P(x) от x не зависит - вместо x нельзя подставить никакую предметную константу. Символ $ называется квантором существования или экзистенциальным квантором.

Формула $xP(x) на обычном языке передается также и следующими способами:

для некоторых x (имеет место) P(x);

для подходящего x (верно) P(x);

имеется x, для которого P(x);

у некоторых вещей есть признак P;

кто-нибудь относится к (есть) P.

Пример 4.2.

$ x (P(x)&Q(x)) º "существует x, который делится на 6" - истинное высказывание.

" x (P(x)&Q(x)) º "все x делятся на 6" - ложное высказывание.

Определение. Алфавит языка логики предикатов содержит:

1) символы предметных переменных x, y, z, x₁, y₁, z₁ и т. д.;

2) символы предикатов P, Q, P₁, Q₁ и т. д.;

3) символы логических операций &, Ú, Ø, É, ~;

4) символы кванторов ", $.

Определение. Слово в алфавите логики предикатов называется формулой, если выполнены следующие условия (одновременно определяются понятия свободной и связанной переменной формулы).

1. P(x₁, x₂, …, x_n) - формула, если P - n-местный предикат (Такая формула называется атомарной). Все переменные x₁, x₂, …, x_n - свободные переменные, связанных переменных в этой формуле нет.

2. Пусть A - формула, тогда ØA - формула с теми же свободными и связанными переменными, что и в формуле A.

3. Пусть A и B - формулы, причем нет таких переменных, которые были бы связаны в одной формуле и свободные - в другой. Тогда (A&B), (AÚB), (AÉB), (A~B) суть формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными.

4. Пусть A - формула, содержащая свободную переменную x. Тогда "x A, $ x A тоже формулы. Переменная x в них связана. Остальные же переменные, которые в формуле A свободны, остаются свободными. Переменные, которые в формуле A были связаны, остаются связанными. В этих вновь полученных формулах формула A называется областью действия квантора " x и $ x соответственно.

5. Слово в алфавите логики предикатов называется формулой только в том случае, если это следует из правил 1-4.

Пример 4.3.

Следующие выражения являются формулами логики предикатов: P(x₁,x₂,x₇) - атомарная формула, в которой x₁, x₂, x₇ - свободные переменные; (" x $ y P(x, y, z))É" x Q(x, w) -формула, в которой переменные x, y связаны, а переменные z, w свободны.

Выражение (" x $ y P(x, y, z))É" x Q(x, y) не является формулой.

Факты не существуют - есть только интерпретации.

Фридрих Ницше