Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 10 down vote accepted

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

share|improve this answer
    
$F \rightarrow (F \rightarrow F)$ equiv $F \rightarrow T$ equiv $T$... but $F \vee F$ equiv $F$. –  GEdgar Jun 28 '11 at 17:43
2  
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? –  macdonjo Oct 3 at 23:01

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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