# Axioms for propositional
logic

## Axioms for propositional
logic

### Motivation for
axioms for propositional logic

We discussed in the previous section the ability to derive new
tautologies from others using substitution and Modus Ponens.

We now aim to identify a group of axioms from which all tautologies
can be derived.

### The axioms

The first is known as "Simplification". In words, this is "if it is
cloudy, then if it is a Tuesday it is also cloudy."

\(\theta \rightarrow (\gamma \rightarrow
\theta )\)

The second is called "Frege".

\((\alpha \rightarrow (\beta \rightarrow
\gamma ))\rightarrow ((\alpha \rightarrow \beta )\rightarrow(\alpha
\rightarrow \gamma ))\)

The third is "Transposition". Consider the statement "If there are no
clouds in the sky, it is not raining." If this is true then it is also
true that "If it is raining there are clouds in the sky."

\((\neg \theta \rightarrow \neg \gamma
)\rightarrow (\gamma \rightarrow \theta )\)

### Independence of axioms

These axioms are independent. That is, if you take one away, you
cannot derive it from the others.

These axioms are also effective. One could define all true formulae
as axioms, however this is not effective.

### Soundness of axioms

Soundness implies that all theories are true.

\(T\vdash A \Rightarrow T\vDash
A\)

These axioms and the deduction rule are sound. We know that the
axioms are tautologies, and we know that the inference rule is
valid.

As the axioms are sound, the theories are consistent. That is, it is
not possible for both \(\theta\) and
\(\neg \theta\) to be theories.

### Completeness of axioms

Completeness implies that all true formulae are theories.

\(T\vDash A \Rightarrow T\vdash
A\)

### Axioms and definitions

A definition is a conservative extension of the language. A
definition statement, for example that a new symbol \(Z\) is always evaluated as false allows us
to make additional statements, but it does not allow us to make
additional statements in the original language.

An axiom allows us to generate additional statements in the original
language, a definition does not.