Wednesday, November 26, 2008

Soundness and Completeness

In first post I define provability of propositional formula. But propositional formula can be interpreted as a Boolean function and if it is equal to true for every arguments then we say that propositional formula is tautology. In similar way if proposition is equal to false for every arguments then it called contradiction.
Let's discuss L propositional calculus, where
Connectives are \neg and →.
Axioms are
  1. A→(B→A).
  2. (A→(B→C))→((A→B)→(A→C)).
  3. (\negB→\negA)→((\negB→A)→B)
And the only inference rule is MP(Modus Ponens).

This system has good properties, such that every tautology is provable L and any provable formula is tautology.The first one is called Completeness and anothe one is called Soundness

Theorem(Soundness) ├P => P is tautology.

Theorem(Completeness) P is tautology => ├P.

No comments: