Number System and Conversion; Boolean Logic

Boolean Function and Basic Gates

A Boolean function is an algebraic expression formed from binary variables and the operations AND (·), OR (+) and NOT ('), whose value is either 0 or 1. For example, $F(A,B,C) = AB + C'$. It can be represented by a truth table, a Boolean expression or a logic circuit.

A Boolean function with $n$ variables has $2^n$ rows in its truth table.

Basic gates

The basic gates are AND, OR and NOT; any Boolean function can be implemented with them.

AND gate

Boolean expression: $X = A \cdot B$

Output is 1 only when all inputs are 1.

Logic symbol

 A ──┐
    │D──── X = A·B
 B ──┘

Truth table

OR gate

Boolean expression: $X = A + B$

Output is 1 when at least one input is 1.

Logic symbol

 A ──┐
    )>──── X = A+B
 B ──┘

Truth table

NOT gate (inverter)

Boolean expression: $X = A'$ or $\bar{A}$

Output is the complement of the single input.

Logic symbol

 A ──▷o── X = A'

Truth table

Example: $F = AB + C'$ is built using one AND gate for $AB$, one NOT gate for $C'$ and one OR gate to combine them.

Decimal to Binary Conversion

The decimal number system uses base 10 (digits 0–9), while the binary number system uses base 2 (digits 0 and 1). To convert a decimal number to its binary equivalent, we repeatedly divide the decimal number by 2 and record the remainders. The binary number is then obtained by reading these remainders from bottom to top (i.e., from the last remainder to the first). This method is called the division-by-2 method or remainder method.

Steps

1. Divide the decimal number by 2.
2. Write down the remainder (0 or 1) to the right.
3. Divide the quotient again by 2.
4. Repeat steps 2 and 3 until the quotient becomes 0.
5. Arrange all the remainders in reverse order (last remainder first). This gives the binary equivalent.

Example: Convert $(25)_{10}$ to binary

Reading the remainders from bottom to top:

$(25)_{10} = (11001)_2$

Verification

$1 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 16 + 8 + 0 + 0 + 1 = 25$

Hence the conversion is correct. The same method works for any decimal integer, and for fractional parts a separate multiply-by-2 method is used.

AND, OR, XOR and XNOR Gates

1. AND Gate

The AND gate gives output 1 only when all its inputs are 1. It performs logical multiplication, so $Y = A \cdot B$.

Symbol:

        ____
A -----|    |
       | &  |------ Y
B -----|____|

Truth Table:

Boolean expression: $Y = A \cdot B$

---

2. OR Gate

The OR gate gives output 1 when any one or both of its inputs are 1. It performs logical addition, so $Y = A + B$.

Symbol:

        ____
A -----|    |
       | ≥1 |------ Y
B -----|____|

Truth Table:

Boolean expression: $Y = A + B$

---

3. XOR Gate (Exclusive OR)

The XOR gate gives output 1 only when the inputs are different (one is 0 and the other is 1). It is denoted by $Y = A \oplus B$.

Symbol:

        ____
A -----|    |
       | =1 |------ Y
B -----|____|

Truth Table:

Boolean expression: $Y = A \oplus B = A'B + AB'$

---

4. XNOR Gate (Exclusive NOR)

The XNOR gate gives output 1 only when the inputs are the same (both 0 or both 1). It is the complement of XOR, so $Y = \overline{A \oplus B}$.

Symbol:

        ____
A -----|    |
       | =1 |o----- Y
B -----|____|

Truth Table:

Boolean expression: $Y = \overline{A \oplus B} = A'B' + AB$

---

Summary Table

Key points:

• AND → output 1 when all inputs are 1
• OR → output 1 when at least one input is 1
• XOR → output 1 when inputs are different
• XNOR → output 1 when inputs are same (XOR followed by NOT)

OR, NAND, NOR and XNOR Gates

A logic gate is a digital circuit whose output depends on the logical combination of its binary inputs.

OR gate

Boolean expression: $X = A + B$

Output is 1 when at least one input is 1.

Logic symbol

 A ──┐
    )>──── X = A+B
 B ──┘

Truth table

NAND gate

Boolean expression: $X = (A \cdot B)'$

Output is 0 only when all inputs are 1; it is an AND gate followed by a NOT gate.

Logic symbol

 A ──┐
    │D o── X = (A·B)'
 B ──┘

Truth table

NOR gate

Boolean expression: $X = (A + B)'$

Output is 1 only when all inputs are 0; it is an OR gate followed by a NOT gate.

Logic symbol

 A ──┐
    )>o── X = (A+B)'
 B ──┘

Truth table

XNOR (exclusive-NOR) gate

Boolean expression: $X = (A \oplus B)' = AB + A'B'$

Output is 1 when the inputs are the same; it is an XOR gate followed by NOT.

Logic symbol

 A ──┐
    =)>o── X = (A⊕B)'
 B ──┘

Truth table

Hexadecimal to binary conversion. Since $16 = 2^4$, every hexadecimal digit is replaced by its equivalent 4-bit binary group, and the groups are written together in the same order.

Steps

1. Write each hex digit separately.
2. Replace each digit with its 4-bit binary value (0 = 0000, 1 = 0001, ..., 9 = 1001, A = 1010, B = 1011, C = 1100, D = 1101, E = 1110, F = 1111).
3. Join the groups (leading zeros of the first group may be dropped).

Example: convert $(2F9)_{16}$ to binary

$(2F9)_{16} = (001011111001)_2 = (1011111001)_2$

Check: $2\times256 + 15\times16 + 9 = 761$, and $1011111001_2 = 512+128+64+32+16+8+1 = 761$.

Binary subtraction using 2's complement. To subtract $B$ from $A$, find the 2's complement of $B$ and add it to $A$. If a carry is produced, discard it; the remaining bits are the positive answer. If there is no carry, the answer is negative and equals the 2's complement of the result.

Steps

1. Make both numbers the same number of bits.
2. Find the 1's complement of the subtrahend (change 0 to 1 and 1 to 0).
3. Add 1 to get the 2's complement.
4. Add it to the minuend.
5. Discard the carry (if any).

Example: $1010_2 - 0110_2$ (that is, $10 - 6$)

• 1's complement of $0110$ = $1001$
• 2's complement = $1001 + 1 = 1010$
• Add: $1010 + 1010 = 1\,0100$
• Discard the carry: result $= 0100$

$1010_2 - 0110_2 = 0100_2 = 4_{10}$

Check: $10 - 6 = 4$.

The binary number system is the base-2 positional system. It uses only two digits, 0 and 1 (bits). Computers use it because electronic circuits easily represent two states (off/on).

(a) Convert each hex digit to 4 bits, then regroup into 3-bit groups for octal.

$D=1101,\ A=1010,\ D=1101$, so $(DAD)_{16} = 1101\,1010\,1101_2 = 110\,110\,101\,101_2$.

Groups: $110=6,\ 110=6,\ 101=5,\ 101=5$.

$(DAD)_{16} = (6655)_8$

(b) $(1111)_2 - (1010)_2$ means $15 - 10$.

1's complement method (Morning): 1's complement of $1010$ is $0101$. Add: $1111 + 0101 = 1\,0100$. The carry 1 is added back to the sum (end-around carry): $0100 + 1 = 0101$.

2's complement method (Day): 2's complement of $1010$ is $0101 + 1 = 0110$. Add: $1111 + 0110 = 1\,0101$. The carry is discarded, leaving $0101$.

Either way the result is $(0101)_2 = 5$.

(b) $x$

By the idempotent law of Boolean algebra, $x + x = x$. Since a variable is either 0 or 1, $0+0=0$ and $1+1=1$ (OR, not arithmetic addition).

(a) 1

By the null (domination) law, $A + 1 = 1$. If either input of an OR is 1, the output is 1 whatever $A$ is.

(a) multiplication operation

An AND gate gives the Boolean product of its inputs, $Y = A\cdot B$, so its output is 1 only when all inputs are 1.

(c) Both a and b

When all inputs are 1, an AND gate gives 1 and an OR gate also gives 1 (OR is high when at least one input is high).

AND, OR and NOT Using NAND Gates Only

NAND is a universal gate, because $X = (AB)'$ can be used to build every other gate.

1. NOT gate. Join both inputs of a NAND gate together:

$X = (A \cdot A)' = A'$

 A ──┬──┐
     │  │D o── X = A'
     └──┘

2. AND gate. NAND followed by a NAND used as NOT (2 gates):

$X = ((AB)')' = AB$

 A ──┐
     │D o──┬──┐
 B ──┘     │  │D o── X = AB
           └──┘

3. OR gate. Invert each input with a NAND-NOT, then feed to a NAND (3 gates):

$X = (A' \cdot B')' = A + B \quad \text{(De Morgan's theorem)}$

 A ──┬──┐
     └──┘D o──┐
              │D o── X = A+B
 B ──┬──┐D o──┘
     └──┘

Truth-table check for OR: for $A=0,B=0$: $A'=1,B'=1$, $(1\cdot1)'=0$; for $A=1,B=0$: $(0\cdot1)'=1$, matching $A+B$.

AND, OR and NOT Using NOR Gates Only

NOR is a universal gate, because $X = (A+B)'$ can be used to build every other gate.

1. NOT gate. Join both inputs of a NOR gate together:

$X = (A + A)' = A'$

 A ──┬──┐
     │  )>o── X = A'
     └──┘

2. OR gate. NOR followed by a NOR used as NOT (2 gates):

$X = ((A+B)')' = A + B$

 A ──┐
     )>o──┬──┐
 B ──┘    │  )>o── X = A+B
          └──┘

3. AND gate. Invert each input with a NOR-NOT, then feed to a NOR (3 gates):

$X = (A' + B')' = A \cdot B \quad \text{(De Morgan's theorem)}$

 A ──┬──┐
     └──)>o──┐
              )>o── X = AB
 B ──┬──┐ ┌───┘
     └──)>o┘

Check for AND: $A=1,B=1$: $A'=B'=0$, $(0+0)'=1 = AB$. For $A=1,B=0$: $(0+1)'=0 = AB$.

Boolean Algebra, AND and NAND Gates

Boolean algebra is the algebra of two-valued variables (0 and 1) that uses the operations AND, OR and NOT. It is used to analyse, simplify and design digital circuits.

AND gate

Boolean expression: $X = A \cdot B$

Output is 1 only when all inputs are 1.

Logic symbol

 A ──┐
    │D──── X = A·B
 B ──┘

Truth table

Venn diagram: Only the overlapping region of the two circles A and B (the intersection $A \cap B$) is shaded.

NAND gate

Boolean expression: $X = (A \cdot B)'$

Output is 0 only when all inputs are 1; it is an AND gate followed by a NOT gate.

Logic symbol

 A ──┐
    │D o── X = (A·B)'
 B ──┘

Truth table

Venn diagram: The whole rectangle except the overlap of A and B is shaded, i.e. $(A \cap B)'$.

De Morgan's Theorem

Statement.

1. The complement of a product equals the sum of the complements: $(A \cdot B)' = A' + B'$
2. The complement of a sum equals the product of the complements: $(A + B)' = A' \cdot B'$

Proof by truth table (for the first law and the second law)

The columns $(A \cdot B)'$ and $A' + B'$ are identical in every row, and so are $(A+B)'$ and $A' \cdot B'$. Hence both laws are proved.

In general, De Morgan's theorem lets us change AND to OR (and OR to AND) by complementing every variable and the whole expression.

To convert a decimal integer to binary, divide repeatedly by 2 and note the remainders. The binary number is the remainders read from bottom to top.

Reading the remainders from the last to the first:

$(513)_{10} = (1000000001)_2$

Check: $2^9 + 2^0 = 512 + 1 = 513$.

Logic Gate and the Basic Gates

Definition. A logic gate is a basic digital circuit that has one or more inputs and a single output, and performs a logical operation (AND, OR, NOT, etc.) on binary inputs (0 and 1). Logic gates are the building blocks of all digital circuits.

The three basic gates are AND, OR and NOT.

AND gate

Boolean expression: $X = A \cdot B$

Output is 1 only when all inputs are 1.

Logic symbol

 A ──┐
    │D──── X = A·B
 B ──┘

Truth table

OR gate

Boolean expression: $X = A + B$

Output is 1 when at least one input is 1.

Logic symbol

 A ──┐
    )>──── X = A+B
 B ──┘

Truth table

NOT gate (inverter)

Boolean expression: $X = A'$ or $\bar{A}$

Output is the complement of the single input.

Logic symbol

 A ──▷o── X = A'

Truth table

Logic Gate, AND, NOT and X-OR

Logic gate: A logic gate is a basic digital circuit that has one or more inputs and a single output, and performs a logical operation (AND, OR, NOT, etc.) on binary inputs (0 and 1). Logic gates are the building blocks of all digital circuits.

AND gate

Boolean expression: $X = A \cdot B$

Output is 1 only when all inputs are 1.

Logic symbol

 A ──┐
    │D──── X = A·B
 B ──┘

Truth table

NOT gate (inverter)

Boolean expression: $X = A'$ or $\bar{A}$

Output is the complement of the single input.

Logic symbol

 A ──▷o── X = A'

Truth table

XOR (exclusive-OR) gate

Boolean expression: $X = A \oplus B = A'B + AB'$

Output is 1 when the inputs are different.

Logic symbol

 A ──┐
    =)>── X = A⊕B
 B ──┘

Truth table

Logic Gate, NAND, NOT and X-NOR

Logic gate: A logic gate is a basic digital circuit that has one or more inputs and a single output, and performs a logical operation (AND, OR, NOT, etc.) on binary inputs (0 and 1). Logic gates are the building blocks of all digital circuits.

NAND gate

Boolean expression: $X = (A \cdot B)'$

Output is 0 only when all inputs are 1; it is an AND gate followed by a NOT gate.

Logic symbol

 A ──┐
    │D o── X = (A·B)'
 B ──┘

Truth table

NOT gate (inverter)

Boolean expression: $X = A'$ or $\bar{A}$

Output is the complement of the single input.

Logic symbol

 A ──▷o── X = A'

Truth table

XNOR (exclusive-NOR) gate

Boolean expression: $X = (A \oplus B)' = AB + A'B'$

Output is 1 when the inputs are the same; it is an XOR gate followed by NOT.

Logic symbol

 A ──┐
    =)>o── X = (A⊕B)'
 B ──┘

Truth table

Logic Gate, XOR, XNOR and OR

Logic gate: A logic gate is a basic digital circuit that has one or more inputs and a single output, and performs a logical operation (AND, OR, NOT, etc.) on binary inputs (0 and 1). Logic gates are the building blocks of all digital circuits.

XOR (exclusive-OR) gate

Boolean expression: $X = A \oplus B = A'B + AB'$

Output is 1 when the inputs are different.

Logic symbol

 A ──┐
    =)>── X = A⊕B
 B ──┘

Truth table

XNOR (exclusive-NOR) gate

Boolean expression: $X = (A \oplus B)' = AB + A'B'$

Output is 1 when the inputs are the same; it is an XOR gate followed by NOT.

Logic symbol

 A ──┐
    =)>o── X = (A⊕B)'
 B ──┘

Truth table

OR gate

Boolean expression: $X = A + B$

Output is 1 when at least one input is 1.

Logic symbol

 A ──┐
    )>──── X = A+B
 B ──┘

Truth table

Boolean Algebra, NOT, NAND and NOR Gates

Boolean algebra is the branch of algebra introduced by George Boole in which variables take only two values, 1 (true) and 0 (false), and are combined using the operations AND, OR and NOT. It is the mathematical basis for designing and simplifying digital logic circuits.

NOT gate (inverter)

Boolean expression: $X = A'$ or $\bar{A}$

Output is the complement of the single input.

Logic symbol

 A ──▷o── X = A'

Truth table

NAND gate

Boolean expression: $X = (A \cdot B)'$

Output is 0 only when all inputs are 1; it is an AND gate followed by a NOT gate.

Logic symbol

 A ──┐
    │D o── X = (A·B)'
 B ──┘

Truth table

NOR gate

Boolean expression: $X = (A + B)'$

Output is 1 only when all inputs are 0; it is an OR gate followed by a NOT gate.

Logic symbol

 A ──┐
    )>o── X = (A+B)'
 B ──┘

Truth table

Note: NAND and NOR are called universal gates because any other gate or Boolean function can be built using only NAND gates or only NOR gates.

Logic Function, X-OR, X-NOR and NOR Gates

Logic function. A logic function (Boolean function) is an expression made of binary variables joined by the logical operations AND, OR and NOT, e.g. $F = AB + C'$. For every combination of input values it gives an output of 0 or 1, and it can be shown by a truth table and implemented with logic gates.

XOR (exclusive-OR) gate

Boolean expression: $X = A \oplus B = A'B + AB'$

Output is 1 when the inputs are different.

Logic symbol

 A ──┐
    =)>── X = A⊕B
 B ──┘

Truth table

XNOR (exclusive-NOR) gate

Boolean expression: $X = (A \oplus B)' = AB + A'B'$

Output is 1 when the inputs are the same; it is an XOR gate followed by NOT.

Logic symbol

 A ──┐
    =)>o── X = (A⊕B)'
 B ──┘

Truth table

NOR gate

Boolean expression: $X = (A + B)'$

Output is 1 only when all inputs are 0; it is an OR gate followed by a NOT gate.

Logic symbol

 A ──┐
    )>o── X = (A+B)'
 B ──┘

Truth table

Four Logic Gates

Four commonly used gates are explained below with symbol, Boolean expression, truth table and Venn diagram.

AND gate

Boolean expression: $X = A \cdot B$

Output is 1 only when all inputs are 1.

Logic symbol

 A ──┐
    │D──── X = A·B
 B ──┘

Truth table

Venn diagram: Only the overlapping region of the two circles A and B (the intersection $A \cap B$) is shaded.

OR gate

Boolean expression: $X = A + B$

Output is 1 when at least one input is 1.

Logic symbol

 A ──┐
    )>──── X = A+B
 B ──┘

Truth table

Venn diagram: Both circles A and B (the union $A \cup B$) are fully shaded.

NOT gate (inverter)

Boolean expression: $X = A'$ or $\bar{A}$

Output is the complement of the single input.

Logic symbol

 A ──▷o── X = A'

Truth table

Venn diagram: Everything outside circle A (inside the universal rectangle) is shaded.

NAND gate

Boolean expression: $X = (A \cdot B)'$

Output is 0 only when all inputs are 1; it is an AND gate followed by a NOT gate.

Logic symbol

 A ──┐
    │D o── X = (A·B)'
 B ──┘

Truth table

Venn diagram: The whole rectangle except the overlap of A and B is shaded, i.e. $(A \cap B)'$.

Distributive Law of Boolean Algebra

Statement. Boolean algebra has two distributive laws:

1. AND distributes over OR: $A(B + C) = AB + AC$
2. OR distributes over AND: $A + BC = (A + B)(A + C)$

Proof of law 1 by truth table

The columns $A(B+C)$ and $AB+AC$ are identical, so law 1 is proved.

Proof of law 2 algebraically

$(A+B)(A+C) = AA + AC + AB + BC = A + AC + AB + BC$ $= A(1 + C + B) + BC = A \cdot 1 + BC = A + BC$

Hence $A + BC = (A+B)(A+C)$.

Two Boolean laws

• Commutative law: $A + B = B + A$ and $AB = BA$
• De Morgan's law: $(AB)' = A' + B'$ (others: associative, distributive, identity, complement, absorption)

Truth table of $F = AB + B'$

Digital diagram

 A ──┐
     │D──── AB ──┐
 B ──┤           )>── F = AB + B'
     │           │
     └──▷o── B' ─┘

An AND gate gives $AB$, a NOT gate gives $B'$, and an OR gate combines them. (It simplifies to $A + B'$, which has the same truth table.)

Truth table. A truth table lists all possible combinations of input values of a logic circuit/expression together with the corresponding output.

Boolean function. A Boolean function is an expression of binary variables joined by AND, OR and NOT, which gives output 0 or 1.

Simplification of $F = (X+Y)(XY'Z + XYZ + XY'Z')$

Take the second bracket first:

$XY'Z + XYZ = XZ(Y' + Y) = XZ$ $XZ + XY'Z' = X(Z + Y'Z') = X(Z + Y')$

since $Z + Y'Z' = Z + Y'$. Now

$F = (X+Y)\cdot X(Y' + Z) = X(Y'+Z) \quad [\because (X+Y)X = X]$

$\boxed{F = XY' + XZ}$

Digital diagram

 Y ──▷o── Y' ──┐
               │D──── XY' ──┐
 X ──┬─────────┘            )>── F
     │                      │
     └──┐                   │
        │D──── XZ ──────────┘
 Z ─────┘

(Equivalent form: OR gate for $Y'+Z$, then AND with $X$.)

Truth table of the simplified expression $F = X(Y'+Z)$

Simplification of $F = PQR + QR + R'$

$PQR + QR = QR(P + 1) = QR$

$F = QR + R' = Q + R' \quad [\because R' + QR = R' + Q]$

$\boxed{F = Q + R'}$

Digital circuit

 R ──▷o── R' ──┐
               )>── F = Q + R'
 Q ────────────┘

Only one NOT gate and one OR gate are needed, instead of the original two AND gates, one NOT gate and an OR gate.

Check: for $Q=0,R=1$: original $= 0+0+0 = 0$; simplified $= 0+0 = 0$. For $Q=0,R=0$: original $= 1$; simplified $= 1$.

Operations used in Boolean algebra: OR (logical addition, $+$), AND (logical multiplication, $\cdot$) and NOT (complement, $'$).

AND operation (logical multiplication). The result is 1 only when all operands are 1; otherwise it is 0. It is written $X = A \cdot B$ and is implemented by the AND gate.

For example, a lamp in series with two switches glows only when both switches are closed.

Hexadecimal number system. It is a positional number system with base 16. It uses sixteen symbols: 0 to 9 and A, B, C, D, E, F, where A = 10, B = 11, C = 12, D = 13, E = 14, F = 15. Each hexadecimal digit equals four binary bits, so it is used as a short form of binary.

Decimal to octal conversion. Divide the integer part repeatedly by 8 and note the remainders until the quotient becomes 0; read the remainders from bottom to top. For the fractional part, multiply repeatedly by 8 and note the integer parts from top to bottom.

Example: convert $(156)_{10}$ to octal

Reading upward: $(156)_{10} = (234)_8$.

Check: $2\times 8^2 + 3\times 8 + 4 = 128 + 24 + 4 = 156$.

Binary number system. It is a positional number system with base 2 that uses only two digits, 0 and 1. Each digit is a bit, and the place values are powers of 2. Computers use it because digital circuits have two states (on/off).

Steps for decimal to octal conversion

1. Divide the decimal number by 8.
2. Write the remainder (0 to 7).
3. Divide the quotient again by 8 and repeat until the quotient is 0.
4. Write the remainders in reverse order (last remainder first).

Example: convert $(125)_{10}$ to octal

Reading from bottom to top: $(125)_{10} = (175)_8$.

Check: $1\times 64 + 7\times 8 + 5 = 125$.

Decimal number system. It is a positional number system with base 10 that uses ten digits, 0 to 9. The place values are powers of 10 (units, tens, hundreds, ...). It is the system used in everyday life.

(a) Convert $(213.112)_{10}$ to binary

Integer part (divide by 2):

Reading upward: $(213)_{10} = (11010101)_2$.

Fractional part (multiply by 2):

Reading downward: $(0.112)_{10} \approx (0.00011100)_2$ (the fraction does not end exactly, so it is taken to 8 places).

$(213.112)_{10} \approx (11010101.00011100)_2$

(b) Subtract $110$ from $1101$ using 2's complement

Make both 4 bits: $1101 - 0110$.

• 1's complement of $0110$ = $1001$
• 2's complement = $1001 + 1 = 1010$
• Add: $1101 + 1010 = 1\,0111$
• Discard the carry: $0111$

$1101_2 - 110_2 = 111_2$

Check: $13 - 6 = 7 = 111_2$.

The hexadecimal number system is a positional number system with base 16. It uses sixteen symbols: the digits 0-9 and the letters A-F (A = 10, B = 11, C = 12, D = 13, E = 14, F = 15). Each digit has a place value that is a power of 16.

(a) Multiply each digit by its place value (powers of 16), using positive powers for the integer part and negative powers for the fractional part.

$(FACE)_{16} = 15\times16^3 + 10\times16^2 + 12\times16^1 + 14\times16^0 = 61440 + 2560 + 192 + 14 = 64206$

$(.CAFE)_{16} = 12\times16^{-1} + 10\times16^{-2} + 15\times16^{-3} + 14\times16^{-4} = 0.75 + 0.0390625 + 0.003662 + 0.000214 \approx 0.792938$

So $(FACE.CAFE)_{16} \approx (64206.792938)_{10}$.

(b) $(1001)_2 - (1010)_2$ means $9 - 10$. Use 4 bits.

• 2's complement of $1010$: 1's complement is $0101$, add 1 to get $0110$.
• Add: $1001 + 0110 = 1111$.
• There is no carry out, so the result is negative. Its magnitude is the 2's complement of $1111$: $0000 + 1 = 0001$.

Result: $-(0001)_2 = -1$, which agrees with $9-10=-1$.

The denary (decimal) number system is the base-10 positional system. It uses ten digits 0-9, and each digit's place value is a power of 10. It is the number system we use in daily life.

(a) Using place values as powers of 16 (A = 10, F = 15, B = 11):

$(3A2F)_{16} = 3\times16^3 + 10\times16^2 + 2\times16^1 + 15\times16^0 = 12288 + 2560 + 32 + 15 = 14895$

$(.4B)_{16} = 4\times16^{-1} + 11\times16^{-2} = 0.25 + 0.04296875 = 0.29296875$

So $(3A2F.4B)_{16} = (14895.29296875)_{10}$.

(b) $(101)_2 - (1111)_2$ means $5 - 15$. Use 4 bits, so the numbers are $0101$ and $1111$.

• 1's complement of $1111$ is $0000$.
• Add: $0101 + 0000 = 0101$.
• There is no end-around carry, so the answer is negative. Take the 1's complement of the sum: $1010$.

Result: $-(1010)_2 = -10$, which agrees with $5-15=-10$.

The octal number system is a positional number system with base 8. It uses the eight digits 0 to 7, and each place value is a power of 8. One octal digit represents exactly three binary bits.

(a) With B = 11, A = 10, E = 14:

$(BAE)_{16} = 11\times16^2 + 10\times16^1 + 14\times16^0 = 2816 + 160 + 14 = 2990$

$(.52)_{16} = 5\times16^{-1} + 2\times16^{-2} = 0.3125 + 0.0078125 = 0.3203125$

So $(BAE.52)_{16} = (2990.3203125)_{10}$.

(b) $(1010)_2 - (1101)_2$ means $10 - 13$.

• 1's complement of $1101$ is $0010$.
• Add: $1010 + 0010 = 1100$.
• There is no carry out, so the result is negative. Take the 1's complement of $1100$: $0011$.

Result: $-(0011)_2 = -3$, which agrees with $10-13=-3$.

(a) Replace each hex digit by its 4-bit binary: $A = 1010$, $B = 1011$, $C = 1100$.

$(ABC)_{16} = (1010\,1011\,1100)_2$

(b) Multiply each digit by a power of 8:

$(2040)_8 = 2\times8^3 + 0\times8^2 + 4\times8^1 + 0\times8^0 = 1024 + 0 + 32 + 0 = 1056$

So $(2040)_8 = (1056)_{10}$.

(c) $1100 - 1111$ means $12 - 15$. Use 4 bits.

• 2's complement of $1111$: 1's complement is $0000$, add 1 to get $0001$.
• Add: $1100 + 0001 = 1101$.
• There is no carry, so the result is negative. Its magnitude is the 2's complement of $1101$: $0010 + 1 = 0011$.

Result: $-(0011)_2 = -3$.

The octal number system is a base-8 positional system that uses the digits 0 to 7. Each octal digit equals three binary bits, which makes it a compact way to write binary numbers.

(a) Convert octal to binary (3 bits per digit), then regroup in 4 bits for hexadecimal.

$3=011,\ 4=100,\ 2=010$, so $(342)_8 = 011\,100\,010_2 = 1110\,0010_2$.

$1110 = E$ and $0010 = 2$, so

$(342)_8 = (E2)_{16}$

Check: $3\times64 + 4\times8 + 2 = 226 = 14\times16 + 2$.

(b) $(111)_2 - (101)_2$ means $7 - 5$. Use 3 bits.

• 1's complement of $101$ is $010$; adding 1 gives the 2's complement $011$.
• Add: $111 + 011 = 1\,010$.
• The carry is discarded, so the result is $010$.

Result: $(10)_2 = 2$.

The decimal number system is the base-10 positional number system. It uses the ten digits 0 to 9, and the place value of each digit is a power of 10.

Steps of binary subtraction using 2's complement ($A - B$):

1. Write both numbers with the same number of bits (add leading zeros if needed).
2. Find the 1's complement of the subtrahend $B$ by changing every 0 to 1 and every 1 to 0.
3. Add 1 to get the 2's complement of $B$.
4. Add this 2's complement to the minuend $A$.
5. If a carry is produced, discard it. The remaining bits are the answer, and it is positive.
6. If there is no carry, the answer is negative. Take the 2's complement of the sum to get its magnitude and put a minus sign in front.

Example: $(1101)_2 - (0101)_2$, that is $13 - 5$.

• 1's complement of $0101$ is $1010$.
• Add 1: $1010 + 1 = 1011$ (2's complement).
• Add to the minuend: $1101 + 1011 = 1\,1000$.
• Discard the carry: the result is $(1000)_2 = 8$.

This agrees with $13 - 5 = 8$.

(a) 173

Divide by 8: $123 \div 8 = 15$ remainder 3; $15 \div 8 = 1$ remainder 7; $1 \div 8 = 0$ remainder 1. Reading upwards gives $(173)_8$. Check: $64 + 56 + 3 = 123$.

(b) 0010

The 1's complement is found by flipping every bit: 1101 becomes 0010.

(c) 1011

The 1's complement of 0101 is 1010. Adding 1 gives 1011, the 2's complement.

(b) 0001 0011

In BCD each decimal digit is written as its own 4-bit binary number: 1 is 0001 and 3 is 0011.

(c) 1010

$10 = 8 + 2 = 1\times2^3 + 0\times2^2 + 1\times2^1 + 0\times2^0$, so the binary is 1010.

(c) 678

Octal uses only the digits 0 to 7. The number 678 contains the digit 8, so it is not an octal number.

(c) $(A+B)+C = A+(B+C)$

The associative law says the grouping of variables does not change the result. Option (a) is the commutative law, (b) is the absorption law and (d) is the distributive law.

(d) $(x.0)+z$

The dual is found by swapping + with . and 0 with 1, leaving the variables unchanged. So $(x+1).z$ becomes $(x.0)+z$.