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

[StopWatch]

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,

Stopwatch

 

[mighty2000]

Hi Stopwatch,

First, let's define the terms we are dealing with. A well-formed formula (wff) is a string of symbols that follows the rules of a given formal language, in this case using the letters P, Q, and the connectives ^ (conjunction) and v (disjunction). A tautology is a wff that is always true, regardless of the truth values assigned to its atomic components.

Now, for the proof by induction. We will use the three steps you mentioned in your post, but let's break them down further for clarity:

1) All atomic wffs have the property of not being a tautology. This is true by definition, since atomic wffs consist of a single letter (P or Q) and cannot be both true and false at the same time.

2) From the assumption that immediate predecessors of any non-atomic wff A have the property of not being a tautology, we can show that A also has this property. This is because the truth value of A is determined by the truth values of its immediate predecessors, and if those predecessors are not tautologies, then A cannot be a tautology either.

3) By using the principle of mathematical induction, we can conclude that all wffs have the property of not being a tautology. This is because we have shown that all atomic wffs have this property, and that any non-atomic wff A will also have this property if its immediate predecessors have it.

In conclusion, we can prove that no wff using only the letters P, Q and the connectives ^,v is a tautology by showing that each step in the induction process holds true. I hope this helps you get started on your proof.

Best of luck,