Skip to main content

Subsection 5.2.2 Universal Generalization Proof Problem: The Barber

The Barber

Assume that whenever we have a barber and a person who needs a haircut then the barber can cut the person’s hair. Let’s show that any barber who needs a haircut could cut his/her own hair. (But notice that, in the real world, self barbering is actually hard. Maybe what we really should do is to change our premise to prevent drawing our conclusion.)

Assign the following names to basic statements:

B(x): True if x is a barber.

H(x): True if x needs a haircut.

C(x, y): True if x can cut y’s hair.

Prove: ∀x (∀y ((B(x) ∧ H(y)) → C(x, y))) Whenever we have a barber and a

person who needs a haircut then the

barber can cut the person’s hair.

∴∀z ((B(z) ∧ H(z)) → C(z, z)) Any barber who needs a haircut can

cut his or her own hair.

You should do this proof yourself.

You can also watch our video, which will outline our strategy for doing this.

Video cover image

Exercises Exercises

1.

Amazed Teacher : Assume the following premise:

[1] (∀x (Student(x) → CompletedHomework(x))) → Amazed(Teacher)

Assume that we want to prove:

Amazed(Teacher)

Which of the following statements, would if combined with [1], be sufficient to enable us to prove Amazed(Teacher)?

I. Student(Flopsy)

II. CompletedHomeworks(Flopsy)

III. ∀x (CompletedHomework(x))

  1. I and II are sufficient.

  2. III is sufficient.

  3. All of them are required.

  4. No combination is sufficient.

Answer.
Correct answer is B.
Solution.

Explanation: If everyone completed the homework, then this statement is also true:

x (Student(x)  CompletedHomework(x))

Then all we need is Modus Ponens to prove the claim.

2.

Let’s continue the Amazed Teacher example. We’ll abbreviate CompletedHomework(x) as Done(x). Assume the following premises:

[1] (∀x (Student(x) → Done(x))) → Amazed(Teacher)

[2] ∀x (Done(x))

Prove Amazed(Teacher).

Answer.
questionId: AmazedTeacher problemType: gradeLogicProof questionTitle: Universal Instantiation and Generalization Practice questionDisplayText: Prove that the teacher is amazed. hints: You will want to do most of your reasoning about some typical student. Notice that, in the first premise, the antecedent of the outer implication is an entire quantified expression. [1] (x (Student(x)  Done(x)))  Amazed(Teacher) Premise [2] x (Done(x)) Premise [3] Done(c) Universal Instantiation [2] [4] Student(c)  Done(c) Addition [3] [5] Student(c)  Done(c) Conditional Disjunction [4] [6] x (Student(x)  Done(x)) Universal Generalization [5] [7] Amazed(Teacher) Modus Ponens [1], [6]
Solution.

3.

NotMotherOfSelf : Assume the following premise:

[1] ∀x (∀y (MotherOf(x, y) → ¬MotherOf(y, x)))

Prove: ∀x (¬MotherOf(x, x))

3. Assume the following premises:

[1] ∀x (P(x) ∨ R(x))

[2] ∀x ((P(x) ∨ (Q(x) ∨ R(x))) → W(x))

Prove: ∀x (W(x) ∨ S(x))

Answer.
questionId: NotMotherOfSelf problemType: gradeLogicProof questionTitle: Instantiation and Generalization Practice questionDisplayText: Prove that no one is her own mother. hints: Try using Universal Instantiation twice. You will probably want to use Conditional Disjunction to get rid of the →. [1] x (y (MotherOf(x, y)  MotherOf(y, x))) Premise [2] y (MotherOf(a, y)  MotherOf(y, a)) Universal Instantiation [1] [3] MotherOf(a, a)  MotherOf(a, a) Universal Instantiation [2] [4] MotherOf(a, a)  MotherOf(a, a) Conditional Disjunction [3] [5] MotherOf(a, a) Idempotence [4] [6] x (MotherOf(x, x)) Universal Generalization [5]
Solution.

4.

Assume: [1] ∀x (P(x) ∨ R(x))

[2] ∀x ((P(x) ∨ (Q(x) ∨ R(x))) → W(x))

Prove: ∀x (W(x) ∨ S(x))

Answer.
questionId: PsQs01 problemType: gradeLogicProof questionTitle: Instantiation and Generalization Practice questionDisplayText: Prove a general claim about the properties S and W. hints: 1. Try using Universal Instantiation twice. 2. S isn’t mentioned in any of the premises. You need to find a way to introduce it. Consider Addition. [1] x (P(x)  R(x)) Premise [2] x ((P(x)  (Q(x)  R(x)))  W(x)) Premise [3] (P(a)  (Q(a)  R(a)))  W(a) Universal Instantiation [2] [4] P(a)  R(a) Universal Instantiation [1] [5] (P(a)  R(a))  Q(a) Addition [4] [6] P(a)  (R(a)  Q(a)) Associativity of or [5] [7] P(a)  (Q(a)  R(a)) Commutativity of or [6] [8] W(a) Modus Ponens [3], [7] [9] W(a)  S(a) Addition [8] [10] x (W(x)  S(x)) Universal Generalization [9]
Solution.