MHB Proving Positive WFFs with Induction

AI Thread Summary
The discussion focuses on proving that a positive well-formed formula (wff) in propositional calculus maintains truth values under certain conditions using induction. It emphasizes the importance of structural induction, which is closely related to induction on the length of formulas. Participants suggest starting with foundational concepts from previous discussions and recommend consulting textbooks that cover structural induction as a key proof technique. An analogy is drawn between the proof of positive wffs and the monotonicity of arithmetic expressions, highlighting the intuitive understanding of these mathematical properties. Overall, the conversation aims to clarify the induction proof process for positive wffs.
kp100591
Messages
5
Reaction score
0
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 .
 
Physics news on Phys.org
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$.
 
Back
Top