Подобно тому, как определялись формулы логики высказываний, можно определить формулы логики предикатов. Не вдаваясь в детали (точные определения будут даны в следующей лекции), скажем только, что эти формулы содержат предикатные символы P(x), Q(x,y) и т.п. с указанием числа и имен предметных переменных, логические операции и кванторы.
Некоторые формулы являются равносильными (или связаны отношением следования) в силу самой их формы, независимо от того, как они будут проинтерпретированы, то есть какова выбранная предметная область, какой «смысл» придан предикатным символам (то есть, какие предикаты подставлены в формулы вместо предикатных символов), какие предметы будут подставлены вместо предметных переменных. Подобного рода равносильности и следования выражают логические законы. В качестве примера можно привести рассмотренные в предыдущем пункте законы де Моргана для кванторов. Особый интерес представляют формулы, которые остаются истинными при любой интерпретации (такие формулы называют общезначимыми). Для формул логики высказываний тождественную истинность формулы можно проверить с помощью таблиц истинности. В случае формул логики предикатов общей процедуры установления общезначимости формулы нет, для каждой формулы приходится подбирать свой метод проверки.
Важной проблемой логики вообще, и в частности логики предикатов, является поиск универсального алгоритма, позволяющего отличать истинные суждения от ложных. Эту проблему в различных ее формулировках называют проблемой разрешения. Для логики предикатов проблема разрешения решается отрицательно. Американским математиком А. Черчем установлено, что не существует общего алгоритма для определения того, что произвольная формула логики предикатов общезначима.
В приводимых ниже формулах использование предикатного символа без указания предметных переменных означает, что соответствующий предикат не зависит от указанных явно предметных переменных. Мы используем знаки ⇔ и ⇒ для указания на то, что формулы равносильны или что одна формула следует из другой при любой интерпретации.
Законы пронесения кванторов через конъюнкцию и дизъюнкцию:
∀x(P(x)∧Q(x)) ⇔ ∀xP(x)∧∀xQ(x);
∀x(P(x)∨Q) ⇔ ∀xP(x)∨Q;
∃x(P(x)∨Q(x)) ⇔ ∃xP(x)∨∃xQ(x);
∃x(P(x)∧Q) ⇔ ∃xP(x)∧Q.
Законы пронесения кванторов через импликацию:
∀x(P(x)→Q) ⇔ ∃xP(x)→Q;
∃x(P(x)→Q) ⇔ ∀xP(x)→Q;
∀x(Q→P(x)) ⇔ Q→∀xP(x);
∃x(Q→P(x)) ⇔ Q→∃xP(x).
Законы удаления квантора общности и введения квантора существования:
∀xP(x) ⇒ P(y); P(y) ⇒ ∃xP(x).
Законы коммутативности для кванторов:
∀x∀yP(x,y) ⇔ ∀y∀xP(x,y)
∃x∃yP(x,y) ⇔ ∃y∃xP(x,y)
∃y∀xP(x,y) ⇒ ∀x∃yP(x,y)
В качестве примера проведем доказательство того, что формулы ∀x(P(x)→Q) и ∃xP(x)→Q равносильны.
Доказательство. Пусть P – произвольный предикат на некотором множестве X, а Q – некоторое утверждение. Рассмотрим два случая: [Q]=0 и [Q]=1. Пусть сначала [Q]=0. При подстановке a∈X вместо x высказывание P(a)→Q истинно, если P(a) ложно, и ложно в противном случае. Таким образом, высказывание ∀x(P(x)→Q) истинно в том и только том случае, когда P(a) ложно для всех a∈X. Высказывание ∃xP(x)→Q истинно, если ложно высказывание ∃xP(x), то есть если P(a) ложно для всех a∈X. Следовательно, высказывания ∀x(P(x)→Q) и ∃xP(x)→Q имеют одинаковое значение истинности при [Q]=0.
Пусть теперь [Q]=1. При подстановке a∈X вместо x высказывание P(a)→Q истинно независимо от того, каково значение истинности высказывания P(a). Таким образом, высказывание ∀x(P(x)→Q) истинно. Но и высказывание ∃xP(x)→Q также истинно (независимо от того, истинно ли высказывание ∃xP(x)), то есть если P(a) ложно для всех a∈X. Следовательно, и при [Q]=1 высказывания ∀x(P(x)→Q) и ∃xP(x)→Q имеют одинаковое значение истинности.
Проведем еще одно доказательство.
Формулы ∀x(P(x)∨Q(x)) и ∀xP(x)∨∀xQ(x) не равносильны.
Доказательство. Для доказательства достаточно привести контрпример. На множестве целых чисел рассмотрим предикаты «x – четное число» и «x – нечетное число» и подставим их вместо соответственно P(x) и Q(x). Имеем:
