I'm having trouble with the following task:
Let A be a propositional formula that uses each variable at most once (e.g. (¬p1 → (p2 ∨ p3)), but not (¬p1 → (p2 ∨ p1))), and in particular does not include ⊤ nor ⊥. Show that A cannot be a tautology, and cannot be a contradiction.
Note: Formulas are defined recursively. Therefore a proof by induction is recommended, induction by the length of the formula. The induction step then contains: Case 1: A = p, Case 2: A = ¬B, Case 3: A = (B ∨ C) etc. for respectively shorter formulas B and C or p ∈ Var.**
I'm a complete beginner in logic, I really don't understand what is meant by the Note and I can't find any examples on the internet for this type of proof. I know the classic mathematical induction with n and n+1, but this is something new for me. It would be great to have explained how I need to approach this, step by step, maybe by another induction as inspiration or something. I hope someone can help me.
I think the basic idea in these kinds of proofs is to check that the property holds in one or a few base cases and then continues to hold if you construct new bigger formulas from the from the former smaller ones.
(An alternative approach to induction over the length would be induction on the degree of a formula, just mentioning in case you want to look that up too.)
So first you check that small formulas (as pointed out in the comments, in this example the single case of one propositional variable should suffice) are not tautological and also not contradictory.
In the induction step you suppose that the property holds for all formulas up to some length (or degree) $n$ and you take a look at a formula of length (or degree) $n+1$. This new bigger formula has a main connective and looks like this $A \rightarrow B$ or like this $\neg A$ or like this $A \lor B$.. etc. for all possible connectives.
But the subformulas $A$ and $B$ are smaller so we know they are not tautological and not contradictory. We also know that no propositional variable occurs in both, so their variables are distinct. So by an assignment of truth values both can be made true and false, independently of each other.
Suppose the bigger formula looked like this $A \lor B$.
We can pick an assignment that makes $A$ true. That will make $A \lor B$ true. We just said such an assignment exists.
We can also pick an assignment that makes $A$ and $B$ both false, since we can make both false independently of each other, as explained above. That will make $A \lor B$ false.
So, depending on your assignment, $A \lor B$ will be true or false, and hence it is not tautological and not contradictory.
The cases of the other connectives should be treatable in a similar way.