Natural Deduction (Predicate Logic)

Builds off of Natural Deduction in Propositional Logic.

List of Additional Rules

You can substitute whatever you want as since it's universally quantified. means substituted into . Note that cannot be an a variable that is already bound (#Variable Capture).

If is true for some value, then there exists a value for which is true. We call a witness to the truth of . Additionally, cannot capture any variables, and we cannot remove functions which rely on bound variables.

must be free for in .

Property

Natural deduction proofs for predicate logic are both sound and complete

Variable Capture

Definition

Variable capture means a location that had a free variable in it becomes bound after the substitution or a location that had bound variable becomes bound to a different quantifier.

Examples

  1. if is then is not allowed
  2. If is
    • Then is
    • Then is not allowed (capture on )

Example

For the formula:

we canNOT chose as our term and conclude:

because the term contains a variable that is bound in the formula.

Important

Watch out for this tricky step:

Line 5 is NOT THE SAME as .

Genuine and Unknown Variables

Definition

  • is an unknown variable iff not all values of satisfy a particular formula
  • is a genuine variable iff all values of satisfy a particular formula

Example

  • is really , is an unknown variable
  • is really , is a genuine variable

To help us in our proofs, we sometimes label variables with "g" and "u" to mark them at genuine and unknown (e.g )

Examples

Example

is a constant. Prove:

proof

Example

Prove:

proof

Example

Prove:

proof

Prove:

proof

Example

Prove:

proof

Example

Prove:

proof

Prove:

proof

Example

Prove:

proof

Prove:

proof

Prove:

proof

Example - Negation of Quantifier rules

Prove:

proof

Example - Commutativity of Quantifiers

Prove:

proof

Example

Prove:

proof

Example

Prove:

proof