In propositional logic the symbols represent facts. These facts are combined using
The Sentences of Propositional Logic
The following is a grammar for the sentences of propositional logic.
The semantics of propositonal logic is given by the truth tables for /\, \/, ~,
< = >, and =>.
- A sentence is either an atomic sentence or a
- 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 =>
Truth tables can be constructed for complex sentences. This gives a complete and sound
- 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
- from a \/ b and ~b \/ c deduce a \/ c. This is the same as
from ~a = > b and b = > c deduce ~a = > c
UG AI home page
Last Changed: 14 October 1995