Summary of Predicate Calculus

Notation

Expressions: Scheme lists, e.g., ((turnip ?x) -> (bitter ?x))
Logic symbols: -> implication, ~ negation, V disjunction (or), & conjunction (and), A universal quantification (forall), E existential quantification (exists)
Variables: symbols preceded by ?

Atomic propositions represent facts (via an interpretation)
Propositions can be true or false
Logical connectives (~ V & -> ) group propositions into expressions whose truth values are defined (in truth tables) as a function of the truth values of the propositions which are connected
Some properties of logical connectives derivable from truth tables (p -> q) <=> (~p V q) (~ (~ p)) <=> p (~ (p & q)) <=> ((~ p) V (~ q)) (~ (p V q)) <=> ((~ p) & (~ q)) (p V (q & r)) <=> ((p V q) & (p V r)) (p & (q V r)) <=> ((p & q) V (p & r))
Propositional logic does not permit reference to relations and objects

Object constants
Relation constants (predicates), with associated arity, number of arguments
Function constants; functions
Variables
Terms
Atomic formulas, literals
Quantifiers (~ (A (?x) (p ?x))) <=> (E (?x) (~ (p ?x))) (~ (E (?x) (p ?x))) <=> (A (?x) (~ (p ?x)))
Well-formed formulas (sentences)
Rules of inference: conditions and conclusions (both sentence patterns); when sentences match conditions, we infer sentences matching the conclusions
- And elimination
- And introduction
- Universal instantiation
- Existential instantiation
- Modus ponens
- Modus tolens
Representing instance and isa relations and exceptions in predicate calculus
Natural language ambiguity and predicate calculus

Last updated: 6 February 1996
URL: http://www.indiana.edu/~gasser/Q351/pred_calc.html
Comments: gasser@salsa.indiana.edu
Copyright 1996, The Trustees of Indiana University