Notation | Conversion | Identities

Since the NAND gate is a universal gate (i.e. all other gates can be created from it), we could treat boolean logic as if it had only one operation (NAND). I searched around on the net for a set of identities for purely NAND-based boolean logic, but found nothing. So I've put them up here for reference.

I assume that the only operation permitted is a two-input NAND
operation. We can indicate NAND by simple concatenation (no operator
between two arguments), but that still leaves us with a confusing
number of parentheses, e.g. **a((b1)(c1))**. So to make it easier
to read, I use the following notation:

**0**and**1**are false and true- Letters
**a**to**z**are variables - Parentheses enclose a subexpression
- A sequence of a power of two number of
false/true/variables/subexpressions concatenated represent a balanced
tree. For example:
**abcd**is**(ab)(cd)**, or**abcdefgh**is**((ab)(cd))((ef)(gh))**. Due to the way that the two inputs of a NAND can be swapped, these sequences can be reordered only in certain ways, e.g.**abcd = bacd = cdab**, but**abcd != cbad**. - A dot is a NAND operator at a lower precedence than concatenation.
So we can write
**1.ab**instead of**1(ab)** - A space is a NAND operator at a lower precedence than dot. So we
can write
**c 1.ab**instead of**c(1(ab))**

I have a perl script downloadable HERE which evaluates expressions in this notation and produces truth tables, for example:

$ ./nand-eval.pl -l 'a.1(b.c1 c.b1) a1.(b.c1 c.b1)' a b c ((a(1((b(c1))(c(b1)))))((a1)((b(c1))(c(b1))))) (15 gates) 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1

Common operations such as AND, OR, XOR and NOT can be converted to NAND logic as follows (using C notation for bit-ops to avoid confusion):

NOT:~a->a1AND:a&b->1.aba&b&c->1(a 1.bc)a&b&c&d->1(1.ab 1.cd)OR:a|b->a1b1a|b|c->a1 1.b1c1a|b|c|d->1.a1b1 1.c1d1XOR:a^b->a.b1 b.a1or1 ab.a1b1a^b^c->a.1(b.c1 c.b1) a1.(b.c1 c.b1)a^b^c^d->(a.b1 b.a1).1(c.d1 d.c1) 1(a.b1 b.a1).(c.d1 d.c1)

Here are the identities, which I mostly derived by converting boolean AND/OR/NOT identities to NAND logic and reducing them down. Note that one identity often covers two AND/OR identities:

11 = 0a0 = 1aa = a1ab = ba(exchange of two variables)a.a1 = 1(equivalent to aa' and a+a')a.ab = a.1b1.1a = a(equivalent to a'' = a)1 a.bc = a.b1 a.c1(four forms of the same expression,1.abac = a.b1c1equivalent to a(b+c) and (a+b)(a+c)abac = 1 a.b1c1expansions)a.bc = 1(a.b1 a.c1)c 1.ab = a 1.bc = b 1.ac(exchange of three variables: 3-input NAND)1.ab 1.cd(abcd may be exchanged freely: 4-input NAND)a 1.b(1.cd)(abcd may be exchanged freely: 4-input NAND)

Have I missed anything?