Автор Тема: Лекция 16. Предикаты и кванторы  (Прочитано 2230 раз)

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 16. Предикаты и кванторы
« : Апрель 11, 2017, 02:01:41 pm »
Лекция 16. Предикаты и кванторы


Главное отличие логики предикатов от логики высказываний в том, что в первой, помимо хорошо известных логических операций, есть две принципиально новые операции - связывание квантором общности или квантором существования. Эти операции над предикатами, вообще говоря, не сводятся к пропозициональным операциям. Связывание квантором единственной предметной переменной одноместного предиката, а также связывание кванторами всех предметных переменных многоместного предиката, превращает последний в высказывание, как и замена предметной переменной на предметную константу. Связывание кванторами некоторых предметных переменных предиката превращает его в предикат меньшей местности (она уменьшается на число кванторов). Рассмотрим кванторные операции над предикатами.

***

Пусть: 1) \(  \large \mathbf{A}  \) - множество одноместных предикатов \(  \large A(x)  \), определённых на некотором множестве \(  \large M  \);
2) \(  \large \mathbf{K}  \) - множество высказываний.

Определение 16.1. Связыванием квантором общности предметной переменной \(  \large x  \) называется такое отображение

\(  \large f \colon \mathbf{A} \to \mathbf{K}  \),

что высказывание \(  \large f(A(x))  \) истинно тогда и только тогда, когда предикат \(  \large A(x)  \) является тождественно истинным.

Замечание 16.1. Образ \(  \large f(A(x))  \) предиката \(  \large A(x)  \) обозначается через \(  \large \forall x A(x)  \). Читается: "для любого \(  \large x  \) \(  \large A(x)  \)", "для каждого \(  \large x  \) \(  \large A(x)  \)", "для произвольного \(  \large x  \) \(  \large A(x)  \)", "каков бы ни был \(  \large x  \), \(  \large A(x)  \)".

Замечание 16.2. Высказывание \(  \large \forall x A(x)  \) называется универсальным для предиката \(  \large A(x)  \).

Замечание 16.3. В силу определения 16.1, \(  \large \forall x A(x)=1  \) тогда и только тогда, когда предикат \(  \large A(x)  \) тождественно истинен. Значит, \(  \large \forall x A(x)=0  \) тогда и только тогда, когда предикат \(  \large A(x)  \) опровержим. Итак,

\(  \large \forall x A(x)= \begin{cases} 1, \ если \ A(x) \ тождественно \ истинен \\ 0, \ если \ A(x) \ опровержим \end{cases}  \).

Замечание 16.4. Символ \(  \large \forall   \) называется квантором общности (всеобщности), а сочетание символов \(  \large \forall x  \) - квантором общности (всеобщности) по переменной \(  \large x  \).
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 16. Предикаты и кванторы
« Ответ #1 : Апрель 11, 2017, 10:11:38 pm »
Определение 16.2. Связыванием квантором существования предметной переменной \(  \large x  \) называется такое отображение

\(  \large \varphi \colon \mathbf{A} \to \mathbf{K}  \),

что высказывание \(  \large \varphi (A(x))  \) ложно тогда и только тогда, когда предикат \(  \large A(x)  \) является тождественно ложным.

Замечание 16.5. Образ \(  \large \varphi (A(x))  \) предиката \(  \large A(x)  \) обозначается через \(  \large \exists x A(x)  \). Читается: "существует такой \(  \large x  \), что \(  \large A(x)  \)", "найдётся такой \(  \large x  \), что \(  \large A(x)  \)", "для некоторых \(  \large x  \) \(  \large A(x)  \)", "хотя бы для одного \(  \large x  \) \(  \large A(x)  \)".

Замечание 16.6. Высказывание \(  \large \exists x A(x)  \) называется экзистенциальным для предиката \(  \large A(x)  \).

Замечание 16.7. В силу определения 16.2, \(  \large \exists x A(x)=0  \) тогда и только тогда, когда предикат \(  \large A(x)  \) тождественно ложен. Значит, \(  \large \forall x A(x)=1  \) тогда и только тогда, когда предикат \(  \large A(x)  \) выполним. Итак,

\(  \large \exists x A(x)= \begin{cases} 1, \ если \ A(x) \ выполним \\ 0, \ если \ A(x) \ тождественно \ ложен \end{cases}  \).

Замечание 16.8. Символ \(  \large \exists   \) называется квантором существования, а сочетание символов \(  \large \exists x  \) - квантором существования по переменной \(  \large x  \).

Замечание 16.9. Как следует из определений 16.1 и 16.2, в высказываниях \(  \large \forall x A(x)  \) и \(  \large \exists x A(x)  \) предметная переменная \(  \large x  \) является связанной. Высказывания \(  \large \forall x A(x)  \) и \(  \large \exists x A(x)  \) уже не зависят от предметной переменной \(  \large x  \). Это значит, что вместо неё уже нельзя подставлять предметные постоянные (высказывание - нульместный предикат).

Замечание 16.10. Символы \(  \large \forall   \) и \(  \large \exists  \) происходят от английских слов All (все) и Exist (существовать). Отсюда и обозначения.

Замечание 16.11. Помимо связывания предметной переменной квантором, говорят о навешивании квантора на предикат.

Пример 16.1. Рассмотрим предикаты \(  \large x^2 \ge 0, \ x \in \mathbb{R}  \), \(  \large k  \) делится на \(  \large 7  \), \(  \large k \in \mathbb{Z}  \), и \(  \large n<0  \), \(  \large n \in \mathbb{N}  \). Первый обозначим через \(  \large A(x)  \), второй - через \(  \large B(x)  \), а третий - через \(  \large C(x)  \). Предикат \(  \large A(x)  \) тождественно истинен (значит, выполним). Следовательно, высказывания \(  \large \forall x A(x)  \) и \(  \large \exists x A(x)  \) истинны. Предикат \(  \large B(x)  \) опровержим, но не является тождественно ложным (выполним). Значит, высказывание \(  \large \forall x B(x) \) ложно, а высказывание \(  \large \exists x B(x)  \) истинно. Наконец, предикат \(  \large C(x)  \) тождественно ложен (значит, опровержим). Следовательно, высказывания \(  \large \forall x C(x)   \) и \(  \large \exists x C(x)  \) ложны.
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 16. Предикаты и кванторы
« Ответ #2 : Апрель 11, 2017, 10:30:36 pm »
В повседневной жизни и математической практике часто встречаются высказывания, содержанием которых являются утверждения о том, что все предметы, принадлежащие определённому множеству, принадлежат (или не принадлежат) другому множеству, а также о том, что некоторые предметы, принадлежащие определённому множеству, принадлежат (или не принадлежат) другому множеству. Это общеутвердительные, общеотрицательные, частоутвердительные и частноотрицательные высказывания. Определим их более строго и рассмотрим примеры.

***

Определение 16.3. Общеутвердительным называется высказывание "Каков бы ни был \(  \large x  \), если он обладает свойством \(  \large A  \), то он обладает свойством \(  \large B  \)".

Определение 16.4. Общеотрицательным называется высказывание "Каков бы ни был \(  \large x  \), если он обладает свойством \(  \large A  \), то он не обладает свойством \(  \large B  \)".

Определение 16.5. Частноутвердительным называется высказывание "Найдётся такой \(  \large x  \), что он обладает свойством \(  \large A  \) и свойством \(  \large B  \)".

Определение 16.6. Частноотрицательным называется высказывание "Найдётся такой \(  \large x  \), что он обладает свойством \(  \large A  \) и не обладает свойством \(  \large B  \)".

Замечание 16.12. Из приведённых выше определений ясно, что общеутвердительное высказывание имеет вид

\(  \large \forall x (A(x) \to B(x))  \),

общеотрицательное -

\(  \large \forall x (A(x) \to \overline{ B(x)})  \),

частноутвердительное -

\(  \large \exists x (A(x) \wedge B(x))  \),

частноотрицательное -

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

Пример 16.2. Высказывание "Все люди - млекопитающие" является общеутвердительным. Его можно прочитать так: "Каким бы ни было животное, если оно является человеком, то оно является млекопитающим". Высказывание "Ни одно натуральное число не является отрицательным" является общеотрицательным. Его можно переформулировать следующим образом: "Каково бы ни было число, если оно является натуральным, то не является отрицательным". Частноутвердительным является высказывание "Некоторые металлы - твёрдые тела". Данная формулировка эквивалентна такой: "Существуют такие вещества, что они являются металламми и твёрдыми телами". Наконец, высказывание "Некоторые прямоугольники не являются квадратами" является частноотрицательным. Иначе оно звучит так: "Найдутся такие фигуры, что они являются прямоугольниками и не являются квадратами".
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 16. Предикаты и кванторы
« Ответ #3 : Апрель 12, 2017, 12:10:16 am »
Как говорилось в начале лекции, кванторы можно навешивать не только на одноместные предикаты. Если навесить квантор на \(  \large n  \)-местный предикат, то получим \(  \large (n-1)  \)-местный предикат, тип которого можно усмотреть, вспомнив классификацию предикатов. Дадим строгое определение квантификации многоместных предикатов.

***

Пусть: 1) \(  \large A(x)   \) - некоторый предикат, определённый на множествах \(  \large M_1,M_2, \ldots, M_n  \);
2) \(  \large  \mathbf{A}_{n} \) и \(  \large  \mathbf{A}_{n-1} \) - множества \(  \large n  \)- и \(  \large (n-1)  \)-местных предикатов соответственно, где \(  \large n \ge 2  \).

Определение 16.7. Связыванием квантором общности по переменной \(  \large x_1  \) называется такое отображение

\(  \large f \colon \mathbf{A}_{n} \to \mathbf{A}_{n-1}  \),

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

Замечание 16.13. Из определения 16.7 заключаем, что предикат \(  \large \forall x_1 A(x_1,x_2, \ldots, x_n)   \) опровержим тогда и только тогда, когда существуют такие \(  \large a_2 \in M_2, \ldots, a_n \in M_n  \), что высказывание \(  \large \forall x_1 A(x_1,a_2, \ldots, a_n)  \) ложно.

Определение 16.8. Связыванием квантором существования по переменной \(  \large x_1  \) называется такое отображение

\(  \large \varphi \colon \mathbf{A}_{n} \to \mathbf{A}_{n-1}  \),

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

Замечание 16.14. Из определения 16.8 заключаем, что предикат \(  \large \exists x_1 A(x_1,x_2, \ldots, x_n)   \) выполним тогда и только тогда, когда существуют такие \(  \large a_2 \in M_2, \ldots, a_n \in M_n  \), что высказывание \(  \large \exists x_1 A(x_1,a_2, \ldots, a_n)  \) истинно.

Замечание 16.15. Определения 16.7 и 16.8 отчасти дублируют определения тождественно истинного и тождественного ложного предикатов. Но важным моментом в них является то, что результат квантификации \(  \large n  \)-местного предиката является \(  \large (n-1)  \)-местным предикатом.

Замечание 16.16. К \(  \large (n-1)  \)-местным предикатам \(  \large \forall x_1 A(x_1,x_2, \ldots, x_n)  \) и \(  \large \exists x_1 A(x_1,x_2, \ldots, x_n)  \) можно снова применять кванторы:

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

\(  \large \exists x_2 \exists x_1 A(x_1,x_2, \ldots, x_n),  \ \forall x_2 \forall x_1 A(x_1,x_2, \ldots, x_n)   \).

И т.д. Кванторы можно навешивать до тех пор, пока не окажутся связанными все предметные переменные предиката \(  \large A(x_1,x_2, \ldots, x_n)  \). В этом случае получаем высказывание.

Замечание 16.17. Связывание кванторами части предметных переменных предиката не исключает подстановки предметных констант вместо оставшихся свободными предметных переменных. Так, из одноместного предиката \(  \large \forall x \exists y (x^2+y>z)  \), подставив \(  \large 1  \) вместо \(  \large z  \), получим высказывание \(  \large \forall x \exists y (x^2+y>1)  \).
 
Сказали спасибо: Alexey

Оффлайн Admin

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

***

Пример 16.3. Найдём истинностные значения высказываний \(  \large \forall y A(0,y)  \), \(  \large \exists x A(x,1)  \), если \(  \large A(x,y)  \) означает \(  \large (x-1)(x-2)+3x=y  \), \(  \large x \ge y  \), где \(  \large x,y \in \mathbb{R}  \).

1) Найдём предикат \(  \large A(0,y)  \). Подставим \(  \large x=0  \) в предикат \(  \large (x-1)(x-2)+3x=y  \). После упрощения получим \(  \large y=2  \). Данный предикат опровержим (например, высказывание \(  \large 3=2  \) ложно). Следовательно, высказывание \(  \large \forall y (y=2)  \) ложно.

Найдём предикат \(  \large A(x,1)  \). Подставим \(  \large y=1  \) в предикат \(  \large (x-1)(x-2)+3x=y  \). Упростив, получим тождественно ложный \(  \large x^2+1=0  \). Значит, высказывание \(  \large \exists x (x^2+1=0)  \) является ложным.

2) Найдём предикат \(  \large A(0,y)  \). Подставим \(  \large x=0  \) в предикат \(  \large x \ge y  \). Получим \(  \large 0 \ge y  \) или (что то же самое) \(  \large y \le 0  \). Этот предикат тождественно истинным не является (в частности, высказывание \(  \large 4 \le 0  \) ложно). Тогда высказывание \(  \large \forall y (y \le 0)  \) ложно.

Наконец, найдём предикат \(  \large A(x,1)  \). Сделаем подстановку \(  \large y=1  \) в предикате \(  \large x \ge y  \). Получится предикат \(  \large x \ge 1  \). Данный предикат выполним (например, высказывание \(  \large 2 \ge 1  \) истинно). Следовательно, высказывание \(  \large \exists x (x \ge 1)  \) истинно.
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 16. Предикаты и кванторы
« Ответ #5 : Апрель 28, 2017, 12:13:26 pm »
Далее покажем, как используется язык логики предикатов для символической записи высказываний.

***

Пример 16.4. Запишем на языке логики предикатов высказывание "Для любых трех человек найдутся один подросток, и двое других незнакомы друг с другом, или все трое знакомы друг с другом".

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

\(  \large \forall x \forall y \forall z ((A(x) \wedge \overline{B(y,z)}) \vee (B(x,y) \wedge B(x,z) \wedge B(y,z)))  \).

Пример 16.5. Используя язык логики предикатов, запишем высказывание "Для любых двух точек не существует прямой, инцидентной им".

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

\(  \large \forall x \forall y \overline{ \exists z \ A(x,y,z) }  \).

Пример 16.6. Переведём на символический язык высказывание "Если любая кошка - хищник или некоторые млекопитающие  - кошки, то если существуют кошки, то существуют хищные млекопитающие".

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

\(  \large (\forall x (A(x) \to B(x)) \vee \exists x (C(x) \wedge A(x)) \to ( \exists x A(x) \to (\exists x (B(x) \wedge C(x))))  \).

Пример 16.7. Запишем на языке логики предикатов высказывание "Каждый студент изучает какой-нибудь иностранный язык".

Пусть \(  \large A(x,y) \) - "\(  \large x \) изучает \(  \large y \)", \(  \large B(x) \) - "\(  \large x \) является студентом", \(  \large C(y) \) - "\(  \large y \) является иностранным языком", где переменная \(  \large x  \) принадлежит множеству людей, а переменная \(  \large y  \) - множеству объектов изучения. Тогда высказывание "Для любого \(  \large x \) если он является студентом, то  найдётся такой объект \(  \large y \), что он является иностранным языком и \(  \large x \) изучает \(  \large y \)" можно записать в виде

\(  \large (\forall x )(B(x)  \to (\exists y) (C(y) \wedge A(x,y)) \).
 
Сказали спасибо: Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 16. Предикаты и кванторы
« Ответ #6 : Май 20, 2017, 12:50:40 pm »
Из определения предиката \(  \large \forall x_1 A(x_1,x_2, \ldots, x_n)  \) сразу же следует, в каком случае данный предикат тождественно истинен, а в каком - опровержим. Используя определения тождественно ложного и выполнимого предиката, легко определить, когда данный предикат тождественно ложен и выполним. Зная определение предиката \(  \large \exists x_1 A(x_1,x_2, \ldots, x_n)  \), легко понять, когда он тождественно ложен, а когда выполним. Применяя определения тождественно истинного предиката и опровержимого предиката, понимаем, когда этот предикат тождественно истинен, а когда опровержим. Чтобы глубже вникнуть в сущность квантификации многоместных предикатов, рассмотрим три задачи. В каждой из них дан некоторый двуместный предикат \(  \large A(x,y)  \) и требуется определить типы предикатов

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

а также истинностные значения высказываний

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


***

Задача 16.1. Рассмотрим предикат \(  \large x+y>1  \), где \(  \large x,y \in M  \), \(  \large M= \{1,2,3 \}  \). Он тождественно истинен, поскольку высказывания

\(  \large 1+1>1, \ 1+2>1, \ 1+3>1  \),

\(  \large 2+1>1,  \ 2+2>1 , \ 2+3>1  \),

\(  \large 3+1>1, \ 3+2>1, \ 3+3>1  \)

истинны. Значит, тождественно истинны (и выполнимы) предикаты

\(  \large \forall y (x+y>1)  \), \(  \large \exists x (x+y>1)  \).

Тогда истинны и высказывания

\(  \large \forall x \forall y (x+y>1)  \), \(  \large \exists x \forall y (x+y>1)  \), \(  \large \forall x \exists y (x+y>1)  \), \(  \large \exists x \exists y (x+y>1)  \).

Задача 16.2. Рассмотрим предикат \(  \large x+y>5  \), где \(  \large x,y \in M  \),  \(  \large M= \{ 2,3,4  \}  \). Данный предикат выполним (высказывание \(  \large 3+4>5  \) истинно) и опровержим (высказывание \(  \large 2+3>5  \) ложно).

Предикат \(  \large \exists y (x+y>5)  \) тождественно истинен (а значит, выполним), поскольку высказывания

\(  \large \exists y (2+y>5)  \), \(  \large \exists y (3+y>5)  \), \(  \large \exists y (4+y>5)  \)

истинны. Они истинны, поскольку соответствующие предикаты выполнимы. Так, предикат \(  \large 2+y>5  \) выполним, так как высказывание \(  \large 2+4>5  \) истинно. Значит, высказывания

\(  \large \exists x \exists y (x+y>5)  \), \(  \large \forall x \exists y (x+y>5)  \)

истинны.

Предикат \(  \large \forall y (x+y>5)  \) опровержим. Он опровержим, так как высказывание \(  \large \forall y (2+y>5)  \) ложно. Оно ложно, так как предикат \(  \large 2+y>5  \) опровержим (высказывание \(  \large 2+3>5  \) ложно). Следовательно, ложно высказывание

\(  \large \forall x \forall y (x+y>5)  \).

Предикат \(  \large \forall y (x+y>5)  \)  выполним, так как высказывание \(  \large \forall y (4+y>5)  \) истинно. Оно истинно, поскольку предикат \(  \large 4+y>5  \) тождественно истинен (высказывания \(  \large 4+2>5  \), \(  \large 4+3>5  \), \(  \large 4+4>5  \) истинны). Значит, истинно высказывание

\(  \large \exists x \forall y (x+y>5)  \).

Задача 16.3. Рассмотрим предикат \(  \large x+y<2  \), где \(  \large x,y \in M  \), \(  \large M=\{ 1,2, 3 \}  \). Он тождественно ложен, так как высказывания

\(  \large 1+1<2, \ 1+2<2, \ 1+3<2  \),

\(  \large 2+1<2, \  2+2<2 , \ 2+3<2  \),

\(  \large 3+1<2, \ 3+2<2, \ 3+3<2  \)

ложны. Значит, тождественно ложны (и опровержимы) предикаты

\(  \large \forall y (x+y<2)  \), \(  \large \exists y (x+y<2)  \),

следовательно, ложны высказывания

\(  \large \forall x \forall y (x+y<2)  \), \(  \large \exists x \forall y (x+y<2)  \), \(  \large \forall x \exists y (x+y<2)  \), \(  \large \exists x \exists y (x+y<2)  \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 16. Предикаты и кванторы
« Ответ #7 : Май 20, 2017, 01:29:49 pm »
Рассмотрим ещё четыре задачи, для решения которых требуется понимание определений квантора общности, квантора существования и операций классической логики высказываний. Кроме того, нам понадобятся теоремы из лекции 15 о связи типов предикатов и логических связок.

***

Задача 16.4. Пусть \(  \large A(x)  \) и \(  \large B(x)  \) - такие одноместные предикаты, определённые на одном и том же множестве \(  \large M  \), что высказывание \(  \large \exists x(A(x)
\vee B(x))   \) ложно. Доказать, что высказывание \(  \large \exists x A(x)  \wedge  \forall x \overline{B(x)} \) ложно.

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

Задача 16.5. Пусть \(  \large A(x)  \) и \(  \large B(x)  \) - такие одноместные предикаты, определённые на одном и том же множестве \(  \large M  \), что высказывание \(  \large \forall x (\overline{A(x)} \vee \overline{B(x)}  \) ложно. Доказать, что высказывание \(  \large \forall x \overline{A(x)} \vee \exists x B(x)  \) истинно.

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

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 16. Предикаты и кванторы
« Ответ #8 : Сентябрь 20, 2017, 09:13:00 pm »
Задача 16.6. Существуют ли такие предикаты \(  \large A(x)  \) и \(  \large B(x)  \), что множество истинности хотя бы одного их них не пусто и высказывания

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

и

\(  \large \exists x (A(x) \vee B(x)) \to \forall x \overline{A(x)}  \)

ложны?

Рассмотрим первое высказывание. Это импликация. Согласно определению, она ложна тогда и только тогда, когда высказывание \(  \large \forall x (A(x) \wedge \overline{B(x)})  \) истинно, а высказывание \(  \large \exists x B(x)  \) ложно. В силу определения кванторов, это означает, что предикат
\(  \large A(x) \wedge \overline{B(x)} \)
тождественно истинен, а предикат \(  \large B(x)  \) тождественно ложен. Конъюнкция предикатов тождественно истинна в том и только том случае, если оба предиката тождественно истинны; отрицание предиката тождественно истинно, если и только если этот предикат тождественно ложен (теоремы из лекции 2). Значит, предикат \(  \large A(x)  \) тождественно истинен, а предикат \(  \large B(x)  \) тождественно ложен.

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

Введём обозначения. Пусть \(  \large A_1  \) означает "предикат \(  \large A(x)  \) тождественно истинен", \(  \large A_2  \) - "предикат \(  \large B(x)  \) тождественно ложен", \(  \large A_3  \) - "предикат \(  \large A(x)  \) выполним", \(  \large A_4  \) - "предикат \(  \large B(x)  \) выполним". Имеем следующее высказывание:

\(  \large A_1 \wedge A_2 \wedge (A_3 \vee A_4) \wedge A_3  \).

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

\(  \large A_1 \wedge A_2 \wedge A_3  \).

Итак, предикат \(  \large A(x)  \) тождественно истинен (и выполним), предикат \(  \large B(x)  \) тождественно ложен. Эти условия совместимы (мы знаем, что всякий тождественно истинный предикат выполним). Можно даже привести пример таких предикатов. Пусть \(  \large A(x)  \) обозначает \(  \large x>0  \), \(  \large B(x)  \) - \(  \large x \le 0  \), где \(  \large x  \) - натуральное число. Первый предикат тождественно истинен, а второй - тождественно ложен. Тогда имеем высказывания

\(  \large \forall x (x >0 \wedge \overline{x \le 0}) \to \exists x  (x \le 0)  \)

и

\(  \large \exists x (x >0 \vee x \le 0) \to \forall x ( \overline{x>0} ) \).

Можно легко убедиться, что оба высказывания ложны.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Лекция 16. Предикаты и кванторы
« Ответ #9 : Февраль 16, 2018, 04:15:22 pm »
Задача 16.7. То же задание для высказываний

\(  \large \forall x A(x) \wedge \exists x ( A(x) \vee B(x))  \)

и

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

первое из которых ложно, а второе истинно.

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

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

Введём обозначения. Пусть \(  \large A_1  \) означает "предикат \(  \large A(x)  \) опровержим", \(  \large A_2  \) - "предикат \(  \large A(x)  \) тождественно ложен", \(  \large A_3  \) - "предикат \(  \large B(x)  \) тождественно ложен", \(  \large A_4  \) - "предикат \(  \large A(x)  \) тождественно истинен". Имеем следующее высказывание:

\(  \large A_1 \wedge A_2 \wedge A_3 \wedge A_3 \wedge A_4  \).

Упростим его, применяя закон идемпотентности конъюнкции:

\(  \large A_1 \wedge A_2 \wedge A_3 \wedge A_4  \).

Итак, предикат \(  \large A(x)  \) тождественно ложен (и опровержим), а также тождественно истинен, предикат \(  \large B(x)  \) тождественно ложен. Но это невозможно, так как тождественно ложный предикат не может быть тождественно истинным. Следовательно, таких предикатов не существует.