2

Why are the standard logical connectives for languages AND and OR (and IMPLIES)? I would agree with the assertion that they are more natural in some way, easier to think about than connectives like NAND or XNOR. What I question is the choice of OR over XOR as a fundamental gate.

XOR behaves like addition of the integers mod 2, analogous to AND behaving as multiplication mod 2, which means that the pair behaves like the field of integers mod 2. I would have supposed that a link this strong to already incredibly well established mathematics with a relatively sturdy structure would make logic even easier to analyze than it currently is.

What makes OR the more common connective despite this? Tradition? Ease of formulation of statments in canonical form?

  • Maybe it is because it occures more often that we need at least one premise to be true instead of exactly one. The origin of OR and AND are logical reasoning and not algebra. – M. Winter Aug 03 '17 at 09:54
  • ...... and NOT. – Mauro ALLEGRANZA Aug 03 '17 at 09:54
  • 1
    Comapre the beautiful properties of Logical disjunction: associativity, commutativity, distributivity, idempotency, monotonicity, truth- and falsehood-preserving, with the lack of many of them in the case of Exclusive or. – Mauro ALLEGRANZA Aug 03 '17 at 10:03
  • It is well known that the theories of Boolean rings and Boolean algebras are essentially equivalent. However, Boolean algebra is the notation of choice in the vast majority of work on the subject. I think this is because the Boolean ring notation (NOT, AND and XOR) obscures a lot of useful symmetries and order-theoretic ideas: AND and OR correspond to greatest lower bounds and least upper bounds and the order-reversing operation NOT neatly interchanges the two notions. – Rob Arthan Aug 03 '17 at 20:59

2 Answers2

2

Here is my anecdotal evidence: when dealing with logic in practice, you usually need either AND or OR, but not XOR. I've programmed hundreds, if not thousands of if-tests, many of them testing several statements with connectives. The number of times I really needed XOR could probably be counted on a hand or two.

So my guess is that we humans are, if not inherently better at understanding AND and OR, at the very least more experienced.

Arthur
  • 199,419
0

When you design logic circuits, you usually start with some specification of desired functionality, and then use any number of techniques to capture that with a logical expression. Those techniques often rely on useful logical equivalences so that you can, for example, use boolean algebra to rewrite and simplify expressions.

And, as it turns out, the AND and the OR are each other's dual operators, which means that not only is it true that you often find yourself going back and forth between them (think Demorgans's Laws!), but they share lots of logical properties, like Commutation, Association, Distribution, Absorption, Reduction, Idempotence, Adjacency, etc. Whereas if you were to work with an AND and an XOR, you would need to remember a different set of such logical properties for each of them. In fact, just the very fact that many of these logical principles just mentioned involve both the AND and the OR is a point in favor of using AND and OR as your 'basic' operators, whereas I doubt you would find just as many useful principles involving the AND and the XOR.

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • Note, though, that ({T,F},XOR,AND) is a field (isomorphic to $\mathbb F_2$) which does bring with it a lot of familiar algebraic principles (though slightly tempered by the fact that fields of characteristic 2 are weird). – hmakholm left over Monica Aug 03 '17 at 13:47