Предикат — понятие логики и программирования¶

Предикат — это выражение (формула, функция или конструкция языка программирования), которое принимает значение «истина» или «ложь». Слово происходит от латинского praedicatum — «утверждаемое, сказуемое». В логике предикат — это функция истинности, заданная на некотором множестве объектов; в математике — условие, которому элементы множества удовлетворяют или не удовлетворяют; в программировании — условие, результат которого используется для принятия решений (ветвление, фильтрация, отбор).

¶Предикат в математической логике

В классическом исчислении предикатов предикат — это функция, значениями которой являются «истина» и «ложь». Если переменная x пробегает множество M, то предикат P(x) называется формулой с переменной x; множество всех x, для которых P(x) истинен, называется областью истинности предиката.

Пример: P(x) = «x чётное число». Для x = 4 предикат истинен, для x = 7 — ложен. Область истинности на целых числах — множество чётных чисел.

Основные логические связки, применяемые к предикатам:

• отрицание (¬P) — инвертирует значение;
• конъюнкция (P ∧ Q) — истинна, когда оба предиката истинны;
• дизъюнкция (P ∨ Q) — истинна, если хотя бы один истинен;
• импликация (P → Q) — ложна только когда P истинен, а Q ложен;
• эквивалентность (P ↔ Q) — истинна при совпадении значений.

Кванторы расширяют язык предикатов: квантор всеобщности (∀x) означает «для всех x», квантор существования (∃x) — «существует такое x». Например, «∀x (x + 0 = x)» читается как «для любого x верно, что x плюс ноль равно x».

¶Предикат в математике

В математике предикат — это свойство или условие, которому объекты подчиняются или не подчиняются. Термин широко используется в теории множеств, алгебре и анализе. Например, «x > 5» — предикат на вещественных числах; «M — компактное пространство» — предикат на топологических пространствах.

Предикаты лежат в основе определений. Определение «чётное число» — это предикат «делится на два без остатка». Аксиоматика теории множеств по Зермело — Френкелю построена на предикате принадлежности x ∈ y.

¶Предикат в теории баз данных

В реляционной алгебре и языке SQL предикат — это условие отбора строк. WHERE-часть SQL-запроса содержит предикат: SELECT * FROM users WHERE age > 18. Строки, для которых предикат истинен, попадают в результат; остальные отбрасываются.

Теоретико-множественная модель данных, предложенная Эдгаром Коддом в 1970 году, строится именно на предикатах: каждая таблица — это набор кортежей, удовлетворяющих некоторому предикату.

¶Предикат в программировании

В языках программирования предикат — это функция (или выражение), возвращающая логическое значение. В Python это может быть лямбда-функция или обычное условие, в SQL — выражение в WHERE, в языках семейства C — выражение в if, while, for.

Пример на Python:

```python def is_even(x): return x % 2 == 0

numbers = [1, 2, 3, 4] evens = list(filter(is_even, numbers)) # [2, 4] ```

Здесь is_even — предикат: он принимает число и возвращает True или False. Функция filter применяет предикат к каждому элементу списка и оставляет только те, для которых предикат истинен.

Предикаты используются в фильтрации коллекций (filter, List.where, select), в условных операторах, в генераторах множеств и в декларативных языках (Prolog, Haskell, SQL). В Prolog предикат — это основная единица знания: программа представляет собой набор предикатов вида parent(ivan, petr). — «Иван — родитель Петра».

¶Предикат в философии и риторике

В традиционной логике, восходящей к Аристотелю, предикат — это часть суждения, которая отрицается или утверждается о субъекте. В суждении «Сократ — человек» субъект — Сократ, предикат — «человек». Классическая схема «субъект — предикат» легла в основу суждений силлогистики.

¶Различие с термином «предсказание»

Предикат не следует путать с предсказанием (prediction). Предикат ничего не прогнозирует — он лишь описывает истинностное значение условия в данный момент. В машинном обучении иногда используется термин «предиктор» (predictor) — признак, по которому строится модель; это другое понятие, хотя этимологически оно родственно.

¶История

Исчисление предикатов было создано Готлобом Фреге в 1879 году в работе «Бegriffsschrift» («Понятийная запись»). Ранее, в 1847 году, Джордж Буль заложил основы алгебры логики, где высказывания обрабатывались как значения «истина» и «ложь». Развитие теории предикатов связано с именами Бертрана Рассела, Артура Гёделя (теорема о полноте и неполноте), Альонасо Чёрча и Алана Тьюринга.

¶Исторические источники и литература

• Фреге Г. Бegriffsschrift, 1879.
• Клейни С. Введение в математику. Синтаксис и семантика.
• Кодд Э. Реляционный модель данных для больших банков данных, 1970.
• Кларк Д., Тавани Дж. Логика для компьютерных наук.
• Дейкстра Э. О структуре программы «goto».