2.6.3. Равносильные формулы логики предикатов

Так как предикаты представляют собой “переменные” высказывания, то для предикатных формул, использующих операции логики высказываний, справедливы все равносильности логики высказываний (см. §1). Поэтому ограничимся лишь рассмотрением специфических формул, связанных с операциями навешивания кванторов.

1.

Действительно, предположим, что для производного предиката Р(Х) (для определенности будем считать, что предикат P зависит только от переменной Х; наличие или отсутствие других переменные в данном случае не существенно) с предметной областью М левая часть тождества принимает значение 1 ("истина"). Другими словами, не существует , такого, что Р(А) = 1. Это значит, что P(A) = 0, т. е. P(A) ≠ 1 или, что то же самое, принимает значение 1.

Предположим теперь, что принимает значение 0, т. е. не верно, что не существует такого, что Р(А) = 1. Или, что то же самое, существует элемент , такой, что Р(А)=1. Таким образом, не для всех Р(А) ≠ 1. Поэтому высказывание ложно. Тождество доказано.

Аналогично доказывается и другие тождества, приведенные ниже.

2.

3.

4.

5.

6.

В 5-ой и 6-ой формулах, вообще говоря, справедливы только указанные импликации. То, что импликации в обратную сторону ложные видно из следующего примера: Р(Х) = Х – четное число”, Q(X) = X – нечетное число”, М = Z – множество целых чисел.

7.

8.

Другими словами, кванторы всеобщности перестановочны друг с другом и кванторы существование также перестановочны друг с другом. Но нельзя переставлять квантор $ и квантор ". Так, например, $X"Y(XY) – ложное высказывание, а "Y$X(XY) Истинное. При перестановке различных кванторов справедлива лишь следующая импликация

9. .

10. .

11. .

12. .

13. .

В последних четырех тождествах предикат Q, вообще говоря, может иметь предметные переменные, но отличные от Х (точно также и Р(Х) может иметь другие переменные, кроме Х).

© 2011-2024 Контрольные работы по математике и другим предметам!