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

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

1. Отрицанием n – местного предиката Р(х₁, х₂, …, х_n), определенного на множествах М₁, М₂, …, М_n, называется новый n-местный предикат, определенный на тех же множествах, обозначаемый Р(х₁, х₂, …, х_n), который превращается в истинное высказывание при всех тех значениях предметных переменных, при которых исходный предикат превращается в ложное высказывание.

Теорема. Для n-местного предиката Р(х₁, х₂, …, х_n), определенного на множествах М₁, М₂, …, М_n, множество истинности его отрицания Р(х₁, х₂, …, х_n) совпадает с его дополнением множества истинности данного предиката:

или .

2. Конъюнкцией n – местного предиката Р(х₁, х₂, …, х_n), определенного на множествах М₁, М₂, …, М_n, и т-местного предиката Q(у₁, у₂, …, у_т), определенного на множествах N₁, N₂, …, N_m, называется новый (n + m)-местный предикат, определенный на множествах М₁, М₂, …, М_n, N₁, N₂, …, N_m, обозначаемый Р(х₁, х₂, …, х_n) Q(у₁, у₂, …, у_т), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката превращаются в истинные высказывания.

Теорема. Для n-местных предикатов Р(х₁, х₂, …, х_n) и Q(х₁, х₂, …, х_n), определенных на множествах М₁, М₂, …, М_n, множество истинности конъюнкции Р(х₁, х₂, …, х_n)  Q(х₁, х₂, …, х_n), совпадает с пересечением множеств истинности исходных предикатов:

.

3. Дизъюнкцией n – местного предиката Р(х₁, х₂, …, х_n), определенного на множествах М₁, М₂, …, М_n, и т-местного предиката Q(у₁, у₂, …, у_т), определенного на множествах N₁, N₂, …, N_m, называется новый (n + m)-местный предикат, определенный на множествах М₁, М₂, …, М_n, N₁, N₂, …, N_m, обозначаемый Р(х₁, х₂, …, х_n) Q(у₁, у₂, …, у_т), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых в истинное высказывание превращается по меньшей мере один исходный предикат.

Теорема. Для n-местных предикатов Р(х₁, х₂, …, х_n) и Q(х₁, х₂, …, х_n), определенных на множествах М₁, М₂, …, М_n, множество истинности дизъюнкции Р(х₁, х₂, …, х_n)  Q(х₁, х₂, …, х_n), совпадает с объединением множеств истинности исходных предикатов: .

Самостоятельная работа №8.

Тема 4.3 Кванторные операции над предикатами.

Специфическая природа предикатов, позволяет ввести над ними такие операции, которые не имеют аналогов среди операций над высказываниями. Имеются в виду две кванторные операции над предикатами.

1. Квантор общности

Для превращения одноместного предиката в высказывание нужно вместо его переменной подставить какой-нибудь конкретный предмет из области задания предиката. Имеется еще один способ для такого превращения – это применение к предикату операций связывания квантором общности или квантором существования. Каждая из этих операций ставит в соответствие одноместному предикату некоторое высказывание, истинное или ложное в зависимости от исходного предиката.

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

Словесным аналогом квантору общности  является: «для любого», «для каждого», «для всякого» и т.п.

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

Если одноместный предикат Р(х) задан на конечном множестве М = {a₁, a₂, …, a_n}, то высказывание эквивалентно конъюнкции Р(а₁) Р(а₂) …  Р(а_n).

Пример. Пусть х определен на множестве людей М, а Р(х) – предикат «х – смертен». Дать словесную формулировку предикатной формулы .

Решение. Выражение означает «все люди смертны». Оно не зависит от переменной х, а характеризует всех людей в целом, т. е. выражает суждение относительно всех х множества М.

Операцией связывания квантором общности по переменной х₁ называется правило, по которому каждому n-местному (n  2) предикату Р(х₁, х₂, …, х_n), определенному на множествах М₁, М₂, …, М_n, сопоставляется новый (n-1)-местный предикат, обозначаемый , который для любых предметов , превращается в высказывание , истинное в том и только в том случае, когда одноместный предикат , определенный на множестве М₁, тождественно истинен, и ложное в противном случае, то есть: