The only knife you'll ever need (if you're a logician)
Definition
The Quine dagger is a binary logical operator, also known as NOR, which returns 1 (true) if and only if both operands have a value of 0 (false). It is usually represented by a downward-pointing arrow (↓), and it corresponds intuitively to the natural language expression neither... nor. The Quine dagger is named for, and was proposed by, W.V.O. Quine.
A | B | A↓B
---+---+-----
1 | 1 | 0
1 | 0 | 0
0 | 1 | 0
0 | 0 | 1
How to forge a Quine dagger
The Quine dagger can be defined in terms of the more familiar operators not (¬), or (∨), and and (&):
A↓B = ¬(A ∨ B) "Not (A or B)"
A↓B = (¬A) & (¬B) "Not A, and not B"
What to do with your Quine dagger
More impressively, if you take your Quine dagger as a given, you can define all other logical operators in terms of it. (As Gritchka observes, this can also be done with a Sheffer stroke, or NAND.) The first thing to do is to get yourself a not. This is very easy, provided you can let go of any prejudice you may have against the appearance of redundancy. We're defining a unary operator in terms of a binary one, here; a little apparent redundancy is perfectly natural:
¬A = A↓A "Neither A nor A"
Or, if this offends your sensibilities, you might want to use the constant 0 instead:
¬A = A↓0 "Neither A nor 0"
To define more complex operators, you need to start thinking like a Quine dagger. Your basic (and only) tool means "neither... nor"—so the best thing to do is, for any given operator, to think of two conditions that exhaustively describe the circumstances under which that operator returns 0. Then take these two conditions and stick them on either side of the Quine dagger, and Willard's your uncle (or your grandfather, if you happen to be MALTP).
For example, if we want to define and, we can begin by noting that there are two conditions under which A&B evaluates to 0:
- A is 0
- B is 0
Since we've already figured out how to say "A is 0" (A↓A), we can now define and as follows:
A&B = (A↓A) ↓ (B↓B) "Neither (not A) nor (not B)"
Okay, what about or? Well, if you've already defined not and and, then you can define or in terms of them. But that's not the most elegant way of doing it. Think like a Quine dagger: What conditions will make A∨B false? Well, A∨B evaluates to 0 iff A and B are both 0. (And we certainly know how to say "A and B are both 0"; after all, that's what a Quine dagger is for.) This is only one condition, not two. But as we learned from defining not, if you only want to negate one thing, just repeat it. So:
A∨B = (A↓B) ↓ (A↓B) "Not (neither A nor B)"
Or, of course, if you allow yourself a constant, you can make do with only two Quine daggers instead of three:
A∨B = (A↓B) ↓ 0 "Not (neither A nor B)"
Given a few more daggers, we can define such exotic notions as xor, entailment, and iff.
Let's start with xor (exclusive or). (I like to think of xor as simply meaning "does not equal" (≠); I'm just going to write out the word xor here, because there's no single, widely-used, unambiguous symbol for it.) There are two conditions under which A xor B returns 0:
- A and B are both 0.
- A and B are both 1.
Condition 1 is easy; it's just A↓B. And condition 2 we've already figured out how to express, because it's A&B, which we've defined as (A↓A)↓(B↓B). So that gives us:
A xor B = (A↓B) ↓ ((A↓A)↓(B↓B)) "Neither (neither A nor B) nor (both A and B)"
The statement "A entails B" (A→B, "if A then B") is like A∨B in that there's only one condition under which it's false: A is 1 and B is 0. Well, we know how to say and, and we know how to say "B is 0" (¬B), so we could build a version of A&(¬B) using our definitions of not and and. But it's more efficient to rephrase the condition as "A is not 0, nor is B 1" ("Neither (not A) nor B"). Then we just take that and negate it to get A→B:
A→B = ((A↓A)↓B) ↓ ((A↓A)↓B) "Not (neither (not A) nor B)"
Finally, what about mutual entailment (↔)? Well, A↔B ("A iff B") is true under exactly those conditions under which A xor B is false, so if all else fails, we can just take our version of A xor B and negate it. But all else doesn't fail. We can easily come up with the two conditions under which A↔B returns 0:
- A is 1 and B is 0
- A is 0 and B is 1
And when we defined "if... then" (→), we figured out how to say things like "A is 1 and B is 0." So our definition of A↔B is going to look a lot like our definition of A→B, only with two different expressions on either side of the highest-level Quine dagger instead of the same one twice:
A↔B = ((A↓A)↓B) ↓ (A↓(B↓B)) "Neither (A and not B) nor (B and not A)"
What to do with your Quine dagger in real life (if you're an electrical engineer)
Gorgonzola says: "This is exactly how electrical engineers design logic gates [...] in microprocessor chips. A transistor means NOR and the other circuits are combinations. Also, bits in memory chips are designed this way."
Source: I first learned about the Quine dagger from L.T.F. Gamut's Logic, Language, and Meaning (University of Chicago Press, 1991). ("L.T.F. Gamut," by the way, is a collective pseudonym for a bunch of Dutch people with too many initials: J.F.A.K. van Benthem, J.A.G. Groenendijk, D.H.L. de Jongh, M.J.B. Stokhof, and H.J. Verkuyl.) Most of the definitions presented here, and the reasoning behind them, I worked out for myself, though of course Quine and others have done so before.