About

The Sheffer Stroke, denoted A ↑ B (also written A | B or NAND), produces FALSE only when both operands are TRUE. Henry Sheffer proved in 1913 that this single connective is functionally complete: every Boolean function, including NOT, AND, OR, and XOR, can be constructed using only NAND gates. This property makes NAND the foundational building block of modern digital circuits. Errors in NAND-chain derivations propagate through entire combinational networks, so verifying intermediate bit-level results matters during hardware design and formal logic proofs.

This tool computes A ↑ B for arbitrary-length binary strings, zero-padding the shorter operand to match lengths. It also derives all six standard gates from pure NAND composition so you can cross-check equivalences. The computation assumes unsigned binary representation with no overflow semantics. Pro tip: when chaining NAND operations for circuit simulation, track propagation delay per gate level - this tool handles the logical layer, not timing.

Formulas

The Sheffer Stroke is defined by negating the conjunction of two operands:

A ↑ B ≡ ¬(A ∧ B)

For each bit position i in binary strings of length n:

R_i = 1 − (A_i × B_i)

Derivation of NOT from NAND:

¬A ≡ A ↑ A

Derivation of AND from NAND:

A ∧ B ≡ (A ↑ B) ↑ (A ↑ B)

Derivation of OR from NAND (De Morgan's):

A ∨ B ≡ (A ↑ A) ↑ (B ↑ B)

Derivation of XOR from NAND:

A ⊕ B ≡ [A ↑ (A ↑ B)] ↑ [B ↑ (A ↑ B)]

Where A = first binary operand, B = second binary operand, R = result bit string, i = bit index from 0 to n − 1, n = max length of operands after zero-padding.

Reference Data

Gate	Symbol	NAND Derivation	Gate Count	Expression	Output for 0,0	Output for 0,1	Output for 1,0	Output for 1,1
NAND (Sheffer)	↑	Native	1	A ↑ B	1	1	1	0
NOT	¬	A ↑ A	1	¬A	1		0
AND	∧	(A ↑ B) ↑ (A ↑ B)	2	A ∧ B	0	0	0	1
OR	∨	(A ↑ A) ↑ (B ↑ B)	3	A ∨ B	0	1	1	1
NOR	↓	[(A ↑ A) ↑ (B ↑ B)] ↑ [(A ↑ A) ↑ (B ↑ B)]	4	¬(A ∨ B)	1	0	0	0
XOR	⊕	[A ↑ (A ↑ B)] ↑ [B ↑ (A ↑ B)]	4	A ⊕ B	0	1	1	0
XNOR	⇔	NOT of XOR chain	5	¬(A ⊕ B)	1	0	0	1
IMPLIES	⇒	(A ↑ A) ↑ (B ↑ B ↑ B)... simplified	2	A ⇒ B	1	1	0	1
Buffer	-	(A ↑ A) ↑ (A ↑ A)	2	A	0		1
Constant 1	-	A ↑ (A ↑ A)	2	1	1
Constant 0	-	[A ↑ (A ↑ A)] ↑ [A ↑ (A ↑ A)]	3	0	0
Inhibition	-	A ∧ ¬B via NAND	3	A ∧ ¬B	0	0	1	0

Frequently Asked Questions

A single connective is functionally complete if every Boolean function can be expressed using only that connective. The Sheffer Stroke (NAND) satisfies this because NOT A ≡ A ↑ A and AND(A, B) ≡ (A ↑ B) ↑ (A ↑ B). Since {NOT, AND} is a complete basis, NAND alone inherits completeness. This was formally proven by Henry Sheffer in 1913 in the Transactions of the American Mathematical Society.

The shorter operand is left-padded with zeros to match the longer operand's length. Since NAND of 0 and any bit X yields 1 (because 0 AND X = 0, negated = 1), padding positions always produce 1 in the result. This mirrors unsigned binary semantics where absent high-order bits are implicitly zero.

The Sheffer Stroke (↑) is NAND: ¬(A ∧ B). The Peirce Arrow (↓) is NOR: ¬(A ∨ B). Both are individually functionally complete. NAND outputs 0 only when both inputs are 1. NOR outputs 1 only when both inputs are 0. In circuit design, NAND gates are preferred in CMOS technology because they require fewer transistors for the same logic depth.

The standard definition applies bit-by-bit (bitwise NAND). Applying it to the numeric values as a whole would require defining NAND for integers, which reduces to the same bitwise operation on their binary representations. There is no alternative algebraic interpretation for multi-bit operands.

A 1-bit full adder requires 9 NAND gates. The sum output S = A ⊕ B ⊕ Cin requires 4 NAND gates per XOR (so 8 for two XORs), but with shared intermediate signals the count optimizes to 9 total for both S and Cout. This is a standard result in VLSI design textbooks.

The Sheffer Stroke is commutative: A ↑ B = B ↑ A, because AND is commutative and negation preserves this. However, it is NOT associative: (A ↑ B) ↑ C ≠ A ↑ (B ↑ C) in general. For example, with A=1, B=1, C=0: (1↑1)↑0 = 0↑0 = 1, but 1↑(1↑0) = 1↑1 = 0. Always use explicit parentheses when chaining NAND operations.