ТЕМА 5 (часть 2)
ИСЧИСЛЕНИЕ ПРЕДИКАТОВ, СИСТЕМА НАТУРАЛЬНОГО ВЫВОДА.
1. Натуральное исчисление предикатов.
2. Правила введения и удаления кванторов.
3. Понятие вывода, завершенного вывода, доказательства и завершенного доказательства.
4. Доказательство теорем логики предикатов.
5. Анализ рассуждений средствами натурального исчисления предикатов.
Литература:
- , Маркин в логику, гл. 6 §1.
Упражнения:
1. Докажите в натуральном исчисление предикатов теоремы:
а) ∀x(Q(y) ⊃ R(x, y)) ⊃ (Q(y) ⊃ ∀xR(x, y)),
б) ∃xR(x, x) ⊃ ∃x∃yR(x, y),
в) ∃x(P(x) ⊃ ∀yP(y)),
г) ∀xP(x) ⊃ (∃y(P(y)&Q(y)) ∨ ∀z¬Q(z))
д) ∃xP(x) ≡¬∀x¬P(x),
е) ∀xP(x) ≡¬∃x¬P(x),
ж) ∀x(P(x) & Q(x)) ≡ (∀xP(x) & ∀xQ(x)),
з) ∃x(P(x) ∨ Q(x)) ≡ (∃xP(x) ∨ ∃xQ(x)).
* для доказательства теоремы, в которой главным знаком является ≡ , надо построить два вывода с ⊃.
2. Обоснуйте правильность рассуждений средствами натурального исчисления предикатов:
а) Существует число, меньшее любого числа. Следовательно, для любого числа найдётся число, которое меньше него.
б) Неверно, что кто-то умнее всех. Значит, каждый не умнее кого-нибудь.
в) Все философы слышали о Сократе. Некоторые обыватели являются философами. Следовательно, некоторые обыватели слышали о Сократе.
г) Все кошки знают французский язык. Некоторые цыплята – кошки. Следовательно, некоторые цыплята знают французский язык.
