Propositional Logic

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

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 =>

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

• A proposition is valid if it is true for all possible assignments of truth values to its atomis components.
• It is statisfiable if there is an assignment of truth values to its components that makes it true. If there is no such assignment it is called unsatisfiable.

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

Resolution

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