C5-Mat-20 Class Notes PDF

Mathematics C5-MAT-20 Lecturer: Dr. T. Diphofu Botho University Class Notes Date: October 6, 2024 1 Hexadecimal Numbers Hexadecimal (or simply hex) is a base-16 number system that uses sixteen distinct sym- bols. The symbols include the digits 0 to 9 to...

Mathematics C5-MAT-20 Lecturer: Dr. T. Diphofu Botho University Class Notes Date: October 6, 2024 1 Hexadecimal Numbers Hexadecimal (or simply hex) is a base-16 number system that uses sixteen distinct sym- bols. The symbols include the digits 0 to 9 to represent values zero to nine, and the letters A to F (or a to f) to represent values 10 to 15. Hexadecimal numbers are widely used in computing and digital electronics because they provide a more human-friendly representation of binary-coded values. 1.1 Hexadecimal Symbols Hexadecimal Decimal 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 A 10 B 11 C 12 D 13 E 14 F 15 1.2 Reading and Writing Hexadecimal Numbers Hexadecimal numbers are often prefixed with “0x” or suffixed with “h” to distinguish them from decimal numbers. For example, the decimal number 255 can be written as 0xFF or FFh in hexadecimal. 1.3 Converting Between Hexadecimal and Decimal To convert a hexadecimal number to a decimal number, multiply each digit by the cor- responding power of 16 and sum the results. Example 1: Convert 0x1A3 to decimal. 1A316 = 1 · 162 + 10 · 161 + 3 · 160 = 256 + 160 + 3 = 41910 To convert a decimal number to hexadecimal, repeatedly divide the decimal number by 16 and record the remainders. Example 2: Convert 419 to hexadecimal. 1  419 ÷ 16 = 26 remainder 3 26 ÷ 16 = 1 remainder 10 1 ÷ 16 = 0 remainder 1 So, 41910 = 1A316 1.4 Converting Between Hexadecimal and Binary Hexadecimal numbers can be easily converted to binary numbers by converting each hex digit to its 4-bit binary equivalent. Example 3: Convert 0x2F to binary. 2F16 = 001011112 Conversely, to convert a binary number to hexadecimal, group the binary digits into sets of four, starting from the right, and convert each group to the corresponding hex digit. Example 4: Convert 11010110 to hexadecimal. 110101102 = 11010110 = D616 2 Uses of Hexadecimal Numbers Hexadecimal numbers are used in various areas of computing and digital electronics, such as: Memory addresses Color codes in web design Machine language code Debugging Hexadecimal provides a compact and readable way to represent binary values, which makes it easier for humans to read and understand large binary numbers. 2.1 Example 1 Convert 2F 416 to decimal: 2F 416 = 2 · 162 + F · 161 + 4 · 160 Here, F = 15, so 2F 416 = 2 · 256 + 15 · 16 + 4 = 512 + 240 + 4 = 75610 2 2.2 Example 2 Convert 4B916 to decimal: 4B916 = 4 · 162 + B · 161 + 9 · 160 Here, B = 11, so 4B916 = 4 · 256 + 11 · 16 + 9 = 1024 + 176 + 9 = 120910 2.3 Example 3 Convert 7A316 to decimal: 7A316 = 7 · 162 + A · 161 + 3 · 160 Here, A = 10, so 7A316 = 7 · 256 + 10 · 16 + 3 = 1792 + 160 + 3 = 195510 2.4 Example 4 Convert 1C716 to decimal: 1C716 = 1 · 162 + C · 161 + 7 · 160 Here, C = 12, so 1C716 = 1 · 256 + 12 · 16 + 7 = 256 + 192 + 7 = 45510 2.5 Example 5 Convert 3E516 to decimal: 3E516 = 3 · 162 + E · 161 + 5 · 160 Here, E = 14, so 3E516 = 3 · 256 + 14 · 16 + 5 = 768 + 224 + 5 = 99710 2.6 Example 6 Convert 9F 116 to decimal: 9F 116 = 9 · 162 + F · 161 + 1 · 160 Here, F = 15, so 9F 116 = 9 · 256 + 15 · 16 + 1 = 2304 + 240 + 1 = 254510 3 3 Operations of Binary Numbers 3.1 Addition Binary addition is similar to decimal addition but uses carry-over rules specific to base 2. 3.2 Tips **Carry Rules:** If the sum is 2 or more, you need to carry over: – 0+0=0 – 1+0=1 – 1 + 1 = 102 (carry 1 to the next higher bit) – 1 + 1 + 1 = 112 (carry 1 to the next higher bit) **Practice:** Perform several addition problems to get comfortable with the carry- over process. 3.2.1 Example 1 Add 10102 and 11012 : 1 0 1 0 + 1 1 0 1 1 0 1 1 1 Here, 10102 + 11012 = 100012. 3.2.2 Example 2 Add 11012 and 10112 : 1 1 0 1 + 1 0 1 1 1 1 0 0 0 Here, 11012 + 10112 = 110002. 3.2.3 Example 3 Add 101012 and 110112 : 1 0 1 0 1 + 1 1 0 1 1 1 0 0 0 0 0 Here, 101012 + 110112 = 1000002. 4 3.3 Subtraction Binary subtraction follows similar rules to decimal subtraction but uses borrowing rules specific to base 2. **Borrow Rules:** Binary subtraction involves borrowing from the next higher bit if the minuend bit is smaller than the subtrahend bit: 0−0=0 1−0=1 1−1=0 102 − 1 = 1 (borrow 1 from the next higher bit) **Negative Result:** If you need to subtract a larger number from a smaller one, use two’s complement for the correct result. 3.3.1 Example 1 Subtract 011012 from 101112 : −1 2 1 0 1 1 1 − 0 1 1 0 1 0 1 0 1 0 Here, 101112 − 011012 = 010102. 3.3.2 Example 2 Subtract 0112 from 1102 : −1 2−1 1 0 0 − 0 1 1 0 0 1 Here, 1002 − 0112 = 0012. 3.3.3 Example 3 Subtract 10012 from 11102 : −1 1 1 1 0 − 1 0 0 1 0 1 0 1 Here, 11102 − 10012 = 01012. 3.4 Multiplication Binary multiplication follows rules similar to decimal multiplication, but with base 2 arithmetic. 5 3.5 Tips Shift and Add: Binary multiplication is performed by shifting and adding. For each bit in the multiplier, shift the multiplicand and add it to the result: 0 × anything = 0 1 × anything = anything Practice with Examples: Work through several multiplication problems to get used to the process of shifting and adding. 3.5.1 Example 1 Multiply 1012 by 112 : 101 × 11 101 +1010 1111 Here, 1012 × 112 = 11112. 3.5.2 Example 2 Multiply 1012 by 112 : 1010 × 1100 0000 00000 101000 +1010000 1111000 Here, 1012 × 112 = 11112. 3.5.3 Example 3 Multiply 1102 by 1012 : 110 × 101 110 0000 +11000 11110 Here, 1102 × 1012 = 111102. 6 3.6 Division Binary division involves dividing a binary number by another binary number, similar to decimal division but with base 2 arithmetic. 3.7 Tips Long Division Method: Use a similar process to decimal long division, but only with binary digits: Compare the divisor to the portion of the dividend. If the divisor is less than or equal to the portion, place a 1 in the quotient and subtract. Bring down the next bit and repeat. Handle Remainders: In binary division, remainders are common. Ensure you un- derstand how to interpret and use them. ex1a.png ex1.png 3.8 Example 3 ex2.png 3.9 Example 4 ex3.png 3.10 Example 5 Divide 10100012 by 112 :
110112 112 10100012 112 1002 112 1002 112 112 112 0 7 Here, 10100012 ÷ 112 = 110112. 4 Logic What is Logic? Logic is the study of reasoning and the principles of valid inference. It provides a frame- work for analyzing the structure of arguments and determining whether conclusions follow from premises. Logic is foundational in mathematics, computer science, philosophy, and many other fields where clear and precise thinking is required. A computer may be pro- grammed to make decisions based on whether certain statements (eg. “There are 60 students registered”) are true or false. The truth or falsity of a statement is called it’s truth value. A statement is either true (T ) or false (F ). Some statements are compound statements, that is, they are composed of sub-statements and various connectives. 4.1 Propositions and Logical Connectives In logic, a proposition is a statement that can be either true or false, but not both. Propo- sitions are the building blocks of logical reasoning. Examples of propositions include: “Bananas are yellow.” “1 + 3 = 4.” Logical connectives are used to combine propositions and form more complex state- ments. The primary logical connectives are: 4.2 Conjunction (AND, ∧) The conjunction of two propositions P and Q (written as P ∧ Q) is true if and only if both P and Q are true. Consider two propositions P and Q. The truth tables for the conjunction P ∧ Q and the disjunction P ∨ Q are as follows: Truth Table for Conjunction (AND) P Q P ∧Q T T T T F F F T F F F F 4.3 Disjunction (OR, ∨) The disjunction of two propositions P and Q (written as P ∨ Q) is true if at least one of P or Q is true. 8 Truth table for Disjunction (OR): P Q P ∨Q T T T T F T F T T F F F 4.4 Negation (NOT, ¬) The negation of a proposition P (written as ¬P ) is true if P is false, and false if P is true. The negation operator, inverts the truth value of a proposition. If the proposition is true, its negation is false, and if the proposition is false, its negation is true. Consider a proposition P. The truth table for the negation ¬P is as follows: Truth table for Negation (NOT): P ¬P T F F T 5 Laws of the Algebra of Propositions The following laws apply to logical propositions. Identity Laws P ∧T =P P ∨F =P P ∧F =F P ∨T =T Idempotent Laws P ∧P =P P ∨P =P Complement Laws P ∧ ¬P = F P ∨ ¬P = T ¬T = F ¬F = T Double Negation (Involution) Law ¬(¬P ) = P 9  Commutative Laws P ∧Q=Q∧P P ∨Q=Q∨P Associative Laws (P ∧ Q) ∧ R = P ∧ (Q ∧ R) (P ∨ Q) ∨ R = P ∨ (Q ∨ R) Distributive Laws P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R) P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R) DeMorgan’s Laws ¬(P ∧ Q) = ¬P ∨ ¬Q ¬(P ∨ Q) = ¬P ∧ ¬Q Absorption Laws P ∧ (P ∨ Q) = P P ∨ (P ∧ Q) = P 5.0.1 Propositions and Truth tables By repetitive use of logical connectives (∧, ∨, ¬ and others to be discussed later), we can construct compound statements that are more involved. For example, 5.0.2 Example 1: Consider the compound statement: ¬(P ∧ ¬Q) where: P and Q are propositions. ∧ denotes AND. ¬ denotes NOT. The truth table for this compound statement is: P Q ¬Q P ∧ ¬Q ¬(P ∧ ¬Q) T T F F T T F T T F F T F F T F F T F T 10 5.0.3 Example 2: Consider the compound statement: (P ∧ ¬Q) ∨ R where: P , Q, and R are propositions. ∧ denotes AND. ∨ denotes OR. ¬ denotes NOT. The truth table for this compound statement is: P Q R ¬Q P ∧ ¬Q (P ∧ ¬Q) ∨ R T T T F F T T T F F F F T F T T T T T F F T T T F T T F F T F T F F F F F F T T F T F F F T F F 5.0.4 Tautologies and Contradictions A tautology is a proposition that only contains T in the last column of it’s truth table, that is, it is true for any truth values of it’s variables. A proposition is called a contradiction if it only contains F in the last column of it’s truth table. For example, the proposition “P or not P ”, that is, P ∨ ¬P , is a tautology and the proposition ““P ∧ ¬P ”is a contradiction. Here are their truth tables: Truth Table for P ∨¬P (Tautology): Truth Table for P ∧ ¬P (Contradic- tion): P ¬P P ∨ ¬P P ¬P P ∧ ¬P T F T T F F F T T F T F 5.1 IMPLICATION or CONDITIONAL (IF... THEN, →) A conditional statement represents an if...then statement where P is the hypothesis (antecedent), and Q is the conclusion (consequent). In essence, it is a statement that claims that if one thing is true, then something else is true also. Examples of these include “If it is sunny, then we will go to the beach.” “If the sky is clear, then we will be able to see the stars.” “Studying for the test is a sufficient condition for passing the class.” 11 5.1.1 Example: Truth Table for Implication Consider the proposition P → Q: P Q P →Q T T T T F F F T T F F T 5.2 BICONDITIONAL (IF AND ONLY IF, ↔) A biconditional statement, sometimes referred to as a bi-implication, may take one the following forms: ”P if and only if q“ ”P is necessary and sufficient for q“ ”If p then q, and conversely“ ”P iff q, where “iff” stands for “if and only if” 5.2.1 Example: Truth Table for Biconditional Consider the proposition P ↔ Q: P Q P ↔Q T T T T F F F T F F F T 5.3 Logical Equivalence (P ≡ Q ) We say two statements P and Q are logically equivalent if they have the same truth table. NOTE: Two logical formulas P and Q are logically equivalent,if and only if P ≡ Q is a tautology. 5.3.1 Example: Proving Logical Equivalence To prove that ¬(P ∧ Q) is logically equivalent to ¬P ∨ ¬Q, we can use truth tables. Truth Table for ¬(P ∧ Q) and ¬P ∨ ¬Q: Truth Table for ¬(P ∧ Q): P Q P ∧ Q ¬(P ∧ Q) T T T F T F F T F T F T F F F T 12  Truth Table for ¬P ∨ ¬Q: P Q ¬P ¬Q ¬P ∨ ¬Q T T F F F T F F T T F T T F T F F T T T By comparing the results in the last columns of both tables, we can see that ¬(P ∧ Q) and ¬P ∨ ¬Q have the same truth values for all possible truth values of P and Q. Therefore, ¬(P ∧ Q) ≡ ¬P ∨ ¬Q. 5.3.2 Exercise Show that (P → R) ∨ (Q → R) ≡ (P ∧ Q) → R 5.3.3 Example Consider the proposition ¬(P ∧ Q) ↔ (¬P ∨ ¬Q): P Q P ∧ Q ¬(P ∧ Q) ¬P ¬Q ¬P ∨ ¬Q ¬(P ∧ Q) ↔ (¬P ∨ ¬Q) T T T F F F F T T F F T F T T T F T F T T F T T F F F T T T T T 5.3.4 Example: Truth Table for (P ↔ Q) ↔ R Consider the proposition (P ↔ Q) ↔ R: P Q R P ↔ Q (P ↔ Q) ↔ R T T T T T T T F T F T F T F F T F F F T F T T F F F T F F T F F T T T F F F T F 5.4 Example: Truth Table for (P → Q) ↔ (¬Q → ¬P ) Consider the proposition (P → Q) ↔ (¬Q → ¬P ): P Q ¬Q ¬P P → Q ¬Q → ¬P (P → Q) ↔ (¬Q → ¬P ) T T F F T T T T F T F F F T F T F T T T T F F T T T T T 13 5.4.1 Example Consider the proposition (P ∨ ¬P ) ∧ (¬Q ∧ Q): P Q ¬P ¬Q P ∨ ¬P ¬Q ∧ Q (P ∨ ¬P ) ∧ (¬Q ∧ Q) T T F F T F F T F F T T F F F T T F T F F F F T T T T F 5.4.2 Example: Consider the proposition (P ∧ Q) ∧ (¬P ∨ ¬Q) ∧ (R ∧ ¬R): P Q R ¬P ¬Q R ∧ ¬R (P ∧ Q) ∧ (¬P ∨ ¬Q) ∧ (R ∧ ¬R) T T T F F F F T T F F F F F T F T F T F F T F F F T F F F T T T F F F F T F T F F F F F T T T F F F F F T T F F 5.5 Exercises 1. Show that (P → Q) ∨ (Q → P ) is a tautology. 2. Show that P → Q and ¬P ∨ Q are logically equivalent. 3. Determine if (P ∧ ¬Q) ∨ (¬P ∧ Q) is a tautology, a contradiction, or neither. Construct its truth table. 4. Show that (P ∧ Q) → (P ∨ Q) is a tautology. Construct its truth table. 5. Verify whether ¬(P ∧ Q) and (¬P ∨ ¬Q) are logically equivalent. Construct a truth table. 6. Determine whether (P → Q) ∧ (¬Q → ¬P ) is a tautology, contradiction, or neither. Construct its truth table. 7. Show that (P ↔ Q) ↔ ((P → Q) ∧ (Q → P )) is a tautology. 8. Prove that (P ∧ (Q ∨ R)) ≡ ((P ∧ Q) ∨ (P ∧ R)) using a truth table. 9. Determine if (P ↔ ¬Q) ∨ (Q ↔ ¬P ) is a tautology. Construct its truth table. 11. Show that (P → Q) ∧ (¬Q → ¬P ) is logically equivalent to P ↔ Q. Construct its truth table. 12. Determine whether the proposition (P ∧ Q) ∨ (¬P ∧ ¬Q) ∨ (P ↔ Q) is a tautology, a contradiction, or neither. Construct its truth table. 14  13. Prove that ¬(¬P ∨ Q) ≡ (P ∧ ¬Q) using a truth table. 14. Show that (P ↔ Q) ∧ (Q ↔ R) ∧ (P ↔ R) is a tautology. Construct its truth table. 5.6 Applications of Truth Tables Truth tables are used in various applications, including: Evaluating Logical Statements: Truth tables help verify the validity of logical statements and arguments. Designing Digital Circuits: In computer science and electrical engineering, truth tables are used to design and analyze digital circuits. Formal Proofs: Truth tables are essential in constructing formal proofs and un- derstanding logical equivalences. 15 6 Introduction to Sets A set is a collection of distinct objects, called elements. Sets are usually denoted by capital letters, and their elements are listed within curly brackets. For example: A = {1, 2, 3}, B = {x, y, z} If x is an element of set A, we write x ∈ A. If x is not an element of set A, we write x∈ / A. 6.1 Universal Set and Empty Set The universal set (denoted by U ) contains all elements under consideration in a par- ticular discussion. For example, if we are discussing the set of natural numbers, then U = N. The empty set (denoted ∅ or {}) is the set with no elements: ∅ = {} 6.2 Set Notation Sets can be described in two common ways: Roster or List notation: Listing all elements. Example: A = {1, 2, 3}. Set-builder notation: Describing the properties of elements. Example: A = {x | x is a natural number and x ≤ 3}. 6.3 Venn Diagrams Venn diagrams are used to visually represent sets and their relationships. Below is an example of a Venn diagram representing sets A and B. U A B 6.4 Operations on Sets 6.4.1 Union and Intersection The union of two sets A and B (denoted A ∪ B) is the set of all elements that belong to A, B, or both. A ∪ B = {x | x ∈ A or x ∈ B} 16  The intersection of two sets A and B (denoted A ∩ B) is the set of all elements that belong to both A and B (or that are common to A and B). A ∩ B = {x | x ∈ A and x ∈ B} Examples: 1. If A = {1, 2, 3} and B = {2, 3, 4}, then: A ∪ B = {1, 2, 3, 4}, A ∩ B = {2, 3} 2. If A = {a, b} and B = {b, c}, then: A ∪ B = {a, b, c}, A ∩ B = {b} 3. If A = {1, 3, 5} and B = {2, 4, 6}, then: A ∪ B = {1, 2, 3, 4, 5, 6}, A∩B =∅ 4. If A = {x | x is even} and B = {x | x is prime}, then A ∪ B includes all even and prime numbers, and A ∩ B = {2}. 6.4.2 Difference between Sets The difference of two sets A and B (denoted A − B or A \ B) is the set of all elements that belong to A but not to B. A − B = {x | x ∈ A and x ∈ / B} Examples: 1. If A = {1, 2, 3} and B = {2, 3, 4}, then: A − B = {1}, B − A = {4} 2. If A = {a, b, c} and B = {b, d}, then: A − B = {a, c}, B − A = {d} 3. If A = {1, 2, 3, 4} and B = {2, 4}, then: A − B = {1, 3}, B−A=∅ 6.5 Disjoint Sets Two sets are said to be disjoint if they have no elements in common, i.e., their intersection is the empty set. A∩B =∅ Examples: 1. If A = {1, 2, 3} and B = {4, 5, 6}, then A and B are disjoint because: A∩B =∅ 2. If A = {a, b} and B = {c, d}, then: A∩B =∅ 3. If A = {x | x is odd} and B = {x | x is even}, then A and B are disjoint sets. 17 6.6 Number of Elements in a Set The cardinality of a set refers to the number of elements in the set, denoted by |A| for a set A. Examples: 1. If A = {1, 2, 3}, then: |A| = 3 2. If B = {a, b, c, d}, then: |B| = 4 3. If C = ∅, then: |C| = 0 For infinite sets, such as the set of natural numbers N = {1, 2, 3, 4,... }, the number of elements is not finite, and we simply say that the set is infinite. 6.7 Complement of a Set The complement of a set A (denoted by Ac or A) is the set of all elements in the universal set U that are not in A. Ac = {x ∈ U | x ∈ / A} For example, if U = {1, 2, 3, 4, 5} and A = {1, 2}, then: Ac = {3, 4, 5} 6.8 Basic Set Identities The following are fundamental set identities: Identity Laws: A ∩ U = A, A∪∅=A Domination Laws: A ∪ U = U, A∩∅=∅ Idempotent Laws: A ∪ A = A, A∩A=A Complementation Law: (Ac )c = A Complement Laws: A ∪ Ac = U, A ∩ Ac = ∅ 18 6.9 Advanced Set Identities In addition to the basic identities, the following are key properties of set operations: Commutative Laws: A ∪ B = B ∪ A, A∩B =B∩A Associative Laws: A ∪ (B ∪ C) = (A ∪ B) ∪ C A ∩ (B ∩ C) = (A ∩ B) ∩ C Distributive Laws: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) Absorption Laws: A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A De Morgan’s Laws: (A ∪ B)c = Ac ∩ B c , (A ∩ B)c = Ac ∪ B c 6.10 Subsets A set A is said to be a subset of another set B (denoted as A ⊆ B) if every element of A is also an element of B. Formally, we can write this as: A⊆B if and only if for all x (x ∈ A implies x ∈ B) If A ⊆ B and A ̸= B, we say that A is a proper subset of B, denoted by A ⊂ B. This means that A is contained within B, but B contains elements not in A. Examples: 1. Let A = {1, 2} and B = {1, 2, 3, 4}. Since every element of A is also in B, we write: A⊆B 2. If A = {a, b} and B = {a, b, c, d}, then A is a subset of B because all elements of A are in B: A⊆B Moreover, A is a proper subset because A ̸= B: A⊂B 3. Let A = {x | x is an odd number} and B = Z (the set of all integers). Every odd number is an integer, so: A⊆B 4. If A = {1, 5} and B = {1, 2, 3}, then: A⊈B since 5 ∈ / B. 19 6.11 Power Set The power set of a set A, denoted by P(A), is the set of all possible subsets of A. This includes the empty set ∅ and A itself. If A has n elements, then the power set P(A) will contain 2n subsets. Examples: 1. If A = {1, 2}, then the power set of A is: P(A) = {∅, {1}, {2}, {1, 2}} Since A has 2 elements, the power set contains 22 = 4 subsets. 2. If B = {a, b, c}, then the power set of B is: P(B) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} Here, B has 3 elements, so the power set has 23 = 8 subsets. 3. If C = {x, y}, then the power set of C is: P(C) = {∅, {x}, {y}, {x, y}} C has 2 elements, so P(C) contains 22 = 4 subsets. 4. For the empty set ∅, its power set is: P(∅) = {∅} Since the empty set has no elements (zero elements), its power set contains 20 = 1 subset, which is the empty set itself. In general, if a set A has n elements, then the number of subsets of A (including the empty set and the set A itself) is 2n. 20 7 Functions 7.1 Definition A function (or mapping) from a set A to a set B is a relation f that assigns exactly one element of B to each element of A. This is denoted by: f :A→B For each element x ∈ A, there is a unique element f (x) ∈ B such that f (x) is the image of x under the function f. 7.2 Domain and Range The domain of a function f is the set A, which consists of all possible inputs for the function. The range (or image) of f is the set of all outputs of f , or more formally: Range of f = {f (x) | x ∈ A} 7.3 Types of Functions Functions can be classified into different types based on their properties: 7.3.1 Injective (One-to-One) Functions A function f : A → B is called injective (or one-to-one) if different elements in A map to different elements in B. In other words, if f (x1 ) = f (x2 ) implies that x1 = x2 , then f is injective. Example: Consider the function f : R → R defined by f (x) = 2x + 3. Suppose f (x1 ) = f (x2 ). Then: 2x1 + 3 = 2x2 + 3 =⇒ x1 = x2 Therefore, f is injective. 7.3.2 Surjective (Onto) Functions A function f : A → B is called surjective (or onto) if every element in B is mapped to by at least one element in A. In other words, the range of f is equal to B: Range of f = B Example: Consider the function g : R → R defined by g(x) = x3. √ For any y ∈ R, we can find x ∈ R such that g(x) = y. Specifically, x = 3 y. Thus, g is surjective because its range is all of R. 21 7.3.3 Bijective Functions A function f : A → B is called bijective if it is both injective and surjective. In other words, every element in A maps to a unique element in B, and every element in B is mapped to by exactly one element in A. Example: Consider the function h : {1, 2, 3} → {a, b, c} defined by: h(1) = a, h(2) = b, h(3) = c h is injective because no two elements in {1, 2, 3} map to the same element in {a, b, c}. h is surjective because every element in {a, b, c} is mapped to by some element in {1, 2, 3}. Therefore, h is bijective. 7.4 Proving that a Function is One-to-One (Injective) To prove that a function f : A → B is injective, we use the following approach: Assume that f (x1 ) = f (x2 ) for two elements x1 , x2 ∈ A. Show that this implies x1 = x2. If we can demonstrate that f (x1 ) = f (x2 ) implies x1 = x2 , then the function is injective. Formal Definition: For all elements x1 , x2 ∈ A, f (x1 ) = f (x2 ) =⇒ x1 = x2 This statement means that no two distinct (different) inputs can have the same output, which is the essence of a one-to-one function. 22 7.4.1 Example 1: Proving Injectivity of a Linear Function Consider the function f : R → R defined by: f (x) = 2x + 3 We will prove that this function is injective. Proof: Assume f (x1 ) = f (x2 ) for some x1 , x2 ∈ R. This means: 2x1 + 3 = 2x2 + 3 Subtract 3 from both sides: 2x1 = 2x2 Divide by 2: x1 = x 2 Since f (x1 ) = f (x2 ) implies x1 = x2 , the function is injective. 7.4.2 Example 2: Proving Injectivity of a Quadratic Function Consider the function f : R → R defined by: f (x) = x2 + 2 We will prove that this function is not injective. Proof: Assume f (x1 ) = f (x2 ), which means: x21 + 2 = x22 + 2 Subtract 2 from both sides: x21 = x22 This implies two possible cases: x1 = x2 or x1 = −x2 Since we can have x1 ̸= x2 and still f (x1 ) = f (x2 ) (for example, f (1) = f (−1) = 1), the function is not injective. 23 7.4.3 Example 3 Consider the function f : R → R defined by: f (x) = 3x3 + 2 We will prove that this function is injective. Proof: Assume f (x1 ) = f (x2 ), which means: 3x31 + 2 = 3x32 + 2 Subtract 2 from both sides: 3x31 = 3x32 Divide by 3: x31 = x32 Since the cube function is one-to-one, we conclude that: x1 = x 2 Therefore, the function f (x) = 3x3 + 2 is injective. 7.4.4 General Strategy for Proving Injectivity To prove that a function is injective: 1. Assume f (x1 ) = f (x2 ). 2. Manipulate the equation until you can conclude that x1 = x2. 3. If you can show this for all x1 , x2 ∈ A, then the function is injective. 24 8 Combinatorial Analysis Combinatorial analysis deals with counting the number of ways to arrange or select items from a set. The key concepts involved include factorial notation, binomial coefficients, permutations, and combinations. 8.1 Factorial Notation The factorial of a positive integer n, denoted n!, is the product of all positive integers less than or equal to n: n! = n × (n − 1) × (n − 2) × · · · × 1 Note that 0! = 1. Examples: 5! = 5 × 4 × 3 × 2 × 1 = 120 4! = 4 × 3 × 2 × 1 = 24 8.2 Binomial Coefficients The binomial coefficient, denoted nr , represents the number of ways to choose r
elements from a set of n elements without considering the order:   n n! = r r!(n − r)! Examples:   5 5! 5×4 = = = 10 2 2!(5 − 2)! 2×1   6 6! 6×5×4 = = = 20 3 3!(6 − 3)! 3×2×1   7 7! 7×6×5×4×3×2×1 = = = 35 4 4!(7 − 4)! (4 × 3 × 2 × 1)(3 × 2 × 1) 8.3 Permutations A permutation is an arrangement of objects where the order matters. The number of ways to arrange r objects out of n is given by: n! P (n, r) = (n − r)! Examples: 25  The number of ways to arrange 3 people out of 5 is 5! 5×4×3 P (5, 3) = = = 30 (5 − 3)! 2 The number of ways to arrange 4 letters from the set {a, b, c, d, e} is 5! 5×4×3×2×1 P (5, 4) = = = 120 (5 − 4)! 1! The number of ways to arrange 2 elements from {1, 2, 3} is 3! P (3, 2) = =6 1! Example: How many 4-letter “words” can you make from the letters {a, b, c, d, e, f} with no repeated letters? 6! 6×5×4×3 P (6, 4) = = = 360 (6 − 4)! 1 8.4 Permutations with Repetition (Partitions) When some objects are repeated, the formula for counting permutations is adjusted. If a set contains n objects, where some objects repeat r1 , r2 ,... , rk times, the number of distinct permutations is given by: n! Prep = r1 !r2 ! · · · rk ! Examples: The number of ways to arrange the letters of the word ”PEPPER” is: 6! 720 = = 60 3!2!1! 12 The number of ways to arrange the letters of the word ”BOOKKEEPER” is: 10! 3, 628, 800 = = 151, 200 2!2!3! 24 The number of ways to arrange the letters of ”SCHOOL” is: 6! 720 = = 360 2! 2 26 8.5 Combinations A combination is a selection of objects where the order does not matter. The number of ways to choose r objects from a set of n is given by: n! C(n, r) = r!(n − r)! Examples: The number of ways to choose 2 people from a group of 5 is 5! C(5, 2) = = 10 2!(5 − 2)! The number of ways to select 3 letters from {a, b, c, d, e} is 5! C(5, 3) = = 10 3!(5 − 3)! The number of ways to choose 4 students from a class of 8 is C(8, 4) = 70 8.6 Difference Between Permutations and Combinations The difference between permutation and combination is fundamental to understanding when to use each concept: Permutations are used when the order of arrangement matters. For example, the order of people in a line matters. Combinations are used when the order does not matter. For example, selecting a committee from a group of people, where the arrangement of members in the committee is not important. Examples: Permutation Example: Arranging 2 letters from {a, b, c}. The permutations are: ab, ba, ac, ca, bc, cb. There are 6 possible arrangements. Combination Example: Choosing 2 letters from {a, b, c}. The combinations are: ab, ac, bc. There are 3 possible selections. The formulas for permutations and combinations are: n! P (n, r) = (n − r)! n! C(n, r) = r!(n − r)! 27 9 Algorithms, Flowcharts, and Pseudocode 9.1 Algorithm An algorithm is a step-by-step set of instructions designed to perform a specific task or solve a problem. Think of it as a recipe that tells you exactly how to achieve a goal, like adding two numbers or sorting a list of items. Example of an Algorithm (Adding 2 numbers and displaying the result) Step 1: Take two numbers as inputs. Step 2: Add the two numbers. Step 3: Display the result. 9.2 What is a Flowchart? A flowchart is a visual representation of an algorithm. It uses symbols to represent different types of operations and arrows to show the flow of the process. Flowcharts help in understanding the flow of a program or process more clearly. Basic Flowchart Symbols Oval: Start/End of the program. Parallelogram: Input/Output operation. Rectangle: Processing step (calculation or action). Diamond: Decision-making (yes/no, true/false). Arrow: Direction of the flow. 28 9.3 Pseudocode Pseudocode is a way of writing algorithms in plain language, which helps programmers plan out their programs. It is not a real programming language but uses basic program- ming concepts to describe the steps of the algorithm. Example of a pseudocode(adding 2 numbers and displaying the answer) START INPUT firstNumber INPUT secondNumber sum = firstNumber + secondNumber PRINT sum END 9.4 Variables A variable is a placeholder used to store values that can change during the execution of a program. For example, you might have a variable x to store the value of a number, which can change as the program runs. 9.5 Constants A constant is a value that does not change throughout the program. It remains the same once it is defined. Constants are useful when you have fixed values like Pi (3.14159) or tax rates. Example: PI = 3.14159 9.6 Variable Names (Identifiers) Variable names, or identifiers, are the names you give to variables in your program. These names should be descriptive to make the code easy to understand. There are some rules for naming variables: Variable names must start with a letter (a-z, A-Z) or an underscore ( ). Variable names cannot contain spaces. They should not be keywords (reserved words in programming like if, while, etc.). Example total_sum = 0 userAge = 25 29 9.7 Compiler Language and Machine Language Compiler Language: High-level programming languages like Python, C, and Java are easy for humans to understand but need to be converted into a format that the computer can understand. This is done by a compiler, which translates the high-level language (called the source program) into machine language (called the object program). Machine Language: This is the binary code that the computer’s processor can directly understand and execute. 9.8 Source Program and Object Program Source Program: The original code written in a high-level language by the pro- grammer. Object Program: The translated code (in machine language) that the computer understands and can execute. Try to remember these!! Concept Definition Algorithm A step-by-step process to solve a problem. Flowchart A diagram that visually represents an algorithm using symbols. Pseudocode A simplified way of writing algorithms in a form close to plain English. Variable A storage location that can hold different values during program execution. Constant A value that does not change throughout the program. Compiler A tool that translates high-level code (source program) into machine language (object program). Source Program The original high-level code written by a programmer. Object Program The machine language code generated by the compiler. 9.9 Example: Adding two numbers and displaying the result Write the algorithm, the flowchart and the pseudocode 9.9.1 Algorithm 1. Start. 2. Input two numbers. 3. Add the two numbers. 4. Display the result. 5. End. 30 9.9.2 Flowchart Oval: Start Parallelogram: Input first number Parallelogram: Input second number Rectangle: Add the two numbers Parallelogram: Display the result Oval: End 9.9.3 Pseudocode START INPUT number1 INPUT number2 sum = number1 + number2 PRINT sum END 31 10 Probability and Statistics Probability is the branch of mathematics that deals with the likelihood of different outcomes in random events. 10.1 Sample Spaces and Events A sample space is the set of all possible outcomes of an experiment. An event is any subset of the sample space, representing a possible outcome or combination of outcomes. Examples 1. Coin Toss: Sample space for a coin toss = {Heads, Tails}. The event of getting a Head is {Heads}. 2. Die Roll: Sample space for rolling a six-sided die = {1, 2, 3, 4, 5, 6}. The event of rolling an odd number is {1, 3, 5}. 3. Card Draw: Sample space for drawing a card from a deck = {All 52 cards}. The event of drawing a spade is the set of 13 spades. 10.2 Finite Probability Spaces A finite probability space is one where the sample space has a finite number of out- comes, and each outcome has a probability assigned to it. The sum of all probabilities must equal 1. Number of outcomes in E P (E) = Total number of outcomes in the sample space Examples 1. Coin Toss: Probability of getting heads = P (Heads) = 12. 2. Die Roll: Probability of rolling a 4 = P (4) = 16. 4 1 3. Card Draw: Probability of drawing an Ace = P (Ace) = 52 = 13. 11 Conditional Probability Conditional probability is the probability of an event occurring given that another event has already occurred. If A and B are events, the conditional probability of A given B is denoted by P (A | B), and is calculated as follows: P (A ∩ B) P (A | B) = P (B) P (A ∩ B) is the probability that both events A and B occur. P (B) is the probability that event B occurs. This formula essentially adjusts the probability of event A based on the knowledge that B has already occurred. 32 1. Example (Card Draw) Suppose you are drawing a single card from a deck of 52 playing cards. If you are told that the card drawn is a spade, what is the probability that it is a 10? Solution Let event A be the event of drawing a 10. Let event B be the event that the card is a spade. In this case, we are interested in the conditional probability P (10 | Spade). The deck has 52 cards, and there are 13 spades in total. Since we’re told the card is a spade, the total possible outcomes are now reduced to 13 spades (this is P (B)). Of these 13 spades, only one is the 10 of Spades. So, the probability of drawing the 10 of Spades from the 13 spades is: 1 P (10 | Spade) = 13 1 This means, if we know the card is a spade, there is a 13 chance that it is the 10 of Spades. 2. Example (Rolling a die) Suppose you roll a six-sided die, and you are told that the result is an odd number. What is the probability that the result is a 3? Solution Let event A be the event that the result is a 3. Let event B be the event that the result is odd. The total possible outcomes of rolling a die are 6: {1, 2, 3, 4, 5, 6}. However, since we are told that the result is odd, the total possible outcomes are reduced to the odd numbers: {1, 3, 5}. This set of odd numbers is our sample space after event B occurs. There is 1 favorable outcome where the result is a 3 out of these 3 odd numbers. Hence, the conditional probability is: 1 P (3 | Odd) = 3 So, if we know the die shows an odd number, the probability that it is 3 is 13. 3. Example (Tossing a coin) Imagine you are tossing a fair coin twice. If you know that the first toss resulted in heads, what is the probability that the second toss also results in heads? Solution Let event A be the event that the second toss is heads. Let event B be the event that the first toss is heads. The possible outcomes for two tosses are: {HH, HT, TH, TT}. Since we know the first toss resulted in heads, we are only interested in the outcomes where the first toss is heads: {HH, HT}. 33  Out of these two outcomes, one of them results in the second toss being heads (i.e., HH). Thus, the conditional probability is: 1 P (Heads on 2nd toss | Heads on 1st toss) = 2 Therefore, knowing that the first toss resulted in heads does not affect the proba- bility of the second toss being heads, which remains 12. 11.1 Independence Two events A and B are independent if the occurrence of one does not affect the probability of the occurrence of the other. Mathematically, this is: P (A ∩ B) = P (A) · P (B) Examples: 1. Coin Toss: The outcome of the first toss is independent of the second toss. 2. Die Roll: Rolling a 4 on one die is independent of rolling a 2 on another die. 3. Card Draw: Drawing an Ace from one deck is independent of drawing a King from another deck. 11.2 Repeated Trials In repeated trials, the same experiment is performed multiple times. For independent trials, the probabilities remain the same for each trial. Examples: 1. Coin Toss: Tossing a coin 10 times. The probability of getting heads in each toss remains 12. 2. Die Roll: Rolling two dice 20 times. The probability of rolling a 6 on each roll is 1 6. 3. Card Draw: Drawing cards from a deck with replacement (meaning you place back the car into the deck before you draw again). The probability of drawing a 4 King remains 52. 34 12 Statistics Statistics is the study of data: how to collect, summarize, and interpret it. 12.1 Frequency Tables A frequency table summarizes the number of occurrences (frequencies) of different outcomes in a dataset. Examples: 1. Student Grades: A table showing how many students received each grade (A, B, C, etc.). 2. Survey Responses: A frequency table summarizing responses to a yes/no survey question. 3. Die Rolls: A table showing how often each number (1 to 6) was rolled after 100 trials. 12.2 Variance Variance is a measure of how spread out a set of data is. It is the average of the squared differences between each data point and the mean. n 1X Variance = (xi − µ)2 n i=1 12.3 Example: Calculating Variance Suppose we have the following dataset of exam scores: {70, 75, 80, 85, 90} To calculate the variance of this dataset, we follow these steps: Step 1: Calculate the Mean The mean µ of the dataset is the average of the numbers: 70 + 75 + 80 + 85 + 90 400 µ= = = 80 5 5 Step 2: Subtract the Mean from Each Data Point Next, we subtract the mean from each score to find the deviations 70 − 80 = −10, 75 − 80 = −5, 80 − 80 = 0, 85 − 80 = 5, 90 − 80 = 10 35 Step 3: Square Each Deviation (−10)2 = 100 (−5)2 = 25 02 = 0 52 = 25 102 = 100 Step 4: Find the Average of the Squared Deviations calculate the average of these squared deviations. This is known as the variance: 100 + 25 + 0 + 25 + 100 250 Variance = = = 50 5 5 Thus, the variance of the exam scores is 50. Step 5: Optional - Standard Deviation If we want to find the standard deviation, we take the square root of the variance: √ Standard Deviation = 50 ≈ 7.07 The variance of the dataset {70, 75, 80, 85, 90} is 50. The standard deviation is approxi- mately 7.07. 12.4 Median and Mode The median is the middle value in a sorted dataset. The mode is the value that appears most frequently in a dataset. Example Consider the following dataset of numbers representing the scores of stu- dents in a test: {85, 90, 76, 85, 92, 90, 85, 77, 89, 90, 92} Step 1: Arranging the Data in Ascending Order To calculate both the median and the mode, we first arrange the data in ascending order: {76, 77, 85, 85, 85, 89, 90, 90, 90, 92, 92} Step 2: Finding the Median The total number of data points in this dataset is 11 (n = 11), which is odd. When the number of data points is odd, the median is the middle value. The middle value is located at the position: n+1 11 + 1 12 = = =6 2 2 2 36  So, the median is the 6th value in the ordered dataset, which is: Median = 89 Mode The mode is the value that appears most frequently in the dataset. From the ordered dataset {76, 77, 85, 85, 85, 89, 90, 90, 90, 92, 92} We can see that both 85 and 90 appear 3 times, making them the most frequent values. Hence, this dataset is bimodal, and the modes are: Mode = 85 and 90 Things to remember Concept Definition Sample Space The set of all possible outcomes of an experiment. Event A subset of the sample space, representing a possible outcome. Finite Probability Space A probability space with a finite number of outcomes. Conditional Probability The probability of one event given that another event has occurred. Independence Two events are independent if the occurrence of one does not affect the other. Variance A measure of the spread of data points. Standard Deviation The square root of the variance. Median The middle value in a sorted dataset. Mode The most frequently occurring value in a dataset. 37