Предикат

Предика́т (лат. praedicatum «заявленное, упомянутое, сказанное») — это утверждение, высказанное о субъекте. Субъектом высказывания называется то, о чём делается утверждение.

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

Далее в этой статье слово предикат используется в значении высказывательной формы.

Определение

Предика́т ([math]\displaystyle{ n }[/math]-местный, или [math]\displaystyle{ n }[/math]-арный) — это функция с множеством значений [math]\displaystyle{ \{ 0,1 \} }[/math] (или {ложь, истина}), определённая на множестве [math]\displaystyle{ M={{M}_{1}}\times {{M}_{2}}\times \ldots \times {{M}_{n}} }[/math]. Таким образом, каждый набор элементов множества [math]\displaystyle{ M }[/math] характеризуется либо как «истинный», либо как «ложный».

Предикат можно связать с математическим отношением: если кортеж [math]\displaystyle{ (m_1, m_2,\dots, m_n) }[/math] принадлежит отношению, то предикат будет возвращать на нём 1. В частности, одноместный предикат определяет отношение принадлежности некоторому множеству.

Предикат — один из элементов логики первого и высших порядков. Начиная с логики второго порядка, в формулах можно ставить кванторы по предикатам.

Предикат называют тождественно-истинным и пишут:

[math]\displaystyle{ P\left ( x_1, ..., x_n \right) \equiv 1 }[/math]

если на любом наборе аргументов он принимает значение [math]\displaystyle{ 1 }[/math].

Предикат называют тождественно-ложным и пишут:

[math]\displaystyle{ P\left ( x_1, ..., x_n \right) \equiv 0 }[/math]

если на любом наборе аргументов он принимает значение [math]\displaystyle{ 0 }[/math].

Предикат называют выполнимым, если хотя бы на одном наборе аргументов он принимает значение [math]\displaystyle{ 1 }[/math].

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

Примеры

Обозначим предикатом [math]\displaystyle{ EQ(x, y) }[/math] отношение равенства («[math]\displaystyle{ x = y }[/math]»), где [math]\displaystyle{ x, y \in \mathbb{R} }[/math]. В этом случае предикат [math]\displaystyle{ EQ }[/math] будет принимать истинное значение для всех равных [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math].

Более житейским примером может служить предикат ПРОЖИВАЕТ[math]\displaystyle{ (x, y, z) }[/math] для отношения «[math]\displaystyle{ x }[/math] проживает в городе [math]\displaystyle{ y }[/math] на улице [math]\displaystyle{ z }[/math]» или ЛЮБИТ[math]\displaystyle{ (x, y) }[/math] для «[math]\displaystyle{ x }[/math] любит [math]\displaystyle{ y }[/math]» для [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] принадлежащих [math]\displaystyle{ M }[/math] , где множество [math]\displaystyle{ M }[/math] — это множество всех людей.

Предикат — это то, что утверждается или отрицается о субъекте суждения.

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

Предикаты, так же, как высказывания, принимают два значения: истинное и ложное, поэтому к ним применимы все операции логики высказываний. Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.

Логические операции

Конъюнкцией двух предикатов A(x) и B(x) называется новый предикат [math]\displaystyle{ A\left( x \right)\wedge B\left( x \right) }[/math], который принимает значение «истина» при тех и только тех значениях х из Т, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях. Множеством истинности Т предиката [math]\displaystyle{ A\left( x \right)\wedge B\left( x \right) }[/math] является пересечение множеств истинности предикатов A(x) —T1 и B(x) — T2, то есть T = T1 ∩ T2. Например: A(x): «x — чётное число», B(x): «x кратно 3». A(x) B(x) — «x — чётное число и x кратно 3». То есть предикат «x делится на 6».

Дизъюнкцией двух предикатов A(x) и B(x) называется новый предикат [math]\displaystyle{ A\left( x \right)\vee B\left( x \right) }[/math], который принимает значение «ложь» при тех и только тех значениях x из Т, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Областью истинности Т предиката [math]\displaystyle{ A\left( x \right)\vee B\left( x \right) }[/math] является объединение областей истинности предикатов A(x) — Т1 и B(x) — Т2, то есть Т = Т1 ⋃ Т2.

Отрицанием предиката A(x) называется новый предикат ¬A(x), который принимает значение «истина» при тех и только тех значениях x из T, при которых предикат A(x) принимает значение «ложь», и принимает значение "ложь" если A(x) принимает значение «истина».

Множеством истинности предиката x X является дополнение T' к множеству T в множестве X.

Импликацией предикатов A(x) и B(x) называется новый предикат [math]\displaystyle{ A\left( x \right)\Rightarrow B\left( x \right) }[/math], который является ложным при тех и только тех значениях x из T, при которых A(x) принимает значение «истина», а B(x) — значение «ложь», и принимает значение «истина» во всех остальных случаях. Читают: «Если A(x), то B(x)».

Например. A(x): «Натуральное число x делится на 3». B(x): «Натуральное число x делится на 4», можно составить предикат: «Если натуральное число x делится на 3, то оно делится и на 4». Множеством истинности предиката [math]\displaystyle{ A\left( x \right)\Rightarrow B\left( x \right) }[/math] является объединение множества T2 — истинности предиката B(x) и дополнения к множеству T1 истинности предиката A(x).

Кванторные операции

Квантор всеобщности [math]\displaystyle{ \forall }[/math]
Квантор существования [math]\displaystyle{ \exists }[/math]
Квантор существования по переменной [math]\displaystyle{ x }[/math]₁

См. также

Литература

Гуц А. К. Математическая логика и теория алгоритмов. — Наследие, Диалог-Сибирь, 2003.
Ершов Ю. Л., Палютин Е. А. Математическая логика. — М.: Наука, Физматлит, 1987.
Игошин В. И. Математическая логика и теория алгоритмов. — Academia, 2008.
Клини С. К. Математическая логика. — М.: Мир, 1973.
Мендельсон Э. Введение в математическую логику. — М.: Наука, 1971.
Новиков П. С. Элементы математической логики. — М.: Наука, 1973.