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!
Universal logic modules vs NAND-like modules
Started by ●May 15, 2005
Reply by ●May 16, 20052005-05-16
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
Reply by ●May 16, 20052005-05-16
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! "JJ" <johnjakson@yahoo.com> wrote in message news:1116236810.947060.102680@o13g2000cwo.googlegroups.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 >
Reply by ●May 16, 20052005-05-16
Candida Ferreira wrote:> NAND and NOR functions by themselves can be used to describe anyother> function, including NOT, ZERO and ONE. But, for instance, the3-multiplexer,> which is also by definition an ULM, can not by itself describe a NANDgate> as it is unable to create a NOT gate. But there are other functionsthat> behave exactly like NAND or NOR gates in the sense that, bythemselves, 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 distinguishthem> 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.
Reply by ●May 16, 20052005-05-16
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.> 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" -- Mike Treseler
Reply by ●May 16, 20052005-05-16
"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. 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!
Reply by ●May 16, 20052005-05-16
On Mon, 16 May 2005 14:42:37 GMT, "Candida Ferreira" <cferreira@seehomepage.com> 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.
Reply by ●May 16, 20052005-05-16
"Candida Ferreira" <cferreira@seehomepage.com> 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 billaud@labri.fr 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)
Reply by ●May 17, 20052005-05-17
> Do you mean, they are _generators_ for whole family of binary functions ?Yes, exactly like NAND and NOR. Just to give another example, you can also do that with the function a'c'+b'c. 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! Michel Billaud wrote:> "Candida Ferreira" <cferreira@seehomepage.com> 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 youneed> > the 1 and the 0 to create a NOT. Without them you cannot create a NOTwith> > the 3-multiplexer. But there are other functions, such as the NAND andthe> > 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 billaud@labri.fr > 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)
Reply by ●May 17, 20052005-05-17
Mike Treseler wrote:> Candida Ferreira wrote: > > > NAND and NOR functions by themselves can be used to describe anyother> > 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...
