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

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

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

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

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.