Set

Review of Inference Rules



List of Implications:
  1. P (P Q) ----- addition
  2. (P Q) P ----- simplification
  3. [P (P Q] Q ----- modus ponens
  4. [(P Q) Q] P ----- modus tollens
  5. [ P (P Q] Q ----- disjunctive syllogism
  6. [(P Q) (Q R)] (P R) ----- hypothetical syllogism
  7. (P Q) [(Q R) (P R)]
  8. [(P Q) (R S)] [(P R) (Q S)]
  9. [(P Q) (Q R)] (P R)


List of Identities:
  1. P (P P) ----- idempotence of
  2. P (P P) ----- idempotence of
  3. (P Q) (Q P) ----- commutativity of
  4. (P Q) (Q P) ----- commutativity of
  5. [(P Q) R] [P (Q R)] ----- associativity of
  6. [(P Q) R] [P (Q R)] ----- associativity of
  7. (P Q) ( P Q) ----- DeMorgan's Law
  8. (P Q) ( P Q) ----- DeMorgan's Law
  9. [P (Q R] [(P Q) (P R)] ----- distributivity of over
  10. [P (Q R] [(P Q) (P R)] ----- distributivity of over
  11. (P True) True
  12. (P False) False
  13. (P False) P
  14. (P True) P
  15. (P P) True
  16. (P P) False
  17. P ( P) ----- double negation
  18. (P Q) ( P Q) ----- implication
  19. (P Q) [(P Q) (Q P)]----- equivalence
  20. [(P Q) R] [P (Q R)] ----- exportation
  21. [(P Q) (P Q)] P ----- absurdity
  22. (P Q) (Q P) ----- contrapositive


Inference Rules Involving Quantifiers
  1. Universal Instantiation:

    x P(x)
    -------
    P(c)

    where c is some arbitrary element of the universe.


  2. Go to Universal Instantiation for further explanations and examples.

  3. Universal Generalization:

    P(c)
    ----------
    x P(x)

    where P(c) holds for every element c of the universe of discourse.


  4. Go to Universal Generalization for further explanations and examples.

  5. Existential Instantiation:

    x P(x)
    -------
    P(c)

    where c is some element of the universe of discourse. It is not arbitrary but must be one for which P(c ) is true.


  6. Go to Existential Instantiation for further explanations and examples.

  7. Existential Generalization:

    P(c)
    ----------
    x P(x)

    where c is an element of the universe.


  8. Go to Existential Generalization for further explanations and examples.

Negation of Quantified Statement

    x P(x) x P(x)

Quantifiers and Connectives
  1. x [ P(x) Q(x) ] [ x P(x) x Q(x) ]
  2. [ x P(x) x Q(x) ] x [ P(x) Q(x) ]
  3. x [ P(x) Q(x) ] [ x P(x) x Q(x) ]
  4. x [ P(x) Q(x) ] [ x P(x) x Q(x) ]