# Proving existence of a wff that is logically equivalent to a wff given some conditions

For convenience, let us define a wff to be positive if there is no use of the negation symbol $\neg$ at all in the wff. Hence, for example, $W=P\iff Q$ is a positive wff.

Now the question is to show that if $W$ is any wff built from propositional variables $P_1,\dots,P_n$ such that if $V(P_1)=\cdots=V(P_n)=T$ implies $V(W)=T$ then $W$ is logically equivalent to a positive wff.

I tried this with an example:

Let $W=\neg[(P\implies \neg Q)\land(R\land(P\lor Q))]$. Then when $V(P)=V(Q)=V(R)=T$ we also have that $V(W)=T$, and in fact we can show (by directly using simple logical equivalences) that $W$ is logically equivalent to $R\implies (P\iff Q)$, which is a positive wff by the definition above.

But for the general case, I haven't got a clue. I tried induction on the length of $W$ to no success. Also tried induction on number of propositional variables, again with no success.

Can anyone provide hints?

Hint

We can assume the set of connectives: $\{ \lnot, \land, \lor, \to \}$.

We need two preliminary facts:

(i) If a formula $F$ is positive (i.e. negation-free), then for any valuation $v$ such that $v(P_i)=$t for all propositional variables $P_i$ occurring in $F$, then $v(F)=$t.

Easily proved by Induction on the complexity of the formula [negation-free means that we can have only the conncetive: $\land$].

(ii) For every formula $F$ there exists a positive formula $G$ with the same propositional variables such that $F$ is logically equivalent to $G$ or to $\lnot G$.

Again provable by induction on the complexity of $F$: the base case [$F$ is a propositional variable] is obvious.

Consider the case when $F$ is $\lnot H$, for some $H$. Then, by induction hypotheses, $H$ is logically equivalent to $H'$ or $\lnot H'$, with $H'$ positive. In the first case, $F$ is equivalent to $\lnot H'$, while in the second case $F$ is equivalent to $\lnot \lnot H'$ i.e. to $H'$.

Similar for the binary connectives, considering in each case the four subcases.

Now consider $F$ such that:

if $v(P_i)=$t for every $P_i$ occurring in $F$, then $v(F)=$t.

By the previous result (ii), there exists positive $G$ such that $F$ is equivalent to $G$ or to $\lnot G$.

But $G$ has the same propositional variables of $F$ and is positive; thus, from the fact that $v(P_i)=$t for all $P_i$, we have that $v(G)=$t, by the previous result (i).

This means that $F$ must be equivalent to $G$ [because $v(\lnot G)=$f ].

• Very very helpful and insightful ! Much appreciated. – satokun Jun 14 '16 at 23:24

For any wff $\alpha$ Define $\lnot$$\alpha$ as ($\alpha$ $\rightarrow$ 0), where 0 indicates the constant false proposition. Then show that all formulas end up logically equivalent to one with $\rightarrow$ and 0 alone.