Chapter 1: Number Systems
1.1 Overview of Number Systems
System Base (b ) Digits
Decimal 10 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Binary 2 0, 1
Octal 8 0, 1, 2, 3, 4, 5, 6, 7
Hexadecimal 16 0–9, A (10), B (11), C (12), D (13), E (14), F (15)
1.2 Converting Between Systems: Step-by-Step
1.2.1 Decimal → Binary (Repeated Division)
1. Divide the decimal number by 2.
2. Record the remainder (0 or 1).
3. Update the number to the integer quotient.
4. Repeat until quotient = 0.
5. Write remainders in reverse (last → first).
Example: Convert 156₁₀ to binary.
156 ÷ 2 = 78, rem 0
78 ÷ 2 = 39, rem 0
39 ÷ 2 = 19, rem 1
19 ÷ 2 = 9, rem 1
9 ÷ 2 = 4, rem 1
4 ÷ 2 = 2, rem 0
2 ÷ 2 = 1, rem 0
1 ÷ 2 = 0, rem 1
Write remainders bottom-up: 10011100₂
1.2.2 Binary → Decimal (Positional Weights)
1. Write bits bn bn−1 … b1 b0 .
n
2. Compute ∑i=0 bi × 2i .
Example: 1011012 = 1⋅ 25 + 0⋅ 24 + 1⋅ 23 + 1⋅ 22 + 0⋅ 21 + 1⋅ 20 = 32 + 0 + 8 + 4 + 0 + 1 = 4510
1
1.2.3 Binary ↔ Octal (Group of 3)
• Binary → Octal: Group bits in threes from the right, pad with 0’s, convert each group to octal digit.
• Octal → Binary: Convert each octal digit to 3-bit binary.
Example: 1011101012 = (101)(110)(101)2 = 5658
1.2.4 Binary ↔ Hexadecimal (Group of 4)
• Binary → Hex: Group bits in fours, pad left, convert each group to hex digit.
• Hex → Binary: Convert each hex digit to 4-bit binary.
Example: 11011110012 = (0011)(0111)(1001)2 = 37916
1.2.5 Decimal ↔ Octal/Hex via Binary (Two-Step)
1. Decimal → Binary (as above).
2. Binary → Octal/Hex using grouping.
1.2.6 Fractional Parts
• Decimal fraction → Binary: Multiply fractional part by base, extract integer part repeatedly.
∞
• Binary fraction → Decimal: 0.b1 b2 b3 ⋯ = ∑i=1 bi ⋅ 2−i .
Section A-9: Encoding
A9.1 Character Encoding Schemes
Scheme Bits per Character Range
ASCII 7 (or 8) 0–127 (or 0–255)
Extended ASCII 8 0–255
Unicode 16, 32 U+0000–U+10FFFF
A9.2 ASCII Table (Selected)
Dec Char Bin | Dec Char Bin
32 SPACE 01000000 | 65 A 01000001
48 0 00110000 | 97 a 01100001
... |
A9.3 Encoding Steps
1. Take character (e.g. 'A').
2
2. Look up ASCII code (65).
3. Convert 65₁₀ → binary: 01000001₂.
A9.4 Other Encodings
• UTF-8: Variable length (1–4 bytes), backward compatible with ASCII.
• Parity Bit: 1 bit added for error detection (even/odd parity).
Chapter 2: Propositional Logic (Part I)
2.1 Propositions & Logical Connectives
• Proposition: A declarative statement that is either true (T) or false (F).
• Connectives: ∧ (AND), ∨ (OR), ¬ (NOT), → (IMPLIES), ↔ (IFF).
2.2 Truth Tables
p q ¬p p∧q p∨q p→q
T T F T T T
T F F F T F
F T T F T T
F F T F F T
2.2.1 Constructing a Table
1. List all combinations of truth values for n propositions (2ⁿ rows).
2. Compute columns of sub-formulae step by step.
2.3 Implication, Antecedent & Consequent
• Implication: p→ q is false only when p is T and q is F.
• Antecedent: p in p → q .
• Consequent: q in p → q .
2.4 Negation, Contrapositive & Equivalences
• Negation: ¬p flips truth.
• Contrapositive: (p→ q) ≡ (¬q → ¬p) .
• Inverse: (¬p)→ (¬q) .
• Converse: q → p .
3
2.4.1 Tautology & Contradiction
• Tautology: Always true (e.g., p ∨ ¬p ).
• Contradiction: Always false (e.g., p ∧ ¬p ).
2.5 Logical Gates & Circuit Symbols
Gate Symbol Boolean Expression
AND y = x1 ∧ x2
OR y = x1 ∨ x2
NOT y = ¬x
NAND y = ¬(x1 ∧ x2 )
NOR y = ¬(x1 ∨ x2 )
XOR y = (x1 ⊕ x2 )
2.6 Example: Verifying a Tautology
Expression: (p ∧ (p → q)) → q \ Construct truth table and observe all outputs = T → tautology.
End of Notes.