Глава 2 логика предикатов

§1. Понятие предиката и кванторных операций

В алгебре логики высказывания структура высказываний и их содержание во внимание не принимаются. В то же время существуют рассуждения, зависящие от содержания используемых в них высказываний. Например, всякий ромб  параллелограмм; АВСМ  ромб, следовательно, АВСМ  параллелограмм. Таким образом, возникает необходимость в построении такой логической системы, средствами которой можно анализировать структуру утверждений, составленных из элементарных высказываний. Такой логической системой является логика предикатов, содержащая логику высказываний в качестве своей части.

В логике предикатов элементарное утверждение расчленяется на субъект (подлежащее) и предикат (сказуемое). Субъект  это то, о чем что-то утверждается в высказывании; предикат это то, что утверждается о субъекте. Например, в высказывании «6  четное число», 6  субъект; четное число предикат. Заменим число 6 переменной х, получим утверждение «х четное число». При одних значениях х это утверждение даёт истинные высказывания, а при других значениях х  ложные высказывания. Последнее утверждение является функцией одной переменной, определенной, например, на множестве N, и принимающей значения на множестве {0,1}.

Определение 1.1. Одноместным предикатом Р(х) называется произвольная функция от переменной х, определенная на множестве D, принимающая значения из множества {0,1}.

Множество D, на котором определен предикат Р(х), называется областью определения предиката Р или его универсом. Множество всех элементов х D, при которых предикат принимает значение 1 (истина), называется множеством истинности предиката Р(х). Например, предикат  « х  четное число» определен на множестве натуральных чисел N , множеством истинности для него является множество всех четных чисел. Предикат S(х)  «1 sin (х)  1» определен на множестве действительных чисел R и его множество истинности  R.

Определение 1.2. п  местным предикатом Р ( ,…, ) называется функция п переменных , … , определенная на множестве = D  … D,

принимающая значения из множества {0,1}.

Предикат Q (x,y,z): является трехместным предикатом; предикат P ( ,…, ):  п  местный.

Выражение Р ( ,…, ) называют элементарной формулой или атомом. Класс формул содержит все элементарные формулы и составные формулы, построенные из элементарных многократным применением всех операции логики высказываний: , , ,  и др. Кроме того вводится две новые операции  («для любого») и  («для некоторых» или «существует»). Утверждение «для всех х верно P (х)» символически записывается х P(х). Символ  называется квантором всеобщности. Утверждение х P(х) истинно, если истинно P(с), какой бы конкретный предмет с из универса предиката P мы ни подставляли вместо х. Например, высказывание х (  0) истинно, если универс  множество действительных чисел. Это высказывание ложно, если универс содержит комплексные числа, т.к. .

Символ  называется квантором существования. Утверждение «существует такое х, что P(х)» символически записывается х P(х). Символ  называется квантором существования. Высказывание х P (х) истинно, если в универсе найдется, хотя бы одно значение с, при котором P(с) истинно.

х P (х) ложно, если при любом значении с ложно P(с). Пусть задан предикат Р(х): «число х кратно 3». Тогда на множестве натуральных чисел N высказывание х Р(х) истинно, а х Р(х)  ложно. По старшинству (в отношении расстановки скобок) кванторы имеют самый высокий приоритет. Формула

х Р  Q означает (х Р)  Q, а не х (Р  Q).

Кванторные операции применяются и к многоместным предикатам. В предикатах, зависящих от нескольких переменных, кванторы можно использовать несколько раз. Предикат  x  y  z Q (x,y,z) читается «для каждого x, для каждого y, для каждого z имеет место Q (x,y,z)», этот предикат истинен, когда для любого набора значений x,y,z из универса истинно. Высказывание х y z Q (x,y,z) истинно, если универс для Q содержит, хотя бы один набор значений, для которых .

Предикат  Р ( ,…, ) зависит от (п  1)- переменной в отличие от предиката Р ( ,…, ), который зависит от п переменных. Истинностное значение предиката  Р ( ,…, ) можно установить, если задать значения , …, , п  2. Рассмотрим предикат P (x,y) « х:y  y делитель х», определенный на множестве N. Предикат х Р(х, y)  «y  делитель любого х » зависит от y и не зависит от х, он истинен для y=1 и ложен для всех остальных значений y. Предикат y Р(х, y)  «существует такое y, которое является делителем х» зависит от х и не зависит от y. Он будет истинен для любого значения х. Применение кванторных операций  и  приводит к восьми возможным высказываниям:

1.y х Р(х, y)  «для всякого y и для всякого х выполняется: y  делитель х».

2. y  х Р(х, y)  «существует y, которое является делителем любого х».

3. y х Р(х, y)  «для всякого y существует х такое, что х делится на y ».

4. y  х Р(х, y)  «существует y и существует х, такие, что y  делитель х».

5.х y Р(х, y)  «для всякого х и для всякого y выполняется: y  делитель х».

6. х y Р(х, y)  «для всякого х существует такое y, что х делится на y».

7. х y Р(х, y)  «существует х и существует y, такие что y  делитель х».

8. хy Р(х, y) «существует х такое, что для всякого y выполняется: х делится на y».

Легко видеть, что высказывания 1, 5 и 8 ложные, а высказывания 2, 3, 4, 6 и 7 истинны.

В формуле х P(х) (х P(х)) подформулу P называют областью действия вхождения квантора х (х). Вхождение переменной х в произвольную формулу Ф называют связанным, если х лежит в области действия некоторого вхождения квантора  или . Если вхождение переменной х в формулу Ф не является связанным, то его называют свободным. Рассмотрим формулу: х (Р(х)  х Q (x, z) y R(х, y))  Q (z, x).

Отметим индексами все вхождения переменных, связанных кванторами. Расставлять индексы нужно начинать изнутри, продвигаясь наружу в соответствии с построением формулы из ее атомов Р(х), Q (x, z), R(х, y), Q (z, x).

х₃ (Р(х₃)  х₁ Q (x₁, z) y₂R(х₃, y₂))  Q (z, x).

Вхождения переменных, оставшихся без индексов (два z и одно x), свободны.

Для формулы Ф запись Ф( ,…, ) обозначает, что все ее свободные переменные входят в последовательность ,…, .