# OR gate from one AND, three NOT?

I'm just starting with digital-logic but I now face a little problem: I learned that AND, OR, NOT were basic gates and that one basic gate could not be made from a combination of two others. How comes that this combination:

produces an OR truth table from only AND and NOT gates?

• It is simply wrong that some of what you call the "basic" gates can't be made from others. For example, you can make all the gates from all NAND or all NOR. – Olin Lathrop Nov 13 '12 at 23:28
• i think someone was confusing "necessary" with "sufficient" – vicatcu Nov 14 '12 at 3:45

Whoever told you that was simply wrong. In fact, many logic families use just one kind of gate, especially in the early days. RTL logic families were basically all NOR gates, and DTL and TTL families are basically NAND gates. In either case, you can think of NOT as a single-input gate.

You can build any logic function at all from just NOR gates or just NAND gates. Entire computers have been built this way, including the earlier Cray supercomputers.

And don't forget that !(A + B) == !A & !B and that !(A & B) == !A + !B. Take the first equation and negate both sides, and you end up with your example: A + B == !(!A & !B).

• It's worth noting that while any combinatorial expression can be realized using primitive gates, in many technologies there are expressions which occur pretty often and can be realized most efficiently using things other than primitive gates. For example, realizing an XOR function using primitive gates in CMOS would require twelve transistors (e.g. use for to compute !X and !Y, then eight to compute (X!Y or Y!X), but it's possible to build an XOR using eight. – supercat Nov 14 '12 at 17:09

Philosphical Logic 101 (aka Propositional Logic) and Digital Logic 101 are both based on Boolean Algebra.

In this example you have inverted both inputs and outputs around an AND gate which one of the basic reciprocal properties converting between AND and OR logic. In this case if either input is 1 the output is 1. or in other words, if both inputs are 0 the output is 0. (where 0 = low = false)

Example

• Let one input be = The Sun is shining
• Let the other input = I have a powered flashlight
• Therefore (assuming one's eyesight is OK and your Logic has power amd there are no other inputs etc.)
• the output = I can see =1 if either A or B is true =1
• The de Morgan Rule is thus I can NOT see if both A AND B are off (=NOT on)

http://en.wikipedia.org/wiki/Boolean_algebra#Basic_operations This will explain more.

What we call De Morgan's Laws are the same as Boolean Logic but with different symbology with some simplification. These were later converted by Veitch to Tables with graphical simplification using an intuititve circle mapping method to reduce complex logic with a simpler realization. However the graphical presentation was not as obvious to the reader in 1952 and in 1953 Karnaugh published the mapping methods used by Veitch and got credit for it until a few decades later. So Karnaugh-Veitch Maps ought to be the proper designation.

All of these Laws of Logic above and Propositional Logic are a subset of the original laws of Logic defined by Aristotle and later amended by Plato and simplified for the purpose of easier understanding. They start with the simple truths of OR, AND and NOT logic. Aristotle documented them but the other's adapted it to Set theory, Electronics design, and the rapid solving of Sudoku puzzles among other things.

The design of Exclusive OR gates, counters, adders, multiplexors and PGA's are all based on these laws with the addition of memory states.

FWIW Philosphical vs Religious Logic ( not )

Now there are beliefs that logic can be extended beyond Laws of proof to experience based results and some religions have called these as truths based on experience and not proof. Although it is fair to call this a belief, it cannot be proven based on Aristotalean Logic. Just beware they exist and you cannot debate this with them as they have different laws of logic. They attempt to "raise the strength of analogy to that of a first order Aristotelian syllogism" This would be like adding to the truth table an analogy and given that the same validity as a proven law which can lead to illogical results. Like adding a hidden term in the Gate saying the Output could also be 1 if one saw the Illuminous One and there was no sun or flashlight. It is only true if you believe it is true but beliefs are not logic as logic is based on proveable assumptions and simple infallible logic of AND, OR and NOT. However this does lead into an interesting topic of Fuzzy Logic which are Rules based on Experience.

It's just logic: think about it (or apply De Morgan's rules).

OR means that the output is true if any of the inputs is true, AND means that the output is true only if both inputs are true.

Now, if you negate both inputs of the AND, you'll have that the output is true only when both inputs are false, because their inverted copy will be true. In another way, if any of the inputs is true the output will be false. Invert this (the NOT at the output) and you get an OR.

Your confusion comes from a little misunderstanding: these gates cannot be made using only one of the other gates, which is not true for inverting gates like NAND or NOR.

A part on how port are implemented internally, it usually interesting have a circuit implemented with just one type of port, to avoid buying to many IC's. The trick you can apply to almost each combinatorial circuit to be wired with just NAND port is to negate the boolean expression twice ( negating twice obviously yield the same table) and applying the DeMorgan law:

NOT(NOT(A+B)) = NOT(NOT(a)*NOT(b))


same strategy apply even to more complex logics. This usually is not the case of internal IC's implementation, where designer are free to do what they want.