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

• 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