boolean algebra - build a OR gate as an NAND gate

Question

I am trying to wrap my mind around how to do this. For what i understand is that a set of logic gates is called "functionally complete" if some combination of the gates can be used to do each of the basic logic operations AND, OR, and NOT. The claim is the NAND gate is functionally complete.

What i dont understand is how to build a OR gate as a nand gate. build a AND gate from a NAND gate etc.. would the formula i come up with have to have the same output?

 X' = X NAND 1
 X + Y = ?
 X * Y = ?

using a truth table how is X' = X NAND 1?

I am not sure what X NAND 1 means.. I understand 1 is fixed as y?

I get confused when i see the gate inbetween 2 inputs like x NAND y

How can i construct a truth table for x+y = NAND?

or should i do it a different way?

Answer 1

Just go by definition:

X NAND Y = ~ (X AND Y) = ~X OR ~Y

Substitute Y = 1 and see you will get

X NAND 1 = ~X OR ~1 = ~X OR 0 = ~X = X'

Edit:

Just so that you get a sense on how to build other gates using NAND gate, this wikipedia article is very good and informative. Hope it helps.

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

Answer 2

Quick truth tables:

NAND 1 0
0    1 1
1    0 1

OR 1 0
0  1 0
1  1 1

NOT
1   0
0   1

What functionally complete means is that, given a pile of the complete gate, you can construct any other gate type.

So if you build a circuit with 1 NAND gate, you get exactly the opposite of an OR gate (inputs reversed). If your goal is to build the OR gate, you have to invert the inputs of the NAND gate. That's easy to do with a couple NOT gates (which is, if you look carefully, the same as a NAND gate with one of its inputs tied to logical 1). So you put those NOT gates before your NAND gate and voila, an OR gate falls out.

For your confusion, putting the gate between its two inputs is just using that gate as a binary operator, like a + sign. It's the same as saying NAND(X, 1) or "The output of the NAND gate when its inputs are X and 1."

Answer 3

Yes, X NAND 1 is like X NAND Y with Y fixed as 1. The thing you're comparing X with doesn't have to be called Y; it can be any variable, any constant or the result of another comparison. All that matters is whether the value is a 0 or a 1, in the end.

Example:

 X | Y | 1 | X OR Y
---+---+---+--------
 0 | 0 | 1 |    0
 0 | 1 | 1 |    1
 1 | 0 | 1 |    1
 1 | 1 | 1 |    1

Now you could do X AND Y, X AND 1 or X AND (X OR Y) just by comparing the numbers in the first column with numbers in the second, third or fourth columns, respectively.

As for NAND specifically, just remember that it means the opposite of AND. It actually stands for "not and." So if you ANDed two things together and got 0, then NANDing the same two things together would give you 1.

That said, your last question doesn't make much sense. There's no such thing as X+Y = NAND. X, Y and X+Y are values; NAND is a gate. You can't compare numbers to gates. Your question is asking you to use NAND gates to compare things over and over until you you get a column of zeroes and ones that looks the same as X+Y does.

EDIT:
Okay, let's look at your question "using a truth table how is X' = X NAND 1?"

 X | X' | 1 |   X AND 1   | X NAND 1 is the same as the opposite of X AND 1
---+----+---+-------------+-------------------------------------------------
 0 | 1  | 1 | 0 AND 1 = 0 |               1 (opposite of 0)
 0 | 1  | 1 | 0 AND 1 = 0 |               1 (opposite of 0)
 1 | 0  | 1 | 1 AND 1 = 1 |               0 (opposite of 1)
 1 | 0  | 1 | 1 AND 1 = 1 |               0 (opposite of 1)

And looking at each column, we can see that X' has the same values as X NAND 1

Answer 4

NAND is basically the reverse of AND:
Truth Table

A    B    A NAND B   A AND B   A OR B   A NOR B
0    0       1         0         o         1
0    1       1         0         1         0
1    0       1         0         1         0
1    1       0         1         1         0

By making the right combinations using these and the remaining boolean operators you should be able to construct any one in terms of the others