Chapter 2: Number System and Logic Functions
2.1 Number System and Conversion
In the realm of computer science, understanding different number systems is fundamental. Computers primarily operate using the binary system, but humans interact with them using decimal, and other systems like octal and hexadecimal are used for convenience in representing large binary numbers.
2.1.1 Decimal, Binary, Octal, Hexadecimal Number System & Conversion
A number system is a way of representing numbers using a set of digits or symbols. Each system has a specific base (or radix) which determines the number of unique digits it uses.
- Decimal (Base 10): This is the most common number system used by humans. It uses ten digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Each digit's position represents a power of 10.
- Binary (Base 2): The native language of computers. It uses only two digits: 0 and 1. Each digit is called a bit. Each position represents a power of 2.
- Octal (Base 8): Uses eight digits: 0, 1, 2, 3, 4, 5, 6, 7. It's often used as a shorthand for binary numbers because three binary digits can represent one octal digit.
- Hexadecimal (Base 16): Uses sixteen digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Here, A represents 10, B represents 11, and so on, up to F representing 15. It's also a convenient shorthand for binary, where four binary digits represent one hexadecimal digit.
Conversions between Number Systems
Decimal to Binary Conversion (Division Method)
To convert a decimal number to binary, repeatedly divide the decimal number by 2 and record the remainder. The binary number is formed by reading the remainders from bottom to top.
Formula: Repeated division by base (2 for binary).
Example: Convert (25)10 to Binary
- 25 ÷ 2 = 12 Remainder 1
- 12 ÷ 2 = 6 Remainder 0
- 6 ÷ 2 = 3 Remainder 0
- 3 ÷ 2 = 1 Remainder 1
- 1 ÷ 2 = 0 Remainder 1
Reading remainders from bottom to top: (11001)2. So, (25)10 = (11001)2.
Binary to Decimal Conversion (Weight Method)
To convert a binary number to decimal, multiply each bit by its positional weight (power of 2) and sum the results. The positional weights start from 20 for the rightmost bit, increasing by one for each position to the left.
Formula: Decimal = dn * 2n + ... + d1 * 21 + d0 * 20, where d is the binary digit and n is its position from right (starting at 0).
Example: Convert (11001)2 to Decimal
(11001)2 = 1 * 24 + 1 * 23 + 0 * 22 + 0 * 21 + 1 * 20
= 1 * 16 + 1 * 8 + 0 * 4 + 0 * 2 + 1 * 1
= 16 + 8 + 0 + 0 + 1 = (25)10
Octal ↔ Binary Conversion (3-bit groups)
This conversion is straightforward because 23 = 8. Each octal digit corresponds to exactly three binary digits.
- Octal to Binary: Replace each octal digit with its 3-bit binary equivalent.
- Binary to Octal: Group binary digits into sets of three from right to left (pad with leading zeros if necessary) and convert each group to its octal equivalent.
Example: Convert (672)8 to Binary
- 6 = 110
- 7 = 111
- 2 = 010
So, (672)8 = (110111010)2.
Example: Convert (101110010)2 to Octal
Group into 3 bits: 101 110 010
- 101 = 5
- 110 = 6
- 010 = 2
So, (101110010)2 = (562)8.
Hexadecimal ↔ Binary Conversion (4-bit groups)
Similar to octal, this conversion is easy because 24 = 16. Each hexadecimal digit corresponds to exactly four binary digits.
- Hexadecimal to Binary: Replace each hexadecimal digit with its 4-bit binary equivalent.
- Binary to Hexadecimal: Group binary digits into sets of four from right to left (pad with leading zeros if necessary) and convert each group to its hexadecimal equivalent.
Example: Convert (A5F)16 to Binary
- A = 1010
- 5 = 0101
- F = 1111
So, (A5F)16 = (101001011111)2.
Example: Convert (11010011101)2 to Hexadecimal
Group into 4 bits (add leading zero): 0110 1001 1101
- 0110 = 6
- 1001 = 9
- 1101 = D
So, (11010011101)2 = (69D)16.
Decimal ↔ Octal Conversion
- Decimal to Octal: Use the repeated division method by 8, similar to decimal to binary.
- Octal to Decimal: Use the weight method, multiplying each octal digit by powers of 8.
Example: Convert (125)10 to Octal
- 125 ÷ 8 = 15 Remainder 5
- 15 ÷ 8 = 1 Remainder 7
- 1 ÷ 8 = 0 Remainder 1
Reading remainders from bottom to top: (175)8. So, (125)10 = (175)8.
Example: Convert (175)8 to Decimal
(175)8 = 1 * 82 + 7 * 81 + 5 * 80
= 1 * 64 + 7 * 8 + 5 * 1
= 64 + 56 + 5 = (125)10
Decimal ↔ Hexadecimal Conversion
- Decimal to Hexadecimal: Use the repeated division method by 16. Remember to convert remainders 10-15 to A-F.
- Hexadecimal to Decimal: Use the weight method, multiplying each hexadecimal digit by powers of 16. Remember to convert A-F to 10-15 before multiplication.
Example: Convert (255)10 to Hexadecimal
- 255 ÷ 16 = 15 Remainder 15 (F)
- 15 ÷ 16 = 0 Remainder 15 (F)
Reading remainders from bottom to top: (FF)16. So, (255)10 = (FF)16.
Example: Convert (FF)16 to Decimal
(FF)16 = F * 161 + F * 160
= 15 * 16 + 15 * 1
= 240 + 15 = (255)10
2.1.2 Binary Addition and Subtraction
Binary arithmetic follows similar principles to decimal arithmetic but uses only two digits (0 and 1).
Binary Addition Rules
The rules for binary addition are:
0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 10(which means 0 with a carry of 1 to the next position)1 + 1 + 1 = 11(which means 1 with a carry of 1 to the next position)
Worked Examples for Binary Addition:
Example 1: Add (101)2 and (011)2
101
+ 011
-----
1000
- Rightmost column: 1 + 1 = 10 (write 0, carry 1)
- Middle column: 0 + 1 + (carry)1 = 10 (write 0, carry 1)
- Leftmost column: 1 + 0 + (carry)1 = 10 (write 0, carry 1)
- Final carry: 1
Result: (1000)2. (Decimal: 5 + 3 = 8)
Example 2: Add (1110)2 and (1011)2
1110
+ 1011
------
11001
- 0 + 1 = 1
- 1 + 1 = 10 (write 0, carry 1)
- 1 + 0 + (carry)1 = 10 (write 0, carry 1)
- 1 + 1 + (carry)1 = 11 (write 1, carry 1)
- Final carry: 1
Result: (11001)2. (Decimal: 14 + 11 = 25)
Binary Subtraction Rules
The rules for binary subtraction are:
0 - 0 = 01 - 0 = 11 - 1 = 00 - 1 = 1(with a borrow of 1 from the next higher position)
Worked Examples for Binary Subtraction:
Example 1: Subtract (011)2 from (101)2
101
- 011
-----
010
- Rightmost column: 1 - 1 = 0
- Middle column: 0 - 1. This requires a borrow. Borrow 1 from the leftmost 1, making it 0. The middle 0 becomes 10 (binary for 2). So, 10 - 1 = 1.
- Leftmost column: 0 (after borrow) - 0 = 0
Result: (010)2. (Decimal: 5 - 3 = 2)
Example 2: Subtract (1011)2 from (1110)2
1110
- 1011
------
0011
- 0 - 1: Borrow from the 1 to its left. The 0 becomes 10 (binary 2), the 1 becomes 0. So, 10 - 1 = 1.
- 0 (after borrow) - 1: Borrow from the 1 to its left. The 0 becomes 10, the 1 becomes 0. So, 10 - 1 = 1.
- 0 (after borrow) - 0 = 0.
- 1 - 1 = 0.
Result: (0011)2. (Decimal: 14 - 11 = 3)
2.1.3 One's and Two's Complement Methods
Complements are used in digital computers for simplifying subtraction operations and for representing negative numbers.
One's Complement
The one's complement of a binary number is obtained by inverting all the bits (changing 0s to 1s and 1s to 0s).
Formula: Flip all bits (0 → 1, 1 → 0).
Example: Find the one's complement of (10110)2
Original number: 10110
One's complement: 01001
Two's Complement
The two's complement is crucial for representing negative numbers and performing subtraction using addition. It is calculated by taking the one's complement of the number and then adding 1 to the least significant bit (LSB).
Formula: Two's Complement = One's Complement + 1
Example: Find the two's complement of (10110)2
- Original number:
10110 - One's complement:
01001 - Add 1 to the one's complement:
01001 + 1 ------- 01010
So, the two's complement of (10110)2 is (01010)2.
Subtraction using Two's Complement
Subtraction of binary numbers can be performed using the two's complement method, which converts subtraction into an addition operation. This simplifies the hardware design for arithmetic logic units (ALUs).
Rule: A - B = A + (Two's Complement of B)
Steps for A - B using Two's Complement:
- Determine the number of bits for representation (e.g., 8-bit). Ensure both numbers have the same number of bits.
- Find the two's complement of the subtrahend (B).
- Add the minuend (A) to the two's complement of B.
- If there is an end-around carry (a carry generated from the leftmost bit position), discard it. The remaining bits represent the positive result.
- If there is no end-around carry, the result is negative and is in two's complement form. To get the magnitude, find the two's complement of the result and prefix with a negative sign.
Example 1: Subtract (011)2 from (101)2 (i.e., 5 - 3) using 4-bit representation
- A = (101)2 = 0101 (4-bit representation)
- B = (011)2 = 0011 (4-bit representation)
- Find two's complement of B (0011):
- One's complement of 0011 is 1100
- Add 1: 1100 + 1 = 1101
- Add A to two's complement of B:
0101 (A) + 1101 (Two's complement of B) ------- 10010 - Discard the end-around carry (the leftmost 1).
Result: 0010, which is (2)10. This is correct (5 - 3 = 2).
Example 2: Subtract (1110)2 from (1011)2 (i.e., 11 - 14) using 5-bit representation
Note: For subtraction where B > A, the result will be negative.
- A = (1011)2 = 01011 (5-bit representation)
- B = (1110)2 = 01110 (5-bit representation)
- Find two's complement of B (01110):
- One's complement of 01110 is 10001
- Add 1: 10001 + 1 = 10010
- Add A to two's complement of B:
01011 (A) + 10010 (Two's complement of B) ------- 11101 - There is no end-around carry. This indicates the result is negative and in two's complement form.
- To find the magnitude of the negative result, take the two's complement of 11101:
- One's complement of 11101 is 00010
- Add 1: 00010 + 1 = 00011
The magnitude is (00011)2, which is (3)10. Since the original result had no carry, the final answer is -(3)10. This is correct (11 - 14 = -3).
2.2 Logic Function and Boolean Algebra
Boolean algebra is a branch of algebra in which the values of the variables are the truth values, true and false, usually denoted 1 and 0, respectively. It is fundamental to the design and analysis of digital circuits.
2.2.1 Introduction to Boolean Algebra
- Boolean algebra: A mathematical system for logical operations, developed by George Boole. It deals with binary variables and logical operations.
- Variables: In Boolean algebra, variables can only take one of two possible values:
TRUE (1)orFALSE (0). These are often represented by letters like A, B, C. - Operations: The basic operations in Boolean algebra are:
- AND (∙): Logical conjunction. Output is 1 only if all inputs are 1.
- OR (+): Logical disjunction. Output is 1 if at least one input is 1.
- NOT (' or ¯): Logical negation. Inverts the input.
2.2.2 Boolean Values, Truth Table, Boolean Expression, Function
- Boolean Values: The only two possible values a Boolean variable can hold are 0 (False) and 1 (True).
- Truth Table: A table that lists all possible combinations of input values for a Boolean expression or function and the corresponding output value. It exhaustively shows the behavior of a logic circuit or function.
- Boolean Expression: A logical combination of Boolean variables and logical operators (AND, OR, NOT). For example,
A + B',(A · B)' + C. - Boolean Function: An expression that defines the output of a logic circuit for a given set of inputs. It maps a set of input Boolean values to a single output Boolean value. A Boolean expression represents a Boolean function.
2.2.3 Logic Gates
Logic gates are the basic building blocks of any digital system. They are electronic circuits having one or more inputs and only one output. The relationship between the input and the output is based on a certain logic.
AND Gate
- Description: The output is 1 (TRUE) only if all inputs are 1 (TRUE). Otherwise, the output is 0 (FALSE).
- Boolean Expression:
Y = A · B(orY = AB) - Logic Symbol: (A D-shaped gate with two inputs A, B and one output Y)
- Truth Table:
A B Y = A · B 0 0 0 0 1 0 1 0 0 1 1 1
OR Gate
- Description: The output is 1 (TRUE) if at least one input is 1 (TRUE). The output is 0 (FALSE) only if all inputs are 0 (FALSE).
- Boolean Expression:
Y = A + B - Logic Symbol: (A curved gate with two inputs A, B and one output Y)
- Truth Table:
A B Y = A + B 0 0 0 0 1 1 1 0 1 1 1 1
NOT Gate (Inverter)
- Description: The output is always the inverse of the input. If the input is 1, the output is 0, and vice versa. It has only one input.
- Boolean Expression:
Y = A'(orY = ¯A) - Logic Symbol: (A triangle with a small circle at the output, one input A and one output Y)
- Truth Table:
A Y = A' 0 1 1 0
NAND Gate (Universal Gate)
- Description: It is a NOT-AND gate. The output is 0 (FALSE) only if all inputs are 1 (TRUE). Otherwise, the output is 1 (TRUE). It is a universal gate, meaning any other logic gate can be implemented using only NAND gates.
- Boolean Expression:
Y = (A · B)' - Logic Symbol: (AND gate symbol with a small circle at the output)
- Truth Table:
A B Y = (A · B)' 0 0 1 0 1 1 1 0 1 1 1 0
NOR Gate (Universal Gate)
- Description: It is a NOT-OR gate. The output is 1 (TRUE) only if all inputs are 0 (FALSE). Otherwise, the output is 0 (FALSE). It is also a universal gate.
- Boolean Expression:
Y = (A + B)' - Logic Symbol: (OR gate symbol with a small circle at the output)
- Truth Table:
A B Y = (A + B)' 0 0 1 0 1 0 1 0 0 1 1 0
XOR Gate (Exclusive OR)
- Description: The output is 1 (TRUE) if the inputs are different. The output is 0 (FALSE) if the inputs are the same.
- Boolean Expression:
Y = A ⊕ B(which is equivalent toA'B + AB') - Logic Symbol: (OR gate symbol with an additional curved line at the input)
- Truth Table:
A B Y = A ⊕ B 0 0 0 0 1 1 1 0 1 1 1 0
XNOR Gate (Exclusive NOR)
- Description: The output is 1 (TRUE) if the inputs are the same. The output is 0 (FALSE) if the inputs are different. It is the inverse of the XOR gate.
- Boolean Expression:
Y = A ⊙ B(which is equivalent toAB + A'B') - Logic Symbol: (XOR gate symbol with a small circle at the output)
- Truth Table:
A B Y = A ⊙ B 0 0 1 0 1 0 1 0 0 1 1 1
2.2.4 Laws of Boolean Algebra
Boolean algebra has a set of laws and theorems that are used to simplify Boolean expressions and logic circuits. These laws are analogous to algebraic laws but operate on Boolean values.
- Boolean Identities:
A + 0 = A(Identity Law for OR)A · 1 = A(Identity Law for AND)A + 1 = 1(Null Law for OR)A · 0 = 0(Null Law for AND)
- Complement Laws:
A + A' = 1(A OR NOT A is always TRUE)A · A' = 0(A AND NOT A is always FALSE)
- Idempotent Laws:
A + A = AA · A = A
- Double Complement Law:
(A')' = A(Double negation returns the original variable)
- Commutative Laws: The order of operands does not affect the result.
A + B = B + A(for OR)A · B = B · A(for AND)
- Associative Laws: The grouping of operands does not affect the result for three or more variables.
(A + B) + C = A + (B + C)(for OR)(A · B) · C = A · (B · C)(for AND)
- Distributive Laws: Allows for expansion and factorization of Boolean expressions.
A · (B + C) = (A · B) + (A · C)(AND over OR)A + (B · C) = (A + B) · (A + C)(OR over AND)
- Absorption Laws:
A + (A · B) = AA · (A + B) = A
- De Morgan's Laws: These are crucial for simplifying expressions and converting between AND/OR forms.
(A + B)' = A' · B'(The complement of a sum is the product of the complements)(A · B)' = A' + B'(The complement of a product is the sum of the complements)
2.2.5 Verification Using Truth Tables
Truth tables provide a systematic way to verify the equivalence of two Boolean expressions or to prove a Boolean law. If the truth tables for both sides of an equation are identical, then the equation is valid.
Step-by-step method to verify any Boolean law:
- Identify all unique input variables (e.g., A, B, C).
- Determine the number of rows needed for the truth table. If there are 'n' variables, there will be 2n rows.
- List all possible input combinations for the variables.
- For each side of the equation, create columns for intermediate expressions until the final output for that side is calculated.
- Compare the final output columns for both sides of the equation. If they are identical for all input combinations, the law is verified.
Example 1: Verify De Morgan's Law: (A + B)' = A' · B'
We need to show that the output of (A + B)' is the same as the output of A' · B' for all possible inputs of A and B.
| A | B | A + B | (A + B)' (LHS) | A' | B' | A' · B' (RHS) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Since the columns for (A + B)' and A' · B' are identical, De Morgan's Law (A + B)' = A' · B' is verified.
Example 2: Verify Distributive Law: A · (B + C) = A · B + A · C
We need to show that the output of A · (B + C) is the same as the output of A · B + A · C for all possible inputs of A, B, and C.
| A | B | C | B + C | A · (B + C) (LHS) | A · B | A · C | A · B + A · C (RHS) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Since the columns for A · (B + C) and A · B + A · C are identical, the Distributive Law A · (B + C) = A · B + A · C is verified.