Некоторые общезначимые формулы с кванторами

1. () Р (х) ( х) .

2. () Р (х) ( х) .

3. ( х) Р (х) ().

4. ( х) Р (х) ().

5. ( х) Р (х) ( х) Q (х) ( х) (Р (х) Q (х)).

6. ( х) Р (х) ( х) Q (х) ( х) (Р (х) Q (х)).

7. ( х) ( у) Р (х, у) ( у) ( х) Р (х, у).

8. (х) (у) Р (х, у) (у) (х) Р (х, у).

9. (х) (у) Р (х, у) (у) (х) Р (х, у).

10. ( х) Р (х) ( х) Q (х) ( х) (Р (х) Q (х)).

11. ( х) (Р (х) Q (х)) ( х) Р (х) ( х) Q (х).

12. ( х) (Р (х) Q (х)) (( х) Р (х) ( х) Q (х)).

13. ( х) Р (х) Р (у).

14. Р (у) ( х) Р (х).

Мы ранее установили равносильность левой и правой частей формул 1-8, следовательно, эквиваленции будут общезначимыми формулами.

Идея доказательства формул 9-12 заключается в том, что область истинности левой части включается в область истинности правой части. Рассмотрим на примере формулы 10:

( х) Р (х) ( х) Q (х) ( х) (Р (х) Q (х)).

Будем считать, что предикаты заданы на множестве А.

Пусть области истинности предикатов Р (х) и Q (х) не совпадают с А. Тогда левая часть импликации ложна, следовательно, импликация истинна.

Если одна из областей истинности совпадает с А, например, М_р = А, но тогда ( х) Р (х) = 1, значит вся левая часть импликации истинна. Так как область истинности Р (х) Q (х) является объединением областей истинности предикатов, то она совпадает с А, следовательно, правая часть импликации истинна, и импликация истина. Тем самым доказана общезначимость формулы 10.

15. Докажем теперь формулу 13: ( х) Р (х) Р (у).

Предикат Р задан на некотором множестве U.

Пусть Р (у) (у из U) – ложно, но тогда ложно ( х) Р (х) (х из U), тогда импликация истинна. Если Р (у) – истина, то и импликация – истина.

Докажем формулу 14: Р (у) ( х) Р (х).

Пусть М = Ø,. Но тогда Р (у) ложно. Следовательно, импликация истинна. Если М_p Ø, то ( х) Р (х) ─ истина, следовательно, импликация истина.

Дата добавления: 2014-01-06