How Logic Works

Table of Contents

In the solutions that follow, we give specific examples of proofs. But there is never just one correct proof. The best way to check the correctness of (formal) proofs is not by comparing them to someone else’s proofs, but by running them through a proof checker. It is fairly easy to write a proof checker for these kinds of proofs, but more difficult to make decisions about how to transform proofs written by humans into data structures that can be processed by a machine.

2 Deducing

Exercise 2.1

  1. Prove that q∧p follows from p∧q. That is, write p∧q on line (1), then use the rules (∧ introduction and elimination) repeatedly until you obtain q∧p.

    (1) p∧q
    (2) p     1 ∧E
    (3) q     1 ∧E
    (4) q∧p   3,2 ∧I
  2. Prove that p∧(q∧r) follows from (p∧q)∧r.

    (1) (p∧q)∧r   
    (2) p∧q      1 ∧E
    (3) p        2 ∧E
    (4) q        2 ∧E
    (5) r        1 ∧E
    (6) q∧r      4,5 ∧I
    (7) p∧(q∧r)  3,6 ∧I

Exercise 2.2 (∧E, ∧I, ∨I)

  1. p∧q ⊢ q∨r

    (1) p∧q
    (2) q    1 ∧E
    (3) q∨r  2 ∨I
  2. p∧q ⊢ (p∨r)∧(q∨r)

    (1) p∧q   
    (2) p            1 ∧E
    (3) p∨r          2 ∨I
    (4) q            1 ∧E
    (5) q∨r          4 ∨I
    (6) (p∨r)∧(q∨r)  3,5 ∧I
  3. p ⊢ q∨(p∨q)

    (1) p
    (2) p∨q      1 ∨I
    (3) q∨(p∨q)  2 ∨I
  4. p ⊢ (p∨r)∧(p∨q)

    (1) p
    (2) p∨r          1 ∨I
    (3) p∨q          1 ∨I
    (4) (p∨r)∧(p∨q)  2,3 ∧I

Exercise 2.3 (∧E, ∧I, ∨I, MP)

  1. p→(q→r),p→q,p ⊢ r

    (1) p→(q→r) 
    (2) p→q
    (3) p
    (4) q        2,3 MP
    (5) q→r      1,3 MP
    (6) r        5,4 MP
  2. (a∨b)→t,z→a,t→w,z ⊢ w

    (1) (a∨b)→t   
    (2) z→a
    (3) t→w
    (4) z
    (5) a         2,4 MP
    (6) a∨b       5 ∨I
    (7) t         1,6 MP
    (8) w         3,7 MP
  3. (a→b)∧(c→a),(c∧(w→z))∧w ⊢ (b∨d)∧(z∨e)

    (1) (a→b)∧(c→a)     
    (2) (c∧(w→z))∧w
    (3) w             2 ∧E
    (4) c∧(w→z)       2 ∧E
    (5) w→z           4 ∧E
    (6) c             4 ∧E
    (7) c→a           1 ∧E
    (8) a→b           1 ∧E
    (9) a             7,6 MP
    (10) b            8,9 MP
    (11) b∨d          10 ∨I
    (12) z            5,3 MP
    (13) z∨e          12 ∨I
    (14) (b∨d)∧(z∨e)  13 ∧I
  4. p→(p→q),p ⊢ q

    (1) p→(p→q)
    (2) p
    (3) p→q      1,2 MP
    (4) q        3,2 MP
  5. p∧(p→q) ⊢ p∧q

    (1) p∧(p→q)
    (2) p         1 ∧E
    (3) p→q       1 ∧E
    (4) q         3,2 MP
    (5) p∧q       2,4 ∧I

Exercise 2.4 Prove that q→(p→r),¬r∧q ⊢ ¬p

(1) q→(p→r)  
(2) ¬r∧q     
(3) q        2 ∧E
(4) ¬r       2 ∧E
(5) p→r      1,3 MP
(6) ¬p       5,4 MT

Exercise 2.5

  1. p∧(q∧r) ⊣⊢ (p∧q)∧r

    (1) p∧(q∧r)
    (2) p        1 ∧E
    (3) q∧r      1 ∧E
    (4) q        3 ∧E
    (5) r        3 ∧E
    (6) p∧q      2,4 ∧I
    (7) (p∧q)∧r  6,5 ∧I

    For the converse, we turn this proof upside down.

    (1) (p∧q)∧r  
    (2) p∧q      1 ∧E
    (3) r        1 ∧E
    (4) q        2 ∧E
    (5) q∧r      3,4 ∧I
    (6) p        2 ∧E
    (7) p∧(q∧r)  6,5 ∧I
  2. p ⊣⊢ p∧p

    (1) p
    (2) p∧p  1,1 ∧I
    (1) p∧p  
    (2) p    1 ∧E

Exercise 2.6

  1. It’s not true that if Ron doesn’t do his homework, then Hermione will finish it for him.

    ¬(¬r→h)

  2. Harry will be singed unless he evades the dragon’s fiery breath.

    s∨e

  3. Aristotle was neither a great philosopher nor a great scientist.

    ¬p∧¬s or equivalently ¬(p∨s)

  4. Mark will get an A in logic if and only if he does the homework or bribes the professor.

    a→(h∨b)

  5. Dumbledore will be killed, and either McGonagal will become head of school and Hogwarts will flourish, or else it won’t flourish.

Exercise 2.7

Exercise 2.8

7 Theories

Exercise 7.2

1   (1) Fa∧∀x(Fx→(x=a))     A
2   (2) Fb                  A
1   (3) ∀x(Fx→(x=a))        1 ∧E
1   (4) Fb→(b=a)            3 UE
1,2 (5) b=a                 4,2 MP
1   (6) Fb→(b=a)            2,5 CP
7   (7) b=a                 A
1   (8) Fa                  1 ∧E
7   (9) a=b                 7 cut (symmetry of =)
1,7 (10) Fb                 9,8 =E
1   (11) (b=a)→Fb           7,10 CP
1   (12) Fb↔(b=a)           6,11 cut (↔ intro)
1   (13) ∀x(Fx↔(x=a))       12 UI

To prove the converse, note that the premise ∀x(Fx↔︎(x=a)) yields Fa↔︎(a=a). But we have a=a by =I, and so we can conclude Fa.

Exercise 7.3

  1. Maren is the only student who didn’t miss any questions on the exam.

    ∀x(¬Mx↔︎(x=m))

    Here I’m using Mx for “x missed a question on the exam”. That phrase is actually quantificationally complex, and could be further cashed out in terms of “questions” and “being on an exam” and “x getting y wrong”.

  2. All professors except Aldous are boring.

    ∀x((Px∧¬Bx)↔︎(x=a))

  3. a is the best of all possible worlds.

    ∀xRax

    This implicitly assumes that “R” represents a relation that has features like “better than”. I would say that R must satisfy the axioms of a partial order.

  4. There is no greatest prime number.

    ¬∃y(Py∧∀x((Px∧¬(x=y))→(x<y)))

    Or: ∀x(Px→∃y(Py∧(x<y)))

    To check: Are these two sentences always equivalent? Or does it depend on the fact that < is a total order?

  1. For each integer, there is a unique next-greatest integer.

    ∀x∃y((x<y)∧¬∃z((x<z)∧(z<y)))

  2. There are at least two Ivy League universities in New York.

    ∃x∃y((Ix∧Nx)∧(x≠y))

  3. For any two sets u and v, there is a largest set w that is contained in both of them.

    We represent this sentence as saying that there is a set w that is contained in both u and v, and any other set that is contained in both u and v is contained in w.

    ∀u∀v∃w(w⊆u∧w⊆v∧∀x((x⊆u∧x⊆v)→x⊆w))

  4. The function f achieves its least upper bound on the domain [0,1]

    ∃x(0≤x≤1 ∧ ∀y((0≤y≤1)→(f(y)≤f(x))))

Exercise 7.4

∀xLxb∧∀x(Lbx↔︎x=a)

By the first conjunct, Lbb. By the second conjunct, Lbb↔︎(b=a). Therefore, b=a.

Exercise 7.5

Let a,b be given. By the total axiom, either a≤b or b≤a. Assume without loss of generality that a≤b. Since also b≤b by reflexivity, there is an x such that a≤x and b≤x. Therefore, the relation ≤ is directed.

Exercise 7.6

This claim is incorrect unless the relation R is also assumed to be serial. For example, in the structure {a}, where the extension of R is empty, the reflexivity and transitivity axioms are satisfied, whereas the reflexivity axiom is not satisfied. If, however, R is also serial, then the result can be proven as follows: given a, there is some b such that Rab. By symmetry, Rba. Thus, Rab∧Rba, and by transitivity, Raa. Since a was an arbitrary element, we have ∀xRxx.

Exercise 7.7

The following sentence is true in the integers, but false in the rational numbers: “There are x and y such that x<y, but there is no z such that x<z and z<y.” Clearly that sentence can be formalized in quantifier logic.

Exercise 7.8

Let a and b be given such that f(a)=f(b). Then a=g(f(a))=g(f(b))=b, hence a=b. Therefore f is one-to-one.

Notice that in the second step, we use the fact that if c=d then g(c)=g(d). That can be proven as follows:

1  (1) c=d              A
   (2) g(c)=g(c)        =I
1  (2) g(c)=g(d)        1,2 =E

Exercise 7.9

The fact that f is one-to-one follows from the previous exercise. To see that f is onto, suppose that b is an arbitrary element in the domain. Then from f(f(b))=b it follows that ∃x(f(x)=b). Therefore, f is onto.

Exercise 7.11

If f is not onto then ∃y∀x(f(x)≠y). Take an instance ∀x(f(x)≠a), and instantiate once as f(a)≠a and a second time as f(f(a))≠a. Since f is one-to-one and f(a)≠a, it follows that f(f(a))≠f(a). Putting the pieces together, we have

(a≠f(a))∧(a≠f(f(a)))∧(f(a)≠f(f(a)))

and thus

∃x∃y∃z((x≠y)∧(x≠z)∧(y≠z)).