logic pset7

Please note: there is no pset6, as the pset numbers correspond to the week number of the course.


Represent the form of the following sentences in predicate logic. We’ve suggested appropriate symbols. (For the sentences about people, you don’t need to add an extra predicate for “x is a person.”)

  1. Not all logicians are celebrities. (Lx,Cx)

  2. No logicians are celebrities. (Lx,Cx)

  3. Only students who do the homework will learn logic. (Sx,Hx,Lx)

  4. All students and professors get a discount. (Sx,Px,Dx)

  5. Everyone loves their mother. (Lxy,Mxy)

  6. Every student respects every professor who respects every student. (Sx,Px,Rxy)

  7. Mark pays the debts of all and only those people who don’t pay their own debts. (m,Pxy ≡ x pays the debts of y)


Prove the following sequents using the propositional logic rules, UE, or UI.

  1. ∀x(Fx→Gx) ⊢ ∀xFx→∀xGx

  2. ∀xFx,∀xGx ⊢ ∀x(Fx∧Gx)

  3. ∀xFx∨∀xGx ⊢ ∀x(Fx∨Gx)

  4. ∀x(Fx → ∀yGy) ⊢ ∀x∀y(Fx → Gy)

  5. ∀x∀y(Fx → Gy) ⊢ ∀x(Fx → ∀yGy)

  6. ∀x(∀yRxy → Rxx)


What is the error in the following “proof”. A good answer can be as short as one sentence.

1   (1) ∀xFx→∀xGx     A
2   (2) Fa            A
2   (3) ∀xFx          2 UI
1,2 (4) ∀xGx          1,3 MP
1,2 (5) Ga            4 UE
1   (6) Fa→Ga         2,5 CP
1   (7) ∀x(Fx→Gx)     6 UI