Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 3, 2011 #1
    Hi physics forum,

    I have no idea where to start with this:

    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.

    Thanks in advance,

  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted