## 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.
- A
** sentence** is either an **atomic sentence** or a
**complex sentence**
- An
**atomic sentence** = true or false or a literal.
- A
**complex sentence** is one of
- ( Sentence)
- Sentence
** Connective ** Sentence
- ~ Sentence

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

- 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