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.



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

  • $\begingroup$ thanks, thats what i thought! $\endgroup$ – ZZS14 Apr 7 '14 at 13:24
  • $\begingroup$ I have no idea what that is to be honest! $\endgroup$ – ZZS14 Apr 7 '14 at 13:27
  • $\begingroup$ could you explain how you got from (1) to (2)? $\endgroup$ – ZZS14 Apr 7 '14 at 13:30
  • $\begingroup$ Using DeMorgan's $\lnot(a \lor b) \equiv \lnot a \land \lnot b$. In our case, $a = \lnot (p_1 \rightarrow p_2)$. $\endgroup$ – amWhy Apr 7 '14 at 13:36
  • 1
    $\begingroup$ 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. $\endgroup$ – 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 :


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

  • $\begingroup$ yes. haven't checked page 50 of the book.. $\endgroup$ – I likeThatMeow Nov 11 '17 at 5:34
  • $\begingroup$ by "sentence symbols in our formula" you mean atoms in our formula? $\endgroup$ – I likeThatMeow Nov 11 '17 at 5:35
  • 1
    $\begingroup$ @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. $\endgroup$ – Mauro ALLEGRANZA Nov 11 '17 at 9:32
  • $\begingroup$ What do you mean with this "It's enough to use truth-tables." ? I don't get it. $\endgroup$ – 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.


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.