Автор Тема: Лекция 20. Следование формул логики предикатов  (Прочитано 757 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 20. Следование формул логики предикатов


Как и в случае с равносильностью, в логике предикатов можно ввести два понятия следования: следование на некотором наборе множеств и следование вообще (на произвольном наборе множеств).

***

Пусть: 1) \(  \large F_1,F_2, \ldots, F_k,G  \) - некоторые формулы логики предикатов, зависящие от предикатных переменных \(  \large P_1,P_2, \ldots, P_n  \);
2) \(  \large M_1, M_2, \ldots, M_n  \) - некоторые множества.

Определение 20.1. Формула \(  \large G  \) называется следствием на множествах \(  \large M_1, M_2, \ldots, M_n  \) формул \(  \large F_1,F_2, \ldots, F_k  \), если для любых предикатов \(  \large A_1,A_2, \ldots, A_n  \), заданных на множествах \(  \large M_1, M_2, \ldots, M_n  \) соответственно, предикат \(  \large G(A_1,A_2, \ldots, A_n)  \) следует из предикатов \(  \large F_i(A_1,A_2, \ldots, A_n), \ i=1,2, \ldots,k   \).

Замечание 20.1. Формула \(  \large G  \) не является следствием формул \(  \large F_1,F_2, \ldots, F_k  \) на множествах \(  \large M_1,M_2, \ldots, M_n  \), если найдутся такие предикаты \(  \large A_1,A_2, \ldots A_n  \), определённые на множествах \(  \large M_1,M_2, \ldots, M_n  \) соответственно, что предикат \(  \large G(A_1,A_2, \ldots, A_n)  \) не следует из предикатов \(  \large F_i(A_1,A_2, \ldots, A_n), \ i=1,2, \ldots,k   \).

Замечание 20.2. Обычно предполагается, что все предикаты определены на одном и том же множестве \(  \large M  \).

Определение 20.2. Формула \(  \large G  \) называется следствием формул \(  \large F_1,F_2, \ldots, F_k  \), если для любых предикатов \(  \large A_1,A_2, \ldots, A_n  \) предикат \(  \large G(A_1,A_2, \ldots, A_n)  \) является следствием предикатов \(  \large F_i(A_1,A_2, \ldots, A_n), \ i=1,2, \ldots,k   \).

Замечание 20.3. В отличие от определения 20.1, предикаты \(  \large A_1,A_2, \ldots, A_n  \) могут быть заданы на произвольных множествах.

Замечание 20.4. Формула \(  \large G  \) не является следствием формул \(  \large F_1,F_2, \ldots, F_k  \), если найдутся такие предикаты \(  \large A_1,A_2, \ldots A_n  \) (заданные на некоторых множествах), что предикат \(  \large G(A_1,A_2, \ldots, A_n)  \) не следует из предикатов \(  \large F_i(A_1,A_2, \ldots, A_n), \ i=1,2, \ldots,k   \).

Замечание 20.5. Если формула \(  \large G  \) является следствием формул \(  \large F_1,F_2, \ldots, F_k  \) на множествах \(  \large M_i, \ i =1,2, \ldots, n  \), используется обозначение \(  \large F_1,F_2, \ldots, F_k \stackrel{M_i}{\models} G  \), в противном случае - \(  \large F_1, F_2, \ldots, F_k \not \stackrel{M_i}{\models} G  \). Если формула \(  \large G  \) является следствием формул \(  \large F_1,F_2, \ldots, F_k  \) (на произвольных множествах), используется обозначение \(  \large F_1,F_2, \ldots, F_k \models G  \), в противном случае - \(  \large F_1, F_2, \ldots, F_k \not \models G  \).

Замечание 20.6. Как в случае со следованием на наборе множеств, так и в случае со следованием вообще, в формулах \(  \large F_1,F_2, \ldots, F_k, G  \) могут отсутствовать любые предикатные переменные.

Замечание 20.7. По аналогии с k-общезначимостью и k-равносильностью можно ввести понятие \(  \large k  \)-следования - следования формул логики предикатов на произвольном множестве, которое состоит из \(  \large k  \) элементов.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Рассмотрим задачи, где требуется доказать, что некоторая формула логики предикатов следует (не следует) из другой формулы логики предикатов (вообще или на произвольном множестве, состоящем из \(  \large k  \) элементов).

***

Задача 20.1. Доказать, что формула \(  \large \exists x P(x) \vee \forall x Q(x)  \) следует из формулы \(  \large \forall x P(x) \wedge \exists x Q(x)  \) на произвольном множестве \(  \large M  \), состоящем из одного элемента.

Пусть \(  \large A(x)  \) и \(  \large B(x)  \) - какие угодно предикаты, определённые на произвольном множестве \(  \large M=\{a \}  \). Поскольку множество конечно, можно выразить кванторы через пропозициональные операции, а именно:

\(  \large \forall x A(x) \wedge \exists x B(x) \Leftrightarrow A(a) \wedge B(a)  \),

\(  \large \exists x A(x) \vee \forall x B(x) \Leftrightarrow A(a) \vee B(a)  \).

Согласно определению, формула формула \(  \large \exists x P(x) \vee \forall x Q(x)  \) является следствием формулы \(  \large \forall x P(x) \wedge \exists x Q(x)  \)  на множестве \(  \large M= \{ a \}  \), если и только если предикат  \(  \large \exists x A(x) \vee \forall x B(x)  \) следует из предиката \(  \large \forall x A(x) \wedge \exists x B(x)   \) (истинность первого высказывания влечёт истинность второго высказывания). Это эквивалентно тому, что истинность высказывания \(  \large A(a) \wedge B(a)  \) влечёт истинность высказывания \(  \large A(a) \vee B(a)  \). Покажем, что это так, используя определения конъюнкции и дизъюнкции. Высказывание \(  \large A(a) \wedge B(a)  \) истинно тогда и только тогда, когда истинны оба члена конъюнкции, что эквивалентно истинности высказывания \(  \large A(a) \vee B(a)  \).

Итак, формула \(  \large \exists x P(x) \vee \forall x Q(x)  \) следует из формулы \(  \large \forall x P(x) \wedge \exists x Q(x)  \) на любом множестве \(  \large M  \), которое состоит из единственного элемента элемента.

Пример 20.2. Доказать, что формула \(  \large \forall y \exists x P(x,y)  \) не следует из формулы \(  \large P(x,x)  \) на любом множестве \(  \large M  \), состоящем из двух элементов.

Пусть \(  \large A(x,y)  \) - некоторый предикат, заданный на произвольном множестве \(  \large M= \{ a_1,a_2 \}  \). Тогда предикат \(  \large A(x,x)  \) получается из \(  \large A(x,y)  \) заменой предметной переменной \(  \large y  \) на \(  \large x  \). В силу определения, формула \(  \large \forall y \exists x P(x,y)  \) не является следствием формулы \(  \large P(x,x)  \) на множестве \(  \large M = \{ a,b\} \), если и только если предикат \(  \large \forall y \exists x A(x,y)  \) не является следствием предиката \(  \large A(x,x)  \). Согласно определению, это означает, что найдётся такая предметная постоянная \(  \large a_i \in M, \ i=1,2  \), что высказывание \(  \large A(a_i,a_i)  \) истинно, а высказывание  \(  \large \forall y \exists x A(x,y)  \) ложно. Снова выразим кванторы через пропозициональные операции:

\(  \large \forall y \exists x A(x,y)  \Leftrightarrow  \)

\(  \large \Leftrightarrow \exists x A(x,a_1) \wedge \exists x A(x,a_2) \Leftrightarrow   \)

\(  \large \Leftrightarrow (A(a_1,a_1) \vee A(a_2, a_1)) \wedge (A(a_1,a_2) \vee A (a_2,a_2)) \).

Пусть \(  \large x=a_1  \). И пусть высказывание \(  \large A(a_1,a_1)  \) истинно. В этом случае высказывание \(  \large (A(a_1,a_1) \vee A(a_2, a_1)) \wedge (A(a_1,a_2) \vee A (a_2,a_2))  \) может быть и ложным (например, если высказывания \(  \large A(a_1,a_2)  \) и \(  \large (a_2,a_2)  \) ложны).

Итак, формула \(  \large \forall y \exists x P(x,y)  \) не следует из формулы \(  \large P(x,x)  \) на произвольном двухэлементном множестве.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Задача 20.3. Доказать, что формула \(  \large \forall x \overline{P(x)}  \) следует из формулы \(  \large \forall x ( \overline{P(x) \vee Q(x)})  \).

Рассмотрим произвольные предикаты \(  \large A(x)  \) и \(  \large B(x)  \), определённые на каком угодно множестве \(  \large M  \). Упомянутое в условии задачи следование, согласно определению, имеет место тогда и только тогда, когда предикат \(  \large \forall x \overline{A(x)}  \) следует из предиката \(  \large \forall x ( \overline{A(x) \vee B(x)})  \). Иначе говоря, истинность высказывания \(  \large \forall x ( \overline{A(x) \vee B(x)})  \) влечёт истинность высказывания \(  \large \forall x \overline{A(x)}  \). Высказывание \(  \large \forall x ( \overline{A(x) \vee B(x)})  \) истинно, если и только если предикат \(  \large  \overline{A(x) \vee B(x)} \) тождественно истинен (согласно определению квантора общности). Это эквивалентно тождественной ложности предиката \(  \large A(x) \vee B(x)  \). Дизъюнкция двух предикатов тождественно ложна тогда и только тогда, когда оба предиката тождественно ложны. Следовательно, предикат \(  \large \overline{A(x)}  \) тождественно истинен (использовали теоремы из лекции 2). Значит, по определению квантора общности, высказывание \(  \large \forall x \overline{A(x)}  \) истинно

Итак, формула \(  \large \forall x \overline{P(x)}  \) следует из формулы \(  \large \forall x ( \overline{P(x) \vee Q(x)})  \).

Задача 20.4. Доказать, что формула \(  \large \exists x (P(x) \wedge Q(x))   \) не следует из формулы \(  \large \exists x P(x)  \).

Пусть \(  \large A(x)  \) и \(  \large B(x)  \) - некоторые предикаты, которые заданы на некотором множестве \(  \large M  \), причём \(  \large A(x)  \) выполним, а \(  \large B(x)  \) тождественно ложен. Если предикат \(  \large A(x)  \) выполним, то высказывание \(  \large \exists x A(x)  \) истинно. Но если предикат \(  \large B(x)  \) тождественно ложен, то предикат \(  \large A(x) \wedge B(x)  \) тождественно ложен (использовали одну из теорем лекции 2). Значит, высказывание \(  \large \exists x (A(x) \wedge B(x))  \) ложно. Это и означает, согласно определению, что формула \(  \large \exists x (P(x) \wedge Q(x))   \) не является следствием формулы \(  \large \exists x P(x)  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Докажем признак следования формул логики предикатов (заодно получим признак отсутствия следования), а также теорему, которая демонстрирует связь между понятиями "равносильность" и "следование" в классической логике предикатов.

***

Теорема 20.1. Формула \(  \large G  \) следует из формул \(  \large F_1,F_2, \ldots, F_k  \) тогда и только тогда, когда общезначима формула

\(  \large (F_1 \wedge F_2 \wedge \ldots \wedge F_k) \to G  \).

Доказательство. Отметим, что теоремы, имеющие форму эквиваленции, прежде мы доказывали так. Сначала доказывали импликацию \(  \large A \to B  \), затем - \(  \large B \to A  \), откуда делали вывод, что \(  \large A \leftrightarrow B  \) (поскольку \(  \large A \leftrightarrow B \simeq (A \to B) \wedge (B \to A)  \)). Это можно и не делать, если получается построить цепочку равносильностей.

Пусть \(  \large F_1,F_2, \ldots, F_k,G  \) - какие угодно формулы логики предикатов, определённые на произвольных множествах \(  \large M_1,M_2, \ldots, M_n  \). И пусть \(  \large F_1,F_2, \ldots, F_k \models G  \). Согласно определению 22.2, это истинно тогда и только тогда, когда для любых предикатов \(  \large A_1,A_2, \ldots, A_n  \) предикат \(  \large G(A_1,A_2, \ldots, A_n)  \) следует из предикатов \(  \large F_i (A_1,A_2, \ldots, A_n), \ i=1,2, \ldots, k  \). В силу теоремы 17.3, какими бы ни были \(  \large A_1,A_2, \ldots, A_n  \), \(  \large F_i (A_1,A_2, \ldots, A_n) \Rightarrow G(A_1,A_2,\ldots, A_n), \ i=1,2, \ldots, k \), если и только если предикат \(  \large (F_1(A_1,A_2, \ldots, A_n) \wedge F_2(A_1,A_2, \ldots, A_n) \wedge \ldots\wedge F_k(A_1,A_2, \ldots, A_n)) \to G(A_1,A_2, \ldots, A_n)  \) тождественно истинен. Данный предикат является тождественно истинным для любых \(  \large A_1,A_2, \ldots, A_n  \) тогда и только тогда, когда соответствующую формула общезначима (определение 18.8).

Теорема доказана.

Теорема 20.2. Формула \(  \large G  \) не является следствием формул \(  \large F_1,F_2, \ldots, F_k  \) тогда и только тогда, когда опровержима формула

\(  \large (F_1 \wedge F_2 \wedge \ldots \wedge F_k) \to G  \).

Доказательство аналогично доказательству теоремы 19.2. Теорема доказана.

Теорема 20.3. Формулы \(  \large F  \) и \(  \large G  \) равносильны, если и только если формула \(  \large  G  \) следует из формулы \(  \large F    \) и формула \(  \large F   \) следует из формулы \(  \large G   \).

Доказательство. Как и при доказательстве теоремы 20.1, построим цепочку равносильностей. Пусть \(  \large F  \) и \(  \large G  \) - произвольные формулы логики предикатов, которые определены на каких угодно множествах \(  \large M_1,M_2, \ldots, M_n  \). И пусть эти формулы равносильны. Они равносильны, согласно определению 19.2, если и только если для любых предикатов \(  \large A_1,A_2, \ldots, A_n  \) предикаты \(  \large F(A_1,A_2, \ldots, A_n)  \) и \(  \large G(A_1,A_2, \ldots, A_n)  \) равносильны. Используя определение 17.1, заключаем, что данные предикаты равносильны тогда и только тогда, когда для любых предметных постоянных \(  \large a_1 \in M_1, a_2 \in M_2, \ldots, a_n \in M_n  \) высказывания \(  \large F(A_1(a_1, \ldots, a_n) , \ldots, A_n(a_1, \ldots, a_n))  \) и \(  \large G(A_1(a_1, \ldots, a_n) , \ldots, A_n(a_1, \ldots, a_n))  \) имеют одинаковые значения истинности. Иначе говоря, если первое истинно, то второе истинно, и наоборот. А это, согласно определению 20.2 и определению 17.2, эквивалентно тому, что формула \(  \large F  \) следует из формулы \(  \large G  \), а формула \(  \large G  \) следует из формулы \(  \large F  \). Теорема доказана.

***

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

***

Задача 20.5. Доказать что формула \(  \large \exists x (\overline{P(x,y)} \to Q(x,y))  \) следует из формулы \(  \large \exists x P(x,y)  \), используя признак следования и основные равносильности логики.

Учитывая признак следования, задача эквивалентна задаче о доказательстве общезначимости формулы

\(  \large \exists x P(x,y) \to \exists x (\overline{P(x,y)} \to Q(x,y))  \).

Преобразуем её равносильным образом. Избавимся от внутренней импликации и воспользуемся законом двойного отрицания:

\(  \large \exists x P(x,y) \to \exists x (P(x,y) \vee Q(x,y))  \).

Избавимся оставшейся импликации:

\(  \large \overline{\exists x P(x,y)} \vee \exists x (P(x,y) \vee Q(x,y)  \).

Воспользуемся дистрибутивностью квантора существования относительно дизъюнкции:

\(  \large \overline{\exists x P(x,y)} \vee \exists x P(x,y) \vee \exists x Q(x,y)  \).

Используем закон исключённого третьего:

\(  \large 1 \vee \exists x Q(x,y)  \).

Эта формула тождественно истинна, поскольку \(  \large 1 \vee F \simeq 1  \).

Итак,

\(  \large \exists x P(x,y) \models \exists x (\overline{P(x,y)} \to Q(x,y))  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Поскольку справедлива теорема о предикатной подстановке в пропозициональную формулу, из каждого пропозционального правила дедуктивного умозаключения получим предикатное правило (точнее, сколь угодно много предикатных правил). Так, из правила modus ponens получим \(  \large P(x), P(x) \to Q(x) \models Q(x)  \), \(  \large \forall x P(x), \forall x P(x) \to Q(x,y) \models Q(x,y)  \) и т.д. Далее будем рассматривать только те правила дедуктивных умозаключений, которые содержат кванторы. При их доказательстве будем использовать определения кванторов и пропозициональных связок, а также теоремы из лекции 15.

Учитывая теоремы 20.1 и 20.3, каждая общезначимая формула логики предикатов вида \(  \large F_1 \leftrightarrow F_2  \) даёт два правила: \(  \large F_1 \models F_2  \) и \(  \large F_2 \models F_1  \). Нас будут интересовать  лишь те, что получаются из общезначимых импликаций вида \(  \large F_1 \to F_2  \).

***


1. Законы дистрибутивности и коммутативности кванторов


Теорема 20.4. Закон дистрибутивности квантора существования относительно конъюнкции.

\(  \large \exists x_1 (P(x_1,x_2, \ldots, x_n) \wedge Q(x_1,x_2, \ldots, x_n)) \models  \exists x_1 P(x_1,x_2, \ldots, x_n) \wedge \exists x_1 Q(x_1,x_2, \ldots, x_n) \)

Доказательство. Пусть \(  \large A(x_1,x_2, \ldots, x_n)   \) и \(  \large B(x_1,x_2, \ldots, x_n)  \) - произвольные предикаты, определённые на каких угодно множествах \(  \large M_1,M_2, \ldots, M_n  \). Докажем, что для любых \(  \large a_2 \in M_2, \ldots, a_n \in M_n  \) истинность высказывания

\(  \large \exists x_1 (A(x_1,a_2, \ldots, a_n) \wedge B(x_1,a_2, \ldots, a_n))  \)

влечёт истинность высказывания

\(  \large \exists x_1 A(x_1,a_2, \ldots, a_n) \wedge \exists x_1 B(x_1,a_2, \ldots, a_n)  \).

Высказывание

\(  \large \exists x_1 (A(x_1,a_2, \ldots, a_n) \wedge B(x_1,a_2, \ldots, a_n))  \)

истинно тогда и только тогда, когда предикат (от переменной \(  \large x_1  \)) \(  \large A(x_1,a_2, \ldots, a_n) \wedge B(x_1,a_2, \ldots, a_n)  \)выполним. Из этого следует выполнимость предикатов \(  \large A(x_1,a_2, \ldots, a_n)  \) и \(  \large B(x_1,a_2, \ldots, a_n)  \). Это эквивалентно истинности высказываний \(  \large \exists x_1 A(x_1,a_2, \ldots, a_n)   \) и \(  \large \exists x_1 B(x_1,a_2, \ldots, a_n)  \). Они истинны, если и только если истинно высказывание

\(  \large \exists x_1 A(x_1,a_2, \ldots, a_n) \wedge \exists x_1 B(x_1,a_2, \ldots, a_n)  \).

Теорема доказана.

Теорема 20.5. Закон дистрибутивности квантора общности относительно дизъюнкции.

\(  \large \forall x_1 P(x_1,x_2, \ldots, x_n) \vee \forall x_1 Q(x_1,x_2, \ldots, x_n) \models  \forall x_1 (P(x_1,x_2, \ldots, x_n) \vee Q(x_1,x_2, \ldots, x_n)) \)

Для доказательства используем признак следования формул логики предикатов, пропозициональный закон контрапозиции и правило подстановки. Выше было доказано, что

\(  \large \exists x_1 (P(x_1,x_2, \ldots, x_n) \wedge Q(x_1,x_2, \ldots, x_n)) \models  \exists x_1 P(x_1,x_2, \ldots, x_n) \wedge \exists x_1 Q(x_1,x_2, \ldots, x_n) \).

В силу признака следования формул, это эквивалентно тождественной истинности формулы

\(  \large  \exists x_1 (P(x_1,x_2, \ldots, x_n) \wedge Q(x_1,x_2, \ldots, x_n))  \to  (\exists x_1 P(x_1,x_2, \ldots, x_n) \wedge \exists x_1 Q(x_1,x_2, \ldots, x_n)) \).

Используя закон контрапозиции, представим эту формулу в виде

\(  \large \overline{\exists x_1 P(x_1,x_2, \ldots, x_n) \wedge \exists x_1 Q(x_1,x_2, \ldots, x_n)} \to \overline{ \exists x_1 (P(x_1,x_2, \ldots, x_n) \wedge Q(x_1,x_2, \ldots, x_n))}   \).

Используя законы де Моргана (пропозициональные и кванторные), получим:

\(  \large (\forall x_1 \overline{P(x_1,x_2, \ldots, x_n) } \vee \forall x_1 \overline{Q(x_1,x_2, \ldots, x_n)} ) \to \forall x_1 (\overline{P(x_1,x_2, \ldots, x_n)} \vee \overline{Q(x_1,x_2, \ldots, x_n)})   \).

С помощью правила подстановки получаем:

\(  \large (\forall x_1 P(x_1,x_2, \ldots, x_n)  \vee \forall x_1 Q(x_1,x_2, \ldots, x_n) ) \to \forall x_1 (P(x_1,x_2, \ldots, x_n) \vee Q(x_1,x_2, \ldots, x_n))   \).

А это, в силу признака следования, означает, что из формулы \(  \large \forall x_1 P(x_1,x_2, \ldots, x_n) \vee \forall x_1 Q(x_1,x_2, \ldots, x_n)  \) следует формула \(  \large \forall x_1 (P(x_1,x_2, \ldots, x_n) \vee Q(x_1,x_2, \ldots, x_n))  \). Теорема доказана.

Теорема 20.6. Закон коммутативности разноимённых кванторов

\(  \large \exists x_2 \forall x_1 P(x_1,x_2, \ldots, x_n) \models \forall x_1 \exists x_2 P(x_1,x_2, \ldots, x_n)  \)

Доказательство. Пусть \(  \large A(x_1,x_2, \ldots, x_n)  \) - произвольный предикат, заданный на каких угодно множествах \(  \large M_1,M_2, \ldots, M_n  \). Следование выполняется тогда и только тогда, когда предикат \(  \large \forall x_1 \exists x_2 A(x_1,x_2, \ldots, x_n)  \) следует из предиката \(  \large \exists x_2 \forall x_1 P(x_1,x_2, \ldots, x_n)   \), а это, согласно определению следования предикатов, означает, что для любых \(  \large a_3 \in M_3, \ldots, a_n \in M_n  \) истинность высказывания  \(  \large \exists x_2 \forall x_1 A(x_1,x_2, a_3, \ldots, a_n)  \) влечёт истинность высказывания \(  \large \forall x_1 \exists x_2 A(x_1,x_2, a_3, \ldots, a_n)   \). Далее будем использовать определения кванторов, выполнимого и тождественно истинного предиката. Высказывание \(  \large \exists x_2 \forall x_1 A(x_1,x_2, a_3, \ldots, a_n)  \) истинно, если и только если предикат (от переменной \(  \large x_2  \)) \(  \large \forall x_1 A(x_1,a_2, a_3, \ldots, a_n)  \) выполним (существует такой элемент \(  \large a_2 \in M_2  \), что высказывание \(  \large \forall x_1 A(x_1,a_2,a_3, \ldots, a_n)  \) истинно). Это эквивалентно тождественной истинности предиката (от переменной \(  \large x_1  \)) \(  \large A(x_1,a_2,a_3, \ldots, a_n)  \) (для любого элемента \(  \large a_1 \in M_1  \) высказывание \(  \large A(a_1,a_2, a_3, \ldots, a_n)  \) истинно). Следовательно, тождественно истинен и предикат (от переменной \(  \large x_1  \)) \(  \large \exists x_2 A(x_1,x_2, a_3, \ldots, a_n)  \). Значит, истинно высказывание \(  \large \forall x_1 \exists x_2 A(x_1,x_2, a_3, \ldots, a_n)  \). Теорема доказана.

Замечание 20.8. Важно понимать, что

\(  \large \exists x_1 P(x_1,x_2, \ldots, x_n) \wedge \exists x_1 Q(x_1,x_2, \ldots, x_n) \not \models \exists x_1 (P(x_1,x_2, \ldots, x_n) \wedge Q(x_1,x_2, \ldots, x_n))  \),

\(  \large  \forall x_1 (P(x_1,x_2, \ldots, x_n) \vee Q(x_1,x_2, \ldots, x_n)) \not \models  \forall x_1 P(x_1,x_2, \ldots, x_n) \vee \forall x_1 Q(x_1,x_2, \ldots, x_n)  \),

\(  \large  \forall x_1 \exists x_2 P(x_1,x_2, \ldots, x_n) \not \models \exists x_2 \forall x_1 P(x_1,x_2, \ldots, x_n)  \).

Примеры соответствующих предикатов приведены здесь, здесь и здесь.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 20. Следование формул логики предикатов
« Ответ #5 : Февраль 16, 2018, 04:09:23 pm »
2. Правила введения и удаления кванторов


Теорема 20.7. Первый закон введения квантора существования.

\(  \large P(x_1,x_2, \ldots, x_n) \models \exists x_1 P(x_1,x_2, \ldots, x_n)  \)

Доказательство. Теорема эквивалентна высказыванию о тождественной истинности формулы

\(  \large P(x_1,x_2, \ldots, x_n) \to \exists x_1 P(x_1,x_2, \ldots, x_n)  \).

Предположим, что она опровержима. Значит, существует такой предикат \(  \large A(x_1,x_2, \ldots, x_n)  \), определённый на некоторых множествах \(  \large M_1,M_2, \ldots, M_n  \), что предикат

\(  \large A(x_1,x_2, \ldots, x_n) \to \exists x_1 A(x_1,x_2, \ldots, x_n)  \)

опровержим. Согласно определению, это означает, что существуют такие предметные постоянные \(  \large a_i \in M_i, \ i =1,2, \ldots, n  \), что высказывание

\(  \large A(a_1,a_2, \ldots, a_n) \to \exists x_1 A(x_1,a_2, \ldots, a_n)  \)

ложно.

В силу определения импликации, это возможно, если и только если посылка истинна, а заключение ложно. Значит, предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) выполним, а предикат \(  \large A(x_1,a_1, \ldots, a_n)  \) тождественно ложен. Но эти условия противоречат друг другу. Следовательно, рассматриваемая формула тождественно истинна, а значит, следование выполняется. Теорема доказана.

Теорема 20.8. Второй закон введения квантора существования.

\(  \large \forall x_1 P(x_1,x_2, \ldots, x_n) \models \exists x_1 P(x_1,x_2, \ldots, x_n)  \)

Учитывая признак следования, доказательство сводится к равносильным преобразованиям соответствующей формулы. Имеем:

\(  \large \forall x_1 P(x_1,x_2, \ldots, x_n) \to \exists x_1 P(x_1,x_2, \ldots, x_n) \simeq  \)

\(  \large \simeq \overline{\forall x_1 P(x_1,x_2, \ldots, x_n)} \vee \exists x_1 P(x_1,x_2, \ldots, x_n)  \simeq  \)

\(  \large \simeq \exists x \overline{P(x_1,x_2, \ldots, x_n)} \vee   \exists x_1 P(x_1,x_2, \ldots, x_n) \simeq  \)

\(  \large \simeq \exists x (\overline{P(x_1,x_2, \ldots, x_n)} \vee P(x_1,x_2, \ldots, x_n))  \).

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

Теорема 20.9. Закон удаления квантора общности.

\(  \large \forall x_1 P(x_1,x_2, \ldots, x_n) \models  P(x_1,x_2, \ldots, x_n)  \)

Доказательство. Данный закон эквивалентен первому закону введения квантора существования (учитывая признак следования формул логики предикатов, правило подстановки, закон контрапозиции и другие законы алгебры высказываний). Имеем:

\(  \large  P(x_1,x_2, \ldots, x_n) \to \exists x_1 P(x_1,x_2, \ldots ,x_n) \simeq \overline{\exists x_1 P(x_1,x_2, \ldots, x_n) } \to \overline{P(x_1,x_2, \ldots, x_n)} \simeq  \)

\(  \large \simeq \forall x_1 \overline{P(x_1,x_2, \ldots, x_n) } \to \overline{P(x_1,x_2, \ldots, x_n)}  \).

Откуда и получаем

\(  \large \forall x_1 P(x_1,x_2, \ldots, x_n)  \to P(x_1,x_2, \ldots, x_n) \).

Теорема доказана.

Замечание 20.9. Стоит особо подчеркнуть, что

\(  \large \exists x_1 P(x_1,x_2, \ldots, x_n) \not \models P(x_1,x_2, \ldots, x_n)    \),

\(  \large \exists x_1 P(x_1,x_2, \ldots, x_n) \not \models \forall x_1 P(x_1,x_2, \ldots, x_n)    \),

\(  \large P(x_1,x_2, \ldots, x_n) \not \models \forall x_1 P(x_1,x_2, \ldots, x_n)    \).

Чтобы доказать, что данные следования не выполняются, достаточно взять любой выполнимый, но не тождественно истинный предикат \(  \large A(x_1,x_2, \ldots, x_n)  \).