Автор Тема: Лекция 18. Формулы логики предикатов  (Прочитано 1665 раз)

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 18. Формулы логики предикатов
« : Апрель 19, 2017, 06:50:32 pm »
Лекция 18. Формулы логики предикатов


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

***

Определение 18.1. Предикатной переменной называется переменная, которая пробегает множество предикатов.

Замечание 18.1. Для обозначения предикатных переменных будут использоваться буквы \(  \large P, \ Q, \ R  \) или они же с числовыми индексами внизу. При необходимости в скобках указывается число предметных переменных. Так, \(  \large R(x,y,z)  \) - трёхместная предикатная переменная (зависит от трёх предметных переменных), а \(  \large Q_1(x_1,x_2,x_3, x_4)  \) - четырёхместная (зависит от четырёх предметных переменных).

Замечание 18.2. Поскольку мы договорились считать высказывание нульместным предикатом, пропозициональные переменные будем считать нульместными предикатными переменными (предикатными переменными, не имеющими ни одной предметной переменной).

Определение 18.2. Формула логики предикатов.

1. Любая предикатная переменная есть формула логики предикатов.
2. Если \(  \large F_1  \) и \(  \large F_2  \) - формулы логики предикатов, то \(  \large \overline{F_1}  \), \(  \large (F_1 \wedge F_2)  \), \(  \large ( F_1 \vee F_2)  \), \(  \large (F_1 \oplus F_2)  \), \(  \large (F_1 \to F_2)  \) и \(  \large (F_1 \leftrightarrow F_2  ) \) также являются формулами логики предикатов.
3. Если \(  \large F  \) - формула логики предикатов и \(  \large x  \) - предметная переменная, которая входит в \(  \large F  \) свободно, то \(  \large \forall x F  \) и \(  \large \exists x F  \) - формулы логики предикатов, в которых предметная переменная \(  \large x  \) связана.
4. Никаких других формул логики предикатов, кроме получающихся согласно пунктам 1-3, нет.
 
Замечание 18.3. В пункте 3 определения формулы логики предикатов говорится о том, что формула \(  \large F  \) содержит свободную предметную переменную \(  \large x  \). Но это не означает, что она не может иметь других предметных переменных. Например, из двуместной предикатной переменной \(  \large P_1(x_1,x_2)  \) (она является формулой, в силу пункта 1 определения) получаем формулу \(  \large \forall x_1 P_1(x_1,x_2)  \).

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

Замечание 18.5. Формула логики предикатов, в отличие от формулы логики высказываний, содержит два вида переменных: предикатные и предметные. Определённые выше формулы называются формулами логики предикатов первого порядка, так как в них разрешается навешивать кванторы лишь по предметным переменным. В логике предикатов второго порядка допускается квантификация предикатных и функциональных переменных (последние являются абстрактными образами функций). Например, там формулами считаются выражения вида

\(  \large \forall P \exists x (P(x,y) \to Q(x))  \),

\(  \large \forall f P(x, f(x)) \wedge \exists y Q(y)  \).

Функциональных переменных нет в нашем определении формулы логики предикатов. Их можно включить и в определение формулы логики предикатов первого порядка, но для рассмотрения чистой логики они не нужны. Они нужны для построения теорий на основе логики предикатов. Далее будет рассматриваться только логика предикатов первого порядка без функциональных переменных (чистая логика предикатов первого порядка).

Замечание 18.6. Определение формулы логики предикатов, как и определение формулы логики высказываний, является индуктивным.

Замечание 18.7. Договоримся обозначать формулы логики предикатов буквами \(  \large F,  G,  H  \) или теми же буквами с нижними числовыми индексами:

\(  \large F_1,  F_2,  \ldots, G_1, G_2,  \ldots, H_1,  H_2,  \ldots  \)

Иногда в скобках будем указывать предикатные переменные, от которых зависит формула логики предикатов, а при необходимости - и предметные переменные, от которых зависят предикатные переменные. Например, \(  \large F(P_1,P_2, P_3)  \) - формула логики предикатов, зависящая от трёх предикатных переменных, \(  \large F_1(P(x,y),Q(x))  \) - формула логики предикатов, которая зависит от двух предикатных переменных \(  \large P  \) и \(  \large Q  \), первая из которых зависит от предметных переменных \(  \large x  \) и \(  \large y   \), а вторая - от предметной переменной \(  \large x  \).

Замечание 18.8. Формулы логики предикатов часто будем называть просто формулами, но, говоря о переменных, будем уточнять их тип - предметные или предикатные.

Замечание 18.9. Согласно определению 18.2, любая формула логики высказываний есть формула логики предикатов, но не наоборот.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 18. Формулы логики предикатов
« Ответ #1 : Апрель 25, 2017, 01:55:41 pm »
Замечание 18.10. Заключим несколько соглашений, позволяющих упростить запись формул. Во-первых, будем считать, что кванторы связывают сильнее любой пропозициональной связки (это неявно сказано в пункте 3 определения 18.2), поэтому будем опускать скобки, окружающие квантор и связанную им предметную переменную. Во-вторых, как и в логике высказываний, внешние скобки у формулы писать не будем, если формула не входит в другую формулу. Например, вместо

\(  \large ((\forall x) (\exists y) (P(x,y) \to Q(x,y,z))  \)

будем писать

\(  \large \forall x \exists y (P(x,y) \to Q(x,y,z)  \)

В-третьих, если бескванторная часть формулы не содержит пропозициональных связок, окружающие её скобки писать не будем.

Например, вместо

\(  \large \exists z \forall x \exists y (P(x,y,z))   \)

можно писать

\(  \large \exists z \forall x \exists y P(x,y,z)   \),

Но вместо

\(  \large \exists y( P_1(x,y,z) \to  P_2(x,y)) \)

нельзя писать

\(  \large \exists y P_1(x,y,z) \to  P_2(x,y) \),

поскольку часть формулы, не содержащая кванторов, включает в себя импликацию. Если скобки всё же опустить, то может сложиться впечатление, что квантором связана лишь предметная переменная \(  \large y  \) предикатной переменной \(  \large P_1  \) (на самом деле эта предметная переменная связана у предикатных переменных \(  \large P_1  \) и \(  \large P_2  \)).

В-четвёртых, предметные переменные, связанные одинаковыми кванторами, можно перечислять через запятую. Так, вместо

\(  \large \forall x_1  \forall x_2 P(x_1,x_2,x_3)  \)

можно писать

\(  \large \forall x_1, x_2 P(x_1,x_2,x_3)  \).

Замечание 18.11. Как и в логике высказываний, в логике предикатов вводятся понятия формализации предиката и интерпретации формулы.
Под формализацией в логике предикатов понимают перевод какого бы то ни было предиката (в том числе нульместного) на символический язык путём составления формулы логики предикатов, соответствующей этому предикату. Формализации в этом смысле предшествует формализация высказывания (составление соответствующего ему предиката). Логика предикатов даёт больше возможностей для формализации, чем логика высказываний. Пусть требуется формализовать высказывание "У любого человека есть дочь". Введём предикат "\(  \large x  \) - дочь \(  \large y  \)", определённый на множестве людей. Тогда высказывание записывается в виде нульместного предиката \(  \large \forall y \exists x   \) (\(  \large x  \) - дочь \(  \large y  \)). Иначе его можно прочитать так: "Для любого человека найдётся такой человек, что второй является дочерью первого". Затем, переходя уже к составлению формулы по данному предикату, можем обозначить предикат "\(  \large x  \) - дочь \(  \large y  \)" предикатной переменной \(  \large P(x,y)  \), тогда получим формулу \(  \large \forall y \exists x P(x,y)  \). Заметим, что формализация рассматриваемого высказывания в рамках логики высказываний свелась бы только к обозначению его какой-нибудь буквой (символом пропозициональной переменной), тогда как формализация в рамках логики предикатов первого порядка позволяет продемонстрировать структуру высказывания.
Интерпретация есть процедура, обратная интерпретации. Под формализацией и интерпретацией будем понимать и результаты соответствующих процедур.

Замечание 18.12. Выше была отмечена ограниченность выразительных средств классической логики высказываний. Выразительные средства классической логики предикатов первого порядка также ограничены. Например, в этой логике нельзя формализовать высказывание "Для любой функции \(  \large f  \) существует такое значение её переменной \(  \large x  \), что \(  \large f(x)=x   \)":

\(  \large \forall f \exists x f(x)=x  \).

Дело в том, что мы не можем навешивать кванторы на функциональные переменные (которые к тому же не фигурируют в нашем определении формулы).

***

Рассмотрим примеры выражений, являющихся формулами логики предикатов, и примеры выражений, которые формулами логики предикатов не являются

***

Пример 18.1. В силу пункта 1 определения 18.2, пропозициональная переменная \(  \large P  \) и предикатные переменные \(  \large  Q(x)  \) и \(  \large R(x,y,z)  \) являются формулами. Тогда, согласно пункту 2 упомянутого выше определения, формулами являются выражения \(  \large P \to R(x,y,z)  \) и \(  \large R(x,y,z) + Q(x)  \). Поскольку все предметные переменные предикатных переменных \(  \large Q  \) и \(  \large R  \) свободны, то формулами, в силу пункта 3 определения 5.2, являются выражения \(  \large \exists x Q(x)  \) и \(  \large \forall x (R(x,y,z) + Q(x))  \). Следовательно, учитывая пункты 2 и 3 определения формулы, выражения \(  \large (P \to R(x,y,z)) \vee \exists x Q(x)  \) и \(  \large \exists z \forall x (R(x,y,z) + Q(x))  \) являются формулами логики предикатов.

Пример 18.2. Поскольку предикатная переменная \(  \large Q(x)  \) зависит лишь от предметной переменной \(  \large x  \), то формулой нельзя считать выражение \(  \large \forall y Q(x)  \). Однако формулой является выражение \(  \large \forall y (Q(x) \leftrightarrow R(x,y,z))  \). Объясним, почему оно является формулой. Поскольку \(  \large Q  \) и \(  \large R  \) - предикатные переменные, то они являются формулами (пункт 1 определения формулы), следовательно, согласно пункту 2 определения формулы, формулой является выражение \(  \large Q(x) \leftrightarrow R(x,y,z)  \). Эта формула включает в себя свободную предметную переменную \(  \large y  \), значит, формулой является выражение \(  \large \forall y (Q(x) \leftrightarrow R(x,y,z))  \) (пункт 3 определения формулы).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 18. Формулы логики предикатов
« Ответ #2 : Апрель 26, 2017, 01:57:54 pm »
Рассмотрим виды формул логики высказываний. В зависимости от наличия свободных предметных переменных, различают открытые и замкнутые формулы.

***

Определение 18.3. Открытыми называются формулы логики предикатов, которые содержат свободные предметные переменные.

Определение 18.4. Замкнутыми называются формулы логики предикатов, не содержащие свободных предметных переменных.

Пример 18.3. Формулы

\(  \large \exists x (P(x,y,z) \leftrightarrow Q(x,y))  \),

\(  \large \forall y \exists x (P_1 (x,y,z) \vee (P_2 \to P_3(x)))  \)

являются открытыми. В первой не связаны предметные переменные \(  \large y   \) и \(  \large z  \), а во второй - \(  \large z  \).

Формулы

\(  \large \forall x \exists y \forall z (P_1(x,y,z) + P_2(x,z))  \),

\(  \large \forall x \exists y (P(x,y) \to (Q \to R(y)))  \)

являются замкнутыми.

Замечание 18.13. Может показаться, что замкнутые формулы логики предикатов являются формулами логики высказываний, поскольку при подстановке вместо предикатных переменных конкретных предикатов эти формулы становятся высказываниями. Однако это не так.

Замечание 18.14. Вернёмся к понятию интерпретации. Пусть \(  \large M_1,M_2, \ldots, M_n  \) - некоторые множества (они могут совпадать). Если в формулу логики предикатов подставить некоторые предикаты, заданные на этих множествах, то она сама станет некоторым предикатом, определённым на том же множестве. Если формула была замкнутой, то получим высказывание (нульместный предикат). Интерпретация на этом закончена. Если же формула была открытой, то чтобы получить высказывание, нам нужно интерпретировать получившийся предикат. Для этого надо придать значения всем свободным предметным переменным получившегося предиката.

Пример 18.4. Дадим интерпретацию формуле

\(  \large \exists x \exists y P(x,y) \).

Подставим вместо двуместной предикатной переменной \(  \large P(x,y)  \) предикат \(  \large x+y=1  \), зависящий от двух предметных переменных \(  \large x,y \in \mathbb{R}  \). Получим высказывание (нульместный предикат)

\(  \large \exists x \exists y  (x+y=1)  \).

Пример 18.5. Интерпретируем формулу логики предикатов

\(  \large \forall y (P(x,y,z) \to Q(y))  \).

Подставим вместо предикатной переменной \(  \large P  \) предикат \(  \large x^2+y^2=z^2  \), а вместо предикатной переменной \(  \large Q  \) - предикат \(  \large y^2>0  \), где \(  \large x,y,z \in \mathbb{N}  \). Получим двуместный предикат

\(  \large \forall y (x^2+y^2=z^2 \to y^2>0)  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 18. Формулы логики предикатов
« Ответ #3 : Апрель 27, 2017, 02:14:00 pm »
Пусть: 1) \(  \large F  \) - некоторая формула логики предикатов, зависящая от предикатных переменных \(  \large P_1,P_2, \ldots, P_n  \);
2) \(  \large M_1, M_2, \ldots, M_n  \) - некоторые множества.

В зависимости от выполнимости интерпретации формулы \(  \large F  \) на множествах \(  \large M_1,M_2, \ldots, M_n  \), различают выполнимые и невыполнимые (тождественно ложные) на множествах \(  \large M_1,M_2, \ldots, M_n  \) формулы, а в зависимости от опровержимости интерпретации формулы \(  \large F  \) на множествах \(  \large M_1,M_2, \ldots, M_n  \), - опровержимые и неопровержимые (тождественно истинные) на множествах \(  \large M_1,M_2, \ldots, M_n  \) формулы.

***

Определение 18.5. Формула \(  \large F  \) называется выполнимой на множествах \(  \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 F(A_1,A_2, \ldots, A_n)  \) выполним.

Определение 18.6. Формула \(  \large F  \) называется невыполнимой (тождественно ложной) на множествах \(  \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 F(A_1,A_2, \ldots, A_n)  \) невыполним (тождественно ложен).

Определение 18.7. Формула \(  \large F  \) называется опровержимой на множествах \(  \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 F(A_1,A_2, \ldots, A_n)  \) опровержим.

Определение 18.8. Формула \(  \large F  \) называется неопровержимой (тождественно истинной) на множествах \(  \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 F(A_1,A_2, \ldots, A_n)  \) неопровержим (тождественно истинен).

Замечание 18.15. Чаще всего говорят о выполнимости (опровержимости) на некотором множестве \(  \large M  \) (когда все предметные переменные принадлежат одному и тому же фиксированному множеству).

Замечание 18.16. Для формулы \(  \large F  \), которая тождественно истинна на некотором известном множестве \(  \large M  \), используется обозначение

\(  \large \stackrel{M}{\models} F  \).

В противном случае (если формула опровержима на множестве \(  \large M  \)) пишут

\(  \large \not \stackrel{M}{\models} F  \).

Замечание 18.17. Итак, формула логики предикатов \(  \large F  \) называется:

1) выполнимой на множестве \(  \large M  \), если существует выполнимый предикат, являющийся интерпретацией данной формулы на множестве \(  \large M  \);

2) тождественно ложной на множестве \(  \large M  \), если любая интерпретация данной формулы на множестве \(  \large M  \) является тождественно ложным предикатом;

3) опровержимой на множестве \(  \large M  \), если существует опровержимый предикат, который является интерпретацией данной формулы на множестве \(  \large M  \);

4) тождественно истинной на множестве \(  \large M  \), если всякая интерпретация данной формулы на множестве \(  \large M  \) есть тождественно истинный предикат.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 18. Формулы логики предикатов
« Ответ #4 : Апрель 28, 2017, 11:51:00 am »
Рассмотрим задачи на доказательство выполнимости (невыполнимости) и опровержимости (неопровержимости) формул классической логики предикатов на некотором множестве.

***

Задача 18.1. Докажем, что формула \(  \large \forall x (\overline{P_1(x,y)} \vee P_2(y))  \) выполнима на множестве \(  \large M=\{2,4,6, \ldots \}  \). Рассмотрим предикаты "\(  \large x  \) делится на \(  \large y  \)" и "\(  \large y  \) делится на \(  \large 2  \)". Тогда интерпретацией рассматриваемой формулы будет одноместный предикат \(  \large \forall x (x \not \vdots y \vee y \vdots 2)  \). Покажем, что этот предикат выполним. Пусть \(  \large y=2  \). Тогда интерпретацией предиката будет высказывание \(  \large \forall x (x \not \vdots y \vee 2 \vdots 2)  \). Оно истинно, поскольку предикат \(  \large x \not \vdots y \vee 2 \vdots 2  \) тождественно истинен. Он является тождественно истинным, поскольку предикат \(  \large 2 \vdots 2  \) тождественно истинен (высказывание истинно), согласно теореме из лекции 15. Итак, формула \(  \large \forall x (\overline{P_1(x,y)} \vee P_2(y))  \) является выполнимой на множестве чётных натуральных чисел.
 
Задача 18.2. Докажем, что формула \(  \large \forall x P(x) \wedge \exists x \overline{P(x)}  \) тождественно ложна на множестве \(  \large M=\{0 \}  \). Рассмотрим произвольный предикат \(  \large A(x)  \), заданный на множестве \(  \large M  \). Получим высказывание \(  \large \forall x A(x) \wedge \exists x \overline{A(x)}  \), равносильное, согласно теоремам из лекции 17, высказыванию \(  \large A(1) \wedge  \overline{A(1)}  \), которое ложно (закон исключённого третьего). Значит, рассматриваемая формула тождественно ложна на множестве, состоящем из нуля. Отметим, что формула \(  \large \forall x P(x) \wedge \exists x \overline{P(x)}  \) тождественно ложна на любом множестве, состоящем из одного-единственного элемента, поскольку высказывание \(  \large A(a) \wedge  \overline{A(a)}  \) ложно для любого предиката \(  \large A(x)  \) и для любого элемента \(  \large a  \).

Задача 18.3. Докажем, что формула \(  \large \exists x (P(x) \wedge Q(x,y))  \) опровержима на множестве \(  \large M= \mathbb{N}  \). Рассмотрим предикаты \(  \large x<0  \) и \(  \large x+y \not = 0  \). Получим одноместный предикат \(  \large \exists x (x<0  \wedge x+y \not = 0)  \). Положим \(  \large y=1  \). Тогда рассматриваемый предикат станет высказыванием: \(  \large \exists x (x <0  \wedge x+1 \not = 0)  \). Оно ложно, поскольку предикат \(  \large x<0  \) тождественно ложен (теорема из лекции 15). Следовательно, формула \(  \large \exists x (P(x) \wedge Q(x,y))  \) является опровержимой на множестве натуральных чисел.

Задача 18.4. Докажем, что формула \(  \large \forall x P(x) \to \exists x P(x)  \) тождественно истинна на множестве \(  \large M= \{1 \}  \). Пусть \(  \large A(x)  \) - произвольный предикат, определённый на множестве \(  \large M  \). Получим высказывание  \(  \large \forall x A(x) \to \exists x A(x)  \), которое равносильно, согласно теоремам из лекции 17, высказыванию \(  \large A(1) \to A(1)  \). Оно истинно, в силу определения импликации. Следовательно, формула \(  \large \forall x P(x) \to \exists x P(x)  \) тождественно истинна на множестве, состоящем из единицы. Следует заметить, что рассматриваемая формула тождественно истинна на любом одноэлементном множестве, так как высказывание \(  \large A(a) \to A(a)  \) истинно, какими бы ни были предикат \(  \large A  \) и элемент \(  \large a  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 18. Формулы логики предикатов
« Ответ #5 : Апрель 28, 2017, 11:51:18 am »
Пусть \(  \large F  \) - некоторая формула логики предикатов, которая зависит от предикатных переменных \(  \large P_1,P_2, \ldots, P_n  \).

Определение 18.8. Формула \(  \large F  \) называется тождественно истинной, если для любых предикатов \(  \large A_1,A_2, \ldots, A_n  \), определённых на произвольных множествах \(  \large M_1,M_2, \ldots, M_n  \), предикат \(  \large F(A_1,A_2, \ldots, A_n)  \) тождественно истинен.

Замечание 18.18. Если формула не является тождественно истинной, то это значит, что найдутся такие предикаты, определённые на некоторых множествах, что предикат опровержим. Это совпадает с определением формулы, опровержимой на наборе множеств \(  \large M_1,M_2, \ldots, M_n  \).

Замечание 18.19. Тождественно истинные формулы логики предикатов называются также общезначимыми формулами и законами логики предикатов.

Замечание 18.20. Учитывая решение задачи 18.4, наряду с понятием общезначимости формулы, можно ввести понятие \(  \large k  \)-общезначимости - тождественной истинности формулы на произвольном \(  \large k  \)-элементном множестве. Так, формула \(  \large \forall P(x) \to \exists x P(x)  \) является тождественно истинной на произвольном множестве, состоящем из одного элемента. Следовательно, данная формула \(  \large 1  \)-общезначима.

Замечание 18.21. Для общезначимых формул будем использовать обозначение

\(  \large \models F  \).

Если формула не является общезначимой, то пишут

\(  \large \not \models F  \).

Замечание 18.22. Общезначимые формулы логики предикатов, как и тавтологии логики высказываний, являются схемами построения истинных высказываний.

Определение 18.9. Формула \(  \large F  \) называется тождественно ложной, если для всяких предикатов \(  \large A_1,A_2, \ldots, A_n  \), определённых на каких угодно множествах \(  \large M_1,M_2, \ldots, M_n  \), предикат \(  \large F(A_1,A_2, \ldots, A_n)  \) тождественно ложен.

Замечание 18.23. Если формула не является тождественно ложной, то это значит, что найдутся такие предикаты, определённые на некоторых множествах, что предикат выполним. Это совпадает с определением выполнимой на множествах \(  \large M_1,M_2, \ldots, M_n  \) формулы.

Замечание 18.24. Тождественно ложные формулы логики предикатов называются также противоречиями.

Замечание 18.25. В отличие от логики высказываний, где тип любой формулы можно определить, составив таблицу истинности, в логике предикатов, в силу теоремы, принадлежащей американскому логику Алонзо Чёрчу, не существует общего алгоритма, позволяющего установить, к какому типу принадлежит формула. Такие алгоритмы существуют лишь для формул некоторых видов, например, для формул, включающих не более чем одноместные предикатные переменные.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 18. Формулы логики предикатов
« Ответ #6 : Апрель 28, 2017, 11:55:18 am »
Рассмотрим задачи, где требуется доказать тождественную истинность и тождественную ложность формул логики предикатов.

***


Задача 18.5. Доказать общезначимость формулы:

\(  \large \forall x P_1(x)  \to \forall x (P_1(x) \vee P_2(x)) \).

Предположим, что формула не является общезначимой (является опровержимой). Иначе говоря, существуют такие предикаты \(  \large A_1(x)  \) и \(  \large A_2(x)  \), определённые на некотором множестве \(  \large M  \), что нульместный предикат

\(  \large \forall x A_1(x) \to \forall x(A_1(x) \vee A_2(x)) \)

опровержим (высказывание ложно). Данная импликация ложна, в силу определения, тогда и только тогда, когда высказывание

\(  \large \forall x A_1(x)  \)

истинно, а высказывание

\(  \large  \forall x(A_1(x) \vee A_2(x))  \)

ложно. Согласно определению квантора общности, истинность первого высказывания эквивалентна тождественной истинности предиката \(  \large A_1(x)  \). Учитывая одну из теорем лекции 15, заключаем, что дизъюнкция предикатов \(  \large A_1(x)  \) и \(  \large A_2(x)  \) тождественно истинна, а значит, истинно и соответствующее универсальное высказывание:

\(  \large  \forall x(A_1(x) \vee A_2(x))  \).

Но, по нашему предположению, данное высказывание ложно. Противоречие. Следовательно, рассматриваемая в задаче формула логики предикатов является общезначимой.

Задача 18.6. Доказать, что формула

\(  \large \overline{P(x,y)} \wedge \forall x \forall y P(x,y)  \)

является противоречием.

Предположим противное. Пусть данная формула логики предикатов выполнима. Значит, учитывая определения выполнимой формулы, найдётся такой предикат \(  \large A(x,y)  \), который задан некоторых множествах \(  \large M_1  \) и \(  \large M_2  \), что предикат

\(  \large \overline{A(x,y)} \wedge \forall x \forall y A(x,y)  \)

выполним. Это означает, в силу определения выполнимого предиката, что найдутся такие предметные константы \(  \large a \in M_1  \) и \(  \large b \in M_2  \), что высказывание

\(  \large \overline{A(a,b)} \wedge \forall x \forall y A(x,y)  \)

истинно. Учитывая определения отрицания, конъюнкции и квантора общности, истинность данного высказывания эквивалентна ложности высказывания \(  \large A(a,b)  \) и тождественной истинности предиката \(  \large A(x,y)  \), интерпретацией которого является данное высказывание. Эти условия взаимно исключают друг друга, согласно определению тождественно истинного предиката. Получили противоречие. Итак, рассматриваемая формула является противоречием.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 18. Формулы логики предикатов
« Ответ #7 : Май 07, 2017, 06:12:44 pm »
Как и в классической логике высказываний, в классической логике предикатов справедлива теорема под названием правило подстановки, позволяющая рассматривать всякий закон логики предикатов в качестве схемы образования таких законов. Это значит, что любую предикатную переменную в общезначимой формуле можно рассматривать как произвольную формулу логики предикатов, кроме случая когда некоторая предметная переменная, связанная в исходной формуле, связана и в формуле, которая подставляется вместо предикатной переменной, зависящей от данной предметной переменной.

***

Теорема 18.1. Пусть: 1) \(  \large F  \) - общазначимая формула, зависящая от предикатных переменных \(  \large P_1,P_2, \ldots , P_n  \);
2) \(  \large H  \) - такая формула логики предикатов, что все предметные переменные, связанные в формуле \(  \large F  \), свободны в формуле \(  \large H  \).
Тогда формула \(  \large F(H,P_2, \ldots, P_n)  \) общезначима.

Доказательство элементарно. Если \(  \large F(P_1,P_2, \ldots, P_n)  \) - общезначимая формула, то, в силу определения, для любых предикатов \(  \large A_1,A_2, \ldots, A_n  \), заданных на каких угодно множествах \(  \large M_1,M_2, \ldots, M_n  \), предикат \(  \large F(A_1,A_2, \ldots, A_n)  \) тождественно истинен. Рассмотрим формулу \(  \large H  \), которая зависит от предикатных переменных \(  \large Q_1,Q_2, \ldots , Q_k  \). Если вместо этих предикатных переменных подставить произвольные предикаты \(  \large B_1,B_2, \ldots, B_k  \), определённые на произвольных множествах \(  \large N_1,N_2, \ldots, N_k  \), то получим произвольный предикат \(  \large H(B_1,B_2, \ldots, B_k)  \). Обозначив этот предикат через \(  \large A_1  \), можем считать, что теорема доказана.

Замечание 18.26. Подчеркнём, что требование о том, что все предметные переменные, которые связаны в формуле \(  \large F  \), свободны в формуле \(  \large H  \), является существенным. Если мы не будем его выполнять, то в результате подстановки получим выражение, не являющееся формулой логики предикатов. Например, выше было доказано, что формула

\(  \large \forall x P_1(x) \to \forall x (P_1(x) \vee P_2(x))  \)

является законом логики высказываний. Поскольку предметная переменная \(  \large x  \) в этой формуле связана, мы можем подставить вместо одноместной предикатной переменной \(  \large P_1(x)  \) формулу \(  \large \exists y P_3 (x,y)  \), где предметная переменная \(  \large x  \) свободна. Получим закон логики предикатов

\(  \large \forall x \exists y P_3(x,y) \to \forall x (\exists y P_3(x,y) \vee P_2(x))  \).

Однако мы не можем подставить формулу \(  \large  \exists x P_4(x,y,z)  \) вместо предикатной переменной \(  \large P_2(x)  \), поскольку в этой формуле предметная переменная \(  \large x  \) связана квантором существования (она же связана квантором общности в исходной формуле). Иначе получим выражение, не являющееся формулой логики предикатов:

\(  \large \forall x P_1(x) \to \forall x (P_1(x) \vee  \exists x P_4(x,y,z))  \).

Замечание 18.27. Подставлять формулы можно не только вместо одной, но и вместо любого количества (в том числе и всех) предикатных переменных.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 18. Формулы логики предикатов
« Ответ #8 : Февраль 16, 2018, 04:13:01 pm »
Оказывается, часть общезначимых формул логики предикатов получается из тавтологий алгебры высказываний. Докажем теорему о предикатной подстановке в пропозициональную формулу.

***

Теорема 18.2. Пусть: 1) \(  \large F  \) - тавтология алгебры высказываний, зависящая от пропозициональных переменных \(  \large P_1,P_2, \ldots, P_n  \);
2) \(  \large R_1,R_2, \ldots, R_n  \) - произвольные формулы логики предикатов.
Тогда \(  \large F(R_1,R_2, \ldots, R_n)  \) - общезначимая формула.

Доказательство. Если формула \(  \large F  \) является тавтологией логики высказываний, то, согласно определению, для любых высказываний \(  \large A_1,A_2. \ldots, A_n  \) высказывание \(  \large F(A_1,A_2, \ldots, A_n)  \) истинно. Нужно доказать, что предикат \(  \large F(B_1,B_2, \ldots, B_n)  \) тождественно истинен, какими бы ни были предикаты \(  \large B_1, B_2, \ldots, B_n  \), определённые на любых множествах \(  \large M_1,M_2, \ldots, M_n  \) (использовали определение общезначимой формулы). Предположим (ради определённости), что предикаты \(  \large B_1,B_2, \ldots, B_n  \) зависят от предметных переменных \(  \large x_1,x_2, \ldots, x_k  \). Согласно определению, тождественная истинность предиката \(  \large F(B_1,B_2, \ldots, B_n)  \) эквивалентна истинности высказывания \(  \large F(B_1(a_1, \ldots, a_k) , \ldots, B_n(a_1, \ldots, a_k))   \) для любых предметных постоянных \(  \large a_1, \ldots, a_k  \). Положим

\(  \large B_1(a_1, \ldots , a_k)=A_1, \ldots, B_n(a_1, \ldots, a_k) =A_n \).

Но высказывание \(  \large F(A_1,A_2, \ldots, A_n)  \) истинно, какими бы ни были высказывания \(  \large A_1,A_2, \ldots, A_n  \). Теорема доказана.

Замечание 18.28. Каждая пропозициональная переменная заменяется соответствующей предикатной формулой. Например, из тавтологии алгебры высказываний \(  \large (P \to Q) \to ( P \to (P \to Q))  \), заменяя \(  \large P  \) и \(  \large Q  \) на \(  \large P(x)  \) и \(  \large Q(x)  \) соответственно, получим закон логики предикатов \(  \large (P(x) \to Q(x)) \to ( P(x) \to (P(x) \to Q(x)))  \).

Замечание 18.29. Законы классической логики предикатов не исчерпываются законами классической логики высказываний. В следующих лекциях будут доказаны специфические законы логики предикатов, включающие кванторы.