2

Show that the formula $¬((p_1 \rightarrow p_2)\rightarrow (p_2\rightarrow p_3))$ is not logically equivalent to a formula involving only connectives from the set $\{∧,\rightarrow\}$.

Am I correct in thinking it is because we cannot write the negation connective $¬$ and the connective $\rightarrow$ using only the connectives in the set $\{∧,\rightarrow \}?$

($\phi \rightarrow \psi$) is logically equivalent to (($\lnot\phi)\lor \psi$) but the connectives $¬$ and $\lor$ do not exist in the set $\{\land, \rightarrow \}.$

I just don't really know how to go any further to show it.

Thanks

Mauro ALLEGRANZA
  • 94,169
ZZS14
  • 819

3 Answers3

3

See Herbert Enderton, A Mathematical Introduction to Logic (2nd ed Harcourt - 2001), page 50.

With only the $\land$ and $\rightarrow$ connectives, if the sentence symbols in our formula are assigned the value $\top$, then the entire formula is assigned the value $\top$.

We have to proof this by induction on the lenght of the formula; i.e. we have to show that for any wff $\alpha$ built up using only these connectives we have that :

in each valuation $v$ such that $v(p_i) = \top$, for each $p_i$ in $\alpha$, then $v(\alpha) = \top$.

The proof is trivial :

Basis

$\alpha$ is $p_1$; then, $v(p_1) = \top = v(\alpha)$.

Induction step

$\alpha$ is $\alpha_1 \land \alpha_2$ or $\alpha_1 \rightarrow \alpha_2$, where we assume by induction hypotheses, that :

if $v(p_i)=\top$ for each $p_i$ in $\alpha_1$ and $\alpha_2$, then $v(\alpha_1)=v(\alpha_2)=\top$.

It's enough to use truth-tables.

Having shown this, we have shown that with only the two connectives $\land$ and $\rightarrow$ we are not able to "produce" a formula that, when all its sentence letters evaluates to $\top$ (i.e.TRUE), it gives as result the value $\bot$ (i.e.FALSE).

But with the valuation $v_0$ such that :

$v_0(p_1)=v_0(p_2)=v_0(p_3)= \top$

the formula $\alpha := \lnot [(p_1 \rightarrow p_2) \rightarrow (p_2 \rightarrow p_3)]$

will have the value $\bot$.

Another way to prove it is based on :

the equivalence between : $p \rightarrow q$ and $\lnot (p \land \lnot q)$,

in classical logic : because we need Double Negation.

Using this equivalence, we may rewrite our formula as :

$(p_1 \rightarrow p_2) \land \lnot (p_2 \rightarrow p_3)$

and again as :

$\lnot (p_1 \land \lnot p_2) \land (p_2 \land \lnot p_3)$.

Now we may apply the above argument in terms of valuations; with $v_0(p_1)=v_0(p_2)=v_0(p_3)= \top$, we have that :

$[\lnot (\top \land \lnot \top) \land (\top \land \lnot \top)] \equiv [\lnot (\top \land \bot) \land (\top \land \bot)] \equiv (\lnot \bot \land \bot) \equiv (\top \land \bot) \equiv \bot$.

But we have the above result that with only the $\land$ and $\rightarrow$ connectives, if the sentence symbols in a formula are assigned the value $\top$, then the entire formula is assigned the value $\top$.

Thus, is not possible to find a formula with only $\land$ and $\rightarrow$ that is equivalent to the original one.

Mauro ALLEGRANZA
  • 94,169
2

$$\begin{align} \lnot((p_1 \rightarrow p_2) \rightarrow(p_2 \rightarrow p_3)) & \equiv \lnot(\lnot(p_1\rightarrow p_2) \lor (p_2\rightarrow p_3))\tag{1}\\ \\ & \equiv (p_1\rightarrow p_2) \land \lnot(p_2\rightarrow p_3)\tag{2}\\ \\ &\equiv (p_1 \rightarrow p_2) \land \lnot(\lnot p_2 \lor p_3) \tag{3}\\ \\ & \equiv (p_1 \rightarrow p_2) \land p_2 \land \lnot p_3\tag{4}\end{align}$$

In $(4)$, we have the connectives $\land, \rightarrow$, but we also have the negation $\lnot$ of the literal $p_3$. (Similarly, in $(2)$ we have the only $\rightarrow$ and $\land$, but still also need $\lnot$.) We cannot simply omit the negation sign in either without losing the meaning of the proposition.

See the Wikipedia entry on Functional Completness for a more formal treatment on how to determine whether a set of connectives is complete, or adequate, to express all possible truth valuations for, in this case, an expression with three variables.

amWhy
  • 209,954
  • thanks, thats what i thought! – ZZS14 Apr 07 '14 at 13:24
  • I have no idea what that is to be honest! – ZZS14 Apr 07 '14 at 13:27
  • could you explain how you got from (1) to (2)? – ZZS14 Apr 07 '14 at 13:30
  • Using DeMorgan's $\lnot(a \lor b) \equiv \lnot a \land \lnot b$. In our case, $a = \lnot (p_1 \rightarrow p_2)$. – amWhy Apr 07 '14 at 13:36
  • a follow on Q is; "is the formula logically equivalent to the set { ^, ¬}, i've continued from (4) in your answer to obtain ((¬$p_1$)v $p_2$)^($p_2$^(¬$p_3$)) but I don't know where to go from there – ZZS14 Apr 07 '14 at 15:46
  • 1
    But why go back to using $\lor$? The point is to try and express the proposition using just $\rightarrow$ and $\land$. And we've been able to do that, save for the $\lnot p_3$. You should find that there is no way to express $\lnot p_3$ using just $\land$ and/or $\rightarrow$. Hence, the set ${\land, \rightarrow}$ cannot be complete. – amWhy Apr 07 '14 at 15:51
  • I am confused. The question is now about the set { ^, ¬}, so I can have the negation connective but want to try and get rid of the implication connective? – ZZS14 Apr 07 '14 at 15:56
  • No, the question asks you to show that the proposition cannot be expressed using the given connectives. We've shown that, try as we may, we need more connectives than are in the given set, namely, in the work above, we invariably need a negation sign, too. But since that's not in the set of "legal" connectives, it must be that ${\land, \rightarrow}$ cannot be expressed using only $\land, \rightarrow.$ First we tried to see if we can limit ourselves to only the given connectives, but in the end, we can't. – amWhy Apr 07 '14 at 16:00
  • Yes but there is a follow on question on the paper asking if the formula is logically equivalent to only connectives of the set { ^, ¬} – ZZS14 Apr 07 '14 at 16:03
  • And my point is that it is not, because we need the negation connective as well as $\land, \rightarrow$. So it cannot be equivalent to any expression using only $\land$ and $\rightarrow$. See the link I give in my answer. – amWhy Apr 07 '14 at 16:07
  • oh okay i get it, sorry, its been a long day – ZZS14 Apr 07 '14 at 16:07
  • No problem. I understand. Do make a point of checking out the link above when you're a little better rested. :-) – amWhy Apr 07 '14 at 16:09
0

Every function created with the connectives $\rightarrow$ and $\land$ has the property that $f(\text{true}, \text{true}, \dots) = \text{true}$

Prove with structural induction.

The provided function doesn't have that property.

DanielV
  • 23,556