# Predicate Logic (Natural deduction & transcription)

1. Transcribe each of the following using Predicate Logic plus Identity.

(a) There are exactly two professors who respect every student.

(b) There are exactly two professors and they respect every student.

• Welcome to PSE! For wrapping my head around these kinds of problems, I often think in terms of sets/venn diagrams. Dec 2, 2014 at 22:55
• What exactly is it that you're having trouble with? If you tell us what you don't understand, we can try to explain, instead of just showing you the answer :-)
– user2953
Dec 2, 2014 at 23:03
• Also, did you get the notation !Exists? It means there exists exactly one ... - This could be helpful for the second exercise. And did you already learn notation for 'the amount of elements of a set'?
– user2953
Dec 2, 2014 at 23:06
• Where I'm mainly getting stuck is on problem 1, when I have to use existential elimination.
– Soph
Dec 3, 2014 at 1:06

For 1a, you are able to go from ∀xFx to Fc, where c is an arbitrary constant. Then anything you can prove about c can be generalized by a universal quantifier, since c was arbitrary.

I think the most helpful rule for this 1b would be Df∃ and Df∀. They just say that: ∀xFx <-> ~∃x(~Fx) ∃xFx <-> ~∀x(~Fx)

For the second problem, existential quantifiers insure a certain amount of something. If I say ∃x∃y, there are at least two things. Likewise, existential quantifiers can tell you when there is no more of something ~∃x. The trick is in the variables you use.

EDIT: Thanks jobermark, I did slip up there.

• It is not true that every variable represents something different. ∃x∃y does not imply there are two things, because it might be true that x=y. You need to be explicit and say ∃x∃y~(x=y). If I have an old, blue thing in a box I can say there is an old thing in the box for which there is a blue thing in the box of the same size, without implying the box contains two things.
– user9166
Dec 10, 2014 at 20:08
• I think the Df laws are a great hint. It is useful to think of ∀xPx as Px[1] ∧ ... ∧ Px[n] and ∃xPx as Px[1] V ... V Px[n] where x[i] enumerates all of the possible x's, (even when they cannot literally be enumerated.) And then these are just the same DeMorgan's laws of negation we use with a single 'and' or 'or'.
– user9166
Dec 10, 2014 at 20:11

In the first exercice, you have to use natural deduction rules (elimination of quantifiers) to go from the premises to the conclusion. Hint: it helps, sometimes, to start from the end. For example, to prove the negation of a proposition, assume the proposition itself and try to derive a contradiction (1a). To prove a universal proposition, assume a new random variable and deduce the proposition for it. And so on recursively if needed (1b).

In the second exercice, perhaps try to feel the difference in meaning between the two sentences, and try to translate that difference in a formal language. Hint: it has to do with the scope of quantifiers. I suppose you learned how to translate "there are two X" in formal language?

I think this is correct. But I would need some feedback. Translations can be tough.

(a) There are exactly two professors who respect every student.

∀q[Sq → ∃x∃y(Px ∧ Py ∧ x≠y ∧ ∀z(Pz → z=x V z=y) ∧ Rxq ∧ Ryq)]

(b) There are exactly two professors and they respect every student.

∃x∃y[ Px ∧ Py ∧ x≠y ∧ ∀z(Pz → z=x V z=y) ∧ ∀q(Sq → Rxq ∧ Ryq)]