# $¬((p_1 \rightarrow p_2)\rightarrow (p_2\rightarrow p_3))$ cannot be expressed using only connectives in $\{∧,\rightarrow\}$

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

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

• thanks, thats what i thought! – ZZS14 Apr 7 '14 at 13:24
• I have no idea what that is to be honest! – ZZS14 Apr 7 '14 at 13:27
• could you explain how you got from (1) to (2)? – ZZS14 Apr 7 '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 7 '14 at 13:36
• 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 7 '14 at 15:51

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.

• yes. haven't checked page 50 of the book.. – I likeThatMeow Nov 11 '17 at 5:34
• by "sentence symbols in our formula" you mean atoms in our formula? – I likeThatMeow Nov 11 '17 at 5:35
• @MichelleGarcía - YES. In propositional calculus we can call the $p_i$ propositional letters or symbols. But we call prop calculus also sentential calculus, and thus we can call them sentential letters or symbols. – Mauro ALLEGRANZA Nov 11 '17 at 9:32
• What do you mean with this "It's enough to use truth-tables." ? I don't get it. – I likeThatMeow Nov 11 '17 at 18:19

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.