Universal logic modules vs NAND-like modules

Generic logic functions are AND, OR, NOT. The NAND and NOR functions are combinations of AND OR and NOT functions

--

Dan Hollands

1120 S Creek Dr Webster NY 14580 585-872-2606 snipped-for-privacy@USSailing.net

functions are

question.

other

3-multiplexer,

gate

that

themselves, they

I think

them

Candida,

There are no more basic functions in Boolean algebra that can be used to create all other functions, than the NAND or NOR functions. These functions themselves can be further simplified into an AND with a NOT, or an OR with a NOT.

A NOT function cannot be used to reduce more than one input -- it is a unary operator. An AND or an OR cannot invert, but they are reduction operators. To derive any higher level function requires the combination of a reduction operator (AND, OR) and the unary inversion operator(NOT).

DeMorgans theorem shows the logical equivalence of the juxtaposition of these 3 types of operators, so it doesn't matter if you use NAND's or NOR's.

Tom Pounds

It all depends on how you see things, I guess. But that was not my question. NAND and NOR functions by themselves can be used to describe any other function, including NOT, ZERO and ONE. But, for instance, the 3-multiplexer, which is also by definition an ULM, can not by itself describe a NAND gate as it is unable to create a NOT gate. But there are other functions that behave exactly like NAND or NOR gates in the sense that, by themselves, they can also describe any other function. Do such functions have a name? I think there is something special about them and I would like to distinguish them from the ordinary ULMs.

Candida

--- Candida Ferreira, Ph.D. Chief Scientist, Gepsoft

GEP: Mathematical Modeling by an Artificial Intelligence

Modeling Software Get APS 3.0 Std free with the book!

"Dan Hollands" :

That would be a PROM (programmable read-only memory). For example, the

82S123 has five inputs and eight outputs (32 X 8 memory). All you do is, for each combination of inputs (really an address) program the outputs to whatever you want them to be.

Good Luck! Rich

--
I don\'t understand your notation.

For example, if we\'re dealing with devices with inputs which can only
be in one of two states, and outputs which can only be in one of two
states, then ISTM that, without inversion, the IF function boils down
to " If A then Y, else Y-"  That is, with a 1 on the input (A) there
will be a one on the output (Y), but with a 0 on the input there will
be a 0 on the output.  Basically, a piece of wire.  If that\'s the
case, how does your notation, "202", apply to that function?

Yeah, I know. But I'm not just interested in "basic" Boolean functions. I'm studying a large set of functions with 3 and 4 inputs and there are lots of functions that can be classified as standard ULMs (that is, functions that together with NOT, ZERO, and ONE can describe any other function) and functions that just by themselves can create any other function (for the time being, I'm calling these functions NAND-like modules - NLM). So, standard ULMs would be, for instance, the IF[a=1,b,c] function (function

202) or the 3-multiplexer (function 172). And an NLM would be, for example, a'c'+b'c (function 39).

Candida

--
Candida Ferreira, Ph.D.
Chief Scientist, Gepsoft
http://www.gene-expression-programming.com/author.asp

GEP: Mathematical Modeling by an Artificial Intelligence
http://www.gene-expression-programming.com/gep/Books/index.asp
Modeling Software
http://www.gepsoft.com/gepsoft/
                          Get APS 3.0 Std free with the book!

--
I see.  

Thank you.

I'm

of

that

example,

I'm using the notation proposed by Stephen Wolfram to classify Boolean functions. For instance, the truth table for the function IF A = 1, THEN B, ELSE C will be:

A B C O

0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1

which can be written more succinctly by 11001010, or in decimal by 202.

Candida

--
Candida Ferreira, Ph.D.
Chief Scientist, Gepsoft
http://www.gene-expression-programming.com/author.asp

GEP: Mathematical Modeling by an Artificial Intelligence
http://www.gene-expression-programming.com/gep/Books/index.asp
Modeling Software
http://www.gepsoft.com/gepsoft/
                          Get APS 3.0 Std free with the book!

I don't quite understand your interpretation of a ULM. To me, a ULM takes in a set of data bits, and a set of control bits, such that the data bits are mapped to a set of output bits via a function, which is determined by the control bits. If you wish to consider the input bits to be split between data bits, and some constants ( 0 and 1 ), that is irrelevant to the ULM.

You can set the control lines of a ULM to produce an output that is always 1 or always 0. Perhaps this is what you imply by 'a function F plus NOT plus 1 and 0'. Or perhaps you are thinking about something like as a five variable logic function by creating a four variable logic function, and cascading it into another logic unit that applies another function to the input F that produces F, F', 1, or 0.

Maybe I'm missing your point, but it seems to me that you are worried about how a universal logic module is implemented, whether by ANDs ORs and NOTs (primitive gates), or by all NANDs or all NORs, which are built from the primitives.

As you're probably aware, anything expressible in AND, OR, or NOT can be expressed as all NANDs or all NORs. An array of all NANDs or all NORs is built using AND OR and NOT gates, if you peel back the curtain a little further. If you can afford a few extra gates, offering the designer an array of NANDs or NORs can result in easier implementation at the cost of extra primitive gates (ANDs ORs and NOTs).

The choice of implementing a ULM using primitives vs. NANDs or NORs is determined by whether or not you have an abundance of gates on a chip such that a 'regular' arrangement of one kind of gate, like a well planned city, is better than some ad hoc layout of different kinds of gates.

This has no bearing on the kind of function you input to the ULM, which you describe at a symbolic level, independent of implementation.

Why would you want to differentiate ULMs based on their implementation? Mostly, You're not suppose to look behind that curtain unless you are building hardware. :^)

Am I missing some context here?

--
Barry

Just a nitpick, but I'd say that at the hardware level, the NANDs and NORs are more likely to be more "primitive", in that they use fewer components - a common-emitter transistor intrinsically inverts. To make an "AND", you invert the output of a NAND, and so on.

But I already gave the answer to the "Universal" gate - a ROM. (or PROM).

Cheers! Rich

That's a useful nit. Thanks. Careful where you put that nit Eugene!

I think of a ULM as a dynamic module, in that one can change the control bits 'at runtime' to access different functions without reprogramming the ROM. As you would do in the L of an ALU. I suppose you could use a larger ROM and consider the upper data bits as control bits. For example, there are 16 functions of 2 variables, so you could select the variables with the 2 lowest input bits of a PROM, and the function by the next 4 bits. Expand to suit. Combinatorial explosion becomes a problem though. There are 256 functions of 3 bits, requiring 8 control bits. For every added data bit, we double the number of control bits (and the redundancy in the ROM). Note to the OP that zero and one are included in the list of available functions, rather than being considered 'special.'

Cheers back atcha!

--
Barry