X | Y | X∧Y | X∨Y | X NAND Y | X NOR Y | |
---|---|---|---|---|---|---|

F | F | F | F | T | T | |

F | T | F | T | T | F | |

T | F | F | T | T | F | |

T | T | T | T | F | F |

You can show that two functions are equivalent by showing that they have the same output as each other for every possible combination of inputs. Here's a simple example to show that ¬X = X NAND X.

X | ¬X | X NAND X | |
---|---|---|---|

F | T | T | |

T | F | F |

If you're not sure what one of the outputs should be, plug in the input values and evaluate it. F NAND F = T, and T NAND T = F, which you can see from the first truth table.

So, here's the solution to the first part of the challenge: X∨Y = (X NAND X) NAND (Y NAND). Here's the truth table.

X | Y | X NAND X | Y NAND Y | (X NAND X) NAND (Y NAND Y) | |
---|---|---|---|---|---|

F | F | F NAND F = T | F NAND F = T | T NAND T = F | |

F | T | F NAND F = T | T NAND T = F | T NAND F = T | |

T | F | T NAND T = F | F NAND F = T | F NAND T = T | |

T | T | T NAND T = F | T NAND T = F | F NAND F = T |

Try to figure out the second part of the challenge (That is replicate the AND function using only NOR) using a truth table now. I'll wait.

.

.

.

.

.

.

.

.

The solution to the second part is X∧Y = (X NOR X) NOR (Y NOR Y). Interestingly, it's exactly the same as the first part, except with ∨ replaced by ∧ and NAND replaced by NOR. I'll talk about that more in a bit, but first notice that since (X NAND X) = ¬X, the solution to the first part can be rewritten as X∨Y = ¬X NAND ¬Y. Also, since (X NAND Y) = ¬(X∧Y), it can be further changed to X∨Y = ¬(¬X∧¬Y). The same way, the solution to the second part can be rewritten as X∧Y = ¬(¬X∨¬Y).

This is an example of De Morgan's Law, which says that ¬(X∧Y) = ¬X∨¬Y and ¬(X∨Y) = ¬X∧¬Y. De Morgan's Law is a very important thing to remember when doing Boolean algebra. It's a useful way of simplifying expressions, and it's vital for programmers to know.

De Morgan's Law also ties back into the other point I made. Notice that the two forms of De Morgan's Law are the same, except with ∧ and ∨ swapped? In fact, you can take any boolean expression, swap ∧ and ∨, and swap T and F, and the expression will mean the same thing.* For example, X∧T=X, swapped X∨F=X. Also, X∧F=F, swapped X∨T=T. This property is called duality.

Why does this happen? Keep in mind that the labels we use are arbitrary. It doesn't matter if we use T and F or 1 and 0, or if we use ∧ and ∨ or AND and OR. What matters is the relationships that hold between the symbols. And the way we've defined them, the relationships between T and ∧ are exactly the same as the relationships between F and ∨. That is, X AND Y is true if and only if both X and Y are true. X OR Y is false if and only if both X and Y are false. Those say exactly the same things, just with the names changed.

*If the expression contains XOR, or other functions besides ∧, ∨ and ¬, those need to be rewritten to use only ∧, ∨ and ¬. Or they can be swapped with their own dual, for example, the dual of XOR is XNOR. ¬ is it's own dual.

## No comments:

## Post a Comment