Hacker News Reader

Comment by deepCelibate | Hacker News Reader

119 pointsdeepCelibate50 comments

For those who want a real deep dive, I recommend this video course on Analysis of Boolean Functions from Ryan O'Donnell:

https://www.youtube.com/watch?v=JIruJ8edYYM https://www.cs.cmu.edu/~odonnell/boolean-analysis/

And his book: http://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-...

Some recent progress in the field includes the amazingly simple proof of the Sensitivity Theorem by Hao Huang: https://arxiv.org/abs/1907.00847

Here's Knuth's one-page proof: https://www.cs.stanford.edu/~knuth/papers/huang.pdf

Thank you very much

Also note that NAND is actually simpler to implement in CMOS than AND, because inversion comes naturally.

https://www.allaboutcircuits.com/uploads/articles/CMOS-AND-g...

That’s pretty interesting. Why can’t you do an AND gate just by putting two transistors in series between your input and output?

That's pass-transistor logic, which is used in lots of processors. The problem is that your voltage levels drop through each gate, so you can't chain many gates together. You need to have "normal" gates in between.

A "normal" gate amplifies and restores the voltage level so what you get out is better than what you put in. But in most technologies, the amplification stage also inverts, so you end up with basic gates such as NAND/NOR/AND-OR-INVERT, rather than AND/OR.

https://en.wikipedia.org/wiki/Pass_transistor_logic

Makes sense, thanks for the explanation!

> The NAND gate is significant because we can implement any Boolean function using a combination of NAND gate.

I would add that the NOR gate is also functionally complete.

> I would add that the NOR gate is also functionally complete.

Yes, one good example being the Apollo Guidance Computer [0], which was constructed wholly using NOR gates.

[0] https://en.wikipedia.org/wiki/Apollo_Guidance_Computer#Desig...

And thus why the excellent course "NAND to Tetris"[1] is named as such.

[1] https://www.nand2tetris.org/

Doesn't the NOR gate take more transistors to build though? IIRC, the NAND gate can be built with only two transistors while you need more for NOR.

If you are building a CMOS 2-input gate then both NAND and NOR use 4 transistors. (2 NMOS and 2 PMOS each)

The reason NAND is preferred is that NMOS transistors have roughly half the resistance of a PMOS transistor of the same size. This means that to get a gate with pull-up and pull-down networks of equal strength (which is usually desirable), the NOR gate needs very large PMOS transistors and tiny NMOS while the NAND gate has all of its' transistors equally sized and relatively small.

The result is that NAND gates are smaller in size and slightly quicker than an equivalent NOR gate.

In standard NMOS or PMOS circuitry, both a NAND gate and a NOR gate require two transistors each (and a resistor, which is usually actually a transistor as well). CMOS requires four transistors for both a NAND gate or a NOR gate. It's only in TTL logic, where you can have a single transistor with multiple emitters that a NAND gate uses fewer transistors.

It's fascinating that silicon has not completely eliminated the asymmetries that were a way of life in vacuum tube circuits.

Depends on the transistor technology you are using. It's possible to create bipolar NORs as compactly as CMOS NANDs.

The article doesn’t really explain very much (not that it ought to explain everything, but there’s very little).

The proof of the standard claims about ‘expressive adequacy’ (=functional completeness) in propositional logic is given in cap. 4 of Button’s Metatheory; forallx:Cambridge uses the same notation and gives a fairly easy (from a skim) introduction to propositional logic.¹

Briefly, however, a simple method of dealing with at least some of the cases is as follows.

Consider the connectives of propositional logic (e.g., ¬, ∧, ∨—add more symbols to taste to represent every other possible connective given by a truth table on two variables).

A sentence contains various sentence letters (P, Q, R, P₁, Q₁, R₁, P₂…—adjust to taste) and connectives; we define them inductively, with the base ‘atomic’ cases as the sentence letters and the inductive cases

- ¬φ where φ is a sentence,

- (φ · ψ) where φ and ψ are sentences, and · is some ‘binary connective’ (i.e., it corresponds to a function given by a truth table with two variables: it could be ∧ or ∨ or even the Quine dagger.)

Now, let the complexity of a sentence be the number of connectives appearing within it, which is equal to the number of invocations of one of the inductive rules above required to obtain a sentence (one can also think of sentences as trees).

We use induction on the complexity of a sentence to prove statements about all sentences. Let us consider, by way of example, or (∨). We can prove that ∨ alone is not expressively adequate.

Consider an assignment of truth values such that the truth value of any sentence letter is T(rue). Now, it should be possible to write some sentence the truth value of which is F(alse) solely using ∨, if ∨ is expressively adequate.

The difficulty is that one can’t. Informally, ∨ cannot take two true statements and give a false one, but it only has (under this assignment of truth values) true statements. It is easy to fill in the base and inductive cases because propositional logic is truth-functional (i.e., it does not matter what a proposition says, merely whether it is true or false.)

Similar strategies to find properties invariant under the use of inductive rules may be used to prove all sorts of metalogical statements, as shown in Button’s book.

0: available at http://www.homepages.ucl.ac.uk/~uctytbu/Metatheory.pdf

1: http://www.homepages.ucl.ac.uk/~uctytbu/OERs.html

Back in the 1990s I did the UC Berkeley computer hardware qualifying exam, which required building an entire pipelined RISC processor bottom-up out of nothing but NAND gates. We had three hours. Of course you build latches and D-flops out of NAND gates with feedback, and we could assume an external source for the clock. It was fun but I wouldn't want to do it again.

I seem to have learned this shit before there were (affordable) logic circuits. NAND was simply a transistor (or relay (or tube)) with punch of diodes pulling the gate or base down. We learned to use "Karnaugh Maps" to simplify the logic circutry to these bare NANDs. https://en.wikipedia.org/wiki/Karnaugh_map

> before there were (affordable) logic circuits.

That would have been a good while ago. You didn't build digital stuff out of TTL on breadboards? Now that I'm typing this, I am getting a hint from the parenthetical "(or relay (or tube))" :)

edit: I was personally an innovator of the "WAS" gate. They're made of smoke.

There were American SN7400s in 1974 of course, but they were expensive compared to single transistors. I also remember the Finnish Parliament voting machine, made with transistors and relays around 1968. It was huge incomprehensible mess on hand-wired breadboards. It was easier to make totally new one with microprocessors and printed circuits.

What was a "WAS" gate? Google does not seem helpful here.

I'm going to assume that the WAS gate was a NAND...until the smoke got let out.

See also DED: Darkness Emitting Diode.

Something that started out as a gate, but now is smoke and a little burnt ember of sadness.

Once you're done googling for WAS gates, head over to the shop and grab me a couple grid squares.

;)

It that to repair the water pump on your VW Beetle?

Thanks for the throwback to the University memory lane!

Also, glad to know that, according to Wikipedia, Mr. Karnaugh is alive.

Blogspam: https://news.ycombinator.com/submitted?id=deepCelibate

In all fairness, the previous versions didn't post correctly; they were never visible (you can verify this). I think it was an issue caused by the temporary outage yesterday.

It's been years since I did any real electronics but I remember using a NAND gate as a "programmable inverter".

The signal from input A to the output is either inverted or not inverted depending on the state of input B.

No, a programmable inverter is an XOR gate or XNOR gate.

You're right, of course. I wasn't thinking about that clearly :)

Well I was hoping to read an article about why or how the NAND gate is so important but the most I've been able to gather from this article is that the author doesn't know either and is unable to interpret any of the relevant literature.

These are helpful and show how any gate can be made from NAND:

https://en.wikipedia.org/wiki/NAND_logic

https://www.nand2tetris.org/

Any boolean function can be represented as a polynomial over the integers modulo 2 (that is, its algebraic normal form).

Modulo 2, AND is multiplication and XOR is addition. We also have the useful properties 1+1=0, x+x=0, and x^2 = x. Thus:

    NAND(0, 0) = 0*0 + 1 = 1

    NAND(x, y) = x*y + 1

    AND(x, y) = NAND(NAND(x, y), NAND(x, y)) = (x*y + 1)*(x*y + 1) + 1 = x*y + x*y + x*y + 1 + 1 = x*y

    XOR(x, y) = NAND(NAND(x, NAND(x, y)), NAND(y, NAND(x, y))) = (x * (x*y + 1) + 1) * (y * (x*y + 1) + 1) + 1 = (x*y + x + 1) * (x*y + y + 1) + 1 = x*y + x*y + x*y + x*y + x*y + x + x*y + y + 1 + 1 = x + y

Since both AND and XOR can be obtained from NAND, any polynomial can be constructed. It also becomes obvious that you can't get x*y from x+y and vice-versa, so neither XOR nor AND can be universal gates on their own.

NOR's algebraic form is x*y + x + y + 1, from which you can similarly derive AND and XOR. XNOR is x + y + 1, from which AND cannot be obtained.

Ah yes, this is probably a more intuitive way of doing things than in my comment (though of course we prove different things).⁰ I should add that for those interested, the SEP page on algebraic propositional logic is quite interesting, although I regrettably have not actually gotten round to working through it.¹

0: https://news.ycombinator.com/item?id=28756727

1: https://plato.stanford.edu/entries/logic-algebraic-propositi...

Is there an explanation as to why can we do this?

i.e. Why can NAND and NOR be used to form all other gates? And why not AND, say?

You need a function of more inputs than outputs in order to compose into a function of multiple inputs and a single output. This rules out NOT.

Then, we just need to rule out all functions that can't build NOT (i.e. invert one of their inputs). AND and OR obviously can't do this. XOR and XNOR can, but only if you can guarantee a consistent synthetic input, which is not a good requirement from either a theoretical or practical perspective. NAND and NOR can implement NOT by just repeating the same input twice.

The important quality of NAND and NOR gates is they can be used as inverters. Send the same value to both inputs and the output will be the inverse. Without an inverter you can't really get anywhere.

There are 8 possible truth tables for two inputs, so we have 8 possible gates. But two of them are obviously useless, the one which yield true for any input and one which yield false for any input. So we have 6 useful gates.

These are AND, OR, XOR, NAND, NOR and XNOR.

Of these, only NAND and NOR can be used as inverters.

Given an inverter and any of the gates you can build any other. E.g AND with an inverted output is NAND, NAND with inverted inputs are OR, OR with inverted output is NOR. XOR can be build by combining NAND and OR.

There are 2^(2x2)=16 possible truth tables with two inputs. The 8 above are the _symmetric_ ones.

This is the topic of "clone theory": the study of which (multivariable) operations can be created by composing together a starting collection of operations. Post's lattice is a complete description of which gates can be generated from which other gates in two-valued logic, but the subject becomes much more difficult in multivalued logic.

If you are just interested in whether a given gate would allow you to generate all possible operations in a multivalued logic, then there is a nice result called the Rosenberg Completeness Theorem that says, roughly speaking, that any operation which doesn't have a nice property (from a certain explicit list of nice properties, such as monotonicity, linearity, etc.) will generate all other operations. To answer your question, NAND is special because it isn't monotone, isn't linear (in the sense of not being a linear function modulo 2), isn't self-dual, doesn't send all-0s to 0, and doesn't send all-1s to 1.

It's not possible to implement inversion using AND or OR.

> the most I've been able to gather from this article is that the author doesn't know either and is unable to interpret any of the relevant literature.

I got the impression that the author is very familiar with the topic and wrote this for shits'n giggles. The "article" is a string of entertaining nonsense that doesn't go anywhere and seems to purely mock some of the typical philosophical musings filled pseudo-tutorial articles that crop up on HN from time to time. Especially comparing it some other stuff on that site[1].

The witty writing style, completely silly analogies and puns somehow remind me of a certain Unix-grey-beard that I had as a high school teacher (the "FerdiNAND" line would be spot on for the guy).

And yes, I have read the response from the author below yours[2], and I believe there's some brilliant trolling going on here at the moment. ("oh yes, you're right! I actually am utterly clueless.")

[1] https://sebastiancarlos.medium.com/from-ai-to-zi-an-encyclop...

[2] https://news.ycombinator.com/item?id=28757743

Author here. You are correct about everything. I appreciate that you took the time to write this.

The only exception is that, honestly, I'm not very familiar with the topic. I did try to mock the typical pseudo-tutorial articles, but I don't claim that I can do any better.

NAND-gates are important because every other boolean operation can be made with a combination of them. This means that you can construct a computer out of nothing but them.

If you want to see it in action try this https://nandgame.com/

Many computers were designed entirely out of NAND gates. Most famously the Cray-1.

Well I've been thoroughly nerd sniped by that game, so much for a productive Tuesday.

Author here, you are correct.

I guess I was trying to express the "saudade" of finding a new topic but not having the time to learn it properly.

It was entertaining.

Thanks!

Using only NAND-gates, you can implement any other logic gates which means you can build an entire programmable computer using only NAND-gates.

For example, if you send the same signal to both inputs of a NAND gate, you have an inverter, i.e. a NOT-gate. If you place a NOT gate after a NAND-gate then the combination is an AND gate. If you invert both inputs you have an OR gate. Binary addition can be built from AND + XOR, subtraction from addition and so forth.

If you pipe the output of an OR-gate back to one of the inputs, then you have a latch which can remember one bit of information. Combine two latches you have flip-flop which can be driven by a clock signal. (The clock signal can be generated by a loop of NOT-gates.) Place flip-flops in parallel you have RAM.

See http://nandgame.com if you want to try it for yourself.

Reply on news.ycombinator.com