UAZUNextUpPrev

NAND-based boolean logic identities

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.

Notation

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

Converting from NOT, AND, OR and XOR

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)

Identities

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?



UAZUNextUpPrev These pages and files, including applets and artwork, are Copyright (c) 1997-2016 Jim Peters unless otherwise stated. Please contact me if you'd like to use anything not explicitly released, or if you have something interesting to discuss.