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:
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 -> a1 AND: a&b -> 1.ab a&b&c -> 1(a 1.bc) a&b&c&d -> 1(1.ab 1.cd) OR: a|b -> a1b1 a|b|c -> a1 1.b1c1 a|b|c|d -> 1.a1b1 1.c1d1 XOR: a^b -> a.b1 b.a1 or 1 ab.a1b1 a^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 = 0 a0 = 1 aa = a1 ab = ba (exchange of two variables) a.a1 = 1 (equivalent to aa' and a+a') a.ab = a.1b 1.1a = a (equivalent to a'' = a) 1 a.bc = a.b1 a.c1 (four forms of the same expression, 1.abac = a.b1c1 equivalent to a(b+c) and (a+b)(a+c) abac = 1 a.b1c1 expansions) 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?