Автор Тема: Лекция 15. Предикаты и логические связки  (Прочитано 984 раз)

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

Оффлайн Admin

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


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

***

Определение 15.1. Отрицанием предиката \(  \large A(x_1,x_2, \ldots, x_n)  \), определённого на множествах \(  \large M_i, \ i=1,2, \ldots, n  \), называется такой предикат \(  \large B(x_1,x_2, \ldots, x_n)  \), определённый на множествах \(  \large M_i, \ i=1,2, \ldots, n  \), что для любых предметных постоянных \(  \large a_i, \ i=1,2, \ldots, n  \), высказывание \(  \large B(a_1,a_2, \ldots, a_n)  \) является отрицанием высказывания \(  \large A(a_1,a_2, \ldots, a_n)  \).

Пример 15.1. Отрицанием одноместного предиката "\(  \large x  \) делится на \(  \large 5  \)", определённого на множестве целых чисел, является одноместный предикат "\(  \large x  \) не делится на \(  \large 5  \)", который определён на том же множестве.

***

Как связаны множества истинности предиката и его отрицания? Как связаны тип предиката и тип его отрицания? Ответы на эти вопросы дают следующие три теоремы.

***

Пусть \(  \large A(x_1,x_2, \ldots, x_n)  \) - предикат, определённый на множествах \(  \large M_i, \ i=1,2, \ldots, n  \).

Теорема 15.1. Множество истинности предиката \(  \large \overline{A(x_1,x_2, \ldots, x_n)}  \) равно дополнению множества истинности предиката \(  \large A(x_1,x_2, \ldots, x_n)  \).

Доказательство. Пусть \(  \large \mathcal{A} \subseteq M_1 \times M_2 \times \ldots \times M_n  \) - множество истинности предиката \(  \large A(x_1,x_2, \ldots, x_n)  \). Согласно определению, множество \(  \large \mathcal{A}  \) состоит из всех таких упорядоченных наборов \(  \large (a_1,a_2, \ldots, a_n)  \), где \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \), что высказывание \(  \large A(a_1,a_2, \ldots, a_n)  \) истинно. Пусть \(  \large \mathcal{B}  \) - множество истинности предиката \(  \large \overline{A(x_1,x_2, \ldots, x_n)}  \). Оно состоит из всех таких упорядоченных наборов, \(  \large (a_1,a_2, \ldots, a_n)  \), где \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \), что высказывание \(  \large \overline{A(a_1,a_2, \ldots, a_n)}  \) истинно. Иначе говоря, эти наборы таковы, что высказывание \(  \large A(a_1,a_2, \ldots, a_n)  \) ложно. Значит, множество \(  \large \mathcal{B}  \) состоит из тех упорядоченных наборов, что не принадлежат множеству \(  \large \mathcal{A}  \). Это, согласно по определению дополнения множества, и означает, что \(  \large \mathcal{B}= \overline{\mathcal{A}}  \). Теорема доказана.

Замечание 15.1. Здесь универсальным множеством является декартово произведение множеств \(  \large M_1, M_2, \ldots , M_n  \):

\(  \large \overline{\mathcal{A} }= (M_1 \times M_2 \times \ldots \times M_n) \setminus \mathcal{A}  \).

Теорема 15.2. Отрицание предиката \(  \large A(x_1,x_2, \ldots, x_n)  \) является тождественно истинным предикатом тогда и только тогда, когда предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) является тождественно ложным.

Доказательство. В силу теоремы 15.1, множество истинности предиката \(  \large \overline{A(x_1,x_2, \ldots, x_n)}  \) равно \(  \large \overline{\mathcal{A}}  \).

1) Пусть отрицание предиката \(  \large A(x_1,x_2, \ldots, x_n)  \) является тождественно истинным предикатом. Значит, \(  \large \overline{ \mathcal{A}}=M_1 \times M_2 \times \ldots \times M_n  \). Тогда

\(  \large \mathcal{A} = \overline{ \overline{ \mathcal{A}}}= \overline{M_1 \times M_2 \times \ldots \times M_n} = \not \circ \).

Мы последовательно использовали теоретико-множественный закон инволюции и тот факт, что дополнением универсального множества \(  \large M_1 \times M_2 \times \ldots \times M_n  \) является пустое множество. Итак, множество истинности предиката \(  \large A(x_1,x_2, \ldots, x_n)  \) пусто. Значит, этот предикат тождественно ложен.

2) Пусть предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) является тождественно ложным. Следовательно, \(  \large \mathcal{A}=\not \circ  \). Тогда, используя тот факт, что дополнением пустого множества является множество универсальное, получим:

\(  \large \overline{\mathcal{A}}= \overline{ \not \circ}= M_1 \times M_2 \times \ldots \times M_n  \).

Итак, универсальное множество является множеством истинности предиката \(  \large \overline{A(x_1,x_2, \ldots, x_n)}  \). Значит, данный предикат тождественно истинен. Теорема доказана.

Теорема 15.3. Отрицание предиката \(  \large A(x_1,x_2, \ldots, x_n)  \) является опровержимым предикатом тогда и только тогда, когда предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) является выполнимым.

Доказательство. Вспомним формулировку предыдущей теоремы и закон противоположности:

\(  \large P \leftrightarrow Q \simeq \overline{P} \leftrightarrow \overline{Q}  \).

Получим: отрицание предиката \(  \large A(x_1,x_2, \ldots, x_n)  \) не является тождественно истинным предикатом тогда и только тогда, когда предикат \(  \large A(x_1,x_2, \ldots, x_n)  \)  не является тождественно ложным. Иначе: отрицание предиката \(  \large A(x_1,x_2, \ldots, x_n)  \) - опровержимый предикат, если и только если предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) выполним. Теорема доказана.

***

Таким образом, из одной теоремы логики предикатов, используя теорему логики высказываний, получили другую (хотя и эквивалентную исходной) теорему логики предикатов. Этот способ уже использовался при изложении логики высказываний. Он будет неоднократно использоваться и при изложении логики предикатов.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 15. Предикаты и логические связки
« Ответ #1 : Апрель 06, 2017, 02:01:36 pm »
Определение 15.2. Конъюнкцией предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(y_1,y_2, \ldots, y_m)  \), определённых на множествах \(  \large M_i, \ i=1,2, \ldots, n  \) и \(  \large N_j, \ j=1,2, \ldots, m  \) соответственно, называется такой предикат \(  \large C(x_1,x_2, \ldots, x_n, y_1,y_2, \ldots, y_m)  \), определённый на множествах \(  \large M_1,M_2, \ldots, M_n, N_1, N_2, \ldots, N_m  \), что для любых предметных постоянных \(  \large a_i, \ i=1,2, \ldots, n  \), \(  \large b_j, \ j=1,2, \ldots, m  \), высказывание \(  \large C(a_1,a_2, \ldots , a_n ,b_1,b_2, \ldots ,b_m)  \) является конъюнкцией высказываний \(  \large A(a_1,a_2, \ldots, a_n)  \) и \(  \large B(b_1, b_2, \ldots, b_m)  \).

Пример 15.2. Конъюнкцией одноместных предикатов \(  \large x> 5  \) и \(  \large y<1  \), которые заданы на множестве вещественных чисел, является определённый на множестве вещественных чисел предикат \(  \large x> 5 \wedge y<1  \).

Замечание 15.2. Если предикаты \(  \large A(x_1,x_2, \ldots, x_n) \) и \(  \large B(x_1,x_2, \ldots, x_n)  \) являются уравнениями или неравенствами, то их конъюнкция записывается так:

\(  \large \begin{cases} A(x_1,x_2, \ldots, x_n) \\ B(x_1,x_2, \ldots, x_n)  \end{cases} \).

Читается: конъюнктивная система или просто система (уравнений, неравенств).

***

Сформулируем и докажем теоремы о связи множеств истинности некоторых предикатов и множества истинности конъюнкции этих предикатов, а также теоремы о связи типов этих предикатов и типа их конъюнкции.

***

Теорема 15.4. Множество истинности конъюнкции предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(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 \mathcal{A}  \) и \(  \large \mathcal{B}  \) - множества истинности предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(x_1,x_2, \ldots, x_n)  \) соответственно. Согласно определению, первое состоит из таких наборов \(  \large (a_1,a_2, \ldots, a_n)  \), что высказывание \(  \large A(a_1,a_2, \ldots, a_n)  \) истинно, а второе - из таких наборов \(  \large (a_1,a_2, \ldots, a_n)  \), что высказывание \(  \large B(a_1,a_2, \ldots, a_n)  \) истинно (здесь \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \)). Пусть \(  \large \mathcal{K}  \) - множество истинности предиката \(  \large A(x_1,x_2, \ldots, x_n) \wedge B(x_1,x_2, \ldots, x_n)  \). Оно включает в себя только такие наборы \(  \large (a_1,a_2, \ldots, a_n)  \), что высказывание \(  \large A(a_1,a_2, \ldots, a_n) \wedge B(a_1,a_2, \ldots, a_n)  \) истинно. Тогда, в силу определения конъюнкции, это такие наборы, что высказывание \(  \large A(a_1,a_2, \ldots, a_n)  \) истинно и высказывание \(  \large B(a_1,a_2, \ldots, a_n)  \) истинно. Учитывая определение пересечения множеств, это и означает, что \(  \large \mathcal{K}= \mathcal{A} \cap \mathcal{B}  \). Теорема доказана.
 
Теорема 15.5. Конъюнкция предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(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 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 \mathcal{A}  \) и \(  \large \mathcal{B}  \) - множества истинности этих предикатов. В силу теоремы 15.4, множество истинности конъюнкции этих предикатов равно \(  \large \mathcal{A} \cap \mathcal{B}  \).

1) Пусть предикат \(  \large A(x_1,x_2, \ldots , x_n) \wedge B(x_1, x_2, \ldots, x_n) \) является тождественно истинным. Значит, \(  \large \mathcal{A} \cap \mathcal{B} =M_1 \times M_2 \times \ldots \times M_n \). Предположим, что предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) опровержим или предикат \(  \large B(x_1,x_2, \ldots, x_n)  \) опровержим. Иначе говоря, предположим, что \(  \large \mathcal{A} \not = M_1 \times M_2 \times \ldots \times M_n  \) или \(  \large \mathcal{B} \not = M_1 \times M_2 \times \ldots \times M_n  \). Дизъюнкция истинна тогда и только тогда, когда истинен хотя бы один из её членов. Рассмотрим все три случая. При этом будем держать в уме, что \(  \large M_1 \times M_2 \times \ldots \times M_n  \) - универсальное множество.

а) Пусть \(  \large \mathcal{A} \not = M_1 \times M_2 \times \ldots \times M_n  \), \(  \large \mathcal{B} = M_1 \times M_2 \times \ldots \times M_n  \). Значит,

\(  \large \mathcal{A} \cap \mathcal{B} = \mathcal{A} \cap M_1 \times M_2 \times \ldots \times M_n= \mathcal{A}  \).

Но, согласно условию теоремы, \(  \large \mathcal{A} \cap \mathcal{B} =M_1 \times M_2 \times \ldots \times M_n \). Следовательно, \(  \large \mathcal{A} =M_1 \times M_2 \times \ldots \times M_n \). Но \(  \large \mathcal{A} \not = M_1 \times M_2 \times \ldots \times M_n  \). Противоречие.

б) Пусть \(  \large \mathcal{A}  = M_1 \times M_2 \times \ldots \times M_n  \), \(  \large \mathcal{B} \not = M_1 \times M_2 \times \ldots \times M_n  \). В данном случае противоречие получаем точно так же, как и в предыдущем случае.

в) Пусть \(  \large \mathcal{A}  \not = M_1 \times M_2 \times \ldots \times M_n  \), \(  \large \mathcal{B} \not = M_1 \times M_2 \times \ldots \times M_n  \). Чтобы понять, что это несовместимо с \(  \large \mathcal{A} \cap \mathcal{B} =M_1 \times M_2 \times \ldots \times M_n \), достаточно воспользоваться диаграммами Эйлера-Венна.

Итак, если  \(  \large \mathcal{A} \cap \mathcal{B} =M_1 \times M_2 \times \ldots \times M_n \), то \(  \large \mathcal{A} = M_1 \times M_2 \times \ldots \times M_n  \) и \(  \large \mathcal{B} = M_1 \times M_2 \times \ldots \times M_n  \). Значит, если предикат \(  \large A(x_1,x_2, \ldots, x_n) \wedge B(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)  \) тождественно истинны.

2) Пусть предикаты \(  \large A(x_1,x_2, \ldots , x_n) \) и \(  \large  B(x_1, x_2, \ldots, x_n)  \) тождественно истинны. Следовательно, \(  \large \mathcal{A} =M_1 \times M_2 \times \ldots \times M_n \) и  \(  \large  \mathcal{B} =M_1 \times M_2 \times \ldots \times M_n \). Тогда, используя идемпотентность пересечения, получим:

\(  \large \mathcal{A} \cap \mathcal{B}=  M_1 \times M_2 \times \ldots \times M_n \cap M_1 \times M_2 \times \ldots \times M_n=M_1 \times M_2 \times \ldots \times M_n \).

Значит, предикат \(  \large A(x_1,x_2, \ldots, x_n) \wedge B(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)  \) тождественно истинны, то их конъюнкция тождественно истинна. Теорема доказана.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 15. Предикаты и логические связки
« Ответ #2 : Апрель 06, 2017, 11:15:05 pm »
Теорема 15.6. Конъюнкция предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(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 P  \) - "конъюнкция предикатов \(  \large A  \) и \(  \large B  \) - тождественно истинный предикат", \(  \large Q  \) - "\(  \large A  \) - тождественно истинный предикат", \(  \large R  \) - "\(  \large B  \) - тождественно истинный предикат". Тогда формула логики высказываний \(  \large P \leftrightarrow (Q \wedge R)  \) является формализацией теоремы 15.5. Преобразуем данную формулу, используя закон противоположности и один из законов де Моргана:

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

Прочитаем: "конъюнкция предикатов \(  \large A  \) и \(  \large B  \) не является тождественно истинным предикатом (является опровержимым предикатом), если и только если предикат \(  \large A  \) не является тождественно истинным (является опровержимым) или предикат \(  \large B  \) не является тождественно истинным (является опровержимым). Итак, теорема доказана.

Теорема 15.7. Если предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) тождественно ложен или предикат \(  \large B(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 A(x_1,x_2, \ldots, x_n)  \) тождественно ложен или предикат \(  \large B(x_1,x_2, \ldots, x_n)  \) тождественно ложен. Значит, \(  \large \mathcal{A} = \not \circ  \) или \(  \large \mathcal{B} = \not \circ  \). Рассмотрим все три случая, когда дизъюнкция истинна, используя свойства пустого множества.

а) Если \(  \large \mathcal{A} = \not \circ  \), \(  \large \mathcal{B} \not = \not \circ  \), то

\(  \large \mathcal{A} \cap \mathcal{B}= \not \circ \cap \mathcal{B}= \not \circ  \).

б) Если \(  \large \mathcal{A} \not = \not \circ  \), \(  \large \mathcal{B}  = \not \circ  \), то

\(  \large \mathcal{A} \cap \mathcal{B}= \mathcal{A} \cap \not \circ= \not \circ  \).

в) Если \(  \large \mathcal{A} = \not \circ  \), \(  \large \mathcal{B}  = \not \circ  \), то

\(  \large \mathcal{A} \cap \mathcal{B}= \not \circ \cap \not \circ= \not \circ  \).

Значит, предикат \(  \large A(x_1,x_2, \ldots, x_n) \wedge B(x_1,x_2, \ldots, x_n)  \) тождественно ложен. Теорема доказана.

Замечание 15.3. Теорема, обратная для теоремы 15.7, неверна, поскольку существует такой тождественно ложный предикат \(  \large A \wedge B  \), что предикаты \(  \large A   \) и \(  \large B  \) выполнимы. В качестве примера можно указать предикат "\(  \large n  \) делится на \(  \large 2  \) и \(  \large n  \) не делится на \(  \large 2  \)", заданный на множестве натуральных чисел. Он тождественно ложен. Но предикаты, являющиеся членами конъюнкции, выполнимы.

Теорема 15.8. Если конъюнкция предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(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 P  \) - "предикат \(  \large A  \) тождественно ложен", \(  \large Q  \) - "предикат \(  \large B  \) тождественно ложен", \(  \large R  \) - "конъюнкция предикатов \(  \large A    \) и \(  \large B \) тождественно ложна. Тогда формула логики высказываний \(  \large (P \vee Q) \to R  \) является формализацией теоремы 17.7. Используем закон контрапозиции и один из законов де Моргана:

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

Прочитаем: "Если конъюнкция предикатов \(  \large A    \) и \(  \large B \) не является тождественно ложным предикатом (является выполнимым), то предикат \(  \large A  \) не является тождественно ложным (выполним) и предикат \(  \large B  \) не является тождественно ложным (выполнимым)". Теорема доказана.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 15. Предикаты и логические связки
« Ответ #3 : Апрель 11, 2017, 01:56:26 pm »
Определение 15.3. Дизъюнкцией предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(y_1,y_2, \ldots, y_m)  \), определённых на множествах \(  \large M_i, \ i=1,2, \ldots, n  \) и \(  \large N_j, \ j=1,2, \ldots, m  \) соответственно, называется такой предикат \(  \large C(x_1,x_2, \ldots, x_n, y_1,y_2, \ldots, y_m)  \), определённый на множествах \(  \large M_1,M_2, \ldots, M_n, N_1, N_2, \ldots, N_m  \), что для любых предметных постоянных \(  \large a_i, \ i=1,2, \ldots, n  \), \(  \large b_j, \ j=1,2, \ldots, m  \) высказывание \(  \large C(a_1,a_2, \ldots , a_n ,b_1,b_2, \ldots ,b_m)  \) является дизъюнкцией высказываний \(  \large A(a_1,a_2, \ldots, a_n)  \) и \(  \large B(b_1, b_2, \ldots, b_m)  \).

Пример 15.3. Дизъюнкцией определённых на множестве вещественных чисел одноместных предикатов \(  \large x \not = 0  \) и \(  \large y \not = 0  \) является определённый на том же самом множестве двуместный предикат \(  \large x \not =0 \vee y \not =0  \).

Замечание 15.4. Если предикаты \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(x_1,x_2, \ldots, x_n)  \) являются уравнениями или неравенствами, то их дизъюнкция записывается следующим образом:

\(  \LARGE  [^{A(x_1,x_2, \ldots, x_n)}_{B(x_1,x_2, \ldots, x_n)}  \).

Читается: дизъюнктивная система или совокупность (уравнений, неравенств).

***

Сформулируем и докажем теоремы о связи множеств истинности некоторых предикатов и множества истинности дизъюнкции этих предикатов, а также теоремы о связи типов этих предикатов и типа их дизъюнкции.

***

Теорема 15.9. Множество истинности дизъюнкции предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(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 \mathcal{A}  \) и \(  \large \mathcal{B}  \) - множества истинности предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(x_1,x_2, \ldots, x_n)  \) соответственно. В силу определения множества истинности, множество \(  \large \mathcal{A}  \) состоит из таких наборов \(  \large (a_1,a_2, \ldots, a_n)  \), что высказывание \(  \large A(a_1,a_2, \ldots, a_n)  \) истинно, а множество \(  \large \mathcal{B}  \) - из таких наборов \(  \large (a_1,a_2, \ldots, a_n)  \), что высказывание \(  \large B(a_1,a_2, \ldots, a_n)  \) истинно (здесь \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \)). Обозначим через \(  \large \mathcal{D}  \) множество истинности предиката \(  \large A(x_1,x_2, \ldots, x_n) \vee B(x_1,x_2, \ldots, x_n)  \). Оно состоит только из таких наборов \(  \large (a_1,a_2, \ldots, a_n)  \), что высказывание \(  \large A(a_1,a_2, \ldots, a_n) \vee B(a_1,a_2, \ldots, a_n)  \) истинно. Следовательно, согласно определению дизъюнкции, это такие наборы, что высказывание \(  \large A(a_1,a_2, \ldots, a_n)  \) истинно или высказывание \(  \large B(a_1,a_2, \ldots, a_n)  \) истинно. Это означает, учитывая определение объединения множеств, что \(  \large \mathcal{D}= \mathcal{A} \cup \mathcal{B}  \). Теорема доказана.

Теорема 15.10. Дизъюнкция предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(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 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 \mathcal{A}  \) и \(  \large \mathcal{B}  \) - множества истинности этих предикатов. Согласно теореме 15.9, множеством истинности дизъюнкции этих предикатов является \(  \large \mathcal{A} \cup \mathcal{B}  \).

1) Пусть предикат \(  \large A(x_1,x_2, \ldots , x_n) \vee B(x_1, x_2, \ldots, x_n) \) тождественно ложен. Значит, \(  \large \mathcal{A} \cup \mathcal{B} =\not \circ \). Предположим, что предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) выполним или предикат \(  \large B(x_1,x_2, \ldots, x_n)  \) выполним. Иначе говоря, предположим, что \(  \large \mathcal{A} \not = \not \circ  \) или \(  \large \mathcal{B} \not = \not \circ  \). Дизъюнкция истинна тогда и только тогда, когда истинен хотя бы один из её членов. Рассмотрим все три случая.

а) Пусть \(  \large \mathcal{A} \not = \not \circ  \), \(  \large \mathcal{B} = \not \circ  \). Значит,

\(  \large \mathcal{A} \cup \mathcal{B} = \mathcal{A} \cup \not \circ= \mathcal{A} \).

Но, в силу условия теоремы, \(  \large \mathcal{A} \cup \mathcal{B} =\not \circ \). Тогда \(  \large \mathcal{A} =\not \circ \). Но \(  \large \mathcal{A} \not = \not \circ  \). Противоречие.

б) Пусть \(  \large \mathcal{A}  = \not \circ  \), \(  \large \mathcal{B} \not = \not \circ  \). В этом случае противоречие получаем ровно тем же способом, что был продемонстрирован выше.

в) Пусть \(  \large \mathcal{A}  \not = \not \circ  \), \(  \large \mathcal{B} \not = \not \circ  \). Воспользовавшись диаграммами Эйлера-Венна, легко понять, что это вступает в противоречие с \(  \large \mathcal{A} \cup \mathcal{B} =\not \circ  \).

Итак, если  \(  \large \mathcal{A} \cup \mathcal{B} =\not \circ \), то \(  \large \mathcal{A} = \not \circ  \) и \(  \large \mathcal{B} = \not \circ  \). Иначе говоря, тождественная ложность дизъюнкции двух предикатов влечёт тождественную ложность обоих членов дизъюнкции.

2) Пусть предикаты \(  \large A(x_1,x_2, \ldots , x_n) \) и \(  \large  B(x_1, x_2, \ldots, x_n)  \) тождественно ложны. Значит, \(  \large \mathcal{A} =\not \circ \) и  \(  \large  \mathcal{B} =\not \circ \). Тогда, используя идемпотентность объединения, получим:

\(  \large \mathcal{A} \cup \mathcal{B}=  \not \circ \cup \not \circ = \not \circ    \).

Значит, предикат \(  \large A(x_1,x_2, \ldots, x_n) \wedge B(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)  \) тождественно ложны, то их дизъюнкция тождественно ложна. Теорема доказана.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 15. Предикаты и логические связки
« Ответ #4 : Декабрь 05, 2017, 08:54:16 pm »
Теорема 15.11. Дизъюнкция предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(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 P  \) - "дизъюнкция предикатов \(  \large A  \) и \(  \large B  \) тождественно ложна", \(  \large Q  \) - "\(  \large A  \) тождественно ложен", \(  \large R  \) - "\(  \large B  \) тождественно ложен". Тогда формула логики высказываний \(  \large P \leftrightarrow (Q \wedge R)  \) является формализацией теоремы 15.10. Выше уже было показано, что данная формула равносильна следующей:

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

Прочитаем: "конъюнкция предикатов \(  \large A  \) и \(  \large B  \) не является тождественно ложным предикатом (выполнима), если и только если предикат \(  \large A  \) не является тождественно ложным (выполним) или предикат \(  \large B  \) не является тождественно ложным (выполним). На этом теорема доказана.

Теорема 15.12. Если предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) тождественно истинен или предикат \(  \large B(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 A(x_1,x_2, \ldots, x_n)  \) тождественно истинен или предикат \(  \large B(x_1,x_2, \ldots, x_n)  \) тождественно истинен. Значит, \(  \large \mathcal{A} =M_1 \times M_2 \times \ldots \times M_n  \) или \(  \large \mathcal{B} = M_1 \times M_2 \times \ldots \times M_n  \). Рассмотрим все три случая, когда дизъюнкция истинна. При этом будут использованы свойства универсального множества.

а) Если \(  \large \mathcal{A} = M_1 \times M_2 \times \ldots \times M_n  \), \(  \large \mathcal{B} \not = M_1 \times M_2 \times \ldots \times M_n \), то

\(  \large \mathcal{A} \cup \mathcal{B}= M_1 \times M_2 \times \ldots \times M_n \cup \mathcal{B}= M_1 \times M_2 \times \ldots \times M_n  \).

б) Если \(  \large \mathcal{A} \not = M_1 \times M_2 \times \ldots \times M_n  \), \(  \large \mathcal{B}  = M_1 \times M_2 \times \ldots \times M_n  \), то аналогично:

\(  \large \mathcal{A} \cup \mathcal{B}= \mathcal{A} \cup M_1 \times M_2 \times \ldots \times M_n= M_1 \times M_2 \times \ldots \times M_n  \).

в) Если \(  \large \mathcal{A} = M_1 \times M_2 \times \ldots \times M_n  \), \(  \large \mathcal{B}  = M_1 \times M_2 \times \ldots \times M_n  \), то

\(  \large \mathcal{A} \cup \mathcal{B}=M_1 \times M_2 \times \ldots \times M_n \cup M_1 \times M_2 \times \ldots \times M_n= M_1 \times M_2 \times \ldots \times M_n \).

Значит, предикат \(  \large A(x_1,x_2, \ldots, x_n) \vee B(x_1,x_2, \ldots, x_n)  \) тождественно истинен. Теорема доказана.

Замечание 15.5 Теорема, обратная для теоремы 15.12, не выполняется, поскольку существует такой тождественно истинный предикат \(  \large A \vee B  \), что предикаты \(  \large A  \) и \(  \large B  \) опровержимы. Возьмём, например, \(  \large x<3 \vee x \ge 3  \), \(  \large x \in \mathbb{R}  \).
 
Теорема 15.13. Если дизъюнкция предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(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 P  \) - "предикат \(  \large A  \) тождественно истинен", \(  \large Q  \) - "предикат \(  \large B  \) тождественно истинен", \(  \large R  \) - "дизъюнкция предикатов \(  \large A    \) и \(  \large B \) тождественно истинна. Тогда формула логики высказываний \(  \large (P \vee Q) \to R  \) является формализацией теоремы 15.12. Нам уже известно, что эта формула равносильна такой:

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

Прочитаем: "Если дизъюнкция предикатов \(  \large A    \) и \(  \large B \) не тождественно истинна  (опровержима), то предикат \(  \large A  \) не тождественно истинен (опровержим) и предикат \(  \large B  \) не тождественно истинен (опровержим)". Теорема доказана.

***

Теоремы о связи типов предикатов и логических операций будут неоднократно применяться в последующем. Поэтому рекомендуется хорошо запомнить их формулировки.
 

Оффлайн Admin

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

***

Теорема 15.14. Предикат \(  \large A(x_1,x_2, \ldots, x_n) \vee \overline{A(x_1,x_2, \ldots, x_n)}  \) является тождественно истинным.

Доказательство.

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

Теорема 15.15. Предикат \(  \large A(x_1,x_2, \ldots, x_n) \wedge \overline{A(x_1,x_2, \ldots, x_n)}  \) является тождественно ложным.

Доказательство.

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 15. Предикаты и логические связки
« Ответ #6 : Февраль 16, 2018, 04:19:49 pm »
Определение 15.4. Строгой дизъюнкцией предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(y_1,y_2, \ldots, y_m)  \), определённых на множествах \(  \large M_i, \ i=1,2, \ldots, n  \) и \(  \large N_j, \ j=1,2, \ldots, m  \) соответственно, называется такой предикат \(  \large C(x_1,x_2, \ldots, x_n, y_1,y_2, \ldots, y_m)  \), определённый на множествах \(  \large M_1,M_2, \ldots, M_n, N_1, N_2, \ldots, N_m  \), что для любых предметных постоянных \(  \large a_i, \ i=1,2, \ldots, n  \), \(  \large b_j, \ j=1,2, \ldots, m  \), высказывание \(  \large C(a_1,a_2, \ldots , a_n ,b_1,b_2, \ldots ,b_m)  \) является строгой дизъюнкцией высказываний \(  \large A(a_1,a_2, \ldots, a_n)  \) и \(  \large B(b_1, b_2, \ldots, b_m)  \).

Определение 15.5. Импликацией предикатов с посылкой \(  \large A(x_1,x_2, \ldots, x_n)  \) и заключением \(  \large B(y_1,y_2, \ldots, y_m)  \), определённых на множествах \(  \large M_i, \ i=1,2, \ldots, n  \) и \(  \large N_j, \ j=1,2, \ldots, m  \) соответственно, называется такой предикат \(  \large C(x_1,x_2, \ldots, x_n, y_1,y_2, \ldots, y_m)  \), определённый на множествах \(  \large M_1,M_2, \ldots, M_n, N_1, N_2, \ldots, N_m  \), что для любых предметных постоянных \(  \large a_i, \ i=1,2, \ldots, n  \), \(  \large b_j, \ j=1,2, \ldots, m  \), высказывание \(  \large C(a_1,a_2, \ldots , a_n ,b_1,b_2, \ldots ,b_m)  \) является импликацией высказываний с посылкой \(  \large A(a_1,a_2, \ldots, a_n)  \) и заключением \(  \large B(b_1, b_2, \ldots, b_m)  \).

Определение 15.6. Эквиваленцией предикатов \(  \large A(x_1,x_2, \ldots, x_n)  \) и \(  \large B(y_1,y_2, \ldots, y_m)  \), определённых на множествах \(  \large M_i, \ i=1,2, \ldots, n  \) и \(  \large N_j, \ j=1,2, \ldots, m  \) соответственно, называется такой предикат \(  \large C(x_1,x_2, \ldots, x_n, y_1,y_2, \ldots, y_m)  \), определённый на множествах \(  \large M_1,M_2, \ldots, M_n, N_1, N_2, \ldots, N_m  \), что для любых предметных постоянных \(  \large a_i, \ i=1,2, \ldots, n  \), \(  \large b_j, \ j=1,2, \ldots, m  \), высказывание \(  \large C(a_1,a_2, \ldots , a_n ,b_1,b_2, \ldots ,b_m)  \) является эквиваленцией высказываний \(  \large A(a_1,a_2, \ldots, a_n)  \) и \(  \large B(b_1, b_2, \ldots, b_m)  \).

Пример 15.4. Рассмотрим предикаты \(  \large x>1  \) и \(  \large y^2-1<0  \), определённые на множестве вещественных чисел. Предикат \(  \large (x>1) + (y^2-1<0)  \) является строгой дизъюнкцией этих предикатов, предикат \(  \large (x>1) \to (y^2-1<0)  \) является их импликацией с посылкой \(  \large x>1  \) и заключением \(  \large y^2-1<0  \), а предикат \(  \large (x>1) \leftrightarrow (y^2-1<0)  \) является эквиваленцией этих предикатов.

Замечание 15.6. Далее будет доказано, что для предикатов справедливы все законы классической логики высказываний, значит, учитывая, что все пропозициональные связки выражаются через отрицание, конъюнкцию и дизъюнкцию, предикаты \(  \large A \oplus B  \), \(  \large A \to B  \) и \(  \large A \leftrightarrow B  \) можно выразить через эти связки. Следовательно, легко решить вопрос о множестве истинности этих предикатов, а также о связи типа предиката и логических операций.