2.6.2. Операции над предикатами

А) Подстановка константы вместо предметной переменной.

Пусть – N-местный предикат на множестве М, и пусть . Подставим вместо (например) ХN константу А. Тогда получим (N-1)–местный предикат .

Можно сразу подставить одну и ту же или разные константы вместо нескольких переменных. Тогда соответствующим образом уменьшится местность предиката.

Например, из 2-местного предиката “X<Y” подстановкой константы 3 вместо У получим одноместный предикат “X<3”. Из 4-местного предиката “X+Y+Z+T=0” путем соответствующих подстановок можно получить 2-местный предикат “X+2+Z+3=0” и т. д..

Б) Операции логики высказываний.

Так как предикаты представляют собой переменные высказывания (они превращаются в обычные высказывания, если вместо всех предметных переменных подставить константы), то для них применимы все операции логики высказываний: , , ù, , и др.. Соединяя символами данных операций элементарные предикаты (т. е. такие, которые не содержат этих операций) будем получать соответствующие формулы логики предикатов, например, и т. д..

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

Пусть IP обозначает область истинности предиката Р.

Легко видеть, что для отрицания областью истинности будет , поскольку =1 всегда, кроме тех случаев, когда Р(Х)=1.

Предикат принимает значение 1 только в тех случаях, когда Р(Х)=1 и Q(Х)=1. Поэтому .

Предикат принимает значение 1 в тех случаях, когда Р(Х)=1 или Q(Х)=1. Поэтому .

Выражая импликацию, эквиваленцию и другие операции через отрицание, конъюнкцию и дизъюнкцию, можно находить области истинности и других сложных предикатов. Следует, однако, следить за совпадением или несовпадением предметных переменных в то смысле, что, например, областью истинности предиката будет не пересечение IP(X) и IQ(X) (как для ), а декартово произведение .

В) Навешивание кванторов.

Пусть Р(Х) – одноместный предикат с предметной областью М.

Символом обозначается высказывание, которое истинно, если Р(Х) тождественно истинный предикат (т. е., если IP(X)=M), и ложно в противном случае.

Знак называется Квантором всеобщности.

Символом обозначается высказывание, которое истинно, если Р(Х) выполнимый предикат (т. е., если IP(X)≠0), и ложно, если Р(Х) тождественно ложный предикат.

Знак называется Квантором существования.

Переход от Р(Х) к или называется Навешиванием квантора на переменную Х (или связыванием переменной Х). При этом переменная Х, на которую навешен квантор, называется Связанной, в противном случае – Свободной.

Кванторы можно навешивать также на переменные многоместных предикатов, на одну переменную, несколько или сразу на все. Рассмотрим, например, предикат . Здесь Х, у – связанные переменные, а Z, T – свободные.

Значение предиката не зависит от связанных переменных, а определяется только значениями свободных переменных. Это означает во-первых, что навешивание квантора на одну переменную уменьшает на 1 местность соответствующего предиката. Так, предикат является двуместным. Во-вторых, предикат не изменится, если связанные переменные поменять на другие (отличные от свободных). Например .

Замечание. Если М = {A1, A2, …, Am} – конечное множество, то можно, что

Для бесконечных множеств М также можно принять, что

.

В этом смысле кванторы и можно рассматривать как обобщения операций конъюнкции и дизъюнкции .

< Предыдущая		Следующая >