# Proofs by induction on immediate predecessors (well-formed formula complexity)

1. Oct 3, 2011

### StopWatch

Hi physics forum,

As far as I know the general pattern for this sort of proof is,

1) All atomic well-formed formulas (wffs) have some property P
2) From the assumption that immediate predecessors of any non-atomic wff A have P, so too does A.
3) Every wff A has P

and I have to:

Prove by induction on immediate predecessors (wff complexity) that
no wff using only the letters P, Q and the connectives ^,v is a tautology.

Any suggestions would be much appreciated.