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

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

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

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

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-местный предикат, то есть высказывание

Высказывание – это частный случай предиката.

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

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

Определение 14 можно сформулировать следующим образом:

Определение 14’. -местным предикатом на множествах называется функция , где - множество всех высказываний.

Например, в 1) - это функция P: N ; в 2) Q(x, y) - функция Z Q ; в 3) R(x, y, z): R ³ .

Поскольку или , то справедливо еще одно определение предиката.

Определение 14’’. -местным предикатом на множествах называется функция .

Определение 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) – решение неравенства (то есть множество истинности предиката ).

Лемма 3. Любые два тождественно истинных (тождественно ложных) предиката, заданных на одних и тех же множествах, равносильны. Обратно, если - тождественно истинный (тождественно ложный) предикат и , то - тождественно истинный (тождественно ложный) предикат.

Доказательство. 1) Пусть , - тождественно истинные предикаты на множествах и .

Пусть и - тождественно ложные предикаты Ø и Ø .

2) Пусть - тождественно истинный предикат и и - тождественно истинный предикат. Лемма доказана.

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

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

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

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

Лемма 4. Пусть - предикат, заданный на множестве .

Тогда

1) (┐ =()\ .

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

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

1) (┐ ={ │ ┐ =1} =

={ │ =0} = ()\ .

2) Пусть ┐ - тождественно истинный предикат (┐ = = ()\ =Ø - тождественно ложный предикат. Лемма доказана.

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

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

Замечание 1.

Операцию можно применить к предикатам, имеющим общие переменные. В этом

случае число переменных в новом предикате будет равно , где

- число переменных в первом предикате,

- число переменных во втором предикате,

- число переменных общих для обоих предикатов.

(Данное утверждение справедливо и для ).

Например,

R, Q, то есть - предикат на R Q,

R, R, то есть - предикат на R R.

Тогда и - предикат на R Q R.

Лемма 5. Пусть и - предикаты на множестве . Тогда

1) = ,

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

Доказательство. 1) = { │ =1}=

={ │ =1 и =1} .

Пусть и и

.

Из и = .

2) Пусть - тождественно истинный предикат = = = и и - тождественно истинные предикаты.

Лемма доказана.

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

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

Лемма 6.

Пусть и - предикаты на множестве . Тогда

1) = ;

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

предикаты.

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

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

Лемма 7. Пусть и - предикаты на множестве . Тогда

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

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