Predicate Logic, in a Nutshell

Predicate Logic is the core system of Formal Logic

Contents

Predicate Logic

Predicate Logic (First-order Logic, Elementary Logic, Predicate Calculus, First-Order Functional Calculus, Quantification Theory) is the core system of Formal Logic.
Predicate Logic consists of:
- a symbolic language,
- rules of inference that provide a way of proving an argument valid,
- a semantics that provides a way of proving an argument invalid.

How it Works, Briefly

How to determine whether the following argument is valid, i.e. whether the conclusion follows from the premises (assuming they’re true):
- Every living human being has a brain.
- No human zygote has a brain.
- Therefore, no human zygote is a living human being.
First, translate the argument into the language of Predicate Logic:
- Let
  - H mean is a living human being
  - Z mean is a human zygote
  - B mean has a brain.
- Then the formalized argument is:
  - ∀x(Hx → Bx)
    - That is: For any x, if x is a living human being then x has a brain.
  - ∀x(Zx → ~Bx)
    - That is: For any x, if x is a human zygote then x doesn’t have a brain.
  - Therefore, ~∃x(Zx & Hx)
    - That is: It’s false that there is an x such that x is a human zygote and x is a living human being.
Then, do one of the following:
- Prove that the argument is valid by deriving ~∃x(Zx & Hx) from ∀x(Hx → Bx) and ∀x(Zx → ~Bx) using the rules of inference of Predicate Logic;
- Prove that the argument is invalid by setting forth a counterexample, i.e. meanings for H, Z and B that make ∀x(Hx → Bx) and ∀x(Zx → ~Bx) true and ~∃x(Zx & Hx) false.
There is in fact a derivation of ~∃x(Zx & Hx) from ∀x(Hx → Bx) and ∀x(Zx → ~Bx). So the argument is valid (and therefore there’s no counterexample).

The Language of Predicate Logic

Traditional English grammar defines eight parts of speech: noun, pronoun, verb, adjective, adverb, conjunction, preposition, and interjection.
The language of predicate logic has five parts of speech:
- Names (Individual Constants), the analog of proper nouns such as “George Washington” and the “Statue of Liberty”.
- Predicate Letters, the analog of predicates (i.e. the part of a sentence that expresses what is said of the subject).
- Connectives, the analog of conjunctions (i.e. words that link words, phrases and clauses, e.g. “and”).
- Variables, the analog of pronouns.
- Quantifiers, the key part of speech of predicate logic and for which there is no analogous part of speech in English.

Names (Individual Constants)

Names are the lower case letters from “a” through “t”.
Like proper nouns, they are used to denote things.
The letters a, b, c, d, for example, might be used so that:
- “a” denotes George Washington,
- “b” denotes the number 5,
- “c” denotes the number 4,
- “d” denotes water.

Predicate Letters

Predicate letters are capital letters from “A” through “Z” plus the identity and non-identity signs “=” and “≠”.
Predicate letters express whatever can be predicated of something.
The letters T, S, P and G, for example, might be used so that:
- “T” means is over six feet tall,
- “S” means signed the Declaration of Independence,
- “P” means is a prime number,
- “G” means is a number greater than another number.
Predicate letters are attached to names, forming simple sentences.
Thus, using the examples:
- “Ta” means that George Washington is over six feet tall,
- “Pb” means that 5 is a prime number,
- “Gbc” means that 5 is greater than 4.
- c ≠ b means that 4 ≠ 5.

Connectives

Connectives are the symbols & v → ↔︎ ~

Conjunction &
- A & B means A and B
  - ∧ and ･are sometimes used instead of &
Disjunction v
- A v B means A or B (or both)
Conditional →
- A → B means if A then B
  - ⊃ is sometimes used instead of →
Biconditional ↔︎
- A ↔︎ B means A if and only if B
  - ≡ is sometimes used instead of ↔︎
Negation ~
- ~A means it’s false that A
  - ￢ and — are sometimes used instead of ~

Names, predicate letters, and connectives can be strung together to form sentences such as:
- Ta & ~Sa, meaning George Washington is over six feet tall and did not sign the Declaration of Independence;
- Pb v Pc, meaning that 5 or 4 is a prime number;
- Gbc → b ≠ c, meaning that if 5 is greater than 4 then 5 ≠ 4.

Variables

Predicate letters are attached to variables, forming simple formulas (not sentences), such as:
- Tx, Py, Gxx, and Gxy.
More complex formulas can be built up using connectives and names:
- Px, Tx & ~Sx, Px v Py, Gxy → x ≠ y, and Ta & ~Sx.
Like the pronoun “it” in the sentence “it is a prime number”, the variable “x” in “Px” doesn’t refer to anything and is said to be a free occurrence of “x” in “Px” (versus a bound occurrence of “x”).
A sentence is a formula with no free variables.
- Thus “Ta & ~Sa” and “Gbc → b ≠ c” are sentences. “Tx & ~Sx” and “Gxy → x ≠ y” are not.
Only sentences are true or false.

Quantifiers

Quantifiers make formulas with free variables into sentences.
There are two kinds of quantifier:
- The universal quantifier is the symbol ∀ followed by a variable, e.g. ∀x, ∀y, ∀z, …
  - “∀x …” means that for every x …
    - and is read “for any x” or “for all x”.
  - Likewise “∀y …” means that for every y …
  - And so on for other variables.
- The existential quantifier is the symbol ∃ followed by a variable, e.g ∃x, ∃y, ∃z, …
  - “∃x …” means that there is at least one x such that ….
    - and is read “there’s an x such that” or “there exists an x such that”
  - Likewise “∃y …” means that there is at least one y such that ….
  - And so for other variables

The Existential Quantifier

Putting ∃x in front of the formula Px & Gxb results in the sentence:
- ∃x(Px & Gxb)
  - which says that there is at least one x such that x is a prime number and x is greater than 5. That is, there’s a prime number greater than 5.
The “x” in ∃x is said to bind the occurrences of “x” in (Px & Gxb), making them bound rather than free.
Thus ∃x(Px & Gxb), having no free variables, is a sentence, meaning it’s true or false. In this case, true.

The Universal Quantifier

Putting ∀x∀y in front of the formula Gxy → x ≠ y results in the sentence:
- ∀x∀y(Gxy → x ≠ y)
  - which says that for any x and for any y, if x is greater than y, then x ≠ y. That is, if one number is greater than another, they’re not equal.
The “x” in ∀x binds the occurrences of “x” in (Gxy → x ≠ y), making them bound.
The “y” in ∀y binds the occurrences of “y” in (Gxy → x ≠ y), making them bound.
Thus ∀x∀y(Gxy → x ≠ y), having no free variables, is a sentence, either true or false. In this case, true.

Quantifiers thus make formulas such as Px & Gxb and Gxy → x ≠ y into sentences by binding their free variables.

The Logic of Quantifiers

The quantifiers not only represent the concepts all and some but have a key logical connection.
- To say that there exists at least one F is to say, in effect, that it’s false that everything is a non-F.
  - That is, ∃xFx is logically equivalent to ~∀x~Fx
- And to say that everything is an F is to say, in effect, that it’s false that there’s at least one non-F.
  - That is, ∀xFx is logically equivalent to ~∃x~Fx
Thus, “not all swans are white” and “some swans are not white” are two ways of saying the same thing.
- That is, ~∀x(Sx → Wx) and ∃x(Sx&~Wx) are logically equivalent.
  - where S means is a swan and W means is white.

Three Senses of the Verb To Be

Predicate Logic makes a syntactic distinction among three senses of “is.”
- The is of predication uses a predicate letter.
  - E.g. 5 is a prime number.
  - Translated as Pa, where “a” denotes 5 and “P” means is a prime number.
- The is of identity uses “=”.
  - E.g. Mark Twain is Samuel Clemens.
  - Translated as m = s, where “m” denotes Mark Twain and “s” denotes Samuel Clemens.
- The is of existence uses the existential quantifier.
  - E.g. there is a solution to the problem.
  - Translated as ∃xSx, where S means is a solution to the problem.

Translations into Predicate Logic

Black swans exist. (B: is black, S: is a swan)
- ∃x(Bx & Sx)
  - There exists an x such that x is B and x is S.
An oral contract isn’t worth the paper it is written on. (C: is a contract, O: is oral, W: is worth the paper it is written on)
- ∀x((Ox & Cx) → ~Wx)
  - For any x, if x is O and x is C then x isn’t W.
Nothing easy is worthwhile. (E: is easy, W: is worthwhile)
- ~∃x(Ex & Wx)
  - It’s false that there exists an x such that x is E and x is W.
Opposites attract. (O: are opposites, A: attract)
- ∀x∀y(Oxy → Axy)
  - For any x and y if x and y are opposites then x and y attract.
There is a guard on duty at all times (though not necessarily the same guard). (G: is a guard, T: is a time, D: is on duty at)
- ∀x(Tx → ∃y(Gy & Dyx))
  - For any x, if x is a time then there’s a y such that y is a guard and y is on duty at x.
The same guard is on duty at all times. (G: is a guard, T: is a time, D: is on duty at)
- ∃y(Gy & ∀x(Tx → Dyx))
  - There exists a y such that y is a guard and for any x if x is a time then y is on duty at x).
No two people have the same fingerprints. (P: is a person, F: has the same fingerprints as)
- ~∃x∃y(Px & Py & Fxy & x≠y)
  - There’s no x and y such that x is a person and y is a person and x and y have the same fingerprints and x is not y.

Proof that the Astral Twin Argument against Astrology is Valid

Astral Twin Argument against Astrology
- People born within minutes of each other in the same hospital have the same astrological chart.
- But some people born within minutes of each other in the same hospital don’t have the same personality traits.
- Therefore, not everyone with the same astrological chart has the same personality traits.

Argument in Symbolic Notation
- ∀x∀y((Bxy & Hxy) → Axy)
- ∃x∃y(Bxy & Hxy & ~Pxy)
- Therefore, ~∀x∀y((Axy → Pxy)
  - where
    - B means x and y are born minutes apart,
    - H means x and y are born in the same hospital,
    - A means x and y have the same astrological chart.
    - P means x and y have the same personality traits.
- That is:
  - For any x and y, if x and y are born minutes apart and x and y are born in the same hospital, then x and y have the same astrological chart.
  - There are x and y such that x and y are born minutes apart and x and y are born in the same hospital and it’s false that x and y have the same personality traits.
  - Therefore, it’s false that, for any x and y, if x and y have the same astrological chart then x and y have the same personality traits.

Derivation of ~∀x∀y((Axy → Pxy) from
- ∀x∀y((Bxy & Hxy) → Axy)
- ∃x∃y(Bxy & Hxy & ~Pxy)
That is, derivation of line 13 from lines 1 and 2.

{1} ∀x∀y((Bxy & Hxy) → Axy)
- Premise
{2} ∃x∃y(Bxy & Hxy & ~Pxy)
- Premise
{3} ∃y(Bay & Hay & ~Pay)
- Premise
{4} Bab & Hab & ~Pab
- Premise
{1} ∀y((Bay & Hay) → Aay)
- Universal Specification on #1
{1} (Bab & Hab) → Aab
- Universal Specification on #6
{1,4} ~(Aab → Pab)
- Tautological Inference on #4 and #6
{1,4} ∃y~(Aay → Pay)
- Existential Generalization on #7
{1,4} ~∀y((Aay → Pay)
- Quantifier Exchange on #8
{1,4} ∃x~∀y((Axy → Pxy)
- Existential Generalization on #9
{1,4} ~∀x∀y((Axy → Pxy)
- Quantifier Exchange on #10
{1,3} ~∀x∀y((Axy → Pxy)
- Existential Specification on #3, #4, #11
{1,2} ~∀x∀y((Axy → Pxy)
- Existential Specification on #2, #3, #12

Counterexamples in Predicate Logic

A counterexample to an argument-form is an interpretation of the predicate letters under which the premises are true and the conclusion false, thereby showing the argument-form invalid.

First Counterexample

Invalid Argument-form:
- ~∀x(Fx → Gx)
  - It’s false that all F’s are G’s
- ~∀x(Gx → Hx)
  - It’s false that all G’s are H’s
- Therefore, ~∀x(Fx → Hx)
  - It’s false that all F’s are H’s
Counterexample:
- F: is an integer > 10
- G: is an integer < 7
- H: is an integer > 5
Thus:
- Not every integer greater than 10 is less than 7, e.g 11.
  - True
- Not every integer less than 7 is greater than 5, e.g. 4.
  - True
- Not every integer greater than 10 is greater than 5
  - False

Second Counterexample

Invalid Argument-form:
- ∀x∃yRxy
  - For every x, there’s at least on y that R’s x.
- ∀x∀y(Rxy → Ryx)
  - For any x and y, if x R’s y then y R’s x.
- Therefore, ∀xRxx
  - For any x, x R’s itself.
Counterexample:
- R: are integers adjacent to each other (that is, either x − y = 1 or y − x = 1)
Thus:
- For every integer, there’s at least one integer adjacent to it.
  - True
- For any integers x and y, if x and y are adjacent to each other, then y and x are adjacent to each other.
  - True
- Every integer is adjacent to itself.
  - False

Rules of Inference for Predicate Logic with Identity

Adapted from Benson Mates Elementary Logic

In the following rules:
- φ and ψ are formulas
- α is a variable
- β is a name
- φα/β is the result of replacing all free occurrences of α in φ with occurrences of β
  - e.g. φα/β = “Fb → Gb”, where φ = “Fy → Gy” and α = “y” and b = “b”

Premise Introduction (P): Any sentence may be entered on any line of a derivation.
- As the sole premise-number of the line take the line-number.
Tautological Inference (T): Any sentence may be entered on a line if it is a tautological consequence of a set of sentences that appear on earlier lines.
- As premise-numbers of the new line take all those of the earlier lines.
Conditionalization (C): The sentence φ → ψ may be entered on a line if ψ appears on an earlier line.
- As premise-numbers of the new line take all those of the earlier line, with the exception of any that is the line number of a line on which φ appears.
Universal Specification (US): The sentence φα/β may be entered on a line if ∀αφ appears on an earlier line.
- As premise-numbers of the new line take all those of the earlier line.
Existential Generalization (EG): The sentence ∃αφ may be entered on a line if φα/β appears on an earlier line.
- As premise-numbers of the new line take all those of the earlier line.
Universal Generalization (UG): The sentence ∀αφ may be entered on a line if φα/β appears on an earlier line and β occurs neither in φ nor in any premise of that earlier line.
- As premise-numbers of the new line take all those of the earlier line.
Existential Specification (ES): Suppose that ∃αψ appears on a line i of a derivation, that ψα/β appears (as a premise) on a later line j, and that φ appears on a still later line k; and suppose further that the constant β occurs neither in φ, ψ nor in any premise of line k other that Ψα/β; then φ may be entered on a new line.
- As premise-numbers of the new line take all those of lines i and k, except the number j.
Quantifier Exchange (Q): The sentence ~∀α~φ may be entered on a line if ∃αφ appears on an earlier line and vice versa. Likewise for the following pairs of sentences: ∀αφ and ~∃α~φ; ~∀αφ and ∃α~φ; ~∃αφ and ∀α~φ.
- As premise-numbers of the new line take all those of the earlier line.
Identity introduction (II): α=α may be entered on any line of a derivation with no premise-numbers.
Leibniz Law (LL): φ may be entered on a line if α=β and ψ appear on earlier lines (where φ results from ψ by replacing one or more occurrences of α in ψ with β).
- As premise-numbers of the new line take all those of the earlier lines.