Logic Gates and Binary Systems
Basic Logic Gates
Logic gates perform basic logical functions in digital circuits. Each gate has a truth table that defines its output for every possible input combination.
| Gate | Symbol | Logic Equation | Description |
|---|---|---|---|
| AND | ∧ | A·B | Output is 1 only if both inputs are 1 |
| OR | ∨ | A+B | Output is 1 if any input is 1 |
| NOT | ¬ | ¬A | Inverts the input value |
| XOR | ⊕ | A ⊕ B = (A·¬B) + (¬A·B) | Output is 1 if the inputs differ |
| NAND | ↑ | ¬(A·B) | Inverse of AND |
| NOR | ↓ | ¬(A+B) | Inverse of OR |
De Morgan's Laws
De Morgan's laws express the relationship between AND, OR, and NOT:
- ¬(A·B) = ¬A + ¬B
- ¬(A+B) = ¬A · ¬B
These allow transforming between AND-OR expressions and are crucial for simplifying logical expressions and designing efficient circuits.
Pushing a bubbled input through a gate swaps AND for OR (and back).
Example
Expression simplification:
¬(A + B·C) = ¬A · ¬(B·C) = ¬A · (¬B + ¬C)
Universal Gates
NAND and NOR are called universal gates because any other gate can be built using only one of them.
NAND Gate as Universal
- NOT: A NAND A = ¬A
- AND: (A NAND B) NAND (A NAND B) = A·B
- OR: (A NAND A) NAND (B NAND B) = A + B
NOR Gate as Universal
- NOT: A NOR A = ¬A
- OR: (A NOR B) NOR (A NOR B) = A + B
- AND: (A NOR A) NOR (B NOR B) = A·B
Why NAND is Preferable
- NAND gates are physically easier and cheaper to implement using CMOS technology
- Faster switching times and lower power consumption
- Simplifies integrated circuit design because NAND alone can represent all logic operations
Two's Complement and Binary Representation
Two's complement is the standard method for representing signed integers in binary.
How It Works
- Positive numbers: regular binary
- Negative numbers: invert all bits (one's complement) and add 1
Example for 8-bit representation:
- +15 →
0000 1111 - -15 → invert →
1111 0000→ add 1 →1111 0001
Why Add 1
Adding 1 after inversion gives a single unique representation for zero and lets binary addition work correctly for both positive and negative numbers.
Example:
0000 1111 (+15)
+ 1111 0001 (-15)
--------------
0000 0000 (0)Glossary
Bubbled Input
A gate input drawn with a small circle instead of a plain line indicates that the input is inverted before the gate's logic is applied. An OR gate with bubbled inputs computes ¬A + ¬B instead of A + B. By De Morgan's law, this is equivalent to ¬(A · B), so an OR gate with bubbled inputs implements the same logic as a NAND gate.