In predicate logic, the operators and laws of Boolean algebra still apply. For example, if P and Q are one-place predicates and a is an entity in the domain of discourse, then P(a) →Q(a) is a proposition, and it is logically equivalent to ¬P(a) ∨ Q(a). Furthermore, if x is a variable, then P(x) → Q(x) is an open statement, and ∀x(P(x) → Q(x)) is a proposition. So are P(a) ∧ (∃x Q(x)) and (∀x P(x)) → (∃xP(x)). Obviously, predicate logic can be very expressive. Unfortunately, the translation between predicate logic and English sentences is not always obvious.
One of the commonly-made mistakes in predicate logic is the difference in translation between statements like: “All humans are mortal” and “There is a human that is mortal”. We discuss the difference in translation of these statements in one of our pencasts: youtu.be/FxR07brGvkw.
Let’s look one more time at the proposition “Roses are red”. If the domain of discourse consists of roses, this translates into predicate logic as ∀x Red(x). However, the sentence makes more sense if the domain of discourse is larger—for example if it consists of all flowers. Then “Roses are red” has to be read as “All flowers which are roses are red”, or “For any flower, if that flower is a rose, then it is red”. The last form translates directly into logic as ∀x(Rose(x) → Red(x)). Suppose we want to say that all red roses are pretty. The phrase ‘red rose’ is saying both that the flower is a rose and that it is red, and it must be translated as a conjunction, Rose(x) ∧ Red(x). So, “All red roses are pretty” can be rendered as ∀x((Rose(x) ∧ Red(x)) → Pretty(x)).
Here are a few more examples of translations from predicate logic to English. Let H(x) represent ‘x is happy’, let C(y) represent ‘y is a computer’, and let O(x, y) represent ‘x owns y’. Then we have the following translations:
• Jack owns a computer: ∃x(O(jack, x) ∧ C(x)). (That is, there is at least one thing such that Jack owns that thing and that thing is a computer.)
- Everything Jack owns is a computer: ∀x(O(jack, x) → C(x)).
- If Jack owns a computer, then he’s happy: (∃y(O(jack, y) ∧ C(y))) → H(jack).
- Everyone who owns a computer is happy:
∀x( (∃y(O(x, y) ∧ C(y)) → H(x)) ).
- Everyone owns a computer: ∀x ∃y(C(y) ∧ O(x, y)). (Note that this allows each person to own a different computer. The proposition∃y ∀x(C(y) ∧ O(x, y)) would mean that there is a single computer which is owned by everyone.)
- Everyone is happy: ∀xH(x).
- Everyone is unhappy: ∀x(¬H(x)).
- Someone is unhappy: ∃x(¬H(x)). ( )
- At least two people are happy: ∃x∃y H(x) ∧ H(y) ∧ (x ) . (The stipulation that x is necessary because two different variables can refer to the same entity. The proposition ∃x∃y(H(x) ∧ H(y)) is true even if there is only one happy person.)
- There is exactly one happy person:
(∃xH(x))) ∧ (∀y∀z((H(y) ∧ H(z)) → (y = z))). (The first
part of this conjunction says that there is at least one happy person. The second part says that if y and z are both happy people, then they are actually the same person. That is, it’s not possible to find two differentpeople who are happy. The statement can be simplified a little however, to get: ∃x(H(x) ∧ ∀y(H(y) → (x = y))) Do you see why this works as well?)