One limitation of the propositional calculus is that you cannot refer to the components of a statement. For example, it would be impossible to prove that the following argument is valid in the propositional calculus:

All humans are mortal.
Socrates is human.
Therefore, Socrates is mortal.

The predicate calculus allows us to break these kinds of statements into parts. For example, to represent "Socrates is mortal" we would use mortal(socrates), where mortal is a predicate symbol, and socrates refers to an object. As we'll see, if we represent things in this way, we can prove that the above argument is valid.

Predicate Calculus Syntax

TYPE	SYMBOLS
Alphabet	a..z, A..Z, 0..9, and _.
Symbols	Any sequence of alphabet characters beginning with a letter.
Variables	Begin with an UPPERCASE letter
Constants	Begin with an lowercase letter
Functions	Begin with an lowercase letter
Predicates	Begin with an lowercase letter

• A function expression consists of a function of arity n followed by n terms, t₁, ..., t_n, enclosed in parentheses and separated by commas.

• A term is a constant, variable, or function expression. Examples of Terms:

  cat
  times(2,3)
  times(square(2),3)
  X
  true
  mother(jane)
  

• A predicate symbol names a relationship between 0 or more objects in the world. Examples of Predicates:

  likes
  equals
  above
  on
  part_of
  

• A atomic expression is predicate of arity n followed by n terms enclosed in parentheses and separated by commas. Examples of Atomic Expressions:

  likes(george,kate).
  likes(george,susie).
  likes(X,george).
  likes(X,X).
  friends(bill,george).
  friends(father(david),father(bill)).
  

  NOTE: The predicates are likes and friends. But father() is a function name. As we will see, function expressions designate objects. For example, father(bill) may designate joe, but predication expressions, such as likes(george,kate), designate truth values.

• Sentences are formed by combining atomic expressions using the logical connectives: ^, v, ~, ->, and =.

  likes(george,kate) -> likes(kate,george).
  likes(george,susie) ^ likes(susie,george).
  ~friends(bill,george).
  

• When a variable occurs in a sentence, it refers to unspecified objects in the domain. The variable quantifiers ∃, there exists, and ∀, for all, are used to clarify the meaning of sentences that involve variables.

  Examples:
  ∃ Y friends(Y,peter).
  ∀ X likes(X,ice_cream).
  

  Literally, the first sentence says "There exists a Y such that Y is friends with peter. More colloquially this says, "Someone is friends with peter." Literally the second sentence says "For all X, X likes ice_cream" or more colloquially "Everybody likes ice_cream."

Summary of Syntax Rules

• Every atomic expression is a sentence.

• If s is a sentence, then so is ~s.

• If s₁ and s₂ are sentences, then so is s₁ ^ s₂.

• If s₁ and s₂ are sentences, then so is s₁ v s₂.

• If s₁ and s₂ are sentences, then so is s₁ -> s₂.

• If s₁ and s₂ are sentences, then so is s₁ = s₂.

• If X is a variable and s is a sentence, then ∀ X s is a sentence.

• If X is a variable and s is a sentence, then ∃ X s is a sentence.

Examples:

plus(two,three) is a function and not a sentence.
equal(plus(two,three),five). is a sentence.
equal(plus(two,three),seven). is a (false) sentence.
equal(plus(two,three),seven) -> equal(five,seven). is a sentence.
∃ Y integer(Y) ^ greater(Y,two). is a sentence
∀ X integer(Y) ^ (odd(Y) v even(Y)). is a sentence

Examples

mother(eve,abel).
mother(eve,cain).
father(adam,abel).
father(adam,cain).
∀ X ∀ Y (father(X,Y) v mother(X,Y)) -> parent(X,Y).
∀ X ∀ Y ∀ Z (parent(X,Y) ^ parent(X,Z)) -> sibling(Y,Z).

These would be translated as:

Eve is the mother of Abel.
Eve is the mother of Cain.
Adam is the father of Abel.
Adam is the father of Cain.
For all X and Y, X is the parent of Y if X is the father of Y or X is the mother of Y.
For all X, Y, and Z, Y is a sibling of Z if X is a parent of Y and X is a parent of Z.

Some Translation Rules of Thumb

• "All", "any", "always", "no", "never" are usually symbolized with the universal quantifier.

• "Some", "sometimes" are usually symbolized with the existential quantifier.

• The universal quantifier always requires an implication: ->.

• The existential quantifier always requires a conjunction: ^.

• "Only if" suggests a necessary condition and should be symbolized as the consequent of an implication: e.g., "The car starts only if it has gas" means "In order to start it is necessary for the car to have gas". However, having gas is not a sufficient condition. So it is wrong to say "If the car has gas then it will start." Instead, this should be symbolized as "If the car starts, then it has gas" -- starts(car) -> gas(car) --

Exercise:  Translate each of the following expressions into English.

sister(jane,joan).
brother(bill,bob).
mother(ann,bill).
father(jim,jane).
∀ X ∀ Y (sister(X,Y) v brother(X,Y)) -> sibling(X,Y).
∀ X ∃ Y sister(X,Y) -> female(X).
∃ X ∃ Y ∃ Z sister(X,Y) ^ mother(X,Z).
∀ X ∀ Y ∀ Z (sister(X,Y) ^ mother(Z,X)) -> mother(Z,Y).
∀ X ∀ Y ∀ Z (sister(X,Y) ^ sister(Y,Z)) -> sister(X,Z).

Exercise: Translate each of the following sentences into predicate calculus sentences.

Some students are lazy.
Some students got Bs.
All students received a passing grade.
Not every student received an A.
Not any student received an A.
An aspirin a day keeps the doctor away.
Baseball players are always male.
Children are in the classroom.
Everything is coming up roses.
Everything that happens isn't his fault.
Only items purchased in Sears can be returned to Sears.
Freshman are not always lonesome.