1

One common type of logic, first-order logic, is commonly presented as having a certain collection of well-known logical operators, including:

  • AND
  • OR
  • IMPLIES
  • NOT
  • etc.

Interestingly, some of the symbols commonly used can be dismissed as “merely a shorthand”; for example, the bidirectional “if and only if” arrow can just be defined as “A IMPLIES B AND B IMPLIES A”.

If we remove the operators that are apparently just “shorthands”, we would expect to end up with the operators that are actually required, in order, I suppose, to express what we would like to be able to express. However, this question is not really that simple.

Perhaps it is tradition, or something about how human cognition, or language, have evolved, but it often seems like the logical operators that are most canonical - and, or, not, and implies - are so because it has something to do with how the nature of reasoning actually is, in the world. We commonly make use of these patterns of reasoning.

But someone can point out that these operators relate to one another. “a or b” has this truth table:

a | b | a or b
1 | 1 | 1
1 | 0 | 1
0 | 1 | 1
0 | 0 | 0

Thus, “not (a or b)” should have truth table:

a | b | not (a or b)
1 | 1 | 0
1 | 0 | 0
0 | 1 | 0
0 | 0 | 1

which one can observe is equivalent to “(not a) and (not b)”.

Obviously, there is a curious mismatch between which logical operators we as humans find worth mentioning, when defining a logic, because they appeal to our common sense; vs. what is actually strictly mathematically necessary, in order to generate a rule set that is identical, anyway, to the structure of the logic we (redundantly) defined. So the question is, why are there multiple equivalent ways to define the same logic? Is this saying something interesting?

To avoid intractable levels of open-endedness, let’s start with systems of “closed” binary operators: f: {0, 1} x {0, 1} -> {0, 1}.

We want to know how many different such functions there are. One such function is defined by listing one of two choices for each input. There are 2 inputs, each of which has 2 choices. Thus there are 4 possible inputs ( (0,0), (0,1), (1,0), (1,1) ). For each of 4 inputs, we need to choose between a one or a zero, so we have 2^4 = 16 possible choices. Therefore, there are 16 possible unique closed binary operators.

Let’s start with the simplest imaginable one, which assigns “0” to all inputs:

a | b | f(a, b)
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 0

As far as I know, this doesn’t correspond to any intuitive human concept like “and” or “or”. It’s a (presumably useless) logical operator which is “blind” to its inputs: it just returns “false” unconditionally on the truth or falsehood of its inputs.

We can consider that maybe this is telling us why such an operator would never be useful in constructing a logic, but I can’t see the explanation clearly right now. Intuitively, I think one angle on it is that this operator “contains no information”, in a way.

The same operator which returns a “1” for each input pair instead is, arguably, in one way or another of an identical nature; since by symmetry, if you flipped, say, the notation for true and false, the “always true” operator becomes the “always false” operator. So, we skip over this one as of an identical nature (I think).

Perhaps, to keep our exploration simple, next we can consider what we might call “selector” operations. They only return “true” for a single input pair. There are 4 such possible operators - “and”, “not-or”, etc.

Basically, I’m trying to develop a mathematical theory here. This is just the prelude. The point is to understand on a deeper level a) which combinations of operators produce equivalent logics, and b) why the exact combination(s) of operators that define first-order logic has the “outstanding” properties it does. In other words, it seems unexpected, even quirky, that a unary operator (“not”), plus at least one binary operator I think (and, or implies), have such useful properties, whereas I assume certain other operators, or combinations of them, produce “degenerate” logics that do not have any of the basic properties we would want, for a logic. That is the question I am working on formulating. Thanks.

7
  • 1
  • 3
    The Sheffer stroke (non-conjunction) is functionally complete, i.e. it allows to express all other logical operators, see en.wikipedia.org/wiki/Sheffer_stroke
    – Jo Wehler
    Mar 25 at 5:30
  • 1
    What is "strictly necessary" depends on simplifying assumptions about logic. The expression for → in terms of ¬ and ∨ only holds for the material conditional, which famously fails to express nuances of → proper. To a lesser extent, the same is true for de Morgan laws that express ∨ and ∧ via each other (and ¬). Boolean algebra is only a rough approximation of propositional logic where ¬, ∧, ∨, → are all "strictly necessary". But functionally complete sets are well-known
    – Conifold
    Mar 25 at 6:39
  • There are 16 binary logical operations. Generally from the stand point of minimalism you can get away with only 2 or 3 of them (if you count NOT) and that is still equivalent to having all of them. Pragmatically we usually only symbolize 4 to 6 of them, but they are all valid and can be symbolized if you want to. Beyond that, I really am not sure what the actual question in this very long post is. Mar 25 at 14:51
  • 4
    Not sure I understand what exactly the question is, but what might interest you is that there is a full classification of families of binary logical operators "up to interdefinability". This results in what is called Post's lattice: en.wikipedia.org/wiki/Post%27s_lattice For example, using the operations AND, OR, TRUE, and FALSE, you are able to construct precisely those operations which are order-preserving in every co-ordinate, in the sense that f(...,0,...) <= f(...,1,...) with the other arguments being equal. Mar 25 at 14:59

1 Answer 1

7

What you are describing is the property of functional completeness.

A combination of logical connectives is said to be functionally complete if it is able to express all truth tables. In the case of bivalent classical logic, there are 16 truth tables for dyadic connectives and there are many different combinations of connectives that are functionally complete. Negation and conjunction are functionally complete, as are negation and disjunction, and material conditional and falsum. There are two connectives that are individually functionally complete: NAND and NOR. This is why NAND gates and NOR gates are common in electronic engineering.

As to why the connectives that seem natural are not the simplest, there's no obvious answer, though I doubt anything interesting follows from it. A similar thing happens in Hilbert axiom systems of logic. The simplest ones, in the sense of the ones with the fewest axioms, tend to have axioms that are weird-looking and unobvious.

The full table of 16 connectives for A*B is as follows:

T*T T*F F*T F*F

 T   T   T   T  true
 T   T   T   F  inclusive or
 T   T   F   T  inverse material conditional
 T   T   F   F  A 
 T   F   T   T  material conditional 
 T   F   T   F  B 
 T   F   F   T  material biconditional 
 T   F   F   F  and
 F   T   T   T  nand 
 F   T   T   F  exclusive or
 F   T   F   T  not B 
 F   T   F   F  negated material conditional 
 F   F   T   T  not A 
 F   F   T   F  negated inverse material conditional 
 F   F   F   T  nor 
 F   F   F   F  false 
7
  • Right, I forgot that you can play tricks with NAND/NOR gates to get them to function as both NOT and OR/AND, which is enough to be functionally complete. Mar 25 at 14:55
  • 1
    I would argue that AND, OR and NOT are intuitive because they satisfy a bunch of simple equations that "explain" what they are. But the same equations also limit what each of them can do. NOR and NAND have more complex, general behaviour. Mar 25 at 15:15
  • 2
    BTW the factoid of NAND and NOR being so common in electronics because of functional completeness should be taken with a grain of salt. Their prevalence has as much to do with the fact that they can be built with only few transistors. If they required more silicon than alternatives based on separate AND and NOT, then processors would use those instead. Slightly easier design wouldn't trump higher production / space / energy cost. Mar 25 at 15:20
  • 1
    Nice table; if you wish you could replace "material conditional" with "implication", "biconditional" with "equivalence" and similar for the negations; I believe most people are much more familiar with those terms.
    – AnoE
    Mar 25 at 15:46
  • 1
    @JuliusHamilton As per Adam Prenosil's comment, it is worth checking out the Wiki article on Post's lattice en.wikipedia.org/wiki/Post%27s_lattice This shows how the connectives can be classified by various criteria.
    – Bumble
    Mar 25 at 15:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .