This blog entry won't serve as an introduction to Boolean Algebra or logic gates, but rather just to illustrate an HTML5 widget I wrote that lets you manipulate NAND gates. In fact, before you begin, you should understand what these tables mean:
NOR = f(a,b) NAND = f(a,b) a b f a b f 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 0
If that makes no sense, start with this Wikipedia article on logic gates.
In the early 20th century, the maths world went wild trying to expand on George Boole's work on logic. Ernst Schröder, Edward Huntington, and Alfred Whitehead each developed conflicting notation systems and postulate sets, each with published works that were pretty arcane. For instance:
Sets of Independent Postulates for the Algebra of Logic
A Treatise on Universal Algebra
Subsequently, Charles Peirce and Henry Sheffer tried to take these methodologies and simplify them, and both created similar works describing a new logic function. Peirce described the NOR function in his paper "A Boolean Algebra with One Constant", which was a novel concept at the time.
Although he wrote it 30 years earlier, his paper wasn't published until well after Sheffer's work describing the same function. What's that, you say? Sheffer's paper was on the NAND function? No, no it wasn't. Here are the postulates from Sheffer's paper "A set of five independent postulates for Boolean algebras, with application to logical constants":
Again, pretty arcane. The business with the class K, and K-rules isn't intuitive, but my understanding is that it refers to functions which take multiple inputs from a set, and returns one output from the same set. Logic functions as the software developer understands them are an example of this, as logic functions have inputs from a class (true/false, or 0/1, or z/u if you're old school), and produce one output from the same class.
The postulates above work equally well for the NOR and NAND functions. Later in the paper he submits these corollaries:
IIa. There is a K-element z such that for any K-element a, (a | z)' = a. IIb. There is a K-element u such that for any K-element a, a' | u' = a
In a footnote he compares z with 0 (zero) and u with 1 (unary), which would make the above equations true only in a NOR function. However, flipping the values of z and u give us NAND. The point of the paper wasn't specifically to illustrate NAND or NOR, but to posit that there exists a logical operation that is functionally complete, and can be used to express the entire gamut of logical operations. Sheffer is credited incorrectly with the NAND function, and the pipe symbol he used in the above paper is referred to as the "Sheffer Stroke".
Because NAND and NOR are functionally complete, they show up in integrated circuits, where they can be placed in series to perform more complex operations. The 4000 series is a good example of this.
And that's also where the fun starts. I've used some logic gate builder web apps before, and I found them all pretty clunky. I wanted something with a simpler user interface, that maybe I could build on later to a full featured circuit builder, or just hook into a simple quiz page (quick, build me an OR gate using only NANDs!). This is where the project stands now:
Here is a video of me using the same to create other basic logic gates:
And lastly, here are some images of using the app to illustrate a couple of Sheffer's postulates:
4. Whenever a, b, and the indicated combinations of a and b are K-elements,
a | (b | b') = a'.
5. Whenever a,b,c, and the indicated combinations of a, b, and c are K-elements,
(a | (b | c))' = (b' | a) | (c' | a).
Left side: 
Right side: 
No comments:
Post a Comment