Предикат

Что такое предикат

Одна из важнейших особенности логики предикатов в том, что все общие имена (такие, как «цветок», «деревня»), знаки свойств («розовый», «большая») и знаки отношений («красивее», «роднее») рассматриваются как относящиеся к одной категории знаков: категории предикаторов (иначе говоря, предметно-истинных функторов).

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

Другой пример: функция, которая соответствует предикатору «больше», сопоставляет истину каждой паре объектов или субъектов, один из которых больше. Например, такая пара, как «слон, мышь». Но всем остальным парам, по типу «мышь, слон» и «мышь, мышь», такая функци будет сопоставлять оценку «ложь».

Предикаторы могут быть:

1. Одноместные. Те, которые представляют предметно-истинные функции от одного аргумента. Например, «человек».
2. Двухместные. Те, которым соответствуют функции двух аргументов. Например, «больше».
3. Другие, в зависимости от количества соответствующих аргументов.

Логические операции над предикатами

Так как предикаты принимают два значения, «истина» и «ложь» (1 и 0), к ним можно применить все операции алгебры логики.

Представим, что в неком множестве N определены два предиката  P(x) и Q(x). Рассмотрим все операции с ними по-отдельности.

Дизъюнкция двух предикатов — предикат \(P(x)\vee Q(x)\), принимающий значение «ложь» исключительно при значениях, когда каждый предикат принимает значение «ложь». Во всех остальных случаях он принимает значение «истина».

Область истины в этом случае — объединение областей истинности обоих утверждений.

\(I_{P\vee Q}I_P\cap I_Q.\)

Отрицание высказывания P(x) — предикат \(\overline{P(x)}\), принимающий значение «истина» при всех значениях \(x\in N\), когда высказывание P(x) принимает значение «истина».

Область истины здесь — дополнение множества истинности утверждения P(x) до множества N, иначе говоря \(I_overline{P}=N\I_P=CI_P.\)

При каждом x справедливо равенство \(P(x)\rightarrow Q(x)=\overline{P(x)}\vee Q(x)\), а это значит, что область истинности \(P(x)\rightarrow Q(x)\) — объединение дополнения области истинности P(x) до множества N и области истинности предиката Q(x). Обозначается выражением: \(I_{P\rightarrow Q}=I_\overline P\cup I_Q.\)

При каждом фиксированном x справедливо равенство \(P(x)\leftrightarrow Q(x)=(\overline P\vee Q)\wedge(P\vee\overline{Q)}\). Это значит, что области истинности утверждения \(P(x)\leftrightarrow Q(x)\) — конъюнкция объединений дополнения области истинности \(P(x)\) до множества N и области истинности \(Q(x)\), а также области истинности \(Q(x)\) до множества N и ОИ \(P(x)7\). Обозначается формулой \(I_{P\leftrightarrow Q}=(I_\overline P\cup I_Q)\cap(I_\overline Q\cup I_P).\)

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

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

Кванторы впервые были определены немецким математиком Готлобом Фреге. Он упомянул их в своей работе «Begriffsschrift» («Исчисление понятий», 1879 года). Однако сам термин был изобретен английским логиком Чарльзом Пирсом в 1885 году. Вместе со словом «квантор» он ввел также и термин «квантификация», который означает измерение качеств признаков.

Обозначение кванторов

Символическое обозначение кванторов придумал итальянский математик Дж. Пеано в 90-е годы XIX века. Выглядят эти символы так:

\(\forall\) — «для любого», «для каждого», «для всех»;

\(\exists\) — «существует», «найдётся».

Кроме самих кванторов и вместе с ними используют обозначения \(«!», «:», «|»\), которые являются сокращениями:

! – «единственный»;

: – «такой, что»;

| – «такой, что».

Знак «:» обычно используется в формулировках определений или теорем, которые записываются с помощью кванторов. Знак «|» применяется в определениях множеств.

Виды кванторов

Квантор общности \(\forall\)

Оно истинно только в том случае, когда \(P(x)\) — тождественно истинен. В ином случае данное высказывание ложно.

Оно истинно только в том случае, когда одноместный предикат \(P(x, a_2, …, a_n)\) на множестве \(N_1\) тождественно истинен. В противном случае оно ложно.

Квантор существования \( \exists\)

Операция связывания квантором существования — это правило, по которому каждому одноместному утверждению \(P(x)\) на множестве N соответствует высказывание \( (\exists)(P(x))\), которое звучит так: « существует \( [значение] x\), такое, что \( P(x)\), [истинное высказывание]»).

Это высказывание ложно только, когда \(P(x)\), тождественно ложен. В противном случае оно истинно.

Операция связывания квантором существования по переменной \(x_1\) — это правило, в соответствие с которым каждому n-местному \((n\geqslant2)\) высказыванию \(P(x_1, x_2, …, x_n)\) на множествах \(N_1, N_2, …, N_n\) соответствует новый (n-1-местный предикат. Он обозначается как \((\exists)(P(x_1, x_2, …, x_n)\). Это высказывание ложно только в том случае, если одноместный предикат \((P(x_1, a_2, …, a_n)\) на множестве \(N_1\) тождественно ложен. В противном случае данное высказывание истинно.

Примеры применения

Использование предикатов

1. Пусть предикат \(P(x, y)\): \(«x=y»\) обозначает отношение равенства, в котором x и y принадлежат множеству целых чисел. Тогда утверждение P будет истинным для всех равных x и y.
2. Дан предикат Работает \((x, y, z)\) для отношения «x работает в городе y в компании z».
3. Дан предикат Нравится \((x, y)\) для «x нравится y» для x и y, которые принадлежат множеству людей N.

Использование кванторов

Пусть предикат «x кратно 5». Тогда с помощью квантора общности можно записать ложные высказывания:

• любое натуральное число делится на 5;
• каждое натурально число делится на 5;
• все натуральные числа делятся на 5.

В этом случае решение будет выглядеть так:

\((\forall_x\in N)P(x).\)

Чтобы обозначить истинные высказывания, используем квантор существования:

• существуют натуральные числа, которые делятся на 5;
• найдется натуральное число, которое делится на 5;
• хотя бы одно натуральное число делится на 5.

В записи оно будет выглядеть так:

\((\exists_x\in N)P(x).\)

На множестве x простых чисел существует предикат: «Простое число является нечетным». Если мы поставим перед предикатом слово «любое», то получим ложное высказывание «Любое простое число является нечетным». Если мы поставим перед предикатом слово «существует», то получим истинное высказывание «Существует простое число, которое является нечетным».

Так, предикат можно превратить в высказывание, если поставить перед ним квантор.