Number System and Boolean Logic

Inside a computer there are only two voltages, so there are only two symbols: 0 and 1. Everything else — your name, a photograph, a song, this sentence — is a pattern of those two symbols. This unit teaches you to move between the number systems people use and the one machines use, to do arithmetic in binary, and then to describe and simplify the switching circuits that carry out that arithmetic. It is the most mechanical unit in the course: almost every mark is earned by applying a procedure correctly, so practise until the procedures are automatic.

2.1 Decimal, Binary, Octal and Hexadecimal number systems and conversion

A number system is a way of writing numbers using a fixed set of symbols. The number of distinct symbols is the base (or radix) r. All four systems in the syllabus are positional: the value of a digit depends on where it stands.

In hexadecimal A = 10, B = 11, C = 12, D = 13, E = 14, F = 15.

Any base → decimal: positional expansion

Multiply each digit by the base raised to its position weight and add.

Fractions use negative powers: (11011.101)_2 = 16+8+2+1 + \frac12 + \frac18 = 27.625.

Decimal → any base: repeated division and multiplication

For the integer part, divide repeatedly by the base and read the remainders bottom to top. For the fraction part, multiply repeatedly by the base and read the carried integers top to bottom.

Binary ↔ octal ↔ hexadecimal: grouping

Because 8 = 2^3 and 16 = 2^4, each octal digit is exactly 3 bits and each hex digit exactly 4 bits. Group from the binary point outwards, padding with zeros at the ends.

2.2 Binary addition and subtraction

Binary arithmetic follows exactly the same column rules as decimal, with only two digits available.

   1111     <- carries
    1011    (11)
  + 1101    (13)
  -------
   11000    (24)

   11010    (26)
  - 01011   (11)
  --------
   01111    (15)

      1101        (13)
    x  101        ( 5)
    --------
      1101
     0000
    1101
    --------
    1000001       (65)

          1010        quotient = 1010 (10)
      ----------
 101 ) 110110
       101
       ---
        0111
         101
         ---
          0101 0
           101
           ---
             100    remainder = 100 (4)

2.3 One's and Two's complement methods of binary subtraction

Hardware has no subtractor. A computer subtracts by adding the complement, so the same adder circuit does both operations. This is why complements matter.

For example, with 4 bits: N = 0110 → 1's complement = 1001 → 2's complement = 1010.

Subtraction by 1's complement

To compute A - B:

1. Take the 1's complement of B (the subtrahend).
2. Add it to A.
3. If a carry comes out of the leftmost column, the answer is positive: add that carry back into the least significant bit (end-around carry). The result is the answer.
4. If there is no carry out, the answer is negative: take the 1's complement of the sum and put a minus sign in front.

     1010
   + 1001
   -------
   1 0011      carry out = 1  -> positive
       +1      end-around carry
   -------
     0100      = 4

     0110
   + 0101
   -------
     1011      no carry out -> negative

Subtraction by 2's complement

1. Take the 2's complement of B.
2. Add it to A.
3. If there is a carry out, discard it; the result is positive.
4. If there is no carry out, the result is negative: take the 2's complement of the sum and put a minus sign in front.

     1010
   + 1010
   -------
   1 0100      discard the carry out
   -------
     0100      = +4

     00101101      (45)
   + 10110010      (2's complement of 78)
   -----------
     11011111      no carry out -> negative

2.4 Introduction to Boolean algebra

Boolean algebra is the algebra of two-valued logic, published by the English mathematician George Boole in An Investigation of the Laws of Thought (1854). In 1938 Claude Shannon showed that it describes switching circuits exactly — a switch is either on or off — and that insight is the foundation of all digital design.

Here + means OR (read "A or B"), \cdot means AND (read "A and B"), and the bar means NOT. The 0 and 1 are not quantities; they are logic levels — false/true, off/on, low/high voltage.

2.5 Boolean values, truth table, Boolean expression and Boolean function

• A Boolean value (logic value) is either 0 (false, low) or 1 (true, high).
• A Boolean variable is a symbol, such as A, that can hold only a Boolean value. A literal is a variable or its complement: A and \bar{A} are two literals.
• A Boolean expression is variables combined by AND, OR and NOT, for example \bar{A}B + AC.
• A Boolean function assigns an output value to every combination of its input variables, written F(A,B,C) = \bar{A}B + AC.
• A truth table lists the output for every input combination. With n input variables it has 2^{n} rows.

For F(A,B,C) = \bar{A}B + AC:

2.6 Logic gates

The NOT gate (inverter) has one input: \bar{0} = 1 and \bar{1} = 0.

In words: AND gives 1 only when all inputs are 1. OR gives 1 when at least one input is 1. XOR gives 1 when the inputs are different — it is the "odd number of 1s" detector. XNOR gives 1 when the inputs are the same, so it is an equality detector. NAND and NOR are the inverses of AND and OR.

Drawing a circuit from an expression

Work from the innermost operation outwards: complements first, then AND terms, then the final OR.

Half adder and full adder

A half adder adds two single bits and produces a sum and a carry. Its two outputs are exactly XOR and AND of the inputs.

A half adder cannot be used for the second and later columns of an addition, because it has nowhere to take the carry in. A full adder adds three bits — A, B and a carry-in C_{in} — and is built from two half adders plus an OR gate.

2.7 Laws of Boolean algebra

Note the second distributive law, A + BC = (A+B)(A+C). It has no counterpart in ordinary algebra and is a favourite examination question.

Simplification using the laws

Simplification using Karnaugh maps

A Karnaugh map (K-map) is a truth table redrawn as a grid, with the rows and columns labelled in Gray code order (00, 01, 11, 10) so that any two neighbouring cells differ in exactly one variable. Then:

1. Write a 1 in every cell whose minterm is in the function.
2. Ring rectangular groups of 1s whose size is a power of two — 1, 2, 4, 8 — making each group as large as possible. Groups may overlap, and they wrap around the edges of the map.
3. For each group write the product of the variables that stay constant inside it; drop the variables that change.
4. OR the group terms together.

2.8 Verification of the laws of Boolean algebra using truth tables

To verify a law, build one column for the left-hand side and one for the right-hand side, fill in every row, and show the two columns are identical.

De Morgan's first theorem: \overline{A+B} = \bar{A}\cdot\bar{B}

Columns 4 and 7 agree in every row, so the theorem is proved.

De Morgan's second theorem: \overline{A\cdot B} = \bar{A} + \bar{B}

Distributive law: A + BC = (A+B)(A+C)

Absorption law: A + AB = A, and redundancy: A + \bar{A}B = A + B

Column 4 equals column 1 (absorption); column 6 equals column 7 (redundancy).

Practice questions

Group A — Multiple choice (1 mark each)

1. (1011)_2 in decimal is [1]a9b11c13d15
2. The hexadecimal equivalent of (11011110)_2 is [1]aDEbEDc9EdBE
3. The 2's complement of (0101)_2 is [1]a1010b1011c0110d1101
4. Which gate gives output 1 only when its two inputs are different? [1]aANDbNORcXORdXNOR
5. According to De Morgan's theorem, \overline{A\cdot B} equals [1]a\bar{A}\cdot\bar{B}b\bar{A}+\bar{B}cA+Bd\overline{A+B}
6. A + \bar{A}B simplifies to [1]aAbBcA+BdAB
7. Which pair of gates is called universal? [1]aAND and ORbNAND and NORcXOR and XNORdNOT and AND
8. The carry output of a half adder is [1]aA \oplus BbA + BcA\cdot Bd\overline{A\cdot B}

Group B — Short answer (5 marks each)

1. Convert(a) (347)_{10} to binary, octal and hexadecimal, and(b) (10110111)_2 to decimal, octal and hexadecimal. [5]
2. Perform the following binary operations:(a) 10110 + 1101,(b) 110100 - 10111,(c) 1011 \times 110,(d) 100101 \div 111. [5]
3. Subtract (0111)_2 from (1101)_2 using(a) the 1's complement method and(b) the 2's complement method. Show every step. [5]
4. State and verify De Morgan's two theorems using truth tables. [5]
5. Simplify F = \bar{A}\bar{B}C + \bar{A}BC + A\bar{B}C + ABC using the laws of Boolean algebra, and draw the logic circuit of the simplified expression. [5]
6. Draw the logic symbol and write the truth table and Boolean function of the NAND, NOR, XOR and XNOR gates. [5]

Group C — Long answer (8 marks each)

1. (a) Convert (2C5)_{16} to decimal, binary and octal. [3](b) Using the 2's complement method in 8 bits, evaluate 58 - 91 and verify your answer in decimal. [5]
2. (a) Define a logic gate. Draw the symbol and truth table of all seven basic gates. [4](b) Draw the logic circuit of a full adder using two half adders and one OR gate, write its truth table, and derive the expressions for the sum and the carry. [4]
3. Simplify F(A,B,C,D) = \sum m(0,1,2,3,8,9,10,11,13,15) using a Karnaugh map. Show the map, the groupings and the final simplified expression, and draw the resulting logic circuit. [8]