1. **Problem 1: Number Systems in Computing** a) The binary, octal, decimal, and hexadecimal number systems are fundamental in computing because they uniquely suit digital electronics and computing architecture. Binary (base 2) aligns naturally with digital circuits using two voltage states (0 and 1), enabling simple, reliable data representation and processing. Octal (base 8) and hexadecimal (base 16) serve as shorthand notations for binary numbers to simplify human readability and reduce errors. Decimal (base 10) is used because of its natural alignment with everyday human counting. b) The main differences among these systems are their bases and digit sets: - Binary uses base 2 with digits {0,1}. - Octal uses base 8 with digits {0,...,7}. - Decimal uses base 10 with digits {0,...,9}. - Hexadecimal uses base 16 with digits {0,...,9,A,...,F} where A=10 to F=15. c) The binary system is used in computers because digital circuits function with two distinct states (e.g., on/off), perfectly modeled by binary digits (bits). This simplicity reduces complexity, improves reliability, and eases hardware implementation. 2. **Problem 2: Number Conversions and Operations** a) Convert (59)$_{10}$ to BCD: 1. Write each decimal digit in 4-bit binary. 2. 5 = 0101, 9 = 1001. 3. Thus, BCD representation is $0101\;1001$. b) Add (34)BCD + (27)BCD: 1. Convert digits to BCD: 3=0011,4=0100, 2=0010,7=0111. 2. Add digit-wise with BCD addition rules: - $0100 + 0111 = 1011_{(11)}$, adjust by adding 6 (0110): $1011 + 0110 = 0001\;0001$ (carry 1). - $0011 + 0010 + 1(carry) = 0110$. 3. Sum in BCD: $0110\;0001$ representing 61. c) Convert (245)$_{10}$ to octal and hexadecimal: - Octal: 1. Divide by 8: 245/8=30 remainder 5. 2. 30/8=3 remainder 6. 3. 3/8=0 remainder 3. 4. Octal number is digits read upwards: $365_8$. - Hexadecimal: 1. Divide by 16: 245/16=15 remainder 5. 2. 15/16=0 remainder 15 (F in hex). 3. Hexadecimal is $F5_{16}$. d) Convert $11001_2$ to Excess-3 code: 1. First convert binary to decimal: $1\times16 + 1\times8 + 0 + 0 + 1 = 16+8+1=25$. 2. Add 3: $25 + 3 = 28$. 3. Represent 28 in binary: $0001\;1100$. 4. Excess-3 code is the binary of $decimal + 3$ per digit: - 2: 2+3=5 → 0101 - 5: 5+3=8 → 1000 5. So Excess-3: $0101\;1000$. e) Subtract $8F2B_{16} - 4C9_{16}$: 1. Equalize digits by padding: $8F2B - 04C9$. 2. Subtraction step: - B(11) - 9 = 2 - 2 - C(12) ?? Need borrow - Borrow 1 from F(15) → F=14 - 14 - 12 = 2 - Next: 14 - 4 = 10 (A) - 8 - 0 = 8 3. Result: $8A22_{16}$. f) Multiply $4F2_{16} imes 2D_{16}$: 1. Convert to decimal for clarity: - $4F2_{16} = 4\times256 + 15\times16 + 2 = 1024 + 240 + 2 = 1266$. - $2D_{16} = 2\times16 +13=45$. 2. Multiply: $1266 \times 45 = 56970$. 3. Convert $56970$ to hexadecimal: - Divide by 16: * $56970/16=3560$ remainder 10 (A) * $3560/16=222$ remainder 8 * $222/16=13$ remainder 14 (E) * $13/16=0$ remainder 13 (D) - Hex: $DE8A_{16}$. g) Represent -13 in 8-bit one’s complement: 1. 13 in binary: $00001101$. 2. One's complement: invert bits → $11110010$. h) Represent -13 in 8-bit two’s complement: 1. Start from one’s complement: $11110010$. 2. Add 1: $11110010 + 1 = 11110011$. i) Add $(10110110)_2$ and $(11001101)_2$ using two’s complement: 1. Add bits: $10110110 + 11001101 = 101000011$ (9 bits). 2. Ignore carry beyond 8 bits → $01000011$. 3. Binary $01000011 = 67_{10}$. j) Explanation of zero, infinity, and NaN in IEEE 754: - Zero: Exponent and mantissa all zeros, sign bit indicates +0 or -0. - Infinity: Exponent all ones, mantissa all zeros, sign bit indicates +∞ or -∞. - NaN (Not a Number): Exponent all ones, mantissa non-zero, used to represent undefined or unrepresentable values. 3. **Problem 3: Propositions and Logic** a) Define a proposition: - A proposition is a declarative statement that is either true or false, but not both. - Examples: "The sky is blue." (True), "5 is an even number." (False). - Non-examples: "Is it raining?" (question), "Close the door!" (command). b) Truth value of "2 is a prime number." → True. c) Difference between conjunction and disjunction: - Conjunction ($p \wedge q$): True only when both $p$ and $q$ are true. Example: "It is raining AND it is cold." - Disjunction ($p \vee q$): True when at least one of $p$ or $q$ is true. Example: "It is raining OR it is snowing." d) If $p$ is true, $q$ is false: - $p \wedge q$ = true AND false = false. - $p \vee q$ = true OR false = true. e) Negation of "This exercise is interesting" is "This exercise is not interesting." f) Truth value of $(p \vee q) \wedge \neg p$ when $p$ is true and $q$ is false: 1. $p \vee q = true \vee false = true$. 2. $\neg p = false$. 3. Combined: $true \wedge false = false$. g) Biconditional statement: - A statement of the form $p \leftrightarrow q$ is true when $p$ and $q$ have the same truth value. - Example: "You can enter the club if and only if you have an ID." h) Express "I will study if and only if I have time" as: $$Study \leftrightarrow Time$$ i) Contribution of mathematical logic: - It underpins digital logic circuits by defining true/false conditions for binary states, enabling design of gates and circuits. - Application at the software level: Boolean algebra is used in programming, algorithms, and decision-making structures. 4. **Problem 4: Sets and Relations** a) Difference between singleton set and infinite set: - Singleton set: contains exactly one element. Example: $\{5\}$. - Infinite set: contains infinitely many elements. Example: set of natural numbers $\mathbb{N}$. b) Set $A = \{2,3,5,7,11,13,17,19\}$ in set-builder notation: $$A = \{ x \in \mathbb{N} \mid x \text{ is prime and } 2 \leq x \leq 19 \}$$ c) Number of students who like at least one subject: - Use formula: $$|M \cup S| = |M| + |S| - |M \cap S|$$ $$|M \cup S| = 20 + 15 - 5 = 30$$ d) Relation definition: A relation $R$ on set $A$ is a set of ordered pairs $(x,y)$ where $x,y \in A$. - Example on $A = \{1,2,3\}$: $R = \{(1,2), (2,3)\}$. e) Relation $R$ on $A = \{1,2,3,4\}$ where $R = \{(x,y) \mid x + y \text{ is even} \}$: - Pairs: - (1,1)=2 even - (1,3)=4 even - (2,2)=4 even - (2,4)=6 even - (3,1)=4 even - (3,3)=6 even - (4,2)=6 even - (4,4)=8 even - Thus, $$R = \{(1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)\}$$ f) For relations on $A = \{1,2,3\}$: i. $R_1 = \{(1,1),(2,2),(3,3)\}$ - Reflexive: Yes, all $(a,a)$ present. - Symmetric: Yes, symmetric pairs trivial here. - Antisymmetric: Yes, no $(a,b)$ and $(b,a)$ with $a \neq b$. - Transitive: Yes, only self loops. ii. $R_2 = \{(1,2),(2,1),(2,3)\}$ - Reflexive: No (missing $(1,1)$, $(2,2)$, $(3,3)$). - Symmetric: No, $(2,3)$ present but $(3,2)$ missing. - Antisymmetric: No, since $(1,2)$ and $(2,1)$ both present. - Transitive: No, since $(1,2)$ and $(2,3)$ present but $(1,3)$ missing.