Тавтологии в логике предикатов.

1) Теорема 1. Всякая тавтология АВ, в которую вместо 0-местных предикатных переменных подставлены любые предикатные переменные n, m-местные, являются тавтологией в логике предикатов.

Доказательство. Любая тавтология Е из АВ принимает значение истины при любом наборе значений, входящих в нее пропозиционных переменных. Следовательно, если любые из них (понимая теперь как 0-местные предикатные переменные) заменить на n, m-местные переменные, то всякая интерпретация такой формулы на любом множестве независимы от значений предикатных переменных останется всегда истинным высказыванием. Это и будет означать, что Е-тавтология в логике предикатов.

2) Существенно новые тавтологии, характерные только для логики предикатов, это тавтологии, связанные с кванторными операциями.

Теорема 2. В логике предикатов тавтологиями являются следующие формулы:

┐(xP(x)) ↔ x┐P(x); (1)

┐( xP(x)) ↔x┐P(x). (2)

Поскольку формулы (1) и (2) утверждают эквиваленцию высказываний, то достаточно показать одновременную истинность каждой пары высказываний.

Докажем, например, (2):

А) P(x)-выполнимо, тогда ┐P(x)-опровержимо. Речь идет о рассмотрении формулы на каком-либо множестве и о взятии вместо Р конкретного предиката.

x P(x) - истина;

x P(x) - ложь;

 x P(x) - ложь.

Значит, значение истинности обоих предикатов формулы (2) совпали, т.е. эквиваленция истинна.

Б) P(x) – тождественная ложь, тогда ┐P(x) – тождественная истина.

x P(x) - ложь;

┐( x P(x)) – истина;

 x┐(P(x)) – истина.

Т.е оба компонента эквиваленции (2) оказались одновременно истинными, значит эквиваленция является истинной. Эквиваленция оказалась истинной на каком бы множестве мы не рассматривали формулу (2) и каков бы предикат Р мы не выбирали вместо предикатной переменой. По определению тавтологий, мы имеем дело с тавтологией 2.

 

3) Распределительный закон для кванторов.

Теорема 3. (( x(P(x)/\Q(x))) ↔(( xP(x)/\( xQ(x))), (3)

( x(P(x) \/Q(x))) ↔(( x(P(x)) \/( xQ(x))). (4)

Докажем (3). Снова выберем произвольную предикатную предикатную область с произвольными предикатами P и Q на ней. Возможны случаи:

а) В случае P и Q – тождественно истинные предикаты на М, тогда P/\Q – тождественная истина на М и любой компонент в (3) по определению кванторной общности – истина. А в правом – каждое высказывание из связанных понятий – «истина», т.е. оба компонента (3) – «истина».

б) Хотя бы один из P или Q – опровержим на М. Для правого компонента в (3) хотя бы один из «участников» есть ложь и вся конъюнкция тогда ложь. Для левого компонента конъюнкция P(x)/\Q(x) является опровержимым предикатом.

По определению кванторной общности, левый компонент – ложь. Оба компонента в (3) тогда принимают значение лжи.

Итак, в обоих случаях а) и б) эквиваленция (3) оказывается истиной, чем доказана истинность предиката (3), а в силу произвольности выбора предметной области и предикатов на ней, доказано, что (3) – это тавтология.

Если в формулах (3), (4) перейти к двойственным операциям, то они перестают быть верными.

Например, не будет тавтологией формула

( x(P(x) \/G(x))↔(( x(P(x)\/( xG(x)). (5)

Чтобы это доказать, надо найти такую предикатную область и такие предикаты на ней, чтобы получаемый предикат (5) стал опровержимым. Точнее (5) как высказывание – ложь. Берем, например, на R: P:”x>=1”; Q:”x<1”.

P\/Q: “x>=1 или x<1”.

Т.е. левый компонент (5) истинен. В то же время для любого xP(x) это ложь. Так что эквиваленция приняла значение лжи. Этим доказано, что (5) не является тавтологией.

 

4) Теорема 4. Для любого 0-местного предиката В имеет место

( x(P(x) \/В)) ↔(( xP(x) \/В), (6)

x(P(x) /\В)) ↔(( xP(x) /\В). (7)

Докажем (7). Выберем конкретную предиктную область М и конкретную предметную область P на М.

а) P(x) – тождественная ложь: левый компонент «ложь», правый - «ложь».

б) P(x) – выполнимо, В – истина: левый компонент – «истина», правый – «истина».

в) P(x) – выполнимо, В – ложь: оба компонента – «ложь», т.е. эквиваленция есть истина, значит ввиду произвольности М, Р и В, (7) будет тавтология.

 

5) Перемещение кванторов за знак импликации.

Теорема 5. Следующие формулы являются тавтологией:

 x (P(x)→B) ↔ ( x P(x))→B;

x (P(x)→B) ↔ (x (P(x))→B;

 x (В→Р(х)) ↔ (В → ( x Р(х)));

x (В→Р(х)) ↔ (В → ( x Р(х))).

Замечание. В утверждениях последних двух пунктов предполагается, что В – 0-местный предикат.

 

6) Коммутативность одноименных кванторных операций.

(xy P(x,y)) ↔(yx P(x,y));

( x y P(x,y)) ↔( y x P(x,y)).

Разноименные кванторы подобным свойством коммутативности не обладают.