3
$\begingroup$

Having always been interested in logic, but never managed to enroll in a logic course, I decided in the last 2 months to immerge myself in the study of this old discipline. The most difficult challanges for me were to really understand how and why to use this 3 connectives, things that still bothers me.
Now, reading online it's not that I'm the only one with such problems, but even though having asked and read and thought about them (some more time and some less) I still can't make my mind happy with them and this thing is torturing me.
Afetr posting my doubts, about the intuition of the "Exclusive or" and my problems with the "Material implication", I stumbled across the material equivalence which woke up my logic demons once more.
I recently looked up disjunctive and conjuctive normal forms, and it confirmed to me that every logical formula (in propostional logic at least) can be reduced or constructed using only the 3 simple operators AND,OR,NOT. Now, I'm here asking myself "Do we really need this ""derived"" operators to make logic easier and more understable?", "Why most beginners struggles with this concepts?" and "What are concrete improvements that they bring"?

$\endgroup$
  • $\begingroup$ No, we don't. The first (quite) modern treatment of math log (the Principia Mathematica (1910-13)) has $\lnot and $\lor$ as primitive conncetives. $\endgroup$ – Mauro ALLEGRANZA Nov 8 '17 at 16:23
  • $\begingroup$ You can even use the one operator NOR or NAND, but what's so onerous about defining XOR, etc.? It's such a simple, low-level thing that asking for concrete improvements is an odd questino. $\endgroup$ – anomaly Nov 8 '17 at 16:25
  • $\begingroup$ $\implies$ is usually used as a primitive to be analogous to deduction. Asserting $A \to B$ should be true iff, assuming $A$, you can derive $B$, regardless of the rules of your logic. Philosophically, "from this follows that" can be a more natural starting place than truth tables. $\endgroup$ – DanielV Nov 8 '17 at 16:29
  • 1
    $\begingroup$ The same for the first modern math log textbook: Hilbert & Ackermann's Grundzüge (1928), where $\to$ is employed only as an abbreviation. $\endgroup$ – Mauro ALLEGRANZA Nov 8 '17 at 16:30
  • 1
    $\begingroup$ For a modern textbook based on $\lnot$ and $\lor$, see Peter Andrews, An Introduction to Mathematical Logic and Type Theory (2nd ed, 2002). $\endgroup$ – Mauro ALLEGRANZA Nov 8 '17 at 16:33
5
$\begingroup$

This is a good question and doesn't deserve the disapproval it's recieving. You're correct that speaking the language of logic using only "AND, OR and NOT" is feasible. For instance, instead of saying

For all real numbers $x$ and $y$, if $xy = 0$, then $x=0$ or $y=0$.

We could say:

For all real numbers $x$ and $y$, either $xy \neq 0$ or $x=0$ or $y=0$.

We can then use the disjunctive syllogism to knockout the possibilities that - well, aren't. For instance:

  • From $xy = 0$, we can conlude $x = 0$ or $y=0$.

  • From $x \neq 0$, we can conclude $xy \neq 0$ or $y=0$.

  • From $y \neq 0$, we can conclude $xy \neq 0$ or $x =0.$

So, you can definitely do this. However, there's a variety of reasons to be hesitant about this 'simplification' of boolean logic.

For starters, it's a bit confusing.

Actually, to be honest, this isn't a very good argument. Presumably, with enough training, we can begin to find the AND/OR/NOT way of talking a bit more intuitive, and as you stated in your question, some people find the meaning of IF-THEN a bit subtle, which isn't too surprising, because logical implication precious little relationship to causation and does not imply that the two statements are connected in any way. For example, it's correct to say that 'if the Jordan Curve Theorem is correct, then Fermat's Last Theorem is true,' because both claims are correct. However, the implicit claim in this statement, that you can use the Jordan Curve Theorem to prove Fermat's Last Theorem, is probably not correct. Any two true statements imply each other, whether or not they're relevant to each other. This can pretty confusing! So, this argument against moving to the AND/OR/NOT way of speaking isn't too strong.

However, there are much stronger arguments against dropping IF-THEN/IFF/XOR. For starters, there's a very strong analogy between AND/OR/IMPLIES and cartesian products/tagged unions/exponential objects. What this means is that if you know how to reason about functions, then you get, completely for free, knowledge of how to reason about AND/OR/IMPLIES. For instance, lets agree to write $Y^X$ for the set of all functions from $X$ to $Y$. In the terminology of category theory, this is called an exponential object. Furthermore, there's a natural transformation $X \times Y^X \rightarrow Y$ given by evaluating the second argument at the first argument. This corresponds to the fact of logic that $x \wedge (x \rightarrow y) \leq y$, for all booleans $x$ and $y$. This tells us that, we can gain knowledge and intuition about logic by studying sets and functions. We can also go the other way, and use our knowledge of logic to conjecture the existence of natural transformations like the one we looked at above. For example, it's a fact of logic that $x \leq (x \rightarrow y) \rightarrow y.$ In words: "If we know that $x$ is true, then from $x \rightarrow y$, we can infer $y$." We can use this to conjecture that there's a natural transformation $X \rightarrow Y^{Y^X}$, and sure enough, there is. The fundamental idea here is called "categorification." More specifically, it's called "propositions as types." The ideas are too involved to describe in a short post like this, but I recommend learning some basic category theory, and then attempting to Google the phrases in quotes in the previous sentence. Good luck with your studies; there's a long road ahead :)

$\endgroup$
  • 1
    $\begingroup$ Thank you for this beautiful and encouraging answer! It adressed all the questions asked and provided the right amount of details and passion. $\endgroup$ – Gabriele Scarlatti Nov 9 '17 at 12:12
  • $\begingroup$ @GabrieleScarlatti, you're welcome. I tend to like people (like you) who question things, having been surrounded most of my life by people who don't :) $\endgroup$ – goblin Nov 9 '17 at 13:36
  • $\begingroup$ I can count on you for doing good in a community that is often too arrogant to allow people to follow their intuition and sense of aesthetics at levels considered too elementary to be worth questioning stuff. As always, +1. Keep it up, man! $\endgroup$ – k.stm Dec 18 '17 at 21:59
  • $\begingroup$ @k.stm, thanks man. Your comment made me very happy :) $\endgroup$ – goblin Dec 24 '17 at 7:03
  • $\begingroup$ @goblin Related to your last paragraph but without needing to move outside of logic or bring in category theory, in non-classical logics and particularly the most common of such, intuitionistic/constructive logic, it is not the case that we can reduce $\to$ to $\neg$, $\land$, and $\lor$. $\endgroup$ – Derek Elkins Feb 17 at 1:30
0
$\begingroup$

No we don't actually need these operators. It's possible to restrict oneself to any functionally complete set of connectives (for example $\lor$ and $\neg$).

However it's not obvious that such a reduction would lead to a better understanding. Probably it would be counterproductive as the use of the other connectives is quite practical at least (even if you don't agree that they convey a better understanding of the intent in some cases). This means at least that other people will use these derived connectives and if you want to get a better knowledge and understanding you will probably need input from others and then you need to understand their language (including the use of derived connectives).

Beginners often struggle with the concepts because they're beginners. Often they also suggest simplifications too, but all to often they are not simplifications in the long run (or they fail to see that they are not so good in the short run either). With time beginners will become advanced and the concepts that they struggled with will no longer be any concern.

$\endgroup$

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.