Universal logic modules vs NAND-like modules

C

Candida Ferreira

Guest
Hi everyone,

Is there a proper name to distinguish NAND-like universal modules from
ordinary ones, that is, the ones formed by a function F, plus NOT, plus ONE,
and ZERO?

Thanks,
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!
 
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
QuickScore@USSailing.net
www.QuickScoreRace.com


"Candida Ferreira" <cferreira@seehomepage.com> wrote in message
news:W_Lhe.80912$Cq2.60893@fe2.news.blueyonder.co.uk...
Hi everyone,

Is there a proper name to distinguish NAND-like universal modules from
ordinary ones, that is, the ones formed by a function F, plus NOT, plus
ONE,
and ZERO?

Thanks,
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!
Click to expand...
 
Tom Pounds wrote:
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
Click to expand...
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!
 
On Mon, 16 May 2005 16:39:45 +0000, Candida Ferreira wrote:
Tom Pounds wrote:
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

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

That would be a PROM (programmable read-only memory). For example, the
Click to expand...
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
 
On Mon, 16 May 2005 16:39:45 GMT, "Candida Ferreira"
<cferreira@seehomepage.com> wrote:


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).
Click to expand...
---
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?

--
John Fields
Professional Circuit Designer
 
John Fields wrote:
On Mon, 16 May 2005 16:39:45 GMT, "Candida Ferreira" wtote:

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

---
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?
Click to expand...

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!
 
On Tue, 17 May 2005 10:57:53 GMT, "Candida Ferreira"
<cferreira@seehomepage.com> wrote:


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.
Click to expand...
---
I see.

Thank you.

--
John Fields
Professional Circuit Designer
 
Candida Ferreira wrote:

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



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
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!



"Dan Hollands" :


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
QuickScore@USSailing.net
www.QuickScoreRace.com


"Candida Ferreira" wrote :


Hi everyone,

Is there a proper name to distinguish NAND-like universal modules from
ordinary ones, that is, the ones formed by a function F, plus NOT, plus
ONE,
and ZERO?
Click to expand...
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
 
On Tue, 17 May 2005 16:19:50 -0400, Barry Jones wrote:

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.
Click to expand...
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
 
Rich Grise wrote:

On Tue, 17 May 2005 16:19:50 -0400, Barry Jones wrote:



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.



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.


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

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


I think of a ULM as a dynamic module, in that one can change the control
Click to expand...
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!
Rich


Cheers back atcha!
Click to expand...
--
Barry
 
Generic logic functions are AND, OR, NOT. The NAND and NOR functions are
combinations of
AND OR and NOT functions
Click to expand...
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
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!



"Dan Hollands" :
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
QuickScore@USSailing.net
www.QuickScoreRace.com


"Candida Ferreira" wrote :
Hi everyone,

Is there a proper name to distinguish NAND-like universal modules from
ordinary ones, that is, the ones formed by a function F, plus NOT, plus
ONE,
and ZERO?

Thanks,
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!
Click to expand...
 
Candida Ferreira wrote:
Generic logic functions are AND, OR, NOT. The NAND and NOR
functions are
combinations of
AND OR and NOT functions

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
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!
Click to expand...
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
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top