Proving Positive WFFs with Induction

[kp100591]

hello, i was wondering if anyone could help me with this induction proof.
thank you

A positive well-formed formula in the Propositional Calculus is a well-formed formula that avoids all use of the negation symbol ∼ .
(a) Use induction on the length of a wff to prove that if W = W(P1,...,Pn) is a positive wff in terms of propositional variables P1, . . . , Pn, then
V(P1) = ... = V(Pn) = T implies V(W)=T .

 

[Evgeny.Makarov]

Hello again, and welcome to the forum! I am glad you found MHB. I like it more than MMF. Nevertheless, I gave you a pretty detailed help in this thread on MMF, and I think it would make sense to start from there. I believe the information I wrote is necessary in order to understand structural induction. (Induction on formula length is almost the same as structural induction on formulas themselves, and I believe the latter concept is cleaner.) If you have any questions about it, I would be happy to answer them here.

I also know that many textbooks on logic and computer science have introductory sections that discuss structural induction because it is an indispensable tool for proving properties of formulas. I am wondering if your textbook has it as well. If you need book references, let us know.

The fact you need to prove is similar to the following. If you have an arithmetic expression $f(x_1,\dots,x_n)$ that uses variables $x_1,\dots,x_n$ and only addition and multiplication (no subtraction or division), then this expression is monotonic. That is, if $x_1\le y_1$, ..., $x_n\le y_n$, then $f(x_1,\dots,x_n)\le f(y_1,\dots,y_n)$. Intuituvely, this is obvious: this is true if $f(x)=x$, and multiplication and addition are monotonic, i.e., greater arguments lead to greater results. Formally, this is proved by structural induction on $f$.