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

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

Оффлайн Admin

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


Ещё в курсе элементарной алгебры мы сталкивались с уравнениями, неравенствами и другими выражениями, включающими в себя неизвестные. Рассмотрим уравнение \(  \large x^3-1=0  \), неравенство \(  \large x^2-5x+6 <0  \) (оба на множестве вещественных чисел) и предложение "\(  \large x  \) делится на \(  \large 7  \)", где \(  \large x  \) - натуральное число. Уравнение \(  \large x^3-1=0  \) имеет единственный вещественный корень: \(  \large x_0=1  \). Это значит, что высказывание \(  \large 1^3-1=0  \) истинно, а любое высказывание \(  \large a^3-1=0  \), где \(  \large a \not =1   \), ложно. Решением неравенства \(  \large x^2-5x+6<0  \) является интервал \(  \large (2,3)  \). Иначе говоря, высказывание \(  \large a^2-5x+6<0  \) истинно, если \(  \large a \in (2,3)  \), и ложно, если \(  \large a \not \in (2,3)  \). Наконец, выражение "\(  \large x   \) делится на \(  \large 7  \) становится истинным высказыванием при \(  \large x=7,14,21, \ldots   \). Итак, выражения \(  \large x^3-1=0  \), \(  \large x^2-5x+6<0  \) и "\(  \large x  \) делится на \(  \large 7  \)", не являясь высказываниями, становятся ими при замене неизвестных некоторыми элементами заданного множества. Переменных может и более одной , и они могут быть не только числовыми. Подобные выражения с переменными и называются предикатами.

Классическая логика предикатов, в отличие от классической логики высказываний, позволяет исследовать структуру высказываний, и следовательно, даёт больше возможностей для изучения закономерностей умозаключений. Для изучения логики предикатов нам понадобятся самые общие знания из теории множеств, рассмотренные в лекциях 7,8 и 9.

Дадим строгое определение предиката.

***

Пусть \(  \large M_1, M_2, \ldots, M_n  \) - некоторые множества.

Определение 14.1. \(  \large n  \)-местным предикатом называется предложение, которое содержит \(  \large n  \) переменных

\(  \large x_1 \in M_1, \ x_2 \in M_2, \ \ldots , \ x_n \in M_n  \)

и становится высказыванием в результате замены этих переменных именами конкретных предметов

\(  \large a_1 \in M_1, \ a_2 \in M_2, \ \ldots , \ a_n \in M_n \).

Замечание 14.1. Переменные \(  \large x_i \in M_i, \ i=1,2, \ldots , n  \) называются предметными, а элементы \(  \large a_i \in M_i, \ i=1,2, \ldots, n, \) - предметными постоянными. Если предметные переменные принадлежат одному и тому множеству, то говорят об односортной логике предикатов, если разным - о многосортной.

Замечание 14.2. \(  \large n  \)-местные предикаты от переменных \(  \large x_i, \ i=1,2, \ldots, n  \) будем обозначать так:

\(  \large A(x_1,x_2, \ldots , x_n), \ B(x_1,x_2, \ldots, x_n), \ C(x_1,x_2, \ldots, x_n), \ \ldots  \)

Выражение \(  \large A(x_1,x_2, \ldots , x_n)  \) читается "\(  \large A   \) от \(  \large x_1, x_2, \ldots , x_n  \)".

Будут использоваться также обозначения с численными индексами внизу:

\(  \large A_1(x_1,x_2, \ldots , x_n), \ A_2(x_1,x_2, \ldots, x_n), \ A_3(x_1,x_2, \ldots, x_n), \ \ldots  \)

\(  \large B_1(x_1,x_2, \ldots , x_n), \ B_2(x_1,x_2, \ldots, x_n), \ B_3(x_1,x_2, \ldots, x_n), \ \ldots  \)

\(  \large C_1(x_1,x_2, \ldots , x_n), \ C_2(x_1,x_2, \ldots, x_n), \ C_3(x_1,x_2, \ldots, x_n), \ \ldots  \)

Если известно, от каких предметных переменных зависит данный предикат, иногда будет писать \(  \large A  \) вместо \(  \large A(x_1,x_2, \ldots, x_n)  \).

Замечание 14.3. Запись \(  \large A(x_1,x_2, \ldots , x_n)  \) означает, что объекты (элементы некоторых известных множеств) находятся в отношении \(  \large A  \). В частности, запись \(  \large A(x)  \) означает, что объект \(  \large x  \) обладает свойством \(  \large A  \). Свойство будем считать частным случаем отношения; объект \(  \large x  \) обладает свойством \(  \large A  \), значит, объект \(  \large x  \) находится в отношении \(  \large A  \) с самим собой.

Замечание 14.4. Высказывание, получающееся из предиката \(  \large A(x_1,x_2, \ldots, x_n)  \) после замены \(  \large x_i=a_i, \ i=1,2, \ldots, n  \), обозначается через \(  \large A(a_1,a_2, \ldots , a_n)  \).

Замечание 14.5. Высказывание \(  \large A(a)  \), которое получено из предиката \(  \large A(x)  \) заменой предметной переменной \(  \large x  \) на предметную постоянную \(  \large a  \), называется единичным. Если его содержанием является утверждение о том, что тот или иной предмет обладает некоторым свойством, то такое высказывание называется единичноутвердительным. Оно называется единичноотрицательным, если в нём утверждается, что некоторый предмет не обладает определённым свойством.

Замечание 14.6. Если \(  \large x_i \in M_i, \ i=1,2, \ldots , n  \), то говорят, что предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) определён или задан на множествах \(  \large M_i, \ i=1,2, \ldots , n   \). Если при этом \(  \large M_1=M_2= \ldots= M_n=M  \), то говорят, что он определён (задан) на множестве \(  \large M  \).

Замечание 14.7. Множества \(  \large M_i, \ i=1,2, \ldots , n   \) могут быть различными.

Пример 14.1. Рассмотрим предикат \(  \large A(x,y)  \): "Город \(  \large x  \) расположен на берегу моря \(  \large y  \)". Здесь \(  \large x \in M_1  \), \(  \large y \in M_2  \), где \(  \large M_1  \) - множество городов, \(  \large M_2  \) - множество морей.

Замечание 14.8. Один и тот же предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) можно определить на разных множествах.

Пример 14.2. Уравнение \(  \large x^4+1=0  \) можно рассматривать как на множестве вещественных чисел, так и на множестве комплексных чисел. В первом случае корней нет, во втором - их четыре.

Замечание 14.9. Если в \(  \large n  \)-местном предикате фиксировать значения \(  \large k  \) предметных переменных \(  \large k<n  \), то получится \(  \large (n-k)  \)-местный предикат. Например, из трёхместного предиката \(  \large x+y+z<1  \), положив \(  \large x=y=0  \), получим одноместный предикат \(  \large z<1  \).

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

Замечание 14.11. Высказывание можно считать нульместным предикатом (предикатом, который не имеет ни одной переменной). Таким образом, ни один предикат не является высказыванием, но все высказывания - предикаты.

Замечание 14.12. Проведём аналогию между формулами логики высказываний и предикатами. Формула логики высказываний становится высказыванием при замене всех пропозициональных переменных конкретными высказываниями, а предикат становится высказыванием, если заменить все его предметные переменные именами конкретных предметов. Следует понимать это и, несмотря на сходство формул логики высказываний и предикатов (и те, и другие являются формами высказываний), не путать их. У предиката нет пропозициональных переменных, поэтому нельзя подставлять высказывания вместо переменных предиката. Эти переменные именуются предметными, поскольку вместо них можно подставлять только имена предметов.

Замечание 14.13. Так как предикаты представляют собой формы высказываний их называют также высказывательными формами.
 
Сказали спасибо: LaLa, Alexey, Fedor1995

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 14. Понятие и виды предикатов
« Ответ #1 : Апрель 05, 2017, 06:37:47 pm »
С каждым предикатом ассоциировано некоторое множество, на котором он обращается в истинное высказывание, - множество истинности.

***

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

Определение 14.2. Множеством истинности предиката \(  \large A(x_1,x_2, \ldots, x_n)  \) называется множество всех таких упорядоченных наборов \(  \large (a_1,a_2, \ldots, a_n)  \), что высказывание \(  \large A(a_1,a_2, \ldots, a_n)  \) истинно.

Замечание 14.14. Множество истинности предиката \(  \large A(x_1,x_2, \ldots, x_n)  \) будем обозначать соответствующей фигурной буквой: \(  \large \mathcal{A}  \).

Замечание 14.15. Множество истинности предиката \(  \large A(x_1,x_2, \ldots, x_n)  \) есть \(  \large n  \)-арное отношение между элементами множеств \(  \large M_i, \ i=1,2, \ldots, n  \).

Замечание 14.16. Множество истинности предиката \(  \large A(x_1,x_2, \ldots, x_n)  \), определённого на множествах \(  \large M_i, \ i=1,2, \ldots, n  \), есть подмножество декартова произведения этих множеств:

\(  \large \mathcal{A} \subseteq M_1 \times M_2 \times \ldots \times M_n  \).

Замечание 14.17. Поскольку высказывание есть нульместный предикат, то нужно договориться о следующем. Множеством истинности ложного высказывания будем считать пустое множество, а множеством истинности истинного высказывания - универсальное множество.

Пример 14.3. Рассмотрим предикат \(  \large A(x)  \) "\(  \large x  \) делится на \(  \large 3  \)", определённый на множестве \(  \large M= \{ 1,2, \ldots, 11 \}  \). Здесь \(  \large  \mathcal{A} = \{ 3,6,9 \}  \).

Пример 14.4. Пусть \(  \large B(x,y)  \) означает \(  \large x \le y  \), причём этот предикат определён на множестве \(  \large M= \{ 0,1,2,3 \}  \). Легко проверить, что

\(  \large \mathcal{B} =\{ (0,0), (0,1), (0,2), (0,3), (1,1), (1,2), (1,3), (2,2), (2,3), (3,3) \}  \).

***

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

***

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

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

Замечание 14.18. Нульместный предикат (высказывание) будем считать уже интерпретированным.

Пример 14.5. Рассмотрим (ложное) высказывание "Луна - спутник Марса". Покажем, как можно формализовать его.

1) Пусть \(  \large A_1(x,y)  \) означает "\(  \large x  \) - спутник \(  \large y  \)", где \(  \large x,y \in M  \), \(  \large M  \) - множество планетарных объектов солнечной системы.

2) Пусть \(  \large A_2(x)  \) означает "\(  \large x  \) - спутник Марса", где \(  \large x \in M  \), \(  \large M  \) - то же самое.

3) Пусть \(  \large A_3(x)  \) означает "Луна - спутник \(  \large x  \)", где \(  \large x \in M  \), \(  \large M  \) - то же самое.

Итак, предикаты \(  \large A_1(x,y)  \), \(  \large A_2(x)  \) и \(  \large A_3(x)  \) являются формализациями высказывания "Луна - спутник Марса".

Пример 14.6. Предложение "Писатель \(  \large x  \) родился в США" является одноместным предикатом \(  \large A(x)  \), определённым на множестве писателей. Если вместо \(  \large x  \) подставить \(  \large a_1=  \)"Рэй Брэдбери", то получим истинное высказывание \(  \large A(a_1)  \), а если подставить \(  \large a_2=  \)"Александр Сергеевич Пушкин", то получим ложное высказывание \(  \large A(a_2)  \). Предложения "Писатель Рэй Брэдбери родился в США" и "Писатель Александр Сергеевич Пушкин родился в США" являются формализациями предиката \(  \large A(x)  \).
Отметим, что Рэй Брэдбери и Александр Сергеевич Пушкин - единичные имена.

Замечание 14.19. Как видно из двух последних примеров, формализация и интерпретация не дают однозначного результата.
 
Сказали спасибо: LaLa, Alexey

Оффлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 14. Понятие и виды предикатов
« Ответ #2 : Декабрь 25, 2017, 06:41:26 pm »
Рассмотрим виды предикатов. Классификация предикатов аналогична классификации формул алгебры высказываний. Это не случайно, так как предикаты и формулы алгебры высказываний являются абстрактными образами высказываний, а высказывания могут быть истинными или ложными. Понятия истины и лжи являются фундаментом классификации предикатов.

***

В зависимости от того, имеет ли предикат истинные интерпретации, различают выполнимые и невыполнимые (тождественно ложные) предикаты. В зависимости от того, имеет ли предикат ложные интерпретации, различают опровержимые и неопровержимые (тождественно истинные) предикаты.

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

Определение 14.5. Предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) называется выполнимым, если найдутся такие элементы \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \), что высказывание \(  \large A(a_1,a_2, \ldots, a_n)  \) истинно.

Определение 14.6. Предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) называется невыполнимым (тождественно ложным), если для любых элементов \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \) высказывание \(  \large A(a_1,a_2, \ldots, a_n)  \) ложно.

Определение 14.7. Предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) называется опровержимым, если найдутся такие элементы \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \), что высказывание \(  \large A(a_1,a_2, \ldots, a_n)  \) ложно.

Определение 14.8. Предикат \(  \large A(x_1,x_2, \ldots, x_n)  \) называется неопровержимым (тождественно истинным), если для любых элементов \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \) высказывание \(  \large A(a_1,a_2, \ldots, a_n)  \) истинно.

Замечание 14.20. Тождественно ложные предикаты будем обозначать через \(  \large 0(x_1,x_2, \ldots, x_n)  \), а тождественно истинные - через \(  \large 1(x_1,x_2, \ldots, x_n)  \).

Пример 14.7. Трёхместный предикат \(  \large x^2+y^2+z^2 <1 \), где \(  \large x,y,z   \) - вещественные числа, является тождественно ложным, а двуместный предикат "\(  \large x+y  \) делится на \(  \large 3  \)", где \(  \large x,y \in \{ 3,9,12,21 \}  \), является тождественно истинным.

Замечание 14.21. Выполнимость, опровержимость, тождественная ложность  и тождественная истинность предиката определяется для конкретных множеств \(  \large M_i, \ i=1,2, \ldots, n  \). Один и тот же предикат может быть одного типа, если он определён  на одном наборе множеств, и другого типа, если на другом.

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

1) выполним тогда и только тогда, когда \(  \large \mathcal{A} \not = \not \circ  \);

2) тождественно ложен тогда и только тогда, когда \(  \large \mathcal{A} = \not \circ  \);

3) опровержим тогда и только тогда, когда \(  \large \mathcal{A} \not = M_1 \times M_2 \times \ldots \times M_n  \);

4) тождественно истинен тогда и только тогда, когда \(  \large \mathcal{A}  = M_1 \times M_2 \times \ldots \times M_n  \).

Замечание 14.23.

а)Любой тождественно истинный предикат выполним. Но не всякий выполнимый предикат тождественно истинен. Рассмотрим, например, предикат \(  \large n-m=1  \), определённый на множестве натуральных чисел. Он выполним, так как высказывание \(  \large 2-1=1  \) истинно, но не тождественно истинен (опровержим), поскольку высказывание \(  \large 4-2=1  \) ложно. Значит, множество тождественно истинных предикатов является подмножеством множества выполнимых предикатов, но не совпадает с ним.

б) Существуют предикаты, которые являются выполнимыми и опровержимыми. Пример мы уже привели выше. Следовательно, множества выполнимых и опровержимых предикатов пересекаются.

в) Ни один тождественно истинный предикат не является тождественно ложным, и наоборот. Значит, множества тождественно истинных и тождественно ложных предикатов не пересекаются.

г) Всякий тождественно ложный предикат опровержим. Но не всякий опровержимый предикат тождественно ложен. Так, предикат \(  \large x>5  \), где \(  \large x  \) - целое число, опровержим (высказывание \(  \large -10>5  \) ложно), но он не тождественно ложен (высказывание \(  \large 11>5  \) истинно).

Связь типов предикатов отображена на диаграмме Эйлера-Венна, где ТИП - тождественно истинные предикаты, ТЛП - тождественно ложные предикаты, ОП - опровержимые предикаты, ВП - выполнимые предикаты.

Замечание 14.24. Тождественная истинность (тождественная ложность) нульместного предиката (высказывания) означает истинность (ложность) этого высказывания. Очевидно, в данном случае тождественная истинность (тождественная ложность) эквивалентна выполнимости (опровержимости).
 

Оффлайн Admin

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