Упражнения
Упражнения
1. Рассмотрите реализацию ℑ = <U, I>, где U – множество натуральных чисел, а I интерпретирующая функция: I(а) = 1, I(b) = 2, I(с) = 3, I(f) = операции возведения в квадрат, I(h) = операции умножения, I(Р) = множество нечетных чисел, I(Q) = множество пар чисел, первое из которых больше второго. Определите, значения в данной реализации следующих термов и формул:
а) f(c), б) h(a, b), в) f(h(b, c)),
г) h(f(b), h(a, c)), д) P(h(a, b)), е) Q(f(b), h(a, a)),
ж) P(c) ∨ ¬P(f(c)), з) ∀xQ(h(x, a), a), и) ∀x(P(f(x) ⊃ P(x)),
к) ∃x∃yQ(c, h(x, y)), л) ∃х(Р(х) & Q(x, f(x))),
м) ∀x(P(x) ⊃ ¬P(h(x, a))).
2. Продемонстрируйте выполнимость следующих формул, подобрав реализации, в которых они принимают значение «истина»:
а) ∃х(Р(х, а) & Р(х, b)), б) ∀х∀у(R(x, y) ⊃ R(y, x)).
3. Продемонстрируйте опровержимость следующих формул, подобрав реализации, в которых они принимают значение «ложь»:
(а) ∀х(Р(х) ∨ Q(x)) ⊃ (∀xP(x) ∨ ∀xQ(x));
(б) ∀x∃yR(x, y) ⊃ ∃y∀xR(x, y).
4. Подберите конкретную реализацию, демонстрирующую, что следующие формулы совместимы по истинности:
а) ¬∀хР(х, а) и ∃хР(а, х), б) ∀х∃уP(f(x), x) и ¬∃xP(x, f(x)).
5. Подберите конкретную реализацию, демонстрирующую, что следующие формулы совместимы по ложности:
а) ∀хР(х, а) и ¬∃хР(х, а).
6. Продемонстрируйте некорректность следующих умозаключений, для чего выявите их логические формы и подберите соответствующие контрреализации:
(а) Каждый человек является экстравертом или интровертом. Следовательно, не существует людей, которые одновременно являлись бы экстравертами и интровертами.
(б) Неверно, что каждый умен. Неверно также, что каждый добр. Следовательно, некто и неумен, и недобр.
7. Рассуждая «от противного» и пользуясь семантическими определениями связок и кванторов, показать:
(а) общезначимость формулы
¬∀х(Р(х) & Q(x) ⊃ ∃x(¬P(x) ∨ ¬Q(x)),
(б) невыполнимость формулы
∀x∀yR(x, y) & ∃х¬R(x, х),
(в) несовместимость по истинности формул
∃х(Р(х) ∨ Q(x)) и ∀х¬Р(х),
(г) несовместимость по ложности формул
∀x(P(x) & Q(x)) и ∃x¬Р(x) ∨ ∃х¬Q(x),
(д) логическое следование формулы
∃xP(a, x) из Р(b, а) и ∀x∀y(P(x, y) ⊃ P(y, x)).
