Question Mark
1
2
3
4
5
6
7
Bonus: Knights and Knaves
/6
/5
/5
/5
/10
/5
/4
/3
TOTAL /40
Page 2 of 3
Questions about Language
1. (6 pts.) Suppose we have an FOL with constant symbols/names a, b, c, d, and e, function symbols
f (x), g (x), h (x, y), predicate symbols P (x), Q (x), R (x, y), x = y, and one ternary connective (x, y, z).
For each of the following, indicate whether they are simple terms, complex terms, atomic
sentences, or complex (non-atomic) sentences, or none of these.
a. (f(a), g(b), h(c, d))
b. Q(h(c, d))
c. (b = c, P(f(e)), R(e, g(a)))
d. (Q(d), Q(a), Q(b)) = c
e. a ≠ b
f. h(f(d), h(e, f(a)))
Informal Proof
2. (5 pts.) Prove (informally) whether if S is a tautological consequence of P1, . . . , Pn, then the set of
sentences {S, P1, . . . , Pn} is consistent.
Explanation
3. (5 pts.) Do exercise 7.21 of your textbook.
Formal Proofs (You may not use TautCon or AnaCon for any of these proofs.)
4. (5 pts.) Provide a formal proof in f showing that the sentence (P P) is a tautology.
5. (10 pts.) Determine whether the following argument is tautologically valid. If it is, provide a
formal proof in f. If it is not, then describe a counterexample.
1. (P(a) P(b)) (R(a, c) Q(a))
2. (R(b, c) Q(b)) (P(b) Q(a))
3. R(a, c) R(b, c)
———-
4. P(a) Q(b)
Translations
6. (5 pts.) Using the predicate symbols from Tarski’s World, translate the following English
sentences into FOL.
1. c is to the right of a, provided it (i.e., c) is small.
2. c is to the right of d only if b is to the right of c and left of e.
3. If e is a tetrahedron, then it’s to the right of b if and only if it is also in front of b.
4. e is in front of d unless it (i.e., e) is a large tetrahedron.
5. d is the same shape as b only if they are the same size.
Page 3 of 3
Equivalence (4 pts.)
Consider the following ternary truth-functional connective:
P Q R (P, Q, R)
T T T F
T T F T
T F T T
T F F T
F T T T
F T F T
F F T T
F F F F
Express this connective with a sentence that only uses the Boolean connectives in its most simplified
form—that is, using a sentence containing no more than two occurrences each of P, Q, and R, and
no more than six occurrences of the Boolean connectives , , and . Briefly explain how you
arrived at this sentence. If you used a chain of equivalences, please include it in your response.
Bonus Question: Knights and Knaves (3pts.)
Harry Potter and Hermione Granger are inhabitants of the island of knights and knaves, where
knights only tell the truth, and knaves only lie. Harry says “I am a knight if and only if Snape is on
the island”. Hermione says that if Harry is a knight, then Snape is not on the island. What are Harry
and Hermione, and is Snape on the island? Explain
