2.2.1
Which of the following strings are formulas in predicate logic?
2.5.3
Provide proofs for the following sequents:
(a) 8xP(x) ‘ 8yP(y)
(b) 8x(P(x) ! Q(x)) ‘ (8x:Q(x)) ! (8x:P(x))
(c) 8x(P(x) ! :Q(x)) ‘ :(9x(P(x) ^ Q(x)))
2.5.11
Prove the following sequents in predicate logic:
(a) 8x8y8z(S(x; y) ^ S(y; z) ! S(x; z)); 8x:S(x; x) ‘ 8x8y(S(x; y) ! :S(y; x)) (b) 8x(P (x) _ Q(x)); 9x:Q(x); 8x(R(x) ! :P (x)) ‘ 9x:R(x)
(c) 8x(P (x) ! (Q(x) _ R(x))); :9x(P (x) ^ R(x)) ‘ 8xP (x) ! Q(x)
(e) (9xP (x)) ! 8yP (y) ‘ 9x8y((P (x) ! P (y)) ^ (P (y) ^ P (x)))
(f) 9x(P (x) ^ Q(x)); 8y(P (y) ! R(y)) ‘ 9xR(x) ^ Q(x)
2.6.1
Consider the formula
φ = 8x 9y Q(g(x; y); g(y; y); z)
Find two models M and M 0 with respective environments l and l0 such that M j=l φ but M 0 6j=l φ
2.6.2
Consider the sentence
φ = 8x 9y 9z (P(x; y) ^ P(z; y) ^ (P(x; z) ! P(z; x)))
Which of the following models satisfies φ?
(a) P M = f(m; n)jm < ng
(b) P M 0 = f(m; 2 ∗ m)jm natural numberg
(c) P M 00 = f(m; n)jm < n + 1g
2.6.3
Let P be a predicate with two arguments. Find a model M which satisfies 8x :P(x; x). Find also a model M 0 such
that M 0 6j= 8x :P(x; x)
2.7.5
Show 8x(P(x) W Q(x)) 6j= 8xP(x) W 8xQ(x). Thus, find a model which satisfies 8x(P(x) W Q(x)), but not 8xP(x) W 8xQ(x)
