16. Понятие предиката. Примеры. Виды предикатов. Равносильные предикаты. Операции над предикатами

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

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

Рассмотрим следующие предложения:

1) “x – простое число” – P(x), N.

2) “x>y” – Q(x,y), Z, Q.

3) “x+y=z” – R(x,y,z), R.

Каждое из предложений 1) – 3) не является высказыванием, так как мы не можем сказать, истинны они или ложны.

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

1) P(3) - “3 – простое число” – истинное высказывание,

P(4) – ложное высказывание.

2) Q( ) –истинное высказывание,

Q( ) - ложное высказывание.

3) R(2,3,5) – истинное высказывание, и так далее.

Предложение 1) – 3) являются примерами предикатов.

Определение 14. –местным предикатом, определенным на множествах , или на множестве , называется предложение, содержащее переменных , которое превращается в высказывание при замене переменной на , , , и обозначается .

Замечание. В определении 14 полагают, что N . При получаем 0-местный предикат, то есть высказывание высказывание – это частный случай предиката.

Переменные в предикате называются предметными переменными.

Множество называется множеством (областью) допустимых значений переменной , .

Определение 15. Пусть - предикат на множествах .

Говорят, что последовательность , где , , удовлетворяет предикату , если - истинное высказывание.

Определение 16. Пусть - предикат на множествах .

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

Виды предикатов

Определение 17. Предикат (на множествах ) называется тождественно истинным, если при любых допустимых значениях его переменных он превращается в истинное высказывание.

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

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

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

Лемма 1. Пусть - предикат на множествах справедливы следующие утверждения:

1) - тождественно истинный предикат .

2) - тождественно ложный предикат Ø.

3) - выполнимый предикат Ø.

4) - опровержимый предикат .

Доказательство осуществляется непосредственной проверкой.

Примеры.

1. - R – тождественно ложный предикат, опровержимый.

2. “x делится на 5” - Z – выполнимый, опровержимый.

3. - N – тождественно истинный предикат, выполнимый.

Равносильность предикатов.

Определение 21. Два -местных предиката и на множествах называются равносильными, если выполняется утверждение: , и обозначается .

Определение 22'. Два -местных предиката и , заданных на одних и тех же множествах, называются равносильными, если их множества истинности совпадают, то есть если .

Лемма 2. Отношение равносильности является отношением эквивалентности на множестве всех - местных предикатов, заданных на множествах .

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

1. Рефлексивность: .

2. Симметричность: Пусть .

3. Транзитивность: Пусть и и . Лемма доказана.

Замечание 1.

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

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

Пример.

Предикаты , R и , R равносильны.

Следовательно, (-3,-2) – решение неравенства (то есть множество истинности предиката ).

Логические операции над предикатами

Над предикатами можно выполнять те же логические операции, что и над высказываниями: ┐, .

I. Отрицание предиката.

Определение 23. Отрицанием - местного предиката , заданного на множестве , называется -местный предикат на множестве , обозначаемый ┐ (читается “неверно, что ”), такой, что высказывание ┐ является отрицанием высказывания .

II. Конъюнкция предикатов.

Определение 24. Конъюнкцией -местного предиката , заданного на множестве , и -местного предиката , заданного на множестве , называется -местный предикат на множестве , обозначаемый (читается “ и ”) такой, что высказывание является конъюнкцией высказываний и .

III. Дизъюнкция предикатов.

Определение 25. Дизъюнкцией -местного предиката , заданного на множестве , и -местного предиката , заданного на множестве , называется -местный предикат, заданный на множестве , обозначаемый (читается “ или ”), такой, что высказывание является дизъюнкцией высказываний и .

IV. и V. Импликация и эквиваленция предикатов.

Определение и - формулируются аналогично определениям 24 и 25.