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

Мы знаем, что выражение 5> 3 - истинное высказывание, а выражение " в неделе восемь дней" - ложное высказывание. Истинность этих и всех других высказываний определяется объективно и однозначно. Является ли выражение " n > 8" высказыванием? По форме оно похоже на высказывание, но не является таковым, поскольку невозможно сказать истинно оно или ложно. Все зависит от того, что представляет собою объект n. Выражение " x^k + y^k = z^k" - также не высказывание, но может стать таковым, если определить что такое к, x, y, z и каковы их значения. Таким образом, существуют выражения похожие по форме на высказывания, но не являющиеся ими. Такие выражения называют предикатами.

Предикатом P(x₁, x₂,..., x_n), заданным на множествах M₁, M₂,..., M_n называется функция P, отображающая их прямое произведение на двоичное множество, т.е. P: M₁ M₂ ... M_n {0, 1}. Множество M называется предметной областью предиката, x₁, x₂,..., x_n M называются предметными переменными или термами. Предикат представляет собой логическую функцию, принимающую, как и булевская функция значение " истина" или " ложь", когда ее предметные переменные принимают определенные значения.

Рассмотрим примеры. " x² - 5x + 6 = 0" - одноместный предикат на множестве комплексных чисел, при этом, например, если x = 2, то " 2² - 5 × 2 + 6 = 0" - истинное высказывание, а положив x = 7 получим " 7² - 5 × 7 + 6= 0" - " ложь". Выражение " X - брат Y" - двухместный предикат заданный на множестве людей. Здесь термы X и Y указывают места, на которые нужно поставить имена двух людей, чтобы получить правильно построенное высказывание. Очевидно, что X - лицо мужского пола, а Y - может выбираться из всего множества людей.

Всякий предикат P(x₁, x₂,..., x_n) определяет отношение R, такое, что (а₁, а₂,..., а_n) R тогда и только тогда, когда P(а₁, а₂,..., a_n) - " истина". В этом случае говорят, что отношение R задается областью истинности предиката P(x₁, x₂,..., x_n). Например, отношение R(M, N) = " расстояние на плоскости между точками M(x₁, y₁) и N(x₂, y₂) больше величины l" можно задать предикатом " (x₂ - x₁)² + (y₂ - y₁)² > l²".

Если в n-местный предикат на место одного из термов подставить определенный элемент из соответствующего множества, по предикат станет (n-1)-местным. Заменив все термы на конкретные значения из предметной области предиката, получим 0- местный предикат, т.е. высказывание. Например, " X- брат Y" - двухместный предикат, " X - брат Маши" - одноместный предикат, " Саша - брат Маши" - высказывание.