The Reed-Muller System is yet another popular and compact Universal Logical System (see the previous post "Go Language: MUX System" about another compact logical system) that uses exclusively NOT, AND, and XOR in the design of electronic circuits.

GeneXproTools implements the Reed-Muller System for all supported programming languages and here we'll take a look at the Reed-Muller Grammar for the Go language.

The Reed-Muller Grammar allows us to convert automatically any logic circuit into NOT-AND-XOR gates. And this is possible because GeneXproTools maps all its 258 built-in logical functions into NOT-AND-XOR. For example, we can create a Reed-Muller circuit for the 3-Majority function:

Now compare this minimal logic circuit with the minimal circuits that we designed for the other universal systems – the Boolean NOT-AND-OR System, the NAND System, the NOR System and the MUX System (they are all shown in the previous post).

As you can see, the NOT-AND-XOR circuit is among the most compact with just 5 literals (the same number of literals as the NOT-AND-OR System and MUX System).

And if we repeat the same exercise that we did in the previous post and convert the minimal Boolean NOT-AND-OR circuit to the Reed-Muller System using our new Go Reed-Muller Grammar, we get:

This circuit is also very compact with just 8 literals (although this should not come as a surprise as we are only mapping the OR gate, which of course favors immensely this system; as a comparison, the NAND and NOR circuits both use 28 literals and the MUX circuit uses 17).

So, like we showed for the MUX System in the previous post, the Reed-Muller System is indeed very well suited for designing extremely compact logic circuits.

This ends our journey into Universal Logical Systems and the Go language. Next I'll talk briefly about the Boolean Grammars for the R language as we will be adding them to GeneXproTools with this mini-release "New Project: Cross-Validation, Var Importance & More".

The building blocks of the MUX Universal System are 3-Multiplexer gates (MUX, for short) and NOT (inverters). And with these two types of building blocks we can design any kind of logic circuit. As a simple example, here's a MUX circuit for the XOR function:

XOR(x,y)= MUX((!(x)),(!(y)),y)

The Go MUX Grammar of GeneXproTools defines not just the XOR function but all the 258 built-in logical functions in terms of MUX gates and NOT. This means that we can automatically convert all kinds of logic circuits to MUX circuits with this grammar.

MUX circuits are very popular, and the reason for their popularity is their compactness. In the remainder of this post I'll show you some simple examples to illustrate this claim.

For this exercise I had to choose a very simple function – the 3-Majority function – otherwise we would get huge circuits for some of the Universal Logical Systems I'll be using to make comparisons, namely, the NAND System and the NOR System.

Furthermore, I also decided on a very simple architecture of only 1 gene so that we could make more meaningful comparisons between the logical systems.

So let's start by designing a minimal logic circuit for the 3-Majority function using just NOT, AND, and OR:

And now let's repeat the exercise separately for NAND and NOR gates:

The minimal NAND circuit:

And the minimal NOR circuit:

And finally, the minimal MUX circuit:

As you can see, compared to the NAND and NOR circuits, the MUX circuit is very compact with only 5 literals (in this case, it's the same number of literals we got for the NOT-AND-OR circuit).

This is of course just a simple exercise using a simple function and we are bound to get some variation with different functions, but overall the MUX System is considerably more compact than the NAND System and the NOR System. And we can further illustrate this with a different exercise by using the built-in universal systems of GeneXproTools (the NAND, NOR, and MUX systems) to automatically convert NOT-AND-OR circuits into NAND, NOR, or MUX circuits.

As an illustration let's use the minimal NOT-AND-OR circuit presented above with only 5 literals.

And now let's convert this circuit to NAND gates using the NAND Grammar of GeneXproTools:

As you can see, the NAND code explodes unceremoniously, going from 5 literals to 28.

And the same is true for the NOR System:

In this case we also ended up with 28 literals.

For the MUX System we get considerably shorter circuits (17 literals in this case):

In the next post I'll talk about yet another Universal Logical System – the popular and compact Reed-Muller System.

In both electronics and logic the NOR gate has the same properties as the NAND gate (see the previous post "Go Language: NAND Grammar"). Like NAND, we can use NOR to define any logical expression. As a simple example here's how we can define the XOR function using only NOR:

XOR(x,y) = NOR(NOR(x,y),NOR(NOR(x,x),NOR(y,y)))

And as expected, the NOR Grammar defines all the 258 built-in logical functions of GeneXproTools in terms of NOR gates alone. These NOR-only function definitions are extremely compact solutions and, like we already saw for the NOT-AND-OR System and NAND System, they were discovered by GeneXproTools itself.

So in order to create the Go NOR Grammar, we can use these function definitions exactly as they are defined in our C# Grammar template (remember, we are using C# as our template for generating all Boolean Grammars for the Go language; see the post "Go Language: All Gates Boolean Grammar") to generate our NOR circuits in Go. Let's see some code examples (again I'll be using the 6-Multiplexer in all code examples).

Let's start with a minimal logic circuit for the 6-Multiplexer designed using only NOR gates (in this case it's irrelevant whether we use the All Gates Grammar or the NOR Grammar to generate the code, as they both give the same output):

And like we saw for the NAND System (see the previous post "Go Language: NAND Grammar"), by adding also NOT and OR to the function set, we can design NOR-only circuits quite easily by applying the NOR Grammar to the final circuit.

For example, the circuit below is a minimal logic circuit for the 6-Multiplexer that was created with NOT, OR and NOR gates:

Converting this minimal logic circuit to NOR gates using the Go NOR Grammar, gives:

As you can see, we went from a circuit with just 11 literals to a circuit slightly more complex with 13 literals.

Curiously, this NOR circuit is almost identical to the first NOR circuit shown above that was generated independently from scratch using just NOR gates! It's true that I chose the same architecture for designing both circuits, but it nevertheless suggests that we shouldn't be very far from the most compact configuration possible for this particular architecture.

And to finish, this last minimal circuit for the 6-Multiplexer was designed using all the logical functions of 2 arguments (not all of them made it through the final circuit, though):

And now converting this circuit to NOR gates using our new NOR Grammar, gives:

And like we saw happening with the NAND System (see the previous post "Go Language: NAND Grammar"), the number of literals almost doubled after the conversion to the NOR System (11 literals versus 20). So again we must choose carefully the building blocks (function set and linking function) that we use to design our circuits, especially if we are planning on using the NOR Grammar to convert the final circuit to NOR gates.

In the next post I'll introduce yet another Universal Logical System – the MUX System – and the MUX Grammar of GeneXproTools.

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:

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):

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):

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:

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

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.

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:

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

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):

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

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):

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

In the next post I'll introduce the widely used NAND System and the NAND Grammar of GeneXproTools.