Подраздел 3.5

1. Выражения 1), 4), 5) и 6) являются формулами. Выражение 2) не является формулой, так как запись в одном кванторе двух переменных не допустима. Выражение 3) не является формулой, так как переменная в высказывание входит связно, а в предикат – свободно, что для формул логики предикатов недопустимо.

2. 1) .

2) .

3)

.

4) .

5) .

6) .

7)

.

8)

.

3. Высказывание 1) ложно, так как оно утверждает, что “существует такое, что для всех истинно ”. Но так как множество состоит из множества пар натуральных чисел то для пары предикат ложен, а поэтому ложно и высказывание 1).

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

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

Аналогичным образом устанавливается ложность высказываний 4), 5), 6) и истинность высказываний 7) и 8).

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

Действительно, мы видим, что в первом подмножестве это неравенство не выполняется для пары , во втором – для пар и , в третьем – для пар (3,1), (3,2) и (3,3) и т.д. Это и доказывает, что предикат является тождественно ложным.

2) Предикат тождественно истинный, так как в подмножествах пар элементов множества существует хотя бы одна пара, для которой выполняется строгое неравенство .

3) Предикат тождественно ложный. Рассуждения аналогичны тем, которые используются в первом примере.

4) Предикат не тождественно истинный и не тождественно ложный. Действительно, для одних пар множества неравенство выполняется, а для других нет. Это можно представить так, что если бы мы могли построить для этого предиката таблицу истинности, то в последнем ее столбце стояли бы не одни 1 или 0, а и то, и другое.

5. Формулы 2) и 7) равносильны формуле а остальные - нет. Действительно: . Формула 2) имеет такой же вид, а формула 7) приводится к такому же виду следующим образом: .

Остальные формулы к такому виду не приводятся.

6. 1) Доказательство обосновывается многократным применением равносильности 4) и двойного отрицания. Так, если формула содержит только кванторы существования, т.е. задана в виде , то мы можем записать последовательность равносильных преобразований:

.

Последняя формула кванторов существования не содержит.

Если в формулу кванторы существования и всеобщности входят в произвольном порядке, то, применяя равносильность 4 и двойное отрицание, мы также можем перейти к формуле, не содержащей кванторов существования. Действительно, пусть формула задана в виде . Тогда запишем последовательность равносильных преобразований:

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

2) Доказывается аналогично задаче 1), но при этом используется равносильность 3 и двойное отрицание.