Hi physics forum,(adsbygoogle = window.adsbygoogle || []).push({});

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,

Stopwatch

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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)

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

Loading...

Similar Threads - Proofs induction immediate | Date |
---|---|

I Can you use proof by contradiction in the midst of induction | Mar 21, 2016 |

Simple Proof for using Induction | Oct 8, 2014 |

Cantor set ℵ , inductive proofs by openly counting. | Nov 8, 2013 |

What's the point of inductive proofs? | Nov 2, 2013 |

Base Case in Strong Induction Proofs | Mar 30, 2013 |

**Physics Forums - The Fusion of Science and Community**