Математическая логика. - 9 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Рубрика: 

- 8 - Математическая логика
в частном случае
∀x P(x)=P(a
1
)&P(a
2
)&…&P(a
m
),
∃x P(x)=P(a
1
) ∨ P(a
2
) ∨ … ∨ P(a
m
);
Говорят, что квантор связывает соответствующую переменную. Преди-
кат (формула) называется замкнутым, если связаны все переменные (если нет
свободных, т.е. несвязных переменных).
Основные равносильности предикатов:
() ()
() ()
() ()
() ()
.xxPxPx .4
;xxPxPx .3
;xPxxxP .2
;xPxxxP .1
∀≡¬¬∃
∃≡¬¬∀
¬∀≡¬∃
¬∃≡¬∀
Пусть
Q – формула, не содержащая переменной х, тогда:
(
)
(
)()
() ()()
() ()()
() ()()
() () () ()()
() () () ()()
() () () ()()
() () () ()
;xR x&xP xxR &xPx 14.
;xRxP xxR xxPx 13.
;xRxP xxR xxPx 12.
;xR&xP xxR x&xPx 11.
Q;xQ .10
Q;xQ .9
;Q&xPxQ&xPx .8
;QxPxQxP
x .7
;Q&xPxQ&xPx .6
;QxPxQxPx .5
∃∃→∃
∨∀→∀∨∀
∨∃≡∃∨∃
∀≡∀∀
≡∃
≡∀
∃≡∃
∨∃≡∨∃
∀≡∀
∨∀≡∨∀
Отметим, что импликация в обратную сторону для формул 13 и 14 не
имеют места, а следовательно,
между левой и правой частями нельзя поставить
знак равносильности (≡).
Например, если
Р(х) – «быть четным числом» и R(x) – «быть нечетным
числом», то из справедливости ∃xP(x)&∃xR(x) не следует справедливость
∃x(P(x)&R(x)), так как нет такого числа, которое бы было одновременно четным
или нечетным.
(
)()
() ()
;yyPxxP .16
;yyPxxP .15
∃≡∃
∀≡∀
Формулы 15 16 имеют место при условии, что
x и y принимают свои зна-
чения из одной предметной области. 
                                             -8-           Математическая логика




в частном случае
       ∀x P(x)=P(a1)&P(a2)&…&P(am),
       ∃x P(x)=P(a1) ∨ P(a2) ∨ … ∨ P(am);

       Говорят, что квантор связывает соответствующую переменную. Преди-
кат (формула) называется замкнутым, если связаны все переменные (если нет
свободных, т.е. несвязных переменных).

       Основные равносильности предикатов:

       1.    ¬∀xP(x ) ≡ ∃x¬P(x );
       2.    ¬∃xP(x ) ≡ ∀x¬P(x );
       3.    ¬∀x¬P(x ) ≡ ∃xP(x );
       4.    ¬∃x¬P(x ) ≡ ∀xP(x ).

       Пусть Q – формула, не содержащая переменной х, тогда:

       5.    ∀x P(x ) ∨ Q ≡ ∀x (P(x ) ∨ Q );
       6.    ∀x P(x ) & Q ≡ ∀x (P(x ) & Q );
       7.    ∃x P(x ) ∨ Q ≡ ∃x (P(x ) ∨ Q );
       8.    ∃x P(x ) & Q ≡ ∃x (P(x ) & Q );
       9.    ∀xQ ≡ Q;
       10.   ∃xQ ≡ Q;
       11.   ∀x P(x ) & ∀x R (x ) ≡ ∀x (P(x ) & R (x ));
       12.   ∃x P(x ) ∨ ∃x R (x ) ≡ ∃x (P(x ) ∨ R (x ));
       13.   ∀x P(x ) ∨ ∀x R (x ) → ∀x (P(x ) ∨ R (x ));
       14.   ∃x P(x ) & R (x ) → ∃x P(x ) & ∃x R (x );

       Отметим, что импликация в обратную сторону для формул 13 и 14 не
имеют места, а следовательно, между левой и правой частями нельзя поставить
знак равносильности (≡).
       Например, если Р(х) – «быть четным числом» и R(x) – «быть нечетным
числом», то из справедливости ∃xP(x)&∃xR(x) не следует справедливость
∃x(P(x)&R(x)), так как нет такого числа, которое бы было одновременно четным
или нечетным.

       15. ∀xP(x ) ≡ ∀yP(y );
       16. ∃xP(x ) ≡ ∃yP(y );

       Формулы 15 16 имеют место при условии, что x и y принимают свои зна-
чения из одной предметной области.

Страницы