Go Language: NAND Grammar

Posted
Comments None

NAND gates play an important role in electronics as we can build all kinds of electronic circuits with just NAND gates. And this is because the NAND gate is a Universal Logical System that can be used to define all kinds of logical expressions.

For example, we can define the XOR function using NAND operators alone [ (XOR(x,y) = NAND(NAND(x,NAND(x,y)),NAND(NAND(x,y),y)) ]; but there's no way to express the NAND function using only XOR. And like we just saw for the XOR function, any logical function or logic circuit can be defined in terms of NAND's alone (the same is true for the NOR function, but I'll talk about the NOR Universal System in the next post).

And that's what the NAND Grammar of GeneXproTools is all about! It defines all the 258 built-in logical functions of GeneXproTools in terms of NAND gates alone, allowing us to design our logic circuits using all kinds of logical functions and then convert them automatically to NAND gates.

Note, however, that GeneXproTools also allows you to design/evolve your logic circuits using NAND gates alone as building blocks, and this is the recommended course of action if you want your circuits to include only NAND gates, since you'll be able to create much more compact circuits if you do. But let's illustrate this with a few code examples to show off our new Go Grammar.

Like in the previous post "Go Language: NOT-AND-OR Grammar", I'll be using again the 6-Multiplexer function in all the code examples, but you'll notice I'll be using a simpler architecture as I want to keep the circuits small even after converting them to the NAND system.

So, here's the first minimal logic circuit created for the 6-Multiplexer using just NAND gates as building blocks:

package gepModel

func gepModel(d []bool) bool {
    y := false

    y = d[2]
    y = gepNand(y,d[1])
    y = gepNand(y,d[2])
    y = gepNand(y,gepNand(d[1],d[3]))
    y = gepNand(y,gepNand(d[0],d[0]))
    y = gepNand(y,gepNand(d[0],gepNand(gepNand(gepNand(d[1],d[1]),d[4]),
        gepNand(d[5],d[1]))))

    return y
}

func gepNand(x, y bool) bool {
    return (!(x && y))
}

Obviously, in this case, if we applied the NAND Grammar to this circuit, we would get exactly the same output as only NAND gates were used in the original circuit.

But now suppose we design a circuit not only with NAND gates but also with AND and NOT (one reason for doing this in GeneXproTools is to get better evolution). The code below shows such a circuit (we are using here the All Gates Grammar to generate the code):

package gepModel

func gepModel(d []bool) bool {
    y := false

    y = d[1]
    y = gepNand(y,d[1])
    y = gepNand(y,d[2])
    y = gepNand(y,gepNand(d[1],d[3]))
    y = gepNand(y,(!(d[0])))
    y = gepNand(y,gepNand(gepNand(gepNand((!(d[1])),d[4]),
        gepNand(d[5],d[1])),d[0]))

    return y
}

func gepNand(x, y bool) bool {
    return (!(x && y))
}

And now if we convert all the elements in this minimal logic circuit to NAND gates using our new Go NAND Grammar, we get a slightly larger circuit (13 literals instead of just 11):

package gepModel

func gepModel(d []bool) bool {
    y := false

    y = d[1]
    y = gepNand(y,d[1])
    y = gepNand(y,d[2])
    y = gepNand(y,gepNand(d[1],d[3]))
    y = gepNand(y,gepNand(d[0],d[0]))
    y = gepNand(y,gepNand(gepNand(gepNand(gepNand(d[1],d[1]),d[4]),
        gepNand(d[5],d[1])),d[0]))

    return y
}

func gepNand(x, y bool) bool {
    return (!(x && y))
}

And finally, the last example shows a circuit where we get a little more inflation when we apply the NAND Grammar to it. This circuit is also minimal and was evolved using all the logical functions of 2 arguments plus NOT. Here's the code generated with the All Gates Grammar:

package gepModel

func gepModel(d []bool) bool {
    y := false

    y = (!(d[5]))
    y = gepNand(y,d[0])
    y = gepNand(y,d[1])
    y = gepNand(y,gepGOE(d[0],d[2]))
    y = gepNand(y,gepNand(gepNor(d[0],d[3]),d[1]))
    y = gepNand(y,gepNand(gepGT(d[0],d[1]),d[4]))

    return y
}

func gepNor(x, y bool) bool {
    return (!(x || y))
}

func gepGT(x, y bool) bool {
    return (x && (!(y)))
}

func gepGOE(x, y bool) bool {
    return (x || (!(y)))
}

func gepNand(x, y bool) bool {
    return (!(x && y))
}

And here's the Go code of the same logic circuit generated with the NAND Grammar:

package gepModel

func gepModel(d []bool) bool {
    y := false

    y = gepNand(d[5],d[5])
    y = gepNand(y,d[0])
    y = gepNand(y,d[1])
    y = gepNand(y,gepNand(gepNand(d[0],d[0]),d[2]))
    y = gepNand(y,gepNand(gepNand(gepNand(gepNand(d[0],d[0]),
        gepNand(d[3],d[3])),(true)),d[1]))
    y = gepNand(y,gepNand(gepNand(gepNand(d[0],gepNand(d[0],d[1])),
        gepNand(d[0],gepNand(d[0],d[1]))),d[4]))

    return y
}

func gepNand(x, y bool) bool {
    return (!(x && y))
}

As you can see, we went from a minimal circuit with just 11 literals to a NAND circuit with 20 literals, almost doubling in complexity.

This kind of inflation happens a lot every time we use more exoteric logical functions in the design of our logic circuits. So depending on our goals, we must articulate the different tools at our disposal (especially circuit architecture, function set and linking functions) to create the kind of circuit that we need.

In the next post I'll talk about the similar NOR System and the NOR Grammar of GeneXproTools.

Author

Comments

There are currently no comments on this article.

Comment

Enter your comment below. Fields marked * are required. You must preview your comment first before finally posting.





← Older Newer →