0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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 ].

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.