Предикат

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

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

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

Определение

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

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

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

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

<math> P\left ( x_1, ..., x_n \right) \equiv 1 </math>

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

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

<math> P\left ( x_1, ..., x_n \right) \equiv 0 </math>

если на любом наборе аргументов он принимает значение 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(x) и B(x) называется новый предикат <math>A\left( x \right)\wedge B\left( x \right)</math>, который принимает значение «истина» при тех и только тех значениях х из Т, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях. Множеством истинности Т предиката <math>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>A\left( x \right)\vee B\left( x \right)</math>, который принимает значение «ложь» при тех и только тех значениях x из T, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Областью истинности предиката <math>A\left( x \right)\vee B\left( x \right)</math> является объединение областей истинности предикатов A(x) и B(x).

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

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

Импликацией предикатов A(x) и B(x) называется новый предикат <math>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>A\left( x \right)\Rightarrow B\left( x \right)</math> является объединение множества T2 — истинности предиката B(x) и дополнения к множеству T1 истинности предиката A(x).

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

• Квантор всеобщности <math>\forall</math>
• Квантор существования <math>\exists</math>
• Квантор существования по переменной <math>x</math>₁

См. также

• Исчисление предикатов
• Предикатив
• Определяющий предикат

Литература

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

Отрывок, характеризующий Предикат

Вдруг князь Ипполит поднялся и, знаками рук останавливая всех и прося присесть, заговорил:
– Ah! aujourd'hui on m'a raconte une anecdote moscovite, charmante: il faut que je vous en regale. Vous m'excusez, vicomte, il faut que je raconte en russe. Autrement on ne sentira pas le sel de l'histoire. [Сегодня мне рассказали прелестный московский анекдот; надо вас им поподчивать. Извините, виконт, я буду рассказывать по русски, иначе пропадет вся соль анекдота.]
И князь Ипполит начал говорить по русски таким выговором, каким говорят французы, пробывшие с год в России. Все приостановились: так оживленно, настоятельно требовал князь Ипполит внимания к своей истории.
– В Moscou есть одна барыня, une dame. И она очень скупа. Ей нужно было иметь два valets de pied [лакея] за карета. И очень большой ростом. Это было ее вкусу. И она имела une femme de chambre [горничную], еще большой росту. Она сказала…
Тут князь Ипполит задумался, видимо с трудом соображая.
– Она сказала… да, она сказала: «девушка (a la femme de chambre), надень livree [ливрею] и поедем со мной, за карета, faire des visites». [делать визиты.]
Тут князь Ипполит фыркнул и захохотал гораздо прежде своих слушателей, что произвело невыгодное для рассказчика впечатление. Однако многие, и в том числе пожилая дама и Анна Павловна, улыбнулись.
– Она поехала. Незапно сделался сильный ветер. Девушка потеряла шляпа, и длинны волоса расчесались…
Тут он не мог уже более держаться и стал отрывисто смеяться и сквозь этот смех проговорил:
– И весь свет узнал…
Тем анекдот и кончился. Хотя и непонятно было, для чего он его рассказывает и для чего его надо было рассказать непременно по русски, однако Анна Павловна и другие оценили светскую любезность князя Ипполита, так приятно закончившего неприятную и нелюбезную выходку мсье Пьера. Разговор после анекдота рассыпался на мелкие, незначительные толки о будущем и прошедшем бале, спектакле, о том, когда и где кто увидится.


Поблагодарив Анну Павловну за ее charmante soiree, [очаровательный вечер,] гости стали расходиться.
Пьер был неуклюж. Толстый, выше обыкновенного роста, широкий, с огромными красными руками, он, как говорится, не умел войти в салон и еще менее умел из него выйти, то есть перед выходом сказать что нибудь особенно приятное. Кроме того, он был рассеян. Вставая, он вместо своей шляпы захватил трехугольную шляпу с генеральским плюмажем и держал ее, дергая султан, до тех пор, пока генерал не попросил возвратить ее. Но вся его рассеянность и неуменье войти в салон и говорить в нем выкупались выражением добродушия, простоты и скромности. Анна Павловна повернулась к нему и, с христианскою кротостью выражая прощение за его выходку, кивнула ему и сказала:
– Надеюсь увидать вас еще, но надеюсь тоже, что вы перемените свои мнения, мой милый мсье Пьер, – сказала она.
Когда она сказала ему это, он ничего не ответил, только наклонился и показал всем еще раз свою улыбку, которая ничего не говорила, разве только вот что: «Мнения мнениями, а вы видите, какой я добрый и славный малый». И все, и Анна Павловна невольно почувствовали это.
Князь Андрей вышел в переднюю и, подставив плечи лакею, накидывавшему ему плащ, равнодушно прислушивался к болтовне своей жены с князем Ипполитом, вышедшим тоже в переднюю. Князь Ипполит стоял возле хорошенькой беременной княгини и упорно смотрел прямо на нее в лорнет.
– Идите, Annette, вы простудитесь, – говорила маленькая княгиня, прощаясь с Анной Павловной. – C'est arrete, [Решено,] – прибавила она тихо.
Анна Павловна уже успела переговорить с Лизой о сватовстве, которое она затевала между Анатолем и золовкой маленькой княгини.
– Я надеюсь на вас, милый друг, – сказала Анна Павловна тоже тихо, – вы напишете к ней и скажете мне, comment le pere envisagera la chose. Au revoir, [Как отец посмотрит на дело. До свидания,] – и она ушла из передней.
Князь Ипполит подошел к маленькой княгине и, близко наклоняя к ней свое лицо, стал полушопотом что то говорить ей.
Два лакея, один княгинин, другой его, дожидаясь, когда они кончат говорить, стояли с шалью и рединготом и слушали их, непонятный им, французский говор с такими лицами, как будто они понимали, что говорится, но не хотели показывать этого. Княгиня, как всегда, говорила улыбаясь и слушала смеясь.
– Я очень рад, что не поехал к посланнику, – говорил князь Ипполит: – скука… Прекрасный вечер, не правда ли, прекрасный?
– Говорят, что бал будет очень хорош, – отвечала княгиня, вздергивая с усиками губку. – Все красивые женщины общества будут там.
– Не все, потому что вас там не будет; не все, – сказал князь Ипполит, радостно смеясь, и, схватив шаль у лакея, даже толкнул его и стал надевать ее на княгиню.
От неловкости или умышленно (никто бы не мог разобрать этого) он долго не опускал рук, когда шаль уже была надета, и как будто обнимал молодую женщину.
Она грациозно, но всё улыбаясь, отстранилась, повернулась и взглянула на мужа. У князя Андрея глаза были закрыты: так он казался усталым и сонным.
– Вы готовы? – спросил он жену, обходя ее взглядом.
Князь Ипполит торопливо надел свой редингот, который у него, по новому, был длиннее пяток, и, путаясь в нем, побежал на крыльцо за княгиней, которую лакей подсаживал в карету.