Propositional Logic Inductive Proof

Question

I am working on a problem to prove, but I do not understand it completely. Where should I use inductive method? What is the base case? And so on. Here is my problem:

A truth assignment $M$ is a function that maps propositional variables to $\{0, 1\}$ ($1$ for true and $0$ for false). We write $M\vDash x$ if $x$ is true under $M$. We define a partial order $\leq$ on truth assignments by $M \le M'$ if $M(p) \le M'(p)$ for every propositional variable $p$.

A propositional formula is positive if it only contains connectives $\wedge$ and $\vee$ (i.e., no negation $\lnot$ or implication $\Rightarrow$).

Use Proof By Induction to show that for any truth assignments $M$ and $M'$ such that $M\le M'$, and any positive propositional formula $x$, if $M \vDash x$, then $M' \vDash x$.

I am really confused. Any help is welcome. Thank you.

Answer 1

Perhaps a more concrete statement of what you need to show is the following:

Let $M \leq M^\prime$ be truth assignments. Then for every positive formula $\varphi$ either $M \not\models \varphi$ or $M^\prime \models \varphi$.

We also note that the family of positive formulas has its own inductive definition, similar to the definition of the family of all formulas:

• Every propositional variable $p$ is a positive formula.
• If $\varphi , \psi$ are positive formulas, then so are $\varphi \wedge \psi$ and $\varphi \vee \psi$.
• (No other formula is positive.)

So to prove the result, we need to show two-and-a-half things: Let $M \leq M^\prime$ be truth assignments, then

1. if $p$ is a propositional variable, then either $M \not\models p$ or $M^\prime \models p$.
2. if $\varphi , \psi$ are formulas such that either $M \not\models \varphi$ or $M^\prime \models \varphi$, and similarly for $\psi$, then
   • either $M \not\models \varphi \wedge \psi$ or $M^\prime \models \varphi \wedge \psi$; and
   • either $M \not\models \varphi \vee \psi$ or $M^\prime \models \varphi \vee \psi$.

To leave with a parting

Hint: The definition of the partial order $\leq$ will be very useful in the base case (1), and the definition of $\models$ (for compound formulas) will be very useful in the inductive step (2).