Can conjunction be expressed via implication?

Question

Exercise 1.5 from Arnold Milner Logic Notes: While disjunction is easily defined via implication (p v q = p->(q->p)) I have trouble defining conjunction and guess this is impossible. I've examined truth tables for expressions with 3 terms and need an insight why this exhausts the search. Or, perhaps, I need to invoke some more advanced method of logic inexpressibility?

The problem reduces to "smaller" one: if I express false constant 0 in terms of implication, then it will allow negation (via -p = p->0) and, consequently, conjunction (via De Morgan's law). This would give full set of connections, which we know only Sheffer connective and its dual enjoy. Therefore, neither 0, nor negation is expressed in terms of implication as well?

Added to the previous answer is a proof that $\land$ cannot be defined purely in terms of $\implies$. — André Nicolas, Jun 28 '11 at 18:23

André Nicolas · Accepted Answer · 2011-06-28T18:21:10.643

14

Is part of the question whether negation can be expressed using implication and nothing else? Certainly it cannot be, for something built using only implication cannot be false if all its components are true. One does not have to go through uniqueness properties of the Sheffer strokes.

Added: Is it clear that (as you assert) $p \implies(q \implies p)$ is equivalent to $p \lor q$? What about when both $p$ and $q$ are false?

About Conjunction: Here is a proof that conjunction cannot be defined in terms of implication alone. It cannot be by a single implication symbol. Now show that if it cannot be done with fewer than $n$, it cannot be done with $n$. Suppose it could be done with the formula $A \implies B$. If $A$ is always true, then $B$ would do the job, contradicting the induction assumption. If $A$ is sometimes false, that can only happen when at least one of $p$ or $q$ is false. But if $A$ is false, then $A \implies B$ is true. So there are situations in which at least one of $p$ and $q$ is false, and $A \implies B$ is true, contradicting the assumption that $A\implies B$ is equivalent to $p \land q$.

edited Jun 28 '11 at 18:21

answered Jun 28 '11 at 17:23

André Nicolas

507,029

$F \rightarrow (F \rightarrow F)$ equiv $F \rightarrow T$ equiv $T$... but $F \vee F$ equiv $F$. – GEdgar Jun 28 '11 at 17:43
3

should be $(p \rightarrow q) \rightarrow q$ – GEdgar Jun 28 '11 at 17:49
Thank you, Edgar, I had managed to pick up the wrong column from truth table:-( – Tegiri Nenashi Jun 28 '11 at 18:33
Do you have a real world example to clarify this? – User Oct 03 '14 at 23:01
As the base of the induction, i would have taken 0 implication symbols :). – Alexey Feb 23 '17 at 16:03

score 0 · Answer 2 · answered Jun 28 '11 at 18:26

A method to see that you can't express implication via conjunction comes as to write out the truth tables involving conjunctions only and two variables. If you do this, after a while, you'll find that only so many truth tables can get generated. Then once you show that only those truth tables can get generated and implication doesn't appear as one of them, you have your demonstration that conjunction can't generate implication. The Schaum's Outline of Boolean Algebra has an example of this, and there's a website around somewhere where you can pick some of the 16 classical propositional connectives and see which ones they can generate... though unfortunately I've forgotten how to find that link.

Can conjunction be expressed via implication?

2 Answers2

Linked