Предикат

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Предикат в программировании — функция, принимающая один или более аргументов и возвращающая значения булева типа.

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

Определение[править | править вики-текст]

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

Предикат можно связать с математическим отношением: если (m1,m2,…,mn) принадлежит отношению, то предикат будет возвращать на ней 1. В частности, одноместный предикат определяет отношение принадлежности некоторому множеству.

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

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

 P\left ( x_1, ..., x_n \right) \equiv 1

если на любом наборе аргументов он принимает значение 1.

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

 P\left ( x_1, ..., x_n \right) \equiv 0

если на любом наборе аргументов он принимает значение 0.

Предикат называют выполнимым, если хотя бы на одном наборе аргументов он принимает значение 1.

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

Примеры[править | править вики-текст]

Обозначим предикатом EQ(x, y) отношение равенства («x = y»), где x и y принадлежат R (множеству вещественных чисел). В этом случае предикат EQ будет принимать истинное значение для всех равных x и y.

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

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

Операции над предикатами[править | править вики-текст]

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

Логические операции[править | править вики-текст]

Конъюнкцией двух предикатов А(х) и В(х) называется новый предикат A\left( x \right)\wedge B\left( x \right), который принимает значение «истина» при тех и только тех значениях х из Т, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях. Множеством истинности Т предиката A\left( x \right)\wedge B\left( x \right) является пересечение множеств истинности предикатов А(х) — Т1 и В(х) — Т2, то есть Т= Т1 ∩ Т2. Например: А(х): «х — четное число», В(х): « х кратно 3». А(х) В(х) — «х — четное число и х кратно 3». То есть предикат «х делится на 6».

Дизъюнкцией двух предикатов А(х) и В(х) называется новый предикат A\left( x \right)\vee B\left( x \right), который принимает значение «ложь» при тех и только тех значениях х из Т, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Областью истинности предиката A\left( x \right)\vee B\left( x \right) является объединение областей истинности предикатов А(х) и В(х).

Отрицанием предиката А(х) называется новый предикат, который принимает значение «истина» при всех значениях х из Т, при которых предикат А(х) принимает значение «ложь», если А(х) принимает значение «истина». Множеством истинности предиката, х Х является дополнение Т' к множеству Т в множестве Х.

Импликацией предикатов А(х) и В(х) называется новый предикат A\left( x \right)\Rightarrow B\left( x \right), который является ложным при тех и только тех значениях х из Т, при которых А(х) принимает значение «истина», а В(х) — значение «ложь», и принимает значение «истина» во всех остальных случаях. Читают: «Если А(х), то В(х)». Например. А(х): «Натуральное число х делится на 3». В(х): «Натуральное число х делится на 4», можно составить предикат: «Если натуральное число х делится на 3, то оно делится и на 4». Множеством истинности предиката A\left( x \right)\Rightarrow B\left( x \right) является объединение множества Т2 — истинности предиката В(х) и дополнения к множеству Т1 истинности предиката А(х).

Кванторные операции[править | править вики-текст]

См. также[править | править вики-текст]

Логотип Викисловаря
В Викисловаре есть статья «предикат»

Литература[править | править вики-текст]

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