Go Language: NOT-AND-OR Grammar

Posted
Comments None

We've already established in the previous post "Go Language: All Gates Boolean Grammar" that we'll be using the C# Grammar as template to generate all the Boolean grammars for the Go language. In fact, I've already explained in the previous post how to make most of the changes all at once for the 6 Boolean grammars and, therefore, our new NOT-AND-OR Grammar should be almost ready. Indeed, we just need to check if all the logical operators for NOT, AND, and OR and the keywords "true" and "false" are the same in C# and Go as these are the only building blocks that are needed for creating the NOT-AND-OR Grammar.

And like we saw in the previous post "Go Language: All Gates Boolean Grammar", these operators are indeed identical in both programming languages, which means we don't have to make any changes in the definitions of all logical functions. So this means we are ready to generate some code!

But before that, just a few words about the NOT-AND-OR Universal Logical System and the NOT-AND-OR Grammar of GeneXproTools.

The purpose of the NOT-AND-OR Grammar is to automatically convert any circuit with any number of different gates to a circuit composed of only NOT-AND-OR gates. And the rules for generating that code are dictated by the NOT-AND-OR Grammar. In this grammar, all the 258 built-in logical functions of GeneXproTools are defined in terms of NOT, AND, and OR gates and "true" and "false". This code was designed to be as parsimonious as possible (the code was generated by GeneXproTools itself!), but there's no guarantee that it's minimal for all the 258 logical functions.

But let's see how the NOT-AND-OR Grammar works with some code examples (and just in case I should forget, all the circuits shown in this post are for the 6-Multiplexer).

Suppose for a moment that my goal was to design a logic circuit with only the basic Boolean operators of NOT, AND, and OR. And also suppose that I also noticed that evolution was more efficient when I also included the functions NAND and NOR as building blocks.

Well, thanks to the NOT-AND-OR Grammar I can go ahead and evolve my circuits with also NAND and NOR. Then in the end I can just replace all the NAND and NOR gates with NOT-AND-OR gates using the NOT-AND-OR Grammar without incurring much penalty in terms of compactness.

So here's a minimal logic circuit for the 6-Multiplexer designed with the basic Boolean functions (NOT, AND, OR) plus NAND and NOR:

package gepModel

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

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

    return y
}

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

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

And here's the same circuit automatically translated to only NOT, AND, and OR gates using the NOT-AND-OR Grammar:

package gepModel

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

    y = (!(d[1] && (!(d[3] || d[0]))))
    y = y && ((d[2] || d[1]) || d[0])
    y = y && (!(d[0] && (!(d[1] || d[4]))))
    y = y && ((!(d[1] && d[0])) || d[5])

    return y
}

Now what happens if we extend our pallet of building blocks to all the logical functions of 2 arguments? We can create minimal circuits just as before, but then upon translation we might incur some penalty. Here's an example: it's again a minimal logic circuit for the 6-Multiplexer and it was evolved using all the logical functions of 2 arguments (the final circuit uses only AND, OR, NAND and LOE gates, though):

package gepModel

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

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

    return y
}

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

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

And here's its conversion to just NOT-AND-OR gates using the NOT-AND-OR Grammar:

package gepModel

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

    y = ((d[0] || d[1]) || d[2])
    y = y && ((!(d[1])) || (d[3] || d[0]))
    y = y && (((!(d[0])) || d[1]) || d[4])
    y = y && (d[5] || (!(d[0] && d[1])))

    return y
}

As you can see, we were lucky in this case and ended up with only gates that translate very parsimoniously to NOT-AND-OR gates. But if instead we ended up with lots of XOR or NXOR gates in our final circuit, its conversion would have resulted in a much more verbose circuit with more gates than the original.

Here's another example to illustrate exactly this situation (this code is far from parsimonious as I wanted to include XOR or NXOR in the final circuit and they refused to show up in the more parsimonious solutions):

package gepModel

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

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

    return y
}

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

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

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

And now translating the circuit above to NOT-AND-OR gates using the NOT-AND-OR Grammar results in a less parsimonious circuit:

package gepModel

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

    y = ((!((d[1] || d[1]))) || (d[1] && d[1]))
    y = y && ((!((d[1] || d[1]))) || (d[1] && d[1]))
    y = y && (!((!((!(d[1])) || (d[3] || d[0])))))
    y = y && (!((!(d[1] || (d[2] || d[0])))))
    y = y && ((!(d[0])) || (!((!((d[1] || d[4]))))))
    y = y && (!((!((!(((!(d[5])) && d[1]))))) && d[0]))

    return y
}

In the next post I'll introduce the widely used NAND System and the NAND 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 →