1.2.1.2. Правила записи сложных формул

Пример 1.58. Дано «некоторые действительные числа являются рациональными». В этом суждении есть два предиката P1(x):= «x - действительное число» и P2(x):= «x - рациональное число».

Формула этого суждения есть F= x(P1(x)&P2(x)). Ошибочными являются формулы F= x(P1(x)→P2(x)):=

«некоторые числа, если они действительные, то они рациональные», и F= x(¬P1(x) P2(x)):= «некоторые числа не являются действительными или являются рациональными».

Пример 1.59. «Некоторые социал-демократы уважают всех демократов. Ни один социал-демократ не уважает ни одного коммуниста. Следовательно, ни один демократ не является коммунистом». В этом суждении три одноместных предиката P1(x):= «быть социал-демократом», P2(x):= «быть демократом», P3(x):= «быть коммунистом» и один двухместный предикат P4(x, y):= «x уважает y».

Формула сложного суждения имеет вид:

x (P1(x) & y (P2 (y) → P4 (x, y))),¬ x (P1(x) → y (P3 (y) → ¬P4 (x.y)))

x (P2 (x) → ¬P3 (x).

Пример 1.60. «Ни один торговец наркотиками не является наркоманом. Некоторые наркоманы привлекались к ответственности. Следовательно, некоторые люди, привлекавшиеся к ответственности, не являются торговцами наркотиков»[15].

В этом суждении три предиката P1(x):= «быть торговцем наркотиков», P2(x):= «быть наркоманом», P3(x):= «привлекаться к ответственности».

Формула этого суждения имеет вид:

x (P1(x) → P2 (x)), x (P2 (x) & P3 (y)

x (P3 (x)&¬P1(x)).

Примеры позволяют сформулировать некоторые правила:

•каждое вхождение логической связки «¬» относится к формуле, следующей непосредственно за логической связкой справа,

•каждое вхождение логических связок «&» или « » после расстановки скобок связывает формулы, непосредственно окружающие логическую связку,

•логические связки по силе упорядочены так: ¬, &, ,

→, ↔.

•за квантором общности чаще всего следует импликация, а за квантором существования - конъюнкции,

•если формула содержит подформулу, то последняя не должна содержать кванторов, связывающих ту же переменную, что и квантор формулы,

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

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

1.2.1.3. Законы алгебры предикатов

Основные законы алгебры предикатов приведены в таблице 1.11.

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

Две формулы Fi(t1, t2, … , tn) и Fj (t1, t2, … , tn) называ-

ются равносильными, если они при одинаковых наборах термов имеют одинаковое значение. Равносильность формул будем обозначать символом «≡», т.е. (F1 ≡ F2). Если две формулы равносильны F1(t1, t2, … , tn)≡F2(t1, t2, … , tn), то они эквивалентны. Эквивалентность формул будем обо-

значать символом «↔», т.е. (Fi(t1, t2, … , tn)↔Fi(t1, t2, … , tn)). И наоборот, если две формулы эквивалентны (Fi↔Fi),

то они равносильны (F1 ≡ F2).

Если в составе формулы F есть формула Fi, т.е. F(t1, t2, …, Fi, …, tn), и для Fi существует эквивалентная формула Fj, т.е. (Fi↔Fj), то возможна подстановка формулы Fj в формулу F без нарушения истинности формулы, т.е.

F(t1, t2, …, Fi, …, tn) ≡ F(t1, t2, …, Fj, …, tn).

Докажем равносильность некоторых законов.

•Дано x(F1(x))& x(F2(x))≡ x(F1(x)&F2(x)).

Если предикаты F1(x)=и, F2(x)=и, F1(x)&F2(x)=и, то истинны x(F1(x))=и, x(F2(x))=и, x(F1(x))& x(F2(x))=и,x(F1(x)&F2(x))=и.

Если предикаты F1(x)=л, F2(x)=и, F1(x)&F2(x)=л, то ложны x(F1(x))=л, x(F1(x))&x(F2(x))=л,x(F1(x)&F2(x))=л.

Следовательно, x(F1(x))&x(F2(x))≡x(F1(x)&F2(x)).

•Дано x(F1(x)) x(F2(x))≡ x(F1(x) F2(x)).

Если предикаты F1(x)=и, F2(x)=и, F1(x) F2(x)=и, то истинны x(F1(x))=и, x(F2(x))=и, x(F1(x)) x(F2(x))=и,x(F1(x) F2(x))=и.

Если предикаты F1(x)=л, F2(x)=и, F1(x) F2(x)=л, то ложны x(F1(x))=л, x(F1(x)) x(F2(x))=л, x(F1(x) F2(x))=л.

Следовательно, x(F1(x)) x(F2(x))≡x(F1(x) F2(x)).

•Дано x(¬F(x))≡¬x(F(x)).

Если предикат ¬F(x)=и, а F(x)=л, то x(¬F(x))=и,x(F(x))=л, ¬x(F(x))=и.

Если предикат ¬F(x)=л, а F(x)=и, то x(¬F(x))=л,x(F(x))=и, ¬x(F(x))=л.

Следовательно, x(¬F(x)) ≡ ¬x(F(x)).

Если в формуле F, содержащей свободную переменную x, выполнить всюду подстановку вместо переменной x терма t , то получим формулу F(t).Этот факт записывают

∫t F(x)

так: x

F(t).

Подстановка называется правильной, если в формуле всюду вместо свободной переменной x выполнена подстановка терма t.

Например,