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?

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.

"JJ" <[email protected]> wrote in message
news:[email protected] oups.com...
> Question doesn't make sense to me.
>
> Try again or pick up a logic book.
>
> Maybe you refer to fixed logic v tablelogic?
>
> So what brings someone in your esteemed field down into the hw
> trenches.
>
> johnjakson at usa dot com
>

Candida Ferreira wrote:
> 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.

I don't follow. Multiplexers are as complete as any logic element.
I'm not sure what you mean by a 3-multiplexer, but I will assume you
mean a 2 input mux with a single control input. You can get a NOT
function by putting a 1 on the I0 input and a 0 on the I1 input and
your signal on the sel input.

> NAND and NOR functions by themselves can be used to describe any other
> function, including NOT, ZERO and ONE.

True. NCR once produced a computer using only NAND gates.

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

A four to one mux can make any boolean function of two variables.
The mux selector takes the two inputs and the mux inputs
become a function code.

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

A NAND or NOR is the simplest case, but requires multiple instances.
A 4:1 mux is the simplest complete case for two inputs.
There are cases in between and redundant cases,
but those are not very interesting.

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

Not in digital electronics. Do some research on "Lattice Theory"

> I don't follow. Multiplexers are as complete as any logic element.
> I'm not sure what you mean by a 3-multiplexer, but I will assume you
> mean a 2 input mux with a single control input. You can get a NOT
> function by putting a 1 on the I0 input and a 0 on the I1 input and
> your signal on the sel input.

That's true and does not contradict the definition of a ULM, but you need
the 1 and the 0 to create a NOT. Without them you cannot create a NOT with
the 3-multiplexer. But there are other functions, such as the NAND and the
NOR functions that, by themselves, can create any other function, without
needing the NOT, the ZERO and the ONE. These are the ULMs I want to
distinguish from the more ordinary ones.

On Mon, 16 May 2005 14:42:37 GMT, "Candida Ferreira"
<[email protected]> wrote:

>"rickman" wrote:
>
>> I don't follow. Multiplexers are as complete as any logic element.
>> I'm not sure what you mean by a 3-multiplexer, but I will assume you
>> mean a 2 input mux with a single control input. You can get a NOT
>> function by putting a 1 on the I0 input and a 0 on the I1 input and
>> your signal on the sel input.
>
>That's true and does not contradict the definition of a ULM, but you need
>the 1 and the 0 to create a NOT. Without them you cannot create a NOT with
>the 3-multiplexer. But there are other functions, such as the NAND and the
>NOR functions that, by themselves, can create any other function, without
>needing the NOT, the ZERO and the ONE. These are the ULMs I want to
>distinguish from the more ordinary ones.

I've seen them named "complete logic gate set" or "primitive logic
gate set". I am not sure whether there is a universally accepted name.

> "rickman" wrote:
>
> > I don't follow. Multiplexers are as complete as any logic element.
> > I'm not sure what you mean by a 3-multiplexer, but I will assume you
> > mean a 2 input mux with a single control input. You can get a NOT
> > function by putting a 1 on the I0 input and a 0 on the I1 input and
> > your signal on the sel input.
>
> That's true and does not contradict the definition of a ULM, but you need
> the 1 and the 0 to create a NOT. Without them you cannot create a NOT with
> the 3-multiplexer. But there are other functions, such as the NAND and the
> NOR functions that, by themselves, can create any other function, without
> needing the NOT, the ZERO and the ONE. These are the ULMs I want to
> distinguish from the more ordinary ones.

Do you mean, they are _generators_ for whole family of binary functions ?

MB

PS: there's a booklet by Emil Post on this subject of binary
functions. Forgot the title, sorry.

Michel Billaud wrote:
> "Candida Ferreira" <[email protected]> writes:
>
> > "rickman" wrote:
> >
> > > I don't follow. Multiplexers are as complete as any logic element.
> > > I'm not sure what you mean by a 3-multiplexer, but I will assume you
> > > mean a 2 input mux with a single control input. You can get a NOT
> > > function by putting a 1 on the I0 input and a 0 on the I1 input and
> > > your signal on the sel input.
> >
> > That's true and does not contradict the definition of a ULM, but you
need
> > the 1 and the 0 to create a NOT. Without them you cannot create a NOT
with
> > the 3-multiplexer. But there are other functions, such as the NAND and
the
> > NOR functions that, by themselves, can create any other function,
without
> > needing the NOT, the ZERO and the ONE. These are the ULMs I want to
> > distinguish from the more ordinary ones.
>
> Do you mean, they are _generators_ for whole family of binary functions ?
>
> MB
>
> PS: there's a booklet by Emil Post on this subject of binary
> functions. Forgot the title, sorry.
>
> --
> Michel BILLAUD [email protected]
> LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792
> 351, cours de la Libération http://www.labri.fr/~billaud
> 33405 Talence (FRANCE)

Mike Treseler wrote:
> Candida Ferreira wrote:
>
> > NAND and NOR functions by themselves can be used to describe any
other
> > function, including NOT, ZERO and ONE.
>
> True. NCR once produced a computer using only NAND gates.
>

It's a good bet that they didn't use any NAND gates to generate
ones or zeroes! This sounds like a mathematician kind of question
rather than engineering...

> It's a good bet that they didn't use any NAND gates to generate
> ones or zeroes! This sounds like a mathematician kind of question
> rather than engineering...

A rose by another name.

I read NOT, ZERO, and ONE as
inverter, tied low, tied high.

Candida Ferreira wrote:
> "rickman" wrote:
>
> > I don't follow. Multiplexers are as complete as any logic element.
> > I'm not sure what you mean by a 3-multiplexer, but I will assume
you
> > mean a 2 input mux with a single control input. You can get a NOT
> > function by putting a 1 on the I0 input and a 0 on the I1 input and
> > your signal on the sel input.
>
> That's true and does not contradict the definition of a ULM, but you
need
> the 1 and the 0 to create a NOT. Without them you cannot create a NOT
with
> the 3-multiplexer. But there are other functions, such as the NAND
and the
> NOR functions that, by themselves, can create any other function,
without
> needing the NOT, the ZERO and the ONE. These are the ULMs I want to
> distinguish from the more ordinary ones.

Gabor wrote:
> Mike Treseler wrote:
> > Candida Ferreira wrote:
> >
> > > NAND and NOR functions by themselves can be used to describe any
> other
> > > function, including NOT, ZERO and ONE.
> >
> > True. NCR once produced a computer using only NAND gates.
> >
>
> It's a good bet that they didn't use any NAND gates to generate
> ones or zeroes! This sounds like a mathematician kind of question
> rather than engineering...

Someone needs to tell me how to create a one or zero using only NAND
gates.

The only thing I can think of would be to use two gates in a loop.
This will have two stable states, 1-0 and 0-1. The two free inputs
will set the gates to the two states when taken low since any input at
a zero will make the output of the gate a one. One of these free
inputs is tied to its twin input to make an inverter. The other is
tied to its own gate output. If the gate output is a one, it causes no
action on the gate and is stable. If a zero, it will cause itself to
become a one and be then be stable.

But this will only generate a stable output after some period of time.
Not exactly my idea of a useful circuit.

rickman wrote:
> Gabor wrote:
> > Mike Treseler wrote:
> > > Candida Ferreira wrote:
> > >
> > > > NAND and NOR functions by themselves can be used to describe
any
> > other
> > > > function, including NOT, ZERO and ONE.
> > >
> > > True. NCR once produced a computer using only NAND gates.
> > >
> >
> > It's a good bet that they didn't use any NAND gates to generate
> > ones or zeroes! This sounds like a mathematician kind of question
> > rather than engineering...
>
> Someone needs to tell me how to create a one or zero using only NAND
> gates.
>
> The only thing I can think of would be to use two gates in a loop.
> This will have two stable states, 1-0 and 0-1. The two free inputs
> will set the gates to the two states when taken low since any input
at
> a zero will make the output of the gate a one. One of these free
> inputs is tied to its twin input to make an inverter. The other is
> tied to its own gate output. If the gate output is a one, it causes
no
> action on the gate and is stable. If a zero, it will cause itself to
> become a one and be then be stable.
>
> But this will only generate a stable output after some period of
time.
> Not exactly my idea of a useful circuit.

This is why I said the problem was mathematical and not engineering.
A Boolian NAND gate performs a truth function on ones and zeroes only.
This is not the same as a Verilog NAND gate which can take X or Z
as well as 1 or 0 and produce X as well as 0 or 1.

The Boolian NAND also does not imply a time delay. So given such a
gate with an unknown input "A", you can produce the inversion of the
unknown input "A_BAR" (A NAND A), and then create 1 by NANDing "A"
with "A_BAR" (A NAND A_BAR).
Zero requires an additional inverter (1 NAND 1).

In the real world this would produce glitches whenever "A" changed
state.

> The Boolian NAND also does not imply a time delay. So given such a
> gate with an unknown input "A", you can produce the inversion of the
> unknown input "A_BAR" (A NAND A), and then create 1 by NANDing "A"
> with "A_BAR" (A NAND A_BAR).
> Zero requires an additional inverter (1 NAND 1).

[nand]
>
> In the real world this would produce glitches whenever "A" changed
> state.

In the real world, who needs to get 0 and 1 from whatever gate anyway ?

BTW, this reminds me of a funny paper on how to build a triple not
circuit using only 2 not gates (and a number of and- and or-
gates).

"rickman" <[email protected]> wrote in message
news:[email protected] oups.com...
> Candida Ferreira wrote:
> > "rickman" wrote:
> >
> > > I don't follow. Multiplexers are as complete as any logic element.
> > > I'm not sure what you mean by a 3-multiplexer, but I will assume
> you
> > > mean a 2 input mux with a single control input. You can get a NOT
> > > function by putting a 1 on the I0 input and a 0 on the I1 input and
> > > your signal on the sel input.
> >
> > That's true and does not contradict the definition of a ULM, but you
> need
> > the 1 and the 0 to create a NOT. Without them you cannot create a NOT
> with
> > the 3-multiplexer. But there are other functions, such as the NAND
> and the
> > NOR functions that, by themselves, can create any other function,
> without
> > needing the NOT, the ZERO and the ONE. These are the ULMs I want to
> > distinguish from the more ordinary ones.
>
> Why?
>

"rickman" wrote:
> Candida Ferreira wrote:
> > "rickman" wrote:
> >
> > > I don't follow. Multiplexers are as complete as any logic element.
> > > I'm not sure what you mean by a 3-multiplexer, but I will assume
> you
> > > mean a 2 input mux with a single control input. You can get a NOT
> > > function by putting a 1 on the I0 input and a 0 on the I1 input and
> > > your signal on the sel input.
> >
> > That's true and does not contradict the definition of a ULM, but you
> need
> > the 1 and the 0 to create a NOT. Without them you cannot create a NOT
> with
> > the 3-multiplexer. But there are other functions, such as the NAND
> and the
> > NOR functions that, by themselves, can create any other function,
> without
> > needing the NOT, the ZERO and the ONE. These are the ULMs I want to
> > distinguish from the more ordinary ones.
>
> Why?
>

Because with them you can find interesting solutions using just one kind of
gate. I think that, if for nothing else, this might be fun. And if fpga
technology allows people to use different kinds of gate such as the
3-multiplexer, why not use other complex modules? And if you know for sure
the module you are using is a NAND-like module you can even relinquish the
use of inverters and build circuits using just that gate.