# Propositional Logic

Propositional logic is based on Propositions, statements about the world that can be either true or false.

All binary logical connectives are right associative. $aāØbāØcĀ meansĀaāØ(bāØc)$ $aā¹bā¹cĀ meansĀaā¹(bā¹c)$

### Checking that a formula is a Tautology

If you remember, from the definition of Tautology, itās that a āpropositional formula $P$ is a tautology (or valid) if $[P]=T$ for **all** Boolean valuationsā. You can check that with a Tautology, itās that a āpropositional formula $P$ is a tautology (or valid) if $[P]=T$ for **all** Boolean valuationsā. You can check that with a Truth Table. However, that truth table grows exponentially with the number of propositional symbols.

Another way we can determine whether a formula is a Tautology is by using a Tautology is by using a Proof Theory!

Proof Theory for Propositional Logic:

- Transformational Proof (sideways proof, statement algebra,$<ā>$)
- Natural Deduction (forward proof, $ā¢$)
- Semantic Tableaux (backward proof, $ā¢$)
- Hilbert Systems (axiom systems)
- Resolution
- DPLL (Davis Putnam Logeman Loveland)
- Binary Decision Diagrams

The only condition is that we need to make sure that our Proof Theory is Sound.