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

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

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

 или .

Определение. Конъюнкцией  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) совпадает с пересечением множеств истинности исходных предикатов:

.

Определение. Дизъюнкцией  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) совпадает с объединением множеств истинности исходных предикатов:

.