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

Понятие предиката

В логике высказываний исследуются простейшие высказывания, которые могут иметь одну из двух истинностных характеристик:

• истина,
• ложь.

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

Рассмотрим несколько примеров предикатов:

• х – нечетное число,
• x на два года старше, чем z,
• в х больше жителей, чем в y.

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

В предикате может фигурировать один объект (аргумент) или большее их количество:

• в одноместных предикатах отражается наличие или отсутствие у объекта каких-то свойств,
• в предикатах от нескольких переменных выражаются отношения между объектами в рамках предметной области.

Рассмотрим двуместный предикат: p(x, y) = (x > y). Предметная область – действительные числа. Множество истинности – множество точек, лежащих ниже прямой y = x (в точках, лежащих на этой прямой и выше нее, предикат превращается в ложное выражение).

Операции над предикатами

Все операции над предикатами можно разделить на две категории:

• операции, аналогичные операциям над высказываниями;
• операции квантификации.

К первой группе относятся следующие операции:

• конъюнкция – в результате из двух исходных получается новый предикат, принимающий значение истины только для тех значений аргументов, при которых истинным выражением являются оба исходных предиката,
• дизъюнкция – в результате из двух исходных получается новый предикат, принимающий значение истины для тех значений аргументов, при которых хотя бы один из исходных предикатов обращается в истинное выражение,
• отрицание – в результате из исходного предиката получается новый предикат, принимающий значение истины для тех аргументов, с которыми исходный предикат обращался в ложь,
• импликация – в результате из двух исходных получается новый предикат, принимающий значение ложь для тех значений, при которых первый предикат из пары исходных превращается в истинное выражение, а второй – в ложное (во всех остальных случаях новый предикат принимает форму истинного выражения),
• эквиваленция – в результате из двух исходных получается новый предикат, принимающий значение истины для тех значений, при которых одновременно оба исходных предиката являются истинными выражениями или одновременно оба исходных предиката являются ложными выражениями.

Вторая группа операций – операции квантификации, или операции навешивания кванторов. Аналогов этим операциям в алгебре высказываний нет. Существуют два основных квантора:

• квантор всеобщности. Он связывает аргумент, превращая предикат в высказывание, принимающее истинное значение только в том случае, если этот предикат истинен для любого элемента предметной области;
• квантор существования. Он связывает аргумент, превращая предикат в высказывание, принимающее истинное значение в том случае, если в предметной области есть хотя бы один элемент, превращающий предикат в истинное высказывание.

В математике часто используются выражения вида «хотя бы n» («по меньшей мере n»), «n и только n» («ровно n»), «не более n», где n – некоторое натуральное число. Такие выражения называют численными кванторами. Они обладают чисто логическим смыслом – их можно заменить равнозначными выражениями, состоящими из логических терминов и знака тождества (не включающими числительные).

Рассмотрим пример при n = 1: словосочетание «по меньшей мере один объект» заменяется на «существует объект»; «не более чем один объект» - на «если существуют объекты, то они совпадают». Словосочетание «один и только один объект» - это конъюнкция приведенных конструкций.

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

Пример обыденного отрицания: «Москва – столица России» и «Москва – не столица России».

В случае с квантифицированными предложениями такой прием не работает.

Не являются взаимными отрицаниями высказывания: «Все кошки любят сметану» и «Все кошки не любят сметану». Оба высказывания ложны, а в случае отрицания одно высказывание из пары должно быть истинным, а второе ложным. Также не являются отрицаниями друг друга истинные высказывания «Некоторые кошки не любят сметану» и «Некоторые кошки любят сметану».

В случае с квантифицированными предикатами можно использовать один из двух способов построения отрицания:

• универсальный вариант – добавление словосочетания «неверно, что» в начало высказывания;
• замена квантора двойственным (квантора существования – на квантор всеобщности, а квантора всеобщности – на квантор существования) с добавлением отрицательной частицы в предикат.

Итак, отрицанием высказывания «Все кошки любят сметану» будут высказывания «Неверно, что все кошки любят сметану» и «Некоторые кошки не любят сметану».