# Proving by induction on the length of a propositional formula?

I'm having a little trouble understanding the following proof question because I'm unsure what defines the 'length' of a propositional formula, I've seen multiple definitions whether it's the number of variables, connectives etc..

Statement: Let $\mathcal A$ be the propositional formula which uses only the connectives ∨ and ∧ and only the propositional variables $p$. Prove using induction on the length of A such that $p ⇒ \mathcal A$.

Secondly I don't quite understand the statement I'm trying to prove as it asks to prove $p \Rightarrow \mathcal A$ where $p$ is the propositional variables in $\mathcal A$, do I have to show that every variable in $\mathcal A$ logically implies $\mathcal A$?

• What exactly is $p$? Is it one propositional variable or collection of propositional variables? If a collection, are they joined with commas (as in $r,s,t$), disjunctions (as in $r\land s\land t$), or other? – Rory Daulton Jun 6 '15 at 10:36
• I'm assuming the set of propositional variables with the naming convention $pi$ i.e $p1, p2$ and as the statement says they can only be joined by $\lor \land$ connectives so if that gives any idea as to what the propositional formula would look like – joe Jun 6 '15 at 10:43
• I interpret the question like this: if the only connectives appearing in $\mathcal A$ are $\lor$ and $\land$ and $p$ is the only propositional variable appearing in $\mathcal A$, then it follows that $\mathcal A$ will be equivalent to $p$. This would be so only if there's a typo in the problem statement, i.e. 'variables $p$' is supposed to be singular 'variable $p$'. – prime4567 Jun 6 '15 at 11:20
• @prime4567: Another possibility is to use it for a group of propositional variables such as $p,q,$ and $r$, and the statement to prove is $p\land q\land r\implies\mathcal A$. In that case implication is true and provable but equivalence is not. I deliberately left those points vague in my answer since they were vague in the question. – Rory Daulton Jun 6 '15 at 11:26
• It makes sense with one propositional variable $p$ and a formula $\mathcal A$ built up with only the connectives $\land$ and $\lor$ and $p$ (like : $p \lor p$ or $p \lor (p \land p)$). To show that $p \Rightarrow \mathcal A$ by induction on the lenght of $\mathcal A$ is to use as $n$ for induction the number of occurrences of connectives in it. For $n=0$, the property clearly holds, because $p \Rightarrow p$. Then assume it true for a formula $\mathcal A_n$ with $n$ occurrences of conenctives and prove that $p \Rightarrow \mathcal A_n \land p$ and $p \Rightarrow \mathcal A_n \lor p$. – Mauro ALLEGRANZA Jun 6 '15 at 13:18

It is not clear from your statement whether the proof is to strictly use induction on some variable such as the number of characters or some more general kind of induction.

Here is how I would do it. The definition of a well formed formula (wff) is almost always defined recursively. Your problem statement apparently uses something like this definition:

1. All propositional variables (such as $p$, $p1$, $p2$, etc.) are wffs.
2. If $\mathcal A$ is a wff then so is $(\mathcal A)$.
3. If $\mathcal A$ and $\mathcal B$ are wffs then so are $\mathcal A\land\mathcal B$ and $\mathcal A\lor\mathcal B$.
4. A statement is a wff if and only if it can be determined to be so by means of rules 1, 2, and 3.

(Note that a complete definition of wff would also include $\lnot\mathcal A$, $\mathcal A\implies\mathcal B$, and $\mathcal A\equiv\mathcal B$, and perhaps some others depending on your particular logical structure, but these are excluded in your problem.)

Then use induction on this (or the actual) definition. First show your problem is true for all propositional variables, then for wffs in parentheses, then for conjunctions and disjunctions.

If you need an actual variable to do induction on, note that each of those rules in the definition of a wff adds to the number of characters in the formula. You can then do induction on the number of characters in the formula. Use the induction

1. Show the statement is true for $n=1$ (statement letters).
2. Show that if the statement is true for all $k<n$ then it is true for $n$ (using definition rules 2 and 3).

In my first version, you could say $n$ is the number of applications of the rules for a wff. There are multiple ways to do the induction: pick the one that works best for you and the details of your class.

Is this clear?

• The induction was supposed to be done on the length of the propositional formula and as I expressed I wasn't sure what definition of 'length' of the propositional formula should be used here. When you say 'statement letters' you're referring to the number of propositional variables in the formula? – joe Jun 6 '15 at 11:11
• Almost: I mean the propositional variables themselves, not the number of them. At the end of my answer I mean the number of characters in the statement. I based my answer on Mendelson's Introduction to Mathematical Logic but I'll edit it to make it closer to your problem statement. – Rory Daulton Jun 6 '15 at 11:22
• This definition of a wff is not correct. Parentheses are necessary. By the rules above A ∧ B ∨ C would be a wff. Suppose A = 0, B = 0, C = 1 (0 is falsity, 1 is truth). Then A ∧ B ∨ C can evaluate to two different truth values. If A = 0, B = 1, and C = 1 we also have different evaluations. – Doug Spoonwood Jun 6 '15 at 23:14
• Some logic systems do require parentheses around all binary operators, but not all. I gave the more general definition since I did not know the OP's logic system. In your case we would use order of operations, where conjunction is done before disjunction. Again, some logic systems do it this way, but I admit not all. Do you have reason to believe that the definition I gave is never used? – Rory Daulton Jun 6 '15 at 23:21