Алгебра предикатов

Высказывания являются утверждениями без предметных переменных, их можно рассматривать как 0-местные предикаты.

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

Отрицание n-местного предиката определяется как n-местный предикат , который при подстановке значений превращается в высказывание , являющееся отрицанием высказывания ;

Конъюнкция n-местных предикатов и определяется как n-местный предикат , который при подстановке значений превращается в высказывание , являющееся конъюнкцией высказываний и .

Для любого множества M допустимых значений предметных переменных предикатов множества истинности предикатов взаимосвязаны с логическими операциями по следующим формулам:

, ,

, ,

.

Для предикатов определены принципиально новые унарные операции – операции квантификации, или операции действия на предметные переменные кванторами.

Для каждой предметной переменной x рассматриваются два вида кванторов: – квантор общности по переменной x (читается «для всех x») и – квантор существования по переменной x (читается «существует x»).

Определение.

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

Определение.

Результатом действия квантора существования по переменной x на одноместный предикат называется высказывание , которое истинно на множестве M допустимых значений переменной x в том и только том случае, если предикат выполним на этом множестве M.

Определение.

Результатом действия квантора общности по переменной x₁ на n-местный предикат называется (n1)-местный предикат , который зависит от переменных и который при значениях в том и только том случае истинен на множестве M допустимых значений переменной x₁, если при любых значениях высказывание истинно.

Определение.

Результатом действия квантора существования по переменной x₁ на n-местный предикат называется (n1)-местный предикат , который зависит от переменных и который при значениях в том и только том случае истинен на множестве M допустимых значений переменной x₁, если при некотором значении высказывание истинно.Квантор существования и единственности определяется как сокращение записи следующей формулы

.

Результат действия такого квантора на предикат обозначается и читается «существует и единственен x, для которого выполняется »).

Ограниченный квантор существования определяется как сокращение записи следующей формулы

.

Результат действия такого квантора на предикат обозначается и и читается «существует x, удовлетворяющий , для которого выполняется ».

Ограниченный квантор общности определяется как сокращение записи следующей формулы

.

Результат действия такого квантора на предикат обозначается и читается «для всех x, удовлетворяющих , выполняется ».

Определение.

Алгеброй предикатов называется множество всех предикатов P с логическими операциями и операциями квантификации , для всех предметных переменных x.