Автор Тема: Лекция 19. Равносильность формул логики предикатов  (Прочитано 1750 раз)

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

Оффлайн Admin

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


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

***

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

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

Замечание 19.1. Формулы логики предикатов \(  \large F(P_1,P_2, \ldots, P_n)  \) и \(  \large G(P_1,P_2, \ldots, P_n)  \) не равносильны на множествах \(  \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)  \) и \(  \large G(A_1,A_2, \ldots, A_n)  \) не равносильны.

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

Определение 19.2. Формулы \(  \large F  \) и \(  \large G  \) называются равносильными, если предикаты \(  \large F(A_1,A_2, \ldots, A_n)  \) и \(  \large G(A_1,A_2, \ldots, A_n)  \) равносильны, какими бы ни были предикаты \(  \large A_1,A_2, \ldots, A_n  \).

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

Замечание 19.4. Согласно определению, формулы \(  \large F  \) и \(  \large G  \) не равносильны, если и только если существуют такие предикаты \(  \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)  \) не являются равносильными.

Замечание 19.5. Если формулы \(  \large F  \) и \(  \large G  \) равносильны на множествах \(  \large M_i, i=1,2, \ldots , n  \), используется обозначение

\(  \large F \stackrel{M_i}{\simeq} G  \),

если они не равносильны на этих множествах -

\(  \large F \not \stackrel{M_i}{\simeq} G  \).

Если формулы равносильны (на любых множествах), то используются те же обозначения, но без указания множеств над знаком равносильности:

\(  \large F \simeq G  \),

\(  \large F \not \simeq G  \).

Замечание 19.6. Любые предикатные переменные в формулах \(  \large F  \) и \(  \large G  \) могут отсутствовать (это относится и к равносильности на множествах).

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

Оффлайн Admin

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

***

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

Пусть \(  \large A(x)  \) - произвольный предикат, определённый на каком угодно множестве \(  \large M_1= \{a \}  \). Тогда \(  \large A(y)  \) - тот же самый предикат, где предметная переменная обозначена через \(  \large y  \). Согласно определению, рассматриваемые в задаче формулы равносильны на множестве \(  \large M_1  \), если и только если предикаты \(  \large \forall x ( \overline{A(x)} \vee A(y))  \) и \(  \large \exists x A(x) \vee \overline{A(y)}  \) равносильны. Из лекции 17 настоящего курса известно, что квантор общности (существования) можно выразить через конъюнкцию (дизъюнкцию), если предикаты заданы на конечных множествах. Следовательно, предикат

\(  \large \forall x ( \overline{A(x)} \vee A(y))  \)

равносилен предикату

\(  \large \overline{A(a)} \vee A(y)  \),


а предикат

\(  \large \exists x A(x) \vee \overline{A(y)}  \)

равносилен предикату

\(  \large A(a) \vee \overline{ A(y)}  \).

Поскольку множество, на котором определены предикаты, состоит из одного элемента, равносильность предикатов, в силу определения, имеет место тогда и только тогда, когда высказывания \(  \large \overline{A(a)} \vee A(a)  \) и \(  \large A(a) \vee \overline{ A(a)}  \) имеют одинаковые значения истинности. Это так, учитывая коммутативность дизъюнкции.

Итак, формулы являются \(  \large 1  \)-равносильными.

Задача 19.2. Доказать, что формулы \(  \large \exists x ( \overline{P(x)} \vee P(y))  \) и \(  \large \forall x \overline{P(x)} \vee P(y)  \) не равносильны на произвольном множестве \(  \large M  \), которое состоит из двух элементов.

Пусть \(  \large A(x)  \) - некоторый предикат, который задан на произвольном множестве \(  \large M_2 = \{a,b \}  \). В силу определения, формулы логики предикатов, рассматриваемые в задаче, не равносильны на множестве \(  \large M_2  \) тогда и только тогда, когда предикаты \(  \large \exists x ( \overline{A(x)} \vee A(y))  \) и \(  \large \forall x \overline{A(x)} \vee A(y)  \) не являются равносильными. Как и в предыдущей задаче, выразим кванторные операции через операции пропозициональные. Тогда первый предикат равносилен предикату

\(  \large \overline{A(a)} \vee A(y) \vee \overline{A(b)} \vee A(y)  \).

а второй предикат - предикату

\(  \large ( \overline{A(a)} \vee A(y) ) \wedge ( \overline{A(b)} \vee A(y))  \).

Согласно определению, эти предикаты не равносильны, если и только если найдётся такой элемент, принадлежащий множеству \(  \large M_2  \), что высказывания, получающиеся из предикатов в результате подстановки этого элемента вместо предметной переменной \(  \large y  \), имеют различные значения истинности. Положим \(  \large y=b  \). Тогда первый предикат становится высказыванием

\(  \large \overline{A(a)} \vee A(b) \vee \overline{A(b)} \vee A(b)  \),

которое равносильно высказыванию \(  \large \overline{A(a)}  \) (использовали идемпотентность дизъюнкции, закон исключённого третьего и правила действий с логическими константами), а второй предикат становится высказыванием

\(  \large ( \overline{A(a)} \vee A(b) ) \wedge ( \overline{A(b)} \vee A(b))  \),

которое равносильно высказыванию \(  \large \overline{A(a)} \vee A(b)  \) (применили закон исключённого третьего и правила действий с константами логики высказываний). Пусть, например, высказывания \(  \large A(a)  \) и \(  \large A(b)  \) истинны. Очевидно, что высказывания \(  \large \overline{A(a)}  \) и \(  \large \overline{A(a)} \vee A(b)  \) имеют разные истинностные значения: первое высказывание ложно, а второе - истинно.

Итак, формулы не являются \(  \large 2  \)-равносильными.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

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

***

Задача 19.3. Доказать, что формулы \(  \large \overline{\forall x \overline{P(x)}}  \) и \(  \large \exists x P(x)  \) равносильны.

Пусть \(  \large A(x)  \) - произвольный предикат, определённый на каком угодно множестве \(  \large M  \). В силу определения, формулы равносильны, если и только если нульместные предикаты (высказывания)  \(  \large \overline{\forall x \overline{A(x)}}  \) и \(  \large \exists x A(x)  \) равносильны (истинностные значения высказываний совпадают).

Пусть высказывание \(  \large \overline{\forall x \overline{A(x)}}  \) истинно. В силу определения отрицания, это имеет место тогда и только тогда, когда высказывание \(  \large \forall x \overline{A(x)}  \) ложно. Ложность этого высказывания, согласно определению квантора общности, эквивалентна опровержимости предиката \(  \large \overline{A(x)}  \). Предикат \(  \large \overline{A(x)}  \) опровержим, если и только если предикат \(  \large A(x)  \) выполним (использовали теорему из лекции 15). В силу определения квантора существования, данный предикат выполним тогда и только тогда, когда высказывание \(  \large \exists x A(x)  \) истинно. Значит, истинность высказывания
\(  \large \overline{\forall x \overline{A(x)}}  \) влечёт истинность высказывания \(  \large \exists x A(x)  \), и наоборот.

Пусть высказывание \(  \large \overline{\forall x \overline{A(x)}}  \) ложно. Ложность этого высказывания, согласно определению отрицания, эквивалентна истинности высказывания \(  \large \forall x \overline{A(x)}  \). В силу определения квантора общности, высказывание \(  \large \forall x \overline{A(x)}  \) истинно, если и только если предикат \(  \large \overline{A(x)}  \) тождественно истинен. Он тождественно истинен тогда и только тогда, когда предикат \(  \large A(x)  \) тождественно ложен (применили теорему из лекции 15). Тождественная ложность предиката \(  \large A(x)  \), учитывая определение квантора существования, эквивалентна ложности высказывания \(  \large \exists x A(x)  \). Следовательно, ложность высказывания \(  \large \overline{\forall x \overline{A(x)}}  \) влечёт ложность высказывания \(  \large \exists x A(x)  \), и наоборот.

Итак, формулы равносильны.

Задача 19.4. Доказать, что формулы \(  \large \forall x P(x) \wedge \exists x Q(x)  \) и \(  \large \forall x (P(x) \vee \overline{Q(x)})   \) не являются равносильными.

Пусть \(  \large A(x)  \) и \(  \large B(x)  \) - некоторые предикаты, заданные на некотором множестве \(  \large M  \). Согласно определению, эти формулы не являются равносильными тогда и только тогда, когда предикаты \(  \large \forall x A(x) \wedge \exists x B(x)  \) и \(  \large \forall x (A(x) \vee \overline{B(x)})   \) не являются равносильными. Поскольку эти предикаты - высказывания, это означает, что их истинностные значения не совпадают.

Пусть высказывание \(  \large \forall x A(x) \wedge \exists x B(x)  \) ложно. Согласно определению конъюнкции, это высказывание ложно, если и только если высказывания \(  \large \forall x A(x)   \) и \(  \large \exists x B(x)  \) ложны. Используя определения кванторов, заключаем, что данное условие эквивалентно опровержимости предиката \(  \large A(x)  \) и тождественной ложности предиката \(  \large B(x)  \). Согласно теоремам из лекции 15, предикат \(  \large B(x)  \) тождественно ложен тогда и только тогда, когда предикат \(  \large \overline{B(x)}  \) тождественно истинен; если один из предикатов является тождественно истинным, то и их дизъюнкция - тождественно истинный предикат. Значит, дизъюнкция предикатов \(  \large A(x)  \) и \(  \large \overline{B(x)}  \) тождественно истинна. Это эквивалентно истинности
высказывания  \(  \large \forall x (A(x) \vee \overline{B(x)})  \). Следовательно, ложность высказывания \(  \large \forall x A(x) \wedge \exists x B(x)  \) влечёт истинность высказывания \(  \large \forall x (A(x) \vee \overline{B(x)})  \).

Итак, формулы не равносильны.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Сформулируем и докажем признак равносильности формул логики предикатов. Он полностью аналогичен соответствующей теореме классической логики высказываний. Вспомнив пропозициональный закон противоположности, сразу же получим необходимое и достаточное условие того, что формулы не являются равносильными. Кроме того, приведём формулировку и доказательство теоремы, которая служит основанием для равносильных преобразований формул логики предикатов.

***

Теорема 19.1. Формулы \(  \large F_1  \) и \(  \large F_2  \) равносильны, если и только если эквиваленция формул \(  \large F_1  \) и \(  \large F_2  \) общезначима.

Доказательство. 1) Пусть формулы логики предикатов \(  \large F_1  \) и \(  \large F_2  \), зависящие от предикатных переменных \(  \large P_1,P_2, \ldots, P_n  \), равносильны. Значит, согласно определению, для любых предикатов \(  \large A_1,A_2, \ldots, A_n  \) предикаты \(  \large F_1(A_1,A_2, \ldots, A_n)  \) и \(  \large F_2(A_1,A_2, \ldots, A_n)  \) равносильны. Следовательно, в силу признака равносильности предикатов, для любых предикатов \(  \large A_1,A_2, \ldots , A_n  \), предикат \(  \large F_1(A_1,A_2, \ldots, A_n) \leftrightarrow F_2(A_1,A_2, \ldots, A_n)  \) тождественно истинен. Тогда, в силу определения, формула \(  \large F_1 \leftrightarrow F_2  \) общезначима.

2) Пусть формула \(  \large F_1 \leftrightarrow F_2  \) общезначима (подформулы \(  \large F_1  \) и \(  \large F_2  \) зависят от предикатных переменных \(  \large P_1,P_2, \ldots, P_n  \)). Следовательно, по определению, предикат \(  \large F_1(A_1,A_2, \ldots, A_n) \leftrightarrow F_2(A_1,A_2, \ldots, A_n)  \) является тождественно истинным, какими бы ни были предикаты \(  \large A_1,A_2, \ldots, A_n  \). Тогда, используя признак равносильности предикатов, заключаем, что для любых предикатов \(  \large A_1,A_2, \ldots, A_n  \) предикаты \(  \large F_1(A_1,A_2, \ldots, A_n)  \) и \(  \large F_2(A_1,A_2, \ldots, A_n)  \) равносильны. Значит, согласно определению, формулы \(  \large F_1  \) и \(  \large F_2  \) равносильны. Теорема доказана.

Теорема 19.2. Формулы \(  \large F_1  \) и \(  \large F_2 \) не являются равносильными тогда и только тогда, когда эквиваленция формул \(  \large F_1  \) и \(  \large F_2  \) опровержима.

Доказательство. Если обозначить высказывание "формулы \(  \large F_1  \) и \(  \large F_2  \) равносильны" через \(  \large A  \), а высказывание "эквиваленция формул \(  \large F_1  \) и \(  \large F_2  \) общезначима" - через \(  \large B  \), то, используя закон противоположности, получим:

\(  \large A \leftrightarrow B \simeq \overline{A} \leftrightarrow \overline{B}  \).

Прочитаем: "Формулы \(  \large F_1  \) и \(  \large F_2 \) не являются равносильными, если и только если эквиваленция формул \(  \large F_1  \) и \(  \large F_2  \) не является общезначимой (является опровержимой)". Теорема доказана.

Теорема 19.3. Если в формуле логики предикатов некоторую её подформулу заменить на формулу, равносильную ей, то полученная формула будет равносильна исходной.

Доказательство. Пусть \(  \large F(P_1, P_2,  \ldots , P_n, G_1)  \) - некоторая формула логики предикатов, где \(  \large G_1(P_1,P_2, \ldots , P_n)  \) - подформула данной формулы, причём

\(  \large G_1 \simeq G_2  \).

Из последнего условия, согласно определению, заключаем, что предикаты \(  \large G_1(A_1,A_2, \ldots, A_n)  \) и \(  \large G_2(A_1,A_2, \ldots, A_n)  \) равносильны, какими бы ни были предикаты \(  \large A_1,A_2, \ldots, A_n  \). Значит, предикаты \(  \large F(A_1,A_2, \ldots, A_n, G_1)  \) и \(  \large F(A_1,A_2, \ldots, A_n, G_2)  \) равносильны для любых предикатов \(  \large A_1,A_2, \ldots, A_n  \). Следовательно,

\(  \large F(P_1, P_2,  \ldots , P_n, G_1)  \simeq F(P_1, P_2,  \ldots , P_n, G_2)    \).

Теорема доказана.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Учитывая теорему о предикатной подстановке в пропозициональную формулу, из любой равносильности логики высказываний можно получить сколь угодно много равносильностей логики предикатов. Например, из закона \(  \large P \to Q \simeq \overline{P} \vee Q  \) получим \(  \large P(x) \to Q(x) \simeq \overline{P(x)} \vee Q(x)  \), \(  \large P(x,y,z) \to Q(x) \simeq \overline{P(x,y,z)} \vee Q(x)  \), из \(  \large \overline{P} \vee P \simeq 1  \) - \(  \large \overline{P(x)} \vee P(x) \simeq 1  \), \(  \large \overline{\exists x P(x)} \vee \exists x P(x) \simeq 1  \).

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

***


1. Законы де Моргана для кванторов (законы отрицания кванторов)


Теорема 19.4. Закон отрицания квантора общности.

\(  \large \overline{\forall x_1 P(x_1,x_2, \ldots, x_n)}  \simeq \exists x_1 \overline{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_2 \in M_2, \ldots , a_n \in M_n  \) высказывания \(  \large \overline{\forall x_1 A(x_1,a_2, \ldots, a_n)}   \) и \(  \large  \exists x_1 \overline{A(x_1,a_2, \ldots, a_n)}  \) имеют одинаковые истинностные значения. Далее будем использовать определения кванторов и отрицания, а также теоремы из пятнадцатой лекции настоящего курса.

Пусть высказывание \(  \large \overline{\forall x_1 A(x_1,a_2, \ldots, a_n)}   \) истинно. Оно истинно тогда и только тогда, когда высказывание \(  \large \forall x_1 A(x_1,a_2, \ldots, a_n)   \) ложно. Это эквивалентно опровержимости предиката (от переменной \(  \large x_1  \)) \(  \large A(x_1,a_2, \ldots, a_n)   \). Это справедливо, в силу одной из теорем лекции 15 и закона двойного отрицания, если и только если предикат \(  \large \overline{ A(x_1,a_2, \ldots, a_n)}   \) выполним, что эквивалентно истинности высказывания \(  \large \exists x \overline{ A(x_1,a_2, \ldots, a_n)}   \).

Пусть высказывание \(  \large \overline{\forall x_1 A(x_1,a_2, \ldots, a_n)}   \) ложно. Данное высказывание ложно тогда и только тогда, когда высказывание \(  \large \forall x_1 A(x_1,a_2, \ldots, a_n)   \) истинно. Это эквивалентно тождественной истинности предиката (от переменной \(  \large x_1  \)) \(  \large A(x_1,a_2, \ldots, a_n)   \). Предикат \(  \large A(x_1,a_2, \ldots, a_n)   \) является тождественно истинным, если и только если предикат \(  \large \overline{ A(x_1,a_2, \ldots, a_n)}   \) является тождественно ложным (в силу одной из теорем лекции 15 и закона двойного отрицания). Это эквивалентно ложности высказывания \(  \large \exists x \overline{ A(x_1,a_2, \ldots, a_n)}   \). Теорема доказана.

Теорема 19.5. Закон отрицания квантора существования.

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

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

Сначала используем закон двойного отрицания:

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

После этого воспользуемся законом отрицания квантора общности:

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

Снимаем двойное отрицание:

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

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

Замечание 19.8. В лекции 17 было доказано, что для предикатов, определённых на конечных множествах квантор общности выражается через конъюнкцию, а квантор существования - через дизъюнкцию. Отметим, что универсальное высказывание \(  \large \forall x A(x)  \), где \(  \large x \in M  \), а множество \(  \large M  \) не обязательно конечно (и даже не обязательно счётно) можно понимать так: \(  \large A(a_1) \wedge A(a_2) \wedge \ldots \wedge A(a_n) \wedge \ldots  \) Иначе говоря, это конъюнкция бесконечного количества высказываний. Экзистенциальное высказывание \(  \large \exists x A(x)  \) можно понимать как дизъюнкцию бесконечного числа высказываний. Таки образом, квантор общности (существования) - обобщение конъюнкции (дизъюнкции). В случае с законами де Моргана аналогия продолжается: кванторные законы де Моргана - обобщения соответствующих пропозициональных законов.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

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


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

\(  \large \forall x_1 (P(x_1,x_2, \ldots, x_n ) \wedge Q(x_1,x_2, \ldots, x_n )) \simeq   \forall x_1 P(x_1,x_2, \ldots, x_n ) \wedge \forall 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 \forall x_1 (A(x_1,a_2, \ldots, a_n ) \wedge B(x_1,a_2, \ldots, a_n ))  \)

и

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

имеют одинаковые значения истинности, какими бы ни были \(  \large a_2 \in M_2, \ldots, a_n \in M_n  \). В ходе доказательства будем использовать определение квантора общности и конъюнкции, теоремы из лекции 15 настоящего курса.

Высказывание \(  \large \forall 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 \forall x_1 A(x_1,a_2, \ldots, a_n )  \) и \(  \large \forall x_1  B(x_1,a_2, \ldots, a_n )  \), что, в свою очередь, эквивалентно истинности их конъюнкции.

Высказывание \(  \large \forall 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 \forall x_1 A(x_1,a_2, \ldots, a_n )  \) и \(  \large \forall x_1  B(x_1,a_2, \ldots, a_n )  \). А это эквивалентно ложности их конъюнкции. Теорема доказана.

Замечание 19.9. Говорят, что квантор общности проносится через конъюнкцию.

Замечание 19.10. Квантор общности, вообще говоря, не проносится через дизъюнкцию. Докажем, что

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

Рассмотрим предикаты \(  \large x<0  \) и \(  \large x \ge 0  \), определённые на множестве вещественных чисел. Первый обозначим через \(  \large P(x)  \), а второй - через \(  \large Q(x)  \). Тогда высказывание \(  \large \forall x (P(x) \vee Q(x))  \) истинно (всякое вещественное число меньше нуля или не меньше нуля), а высказывание  \(  \large \forall x P(x) \vee  \forall x Q(x)  \) ложно, поскольку ложен каждый из членов дизъюнкции (неверно, что любое вещественное число меньше нуля, и неверно, что любое вещественное число не меньше нуля).

Однако есть исключение: данный квантор всё же проносится через дизъюнкцию, если один из членов дизъюнкции не зависит от предметной переменной, связанной квантором (в частности, один из членов дизъюнкции является пропозициональной переменной). Правда, при этом он не навешивается на член дизъюнкции, не зависящий от переменной, которая связана квантором (иначе будет противоречие с определением формулы логики предикатов). Данный факт для случая, когда \(  \large Q  \) является пропозициональной переменной, доказывается в следующей теореме.

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

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

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

1) Ложность высказывания \(  \large \forall x_1 (A(x_1,a_2, \ldots, a_n ) \vee B)  \) эквивалентна опровержимости предиката \(  \large A(x_1,a_2, \ldots, a_n ) \vee B  \). Данная дизъюнкция является опровержимым предикатов тогда и только тогда, когда оба её члена - опровержимые предикаты. Для нульместного предиката \(  \large B  \) это означает ложность. Опровержимость предиката \(  \large A(x_1,a_2, \ldots , a_n)  \) эквивалентна ложности высказывания \(  \large \forall x_1 A(x_1,a_2, \ldots , a_n)  \). Это высказывание и высказывание \(  \large B  \) принимают истинностное значение "ложь", если и только если ложно высказывание \(  \large \forall x_1 A(x_1,a_2, \ldots , a_n) \vee B  \). Итак, высказывание \(  \large \forall x_1 (A(x_1,a_2, \ldots, a_n ) \vee B)  \) ложно тогда и только тогда, когда ложно высказывание \(  \large \forall x_1 A(x_1,a_2, \ldots , a_n) \vee B  \).

2) Истинность высказывания \(  \large \forall x_1 A(x_1,a_2, \ldots , a_n) \vee B  \) эквивалентна истинности высказывания \(  \large \forall x_1 A(x_1,a_2, \ldots , a_n)  \) или истинности высказывания \(  \large B  \). Высказывание \(  \large \forall x_1 A(x_1,a_2, \ldots , a_n)  \) истинно или высказывание \(  \large B  \) истинно, если и только если предикат \(  \large A(x_1,a_2, \ldots , a_n)  \) тождественно истинен или предикат \(  \large B  \) тождественно истинен (данное высказывание истинно). Отсюда следует тождественная истинность предиката \(  \large A(x_1,a_2, \ldots, a_n ) \vee B  \), что эквивалентно истинности высказывания \(  \large \forall x_1 (A(x_1,a_2, \ldots, a_n ) \vee B)  \). Итак, высказывание \(  \large \forall x_1 A(x_1,a_2, \ldots , a_n) \vee B  \) истинно, если и только если истинно высказывание \(  \large \forall x_1 (A(x_1,a_2, \ldots, a_n ) \vee B)  \).

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

Замечание 19.11. Доказательство теоремы

\(  \large \forall x_1 (P(x_1,x_2, \ldots, x_n ) \vee Q(y_1,y_2, \ldots, y_m)) \simeq   \forall x_1 P(x_1,x_2, \ldots, x_n ) \vee Q (y_1,y_2, \ldots, y_m) \)

аналогично доказательству теоремы 19.7, поэтому мы его не приводим.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

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

\(  \large \exists x_1 (P(x_1,x_2, \ldots, x_n ) \vee Q(x_1,x_2, \ldots, x_n )) \simeq   \exists x_1 P(x_1,x_2, \ldots, x_n ) \vee \exists x_1 Q(x_1,x_2, \ldots, x_n )  \)

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

Сначала воспользуемся законом двойного отрицания:

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

Теперь применим закон отрицания квантора существования:

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

Воспользуемся одним из пропозициональных законов де Моргана:

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

Проносим квантор общности через конъюнкцию:

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

Снова используем пропозициональный закон де Моргана:

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

Применяем закон отрицания квантора общности:

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

Осталось воспользоваться законом двойного отрицания:

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

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

Замечание 19.12. Говорят, что квантор существования проносится через дизъюнкцию.

Замечание 19.13. Квантор существования не проносится через конъюнкцию. Докажем, что

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

Рассмотрим предикаты "\(  \large x   \) делится на \(  \large 7  \)" (\(  \large P(x)  \)) и "\(  \large x  \) не делится на \(  \large 7  \)" (\(  \large Q(x)  \)), которые определим на множестве натуральных чисел. Тогда высказывание \(  \large \exists x (P(x) \wedge Q(x))  \) ложно (нет натуральных чисел, одновременно делящихся на семь и не делящихся на семь), а высказывание \(  \large \exists x P(x)  \wedge \exists x Q(x) \) истинно, поскольку истинен каждый член конъюнкции (есть натуральные числа, которые делятся на семь, и есть натуральные числа, которые не делятся на семь).

Как и в случае с квантором общности, есть исключение: данный квантор дистрибутивен относительно конъюнкции, если один из её членов не зависит от предметной переменной, связанной квантором. Этот факт будет доказан ниже для случая, когда \(  \large Q  \) - пропозициональная переменная.

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

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

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

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

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

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

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

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

Далее применяем ранее доказанную теорему 19.7:

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

Снова прибегаем к помощи пропозиционального закона де Моргана:

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

Используя закон отрицания квантора общности и закон двойного отрицания, получим:

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

Теорема доказана.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

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


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

\(  \large \forall x_1 \forall x_2 P(x_1,x_2, \ldots, x_n) \simeq \forall x_2 \forall 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 \forall x_1 \forall x_2 A(x_1,x_2,a_3, \ldots, a_n)  \) и \(  \large \forall x_2 \forall x_1 A(x_1,x_2,a_3 \ldots, a_n)  \) имеют одинаковые истинностные значения, какими бы ни были \(  \large a_3 \in M_3, \ldots, a_n \in M_n  \). Далее будем использовать определение квантора общности.

1) Ложность высказывания \(  \large \forall x_1 \forall x_2 A(x_1,x_2,a_3, \ldots, a_n)  \) имеет место тогда и только тогда, когда предикат \(  \large A(x_1,x_2, a_3, \ldots, x_n)  \) (от переменных \(  \large x_1  \) и \(  \large x_2  \)) опровержим. Это эквивалентно опровержимости предиката \(  \large \forall x_1 A(x_1,x_2, a_3, \ldots, x_n)  \) (от переменной \(  \large x_2  \)). Предикат \(  \large \forall x_1 A(x_1,x_2, a_3, \ldots, x_n)  \) опровержим, если и только если высказывание \(  \large \forall x_2 \forall x_1 A(x_1,x_2, a_3, \ldots, x_n)  \) ложно.

2) Высказывание \(  \large \forall x_1 \forall x_2 A(x_1,x_2,a_3, \ldots, a_n)  \) истинно, если и только если предикат \(  \large A(x_1,x_2, a_3, \ldots, x_n)  \) (от переменных \(  \large x_1  \) и \(  \large x_2  \)) является тождественно истинным. Это эквивалентно тождественной истинности предиката \(  \large \forall x_1 A(x_1,x_2, a_3, \ldots, x_n)  \) (от переменной \(  \large x_2  \)). Предикат \(  \large \forall x_1 A(x_1,x_2, a_3, \ldots, x_n)  \) тождественно истинен тогда и только тогда, когда высказывание \(  \large \forall x_2 \forall x_1 A(x_1,x_2, a_3, \ldots, x_n)  \) принимает значение "истина".

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

Замечание 19.14. Учитывая правило подстановки и признак равносильности формул, любую предикатную переменную в равносильностях логики предикатов можно рассматривать как произвольную формулу с одним лишь условием: все предметные переменные, связанные в равносильности, свободны в подставляемой вместо предикатной переменной формуле. Например, из первого закона де Моргана для кванторов

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

получаем его обобщение

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

где \(  \large F  \) - произвольная формула логики предикатов, предикатные переменные которой зависят от предметных переменных \(  \large x_1,x_2, \ldots, x_n  \), причём предметная переменная \(  \large x_1  \) свободна. Данный факт используем для доказательства следующей теоремы.

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

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

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

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

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

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

Согласно определению равносильности формул логики предикатов, это означает, что каким бы ни был предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) (определённый на произвольных множествах), предикаты \(  \large \overline{\exists x_1 \exists x_2 A(x_1,x_2, \ldots, x_n) } \) и \(  \large \overline{\exists x_2 \exists x_1 A(x_1,x_2, \ldots, x_n)}  \) равносильны. Отсюда, используя определение равносильности предикатов и теоремы из лекции 17, выводим равносильность предикатов \(  \large \exists x_1 \exists x_2 A(x_1,x_2, \ldots, x_n)  \) и \(  \large \exists x_2 \exists x_1 A(x_1,x_2, \ldots, x_n)  \). Значит,

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

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

Замечание 19.15. Теоремы 19.10 и 19.11 означают, что одноимённые кванторы можно переставлять местами.

Замечание 19.16. Разноимённые кванторы не коммутативны. Докажем, что

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

Рассмотрим определённый на множестве натуральных чисел предикат \(  \large x<y   \), который обозначим через \(  \large P(x,y)  \). Тогда высказывание \(  \large \forall x \exists y (x<y)  \) (для любого натурального числа найдётся натуральное число, большее его) истинно, а высказывание \(  \large \exists y \forall x (x<y)  \) (существует такое натуральное число, что для любого натурального числа первое больше второго) ложно.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
В логике высказываний есть удобные виды формул, к которым их можно привести с помощью равносильных преобразований. Это ДНФ и КНФ. В логике предикатов тоже есть аналогичный вид формул. Им является предварённая нормальная форма.

***

Определение 19.3. Предварённой нормальной формой формулы логики предикатов называется формула вида

\(  \large Q_1 x_1 Q_2 x_2 \ldots Q_m x_m F(x_1,x_2, \ldots, x_n)  \),

где \(  \large Q_i, \ i =1,2, \ldots, m,  \) является квантором общности или квантором существования, \(  \large m \le n  \), \(  \large F  \) - формула, представленная в КНФ или ДНФ и не содержащая кванторов.

Замечание 19.17. КНФ и ДНФ есть формулы логики высказываний. Говоря о КНФ и ДНФ в рамках логики предикатов, мы подразумеваем то же самое, что и в логике высказываний, но вместо пропозициональных переменных используем предикатные переменные.

Замечание 19.18. Вместо словосочетания "предварённая нормальная форма" далее часто будем писать ПНФ.

Замечание 19.19. Иногда предварённая нормальная форма формулы логики предикатов называется префиксной нормальной формой, при этом выражение

\(  \large Q_1 x_1 Q_2 x_2 \ldots Q_m x_m  \)

именуют кванторным префиксом или кванторной приставкой.

Замечание 19.20. Предварённая нормальная форма может быть как замкнутой, так и открытой формулой.

Замечание 19.21. Кванторы в предварённой нормальной форме могут отсутствовать совсем.

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

Пример 19.1. ПНФ являются следующие формулы:

1) \(  \large \exists x_1 \forall x_2 ((\overline{P_1(x_1)} \vee P_2 (x_1,x_2)) \wedge \overline{P_3(x_1,x_3)})  \);

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

3) \(  \large P(x,y) \wedge ( \overline{Q(x,y,z)} \vee R(y,z))  \);

4) \(  \large \overline{P} \vee (P \wedge \overline{Q}) \vee (\overline{P} \wedge R)  \).

Пример 19.2. Представленные ниже формулы логики предикатов не являются ПНФ:

1) \(  \large \exists y \forall x (P(x,y,z) \vee \exists z Q(y,z))  \);

2) \(  \large \forall x_1 \overline{ \exists x_2 (P_1(x_1,x_2) \vee P_2(x_2,x_3))  } \);

3) \(  \large \exists z \forall y (\overline{P(x,y)} \to (Q(y,z,t) \vee R(x,z)))  \);

4) \(  \large \overline{P \vee (\overline{Q} \wedge \overline{R})}  \).

Первая формула не является ПНФ, так как область действия одного из кванторов не распространяется на всю формулу. Вторая формула не является ПНФ, поскольку отрицание стоит над квантором существования. Третья формула не является ПНФ, так как бескванторная часть данной формула не является ДНФ или КНФ (содержит импликацию). Наконец, четвёртая формула не является ПНФ, так как она не является КНФ или ДНФ.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Любую формулу логики предикатов можно представить в предварённой нормальной форме. Формулы бывают двух видов - бескванторные и содержащие кванторы. Чтобы привести бескванторную формулу к предварённой нормальной форме, достаточно привести её к КНФ или ДНФ. Рассмотрим второй случай. Пусть формула содержит кванторы. Во-первых, возможна ситуация, когда все кванторы уже стоят в начале формулы. Если бескванторная часть формулы представлена в КНФ или ДНФ, то имеем ПНФ. Если нет, то всегда можем привести к КНФ или ДНФ. Во-вторых, возможна ситуация, когда не все кванторы стоят в начале формулы. Тогда, выразив все логические операции через конъюнкцию, дизъюнкцию и отрицание, и пронеся кванторы через конъюнкцию и дизъюнкцию (при необходимости нужно переобозначить предметные переменные, связанные кванторами), получим ситуацию, когда все кванторы находятся в начале формулы. Отметим, что:

\(  \large \forall x (P(x) \wedge Q(y)) \simeq \forall x P(x) \wedge \forall x (Q(y) \wedge (R(x) \vee \overline{R(x)}) \simeq \forall x P(x) \wedge Q(y)  \)

\(  \large \exists x (P(x) \vee Q(y)) \simeq \exists x P(x) \vee \exists x (Q(y) \vee (R(x) \wedge \overline{R(x)}) \simeq \forall x P(x) \vee Q(y)  \).

Правда, здесь пропущены шаги преобразований, включающие \(  \large \forall x Q(y)  \) и \(  \large \exists x Q(y)  \), но это не формулы, согласно нашему же определению. Простим себе эту небольшую неточность. Если все кванторы стоят в начале формулы, то нам осталось привести бескванторную часть к КНФ или ДНФ.

Итак, предварённая нормальная форма существует, но не единственна, так как, во-первых, КНФ и ДНФ не единственны, во-вторых, кванторы можно вынести наружу в различном порядке. Рассмотрим две задачи (с переобозначением переменных и без него).

***

Задача 19.5. Привести к формулу

\(  \large \exists x (P_1(x) \to P_2(x)) \to (\exists x \overline{P_1(x)} \to \exists y P_2(y))  \)

к предварённой нормальной форме.

Сначала избавимся от внутренних импликаций:

\(  \large \exists x (P_1(x) \to P_2(x)) \to (\exists x \overline{P_1(x)} \to \exists y P_2(y))\simeq  \)

\(  \large \simeq \exists x (\overline{P_1(x)} \vee P_2(x)) \to ( \overline{\exists x \overline{P_1(x)}} \vee \exists y P_2(y))  \).

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

\(  \large  \exists x (\overline{P_1(x)} \vee P_2(x)) \to ( \overline{\exists x \overline{P_1(x)}} \vee \exists y P_2(y)) \simeq  \)

\(  \large \simeq \exists x (\overline{P_1(x)} \vee P_2(x)) \to ( \forall x P_1(x) \vee \exists y P_2(y))  \).

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

\(  \large \exists x (\overline{P_1(x)} \vee P_2(x)) \to ( \forall x P_1(x) \vee \exists y P_2(y)) \simeq  \)

\(  \large \simeq \overline{\exists x (\overline{P_1(x)} \vee P_2(x))} \vee ( \forall x P_1(x) \vee \exists y P_2(y))  \).

Снова воспользуемся законом отрицания квантора существования, а затем - одним из пропозициональных законов де Моргана и законом двойного отрицания:

\(  \large \overline{\exists x (\overline{P_1(x)} \vee P_2(x))} \vee ( \forall x P_1(x) \vee \exists y P_2(y)) \simeq  \)

\(  \large \simeq \forall x (P_1(x) \wedge  \overline{P_2(x)}) \vee ( \forall x P_1(x) \vee \exists y P_2(y))   \).

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

\(  \large \forall x (P_1(x) \wedge  \overline{P_2(x)}) \vee ( \forall x P_1(x) \vee \exists y P_2(y))  \simeq  \)

\(  \large \simeq (\forall x P_1(x) \wedge \forall x  \overline{P_2(x)}) \vee  \forall x P_1(x) \vee \exists y P_2(y)  \).

Формулу можно сократить, используя один из пропозициональных законов поглощения:

\(  \large (\forall x P_1(x) \wedge \forall x  \overline{P_2(x)}) \vee  \forall x P_1(x) \vee \exists y P_2(y)  \simeq \).

\(  \large \simeq  \forall x P_1(x) \vee \exists y P_2(y)  \).

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

\(  \large   \forall x P_1(x) \vee \exists y P_2(y) \simeq \forall x (P_1(x) \vee \exists y P_2(y)) \).

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

\(  \large  \forall x (P_1(x) \vee \exists y P_2(y)) \simeq \forall x \exists y (P_1(x) \vee P_2(y)) \).
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Задача 19.6. Задание то же:

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

Как и в предыдущей задаче, сначала избавимся от внутренних импликаций:

\(  \large \exists y (\overline{Q(y)} \to \overline{P(x)}) \to \forall y (\exists z \overline{Q(z)} \to P(y)) \simeq  \)

\(  \large \simeq \exists y (\overline{\overline{Q(y)}} \vee \overline{P(x)}) \to \forall y (\overline{\exists z \overline{Q(z)}} \vee P(y))  \).

Используем закон двойного отрицания и закон отрицания квантора существования:

\(  \large  \exists y (\overline{\overline{Q(y)}} \vee \overline{P(x)}) \to \forall y (\overline{\exists z \overline{Q(z)}} \vee P(y)) \simeq \)

\(  \large \simeq \exists y (Q(y) \vee \overline{P(x)}) \to \forall y (\forall z Q(z) \vee P(y))  \).

Выразим оставшуюся импликацию через дизъюнкцию и конъюнкцию:

\(  \large \exists y (Q(y) \vee \overline{P(x)}) \to \forall y (\forall z Q(z) \vee P(y)) \simeq  \)

\(  \large \simeq \overline{\exists y (Q(y) \vee \overline{P(x)})} \vee \forall y (\forall z Q(z) \vee P(y))  \).

Применим закон отрицания квантора существования, пропозициональный закон де Моргана и закон двойного отрицания:

\(  \large \overline{\exists y (Q(y) \vee \overline{P(x)})} \vee \forall y (\forall z Q(z) \vee P(y))  \simeq \)

\(  \large \simeq \forall y (\overline{Q(y)} \wedge P(x)) \vee \forall y (\forall z Q(z) \vee P(y))  \).

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

\(  \large  \forall y (\overline{Q(y)} \wedge P(x)) \vee \forall y (\forall z Q(z) \vee P(y)) \simeq \)

\(  \large \simeq \forall y (\overline{Q(y)} \wedge P(x)) \vee \forall t (\forall z Q(z) \vee P(t))  \).

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

\(  \large  \forall y (\overline{Q(y)} \wedge P(x)) \vee \forall t (\forall z Q(z) \vee P(t)) \simeq  \)

\(  \large \simeq \forall y ( (\overline{Q(y)} \wedge P(x)) \vee \forall t (\forall z Q(z) \vee P(t)))  \).

Затем проносим второй квантор:

\(  \large  \forall y ( (\overline{Q(y)} \wedge P(x)) \vee \forall t (\forall z Q(z) \vee P(t))) \simeq \)

\(  \large \simeq \forall y \forall t  ( (\overline{Q(y)} \wedge P(x)) \vee \forall z Q(z) \vee P(t))  \).

Наконец, проносим через дизъюнкцию третий квантор:

\(  \large \forall y \forall t  ( (\overline{Q(y)} \wedge P(x)) \vee \forall z Q(z) \vee P(t)) \simeq  \)

\(  \large \simeq \forall y \forall t \forall z  ( (\overline{Q(y)} \wedge P(x)) \vee  Q(z) \vee P(t))  \).
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

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

***

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

\(  \large \overline{\exists x_2 \exists x_1 P(x_1,x_2, x_3)} \to \exists x_2 ( \forall x_1 \overline{P(x_1,x_2, x_3)} \to \forall x_3 Q(x_2,x_3))  \)

и

\(  \large \exists x_2 ( \exists x_3 \overline{Q(x_2,x_3)} \to \exists x_1 P(x_1,x_2, x_3))  \)

равносильны, используя основные законы логики.

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

\(  \large \overline{\exists x_2 \exists x_1 P(x_1,x_2, x_3)} \to \exists x_2 ( \forall x_1 \overline{P(x_1,x_2, x_3)} \to \forall x_3 Q(x_2,x_3)) \simeq   \)

\(  \large \simeq \overline{ \overline{\exists x_2 \exists x_1 P(x_1,x_2, x_3)}} \vee \exists x_2 ( \overline{\forall x_1 \overline{P(x_1,x_2, x_3)} } \vee \forall x_3 Q(x_2,x_3))  \).

Снимаем двойное отрицание:

\(  \large \overline{ \overline{\exists x_2 \exists x_1 P(x_1,x_2, x_3)}} \vee \exists x_2 ( \overline{\forall x_1 \overline{P(x_1,x_2, x_3)} } \vee \forall x_3 Q(x_2,x_3)) \simeq    \)


\(  \large \simeq \exists x_2 \exists x_1 P(x_1,x_2, x_3) \vee \exists x_2 ( \overline{\forall x_1 \overline{P(x_1,x_2, x_3)} } \vee \forall x_3 Q(x_2,x_3))  \).

Используем закон отрицания квантора общности, а заодно снимаем появившееся в результате применения этого закона двойное отрицание:

\(  \large \exists x_2 \exists x_1 P(x_1,x_2, x_3) \vee \exists x_2 ( \overline{\forall x_1 \overline{P(x_1,x_2, x_3)} } \vee \forall x_3 Q(x_2,x_3)) \simeq  \)

\(  \large \simeq \exists x_2 \exists x_1 P(x_1,x_2, x_3) \vee \exists x_2 (\exists x_1 P(x_1,x_2, x_3) \vee \forall x_3 Q(x_2,x_3))  \).

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

\(  \large  \exists x_2 \exists x_1 P(x_1,x_2, x_3) \vee \exists x_2 (\exists x_1 P(x_1,x_2, x_3) \vee \forall x_3 Q(x_2,x_3)) \simeq  \)

\(  \large \simeq \exists x_2 \exists x_1 P(x_1,x_2, x_3) \vee \exists x_2 \exists x_1 P(x_1,x_2, x_3) \vee \exists x_2 \forall x_3 Q(x_2,x_3)  \).

Вычёркиваем один из повторяющихся членов дизъюнкции, зная, что данная пропозициональная связка идемпотетна:

\(  \large  \exists x_2 \exists x_1 P(x_1,x_2, x_3) \vee \exists x_2 \exists x_1 P(x_1,x_2, x_3) \vee \exists x_2 \forall x_3 Q(x_2,x_3) \simeq  \)

\(  \large \simeq \exists x_2 \exists x_1 P(x_1,x_2, x_3) \vee \exists x_2 \forall x_3 Q(x_2,x_3)  \).

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

\(  \large \exists x_2 \exists x_1 P(x_1,x_2, x_3) \vee \exists x_2 \forall x_3 Q(x_2,x_3)  \simeq \)

\(  \large \simeq \exists x_2 (\forall x_3 Q(x_2,x_3) \vee \exists x_1 P(x_1,x_2, x_3))  \).

Навешиваем двойное отрицание:

\(  \large  \exists x_2 (\forall x_3 Q(x_2,x_3) \vee \exists x_1 P(x_1,x_2, x_3))  \simeq  \)

\(  \large \simeq \exists x_2 (\overline{ \overline{\forall x_3 Q(x_2,x_3) }} \vee \exists x_1 P(x_1,x_2, x_3))  \).

Воспользуемся равносильностью \(  \large \overline{P} \vee Q \simeq P \to Q  \):

\(  \large  \exists x_2 ( \overline{ \overline{\forall x_3 Q(x_2,x_3) }} \vee \exists x_1 P(x_1,x_2, x_3)) \simeq   \)

\(  \large \simeq \exists x_2 ( \overline{\forall x_3 Q(x_2,x_3) } \to \exists x_1 P(x_1,x_2, x_3))  \).

Наконец, воспользуемся законом отрицания квантора общности:

\(  \large  \exists x_2 ( \overline{\forall x_3 Q(x_2,x_3) } \to \exists x_1 P(x_1,x_2, x_3))  \simeq  \)

\(  \large \simeq \exists x_2 ( \exists x_3 \overline{Q(x_2,x_3) } \to \exists x_1 P(x_1,x_2, x_3))  \).

Итак, преобразовав равносильным образом первую формулу, мы получили вторую формулу. Следовательно, эти формулы равносильны.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

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

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

и

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

не равносильны, используя основные законы логики.

Упростим первую формулу. Избавимся от импликации:

\(  \large \exists x \forall y \overline{P(x,y)}  \to (\exists x Q(x) \wedge \forall x \exists y P(x,y)) \simeq  \)

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

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

\(  \large  \overline{\exists x \forall y \overline{P(x,y)}}  \vee (\exists x Q(x) \wedge \forall x \exists y P(x,y)) \simeq  \)

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

Применим один из законов поглощения:

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

Займёмся упрощением второй формулы. Выразим импликацию через дизъюнкцию и отрицание, получившееся двойное отрицание снимаем, используя соответствующий закон логики:

\(  \large \exists y ( \overline{\forall x P(x,y)} \to \overline{\exists x \overline{P(x,y)}}) \simeq  \)

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

Применим законы отрицания квантора существования и двойного отрицания:

\(  \large \exists y (\forall x P(x,y) \vee \overline{\exists x \overline{P(x,y)}}) \simeq  \)

\(  \large \simeq \exists y ( \forall x P(x,y) \vee \forall x P(x,y))  \).

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

\(  \large \simeq \exists y ( \forall x P(x,y) \vee \forall x P(x,y)) \simeq \exists y \forall x P(x,y)  \).

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 19. Равносильность формул логики предикатов
« Ответ #13 : Декабрь 11, 2017, 12:41:42 pm »
Задача 19.9. Записать отрицание определения простого числа, используя символику логики предикатов и основные законы логики.

Решение. Как известно, натуральное число называется простым, если оно не равно единице и делится только на самого себя и единицу. Прежде чем переходить к формализации данного определения, уясним, что значит слово "делится". Согласно определению, число \(  \large x  \) делится на число \(  \large y  \), если существует такое число \(  \large z  \), что \(  \large x=yz  \). Следовательно, число \(  \large x  \) называется простым, если оно не равно единице и каким бы ни было число \(  \large y  \), если найдётся такое число \(  \large z  \), что \(  \large x=yz  \), то число \(  \large y  \) равно числу \(  \large x  \) или число \(  \large y  \) равно единице. Тогда имеем такую символическую запись данного определения:

\(  \large \overline{ x  = 1} \wedge \forall y ( \exists z (x=yz) \to (y=x \vee y=1))  \).

Построим отрицание данного определения. Сначала используем один из пропозициональных законов де Моргана:

\(  \large \overline{ \overline{x = 1} \wedge \forall y ( \exists z (x=yz) \to (y=x \vee y=1))} \Leftrightarrow  \)

\(  \large \Leftrightarrow \overline{\overline{x =1}} \vee \overline{ \forall y ( \exists z (x=yz) \to (y=x \vee y=1)) }  \).

Далее применим два закона логики - закон двойного отрицания и закон отрицания квантора общности:

\(  \large \overline{\overline{x =1}} \vee \overline{ \forall y ( \exists z (x=yz) \to (y=x \vee y=1)) }  \Leftrightarrow  \)

\(  \large \Leftrightarrow x =1 \vee \exists y (  \overline{\exists z (x=yz) \to (y=x \vee y=1)})    \).

Займёмся равносильными преобразованиями выражения, стоящего под знаком отрицания. Выразим импликацию через дизъюнкцию и отрицание, а затем воспользуемся законом отрицания квантора существования. Имеем:

\(  \large  x =1 \vee \exists y (  \overline{\exists z (x=yz) \to (y=x \vee y=1)}) \Leftrightarrow   \)

\(  \large \Leftrightarrow x =1 \vee \exists y (  \overline{\forall z (\overline{x=yz}) \vee y=x \vee y=1})    \).

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

\(  \large  x =1 \vee \exists y (  \overline{\forall z (\overline{x=yz}) \vee y=x \vee y=1}) \Leftrightarrow   \)

\(  \large \Leftrightarrow x =1 \vee \exists y ( \exists z (\overline{\overline{x=yz}}) \wedge \overline{y=x} \wedge \overline{y=1})    \).

Завершаем равносильные преобразования, применяя закон двойного отрицания и пронося квантор существования через конъюнкцию:

\(  \large x =1 \vee \exists y ( \exists z (\overline{\overline{x=yz}}) \wedge \overline{y=x} \wedge \overline{y=1}) \Leftrightarrow    \)

\(  \large \Leftrightarrow x =1 \vee \exists y  \exists z (x=yz \wedge y \not =x \wedge y \not =1)    \).

Итак, натуральное число \(  \large x  \) не является простым, если оно равно единице или существуют такие натуральные числа \(  \large y  \) и \(  \large z  \), что \(  \large x=yz  \), \(  \large y \not = x  \) и \(  \large y \not = 1  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 19. Равносильность формул логики предикатов
« Ответ #14 : Декабрь 11, 2017, 12:42:26 pm »
Задача 19.10. Дано высказывание "Некоторые жители Бельгии владеют французским и фламандским языками, или ни один житель этой страны не владеет арабским языком". Записать отрицание данного высказывания, используя символический язык логики предикатов и основные законы логики.

Решение. Введём предикаты, определённые на множестве жителей Бельгии: \(  \large A(x)  \), \(  \large B(x)  \) и \(  \large C(x)  \). Первый обозначает "\(  \large x  \) владеет французским языком", второй - "\(  \large x  \) владеет фламандским языком", третий - "\(  \large x  \) владеет арабским языком". Переформулируем исходное высказывание: "Некоторые жители Бельгии владеют французским и фламандским языками, или неверно, что некоторые жители Бельгии владеют арабским языком". Переходим к формализации:

\(  \large \exists x (A(x) \wedge B(x)) \vee \overline{ \exists x C(x)}  \).

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

\(  \large \overline{ \exists x (A(x) \wedge B(x)) \vee \overline{ \exists x C(x)}} \Leftrightarrow   \)

\(  \large \Leftrightarrow \overline{\exists x (A(x) \wedge B(x)) } \wedge \overline{ \overline{ \exists x C(x)}}  \).

Применим закон отрицания квантора существования и закон двойного отрицания:

\(  \large \overline{\exists x (A(x) \wedge B(x)) } \wedge \overline{ \overline{ \exists x C(x)}} \Leftrightarrow  \)

\(  \large \Leftrightarrow \forall x ( \overline{ A(x) \wedge B(x) }) \wedge  \exists x C(x)  \).

Снова используем пропозициональный закон де Моргана:

\(  \large \forall x ( \overline{ A(x) \wedge B(x) }) \wedge  \exists x C(x) \Leftrightarrow  \)

\(  \large \Leftrightarrow \forall x ( \overline{ A(x)} \vee \overline{B(x) }) \wedge  \exists x C(x)  \).

Итак, отрицанием исходного высказывания является следующее высказывание: "Любой житель Бельгии не владеет французским языком или не владеет фламандским языком, и существуют жители этой страны, владеющие арабским языком.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 19. Равносильность формул логики предикатов
« Ответ #15 : Декабрь 11, 2017, 12:42:48 pm »
Задача 19.11. Записать на языке логики предикатов высказывание "Любые две прямые, параллельные третьей, параллельны между собой". Построить его отрицание.

Решение. Предварительно представим высказывание в виде "Для любых трёх прямых если первая параллельна третьей и вторая параллельна третьей, то первая параллельна второй". Пусть \(  \large P(x,y)  \) - предикат, определённый на множестве прямых, который означает "\(  \large x  \) параллельна \(  \large y  \)". Тогда высказывание можно записать следующим образом:

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

Построим отрицание:

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

Упростим полученную формулу. Для этого последовательно используем закон отрицания квантора общности, равносильность \(  \large P \to Q \simeq \overline{P} \vee Q  \), пропозициональный закон отрицания дизъюнкции и закон двойного отрицания. Получим:

\(  \large \exists x \exists y \exists z (P(x,z) \wedge P(y,z) \wedge \overline{P(x,y)})  \).

Прочитаем: "Существуют такие три прямые, что первая параллельна третьей, вторая параллельна третьей и первая не параллельна второй".
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 19. Равносильность формул логики предикатов
« Ответ #16 : Декабрь 11, 2017, 12:43:18 pm »
Задача 19.12. Записать высказывание в виде формулы логики предикатов: "Не всякий хорошо сдавший экзамен, списывал, и не каждый, кто списывал, хорошо сдал экзамен". Построить отрицание данного высказывания.

Решение. Переформулируем высказывание: "Неверно, что, каким бы ни был человек, если он хорошо сдал экзамен, то он списывал, и неверно, что, каким бы ни был человек, если он списывал, то он хорошо сдал экзамен". Введём следующие предикаты, определённые на множестве всех людей: \(  \large P(x)  \) - "\(  \large x  \) хорошо сдал экзамен", \(  \large Q(x)  \) - "\(  \large x  \) списывал". Запишем высказывание в виде формулы логики предикатов:

\(  \large \overline{ \forall x (P(x) \to Q(x)) } \wedge \overline{\forall x (Q(x) \to P(x))} \).

Запишем отрицание:

\(  \large \overline{ \overline{ \forall x (P(x) \to Q(x)) } \wedge \overline{\forall x (Q(x) \to P(x))}} \).

Упростим отрицание высказывания, используя закон отрицания конъюнкции и закон двойного отрицания:

\(  \large \forall x (P(x) \to Q(x)) \vee \forall x (Q(x) \to P(x))  \).

Переведём на естественный язык: "Любой, кто хорошо сдал экзамен, списывал, или любой, кто списывал, хорошо сдал экзамен".
 

Оффлайн Admin

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

\(  \large (\overline{ (x <2 )} \wedge (y>1)) \to (( x \ge 0) \wedge (x <y))  \).

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

\(  \large P \to Q \simeq \overline{P} \vee Q \),

то

\(  \large (\overline{ (x <2 )} \wedge (y>1)) \to (( x \ge 0) \wedge (x <y)) \Leftrightarrow (\overline{\overline{ (x <2 )} \wedge (y>1)}) \vee (( x \ge 0) \wedge (x <y))   \).

Так как

\(  \large \overline{P \wedge Q} \simeq \overline{P} \wedge \overline{Q}, \ \overline{\overline{P}} \simeq P  \),

то

\(  \large (\overline{\overline{ (x <2 )} \wedge (y>1)}) \vee (( x \ge 0) \wedge (x <y)) \Leftrightarrow (x <2 ) \vee (\overline{y>1})\vee (( x \ge 0) \wedge (x <y))  \).

Отрицанием неравенства \(  \large y>1  \) является неравенство \(  \large y \le 1  \). Значит,

\(  \large (x <2 ) \vee (\overline{y>1})\vee (( x \ge 0) \wedge (x <y))  \Leftrightarrow (x <2 ) \vee (y \le 1) \vee (( x \ge 0) \wedge (x <y))  \).

Поскольку множеством истинности предиката \(  \large P_1 \wedge P_2  \) (\(  \large P_1 \vee P_2  \)) является пересечение (объединение) множеств истинности предикатов \(  \large P_1  \) и \(  \large P_2  \), то задача заключается в следующем:

1) найти множества истинности предикатов \(  \large x<2  \), \(  \large y \le 1  \), \(  \large x \ge 0  \) и \(  \large x<y  \);

2) найти объединение множеств истинности предикатов \(  \large x<2  \) и \(  \large y \le 1  \);

3) найти пересечение множеств истинности предикатов \(  \large x \ge 0  \) и \(  \large x<y  \);

4) найти объединение множеств истинности предикатов \(  \large x<2 \vee y \le 1  \) и \(  \large  x \ge 0 \wedge x<y  \).

Выясним, какие множества задаются неравенствами. Неравенство \(  \large x<2  \) задаёт область плоскости, расположенную левее прямой \(  \large x=2  \), исключаю саму эту прямую. Неравенство \(  \large y \le 1  \) определяет часть плоскости, которая расположена ниже прямой \(  \large y=1  \), включая прямую \(  \large y=1  \). Неравенством \(  \large x \ge 0  \) задаётся множество точек плоскости, которые расположены правее оси ординат, включая ось ординат. Наконец, неравенство \(  \large x<y  \) определяет множество точек, расположенных строго выше биссектрисы первого и третьего координатных углов. Множество истинности предиката \(  \large x<2 \vee y \le 1  \) изображено на рисунке 1, множество истинности предиката \(  \large  x \ge 0 \wedge x<y  \) - на рисунке 2, а множество истинности предиката  \(  \large (\overline{ (x <2 )} \wedge (y>1)) \to (( x \ge 0) \wedge (x <y))  \) - на рисунке 3.

Таким образом, множеством истинности исходного предикат является вся плоскость, исключая область, ограниченную слева прямой \(  \large x=2  \) (эта прямая тоже не входит в множество истинности), сверху - прямой \(  \large y=x  \) (данная прямая  не входит в множество истинности), снизу - прямой \(  \large y=1  \) (прямая \(  \large y=1  \) входит в множество истинности).