Propositional Logic

In propositional logic the symbols represent facts. These facts are combined using Boolean connectives

The Sentences of Propositional Logic

The following is a grammar for the sentences of propositional logic.
  1. A sentence is either an atomic sentence or a complex sentence
  2. An atomic sentence = true or false or a literal.
  3. A complex sentence is one of
    1. ( Sentence)
    2. Sentence Connective Sentence
    3. ~ Sentence
  4. A Connective is one of /\, \/, < = >, or =>
The semantics of propositonal logic is given by the truth tables for /\, \/, ~, < = >, and =>.

Truth tables can be constructed for complex sentences. This gives a complete and sound inference method.

Proof Rules for Propositional Logic

Modus Ponens
From a = > b and a deduce b
and elimination
From a1/\ a2 /\a3/\ .../\ak deduce a1
and introduction
from a1 , a2, a3, ... , ak deduce a1/\ a2 /\a3/\ .../\ak
Or introduction
from a1 deduce a1 \/ a2 \/ a3\/ ...\/ ak
Double negation elimination
from ~ ~ a deduce a
Unit resolution
from a \/ b and ~b deduce a
from a \/ b and ~b \/ c deduce a \/ c. This is the same as from ~a = > b and b = > c deduce ~a = > c

Return to UG AI home page

Last Changed: 14 October 1995