Discrete Structure By Sir Jawad 2nd Semester PDF

# Semester #02 Discrete Structures Notes ## Def: Discrete Structures Refers to a branch of mathematics that studies objects that can be counted, are finite and distinct from one another. These structures are fundamentally discrete rather than continuous. ## Examples: Sets - A collection of finit...

# Semester #02 Discrete Structures Notes ## Def: Discrete Structures Refers to a branch of mathematics that studies objects that can be counted, are finite and distinct from one another. These structures are fundamentally discrete rather than continuous. ## Examples: Sets - A collection of finite and distinct objects - Set of natural No S = {1, 2, 3.....} - Set of courses in Sem 2 = {200P, DLD, DS} ### Discrete ### Continuous A line illustrating discrete values with dots steadily increasing in value. A line illustrating continuous values with a smooth, increasing curve. ## Graph theory A graph is a data structure consisting of nodes (also called vertices) connected by edges. ### Mathematically, G₁ = (V, E) ## Types of graph: 1. **Directed graph:** A graph in which the direction of an edge is defined to a particular node is a directed graph. - A diagram showing a graph with three nodes marked A, B, and C. Nodes A and B are connected in a single direction with a line marked 1. Nodes B and C are connected in a single direction with a line marked 1. - Another diagram showing a graph with four nodes marked A, B, C, and D. Node A is connected to node D in a single direction, node D is connected to node B in a single direction, and node B is connected to node C in a single direction. 2. **Undirected graph:** A graph in which edges have no direction, meaning the edges do not have arrows indicating the direction. - An example is when you add a friend on Facebook. Both have full access to each other's content. - A diagram showing a graph with five nodes marked A, B, C, D, and E. Node A is connected to node B, node B is connected to node C, and node C is connected to node D, with an arrow on each end of each line indicating the direction. Node E is connected to node C and node D with a single direction arrow. 3. **Complete graph:** A graph in which each vertex is connected to every other vertex. - An example is a tournament graph where every player plays against every other player. - Two diagrams are shown with vertices A, B, and C, and vertices A, B, C, and D. The first diagram shows vertices A, B, and C connected with each other by lines. The second diagram shows all the vertices in the graph connected with each other by lines. ### Edges in a Complete graph: n(n-1)/2 4. **Weighted graphs:** A graph in which edges have weights or costs associated with them. - An example is a road network graph where the weights can represent the distance between two cities. - A diagram showing a graph with three nodes, A, B, and C. Node A is connected to node B with a line annotated 2, node A is connected to node C with a line annotated 4, and node B is connected to node C with a line annotated 3. Below the image is the text: weighted graph. - A diagram showing a graph with three nodes, A, B, and C. Node A is connected to node B with a line, node A is connected to node C with a line, and node B is connected to node C with a line. Below the image is the text: unweighted graph. ## Loop in the graph In graph theory, a loop (also called a self-loop or a buckle) is an edge that connects a vertex to itself. - A diagram showing a graph with four nodes marked A, B, C, and D. Node A is connected to node B, node A is connected to node C, and node C is connected to node D using lines with arrow indicators. Node A is connected to itself using a curved line with an arrow indicator. ## Degree of a graph It is the number of vertices adjacent to a vertex. ### Notation = deg (V) ## Degree of undirected graph - A diagram showing a graph with five nodes marked a, b, c, d, and e. Node a is connected to node b and node d with a line. Node b is connected to node a, node c, and node d with a line. Node c is connected to node b with a line. Node d is connected to node a and node b with a line. Node e is not connected to any other node. ### deg(a) = 2, deg(d) = 2 ### deg(b) = 3 ### deg(e) = 0 [Isolated vertex] ### deg(c) = 1 [Pendent vertex] # Do it by yourself: - a diagram showing a graph with eight nodes marked a, b, c, d, e, f, g, and h. Node a is connected to node b, node c, and node e with a line. Node b is connected to node a, node d, and node e with a line. Node c is connected to node a, and node d with a line. Node d is connected to node b, node c, and node f with a line. Node e is connected to node a, node b, and node f with a line. Node f is connected to node d, node e, and node g with a line. Node g is connected to node f and node h with a line. Node h is connected to node g with a line. ## Degree of Directed graph ### Indegree of a graph Indegree of a vertex is the number of edges that are coming into the vertex. ### Notation: deg -(V) ### Outdegree of a graph: Outdegree of a vertex is the number of edges that are going out from the vertex. ### Notation = deg+(V) - A diagram showing a graph with eight nodes marked a, b, c, d, e, f, g, and h. Node a is connected to node b with a single direction arrow, node a is connected to node c with a single direction arrow, node c is connected to node b with a single direction arrow, node c is connected to node d with a single direction arrow, node d is connected to node e with a single direction arrow, node e is connected to node f with a single direction arrow, node f is connected to node g with a single direction arrow, and node g is connected to node a with a single direction arrow. | Vertex | Indegree | Outdegree | | ------ | -------- | --------- | | a | 1 | 2 | | b | 2 | 0 | | c | 2 | 2 | | d | 1 | 1 | | e | 1 | 1 | | f | 1 | 0 | | g | 1 | 1 | # Do it by yourself: - a diagram showing a graph with six nodes marked a, b, c, d, e, and f. Node a is connected to node b with a double direction arrow, node a is connected to node c with a single direction arrow, and node b is connected to node d with a single direction arrow, node d is connected to node e with a single direction arrow, and node e is connected to node f with a single direction arrow. ## Adjacency Matrix An adjacency matrix is a square NXN size matrix where N is the numbers of nodes in the graph, and it is used to represent the connection between the edges. - A diagram showing a graph with three nodes marked 1), 2), and 0). Node 1) is connected to node 0) with a line, and node 2) is connected to node 0) and node 1) with a line. Below the graph there is the text: undirected graph. A table is shown below the graph with rows 0) 1) 2) and columns marked 0) 1) 2). In this table, values are shown as follows: - 0) 0 1 1 - 1) 1 0 1 - 2) 1 1 0 - A diagram showing a graph with three nodes marked 1), 2) and 0). Node 1) is connected to node 2) with a double direction arrow. Node 2) is connected to node 0) with a single direction arrow. There is the text: Adjacency matrix below the image. A table is shown below the graph with rows 0) 1) 2) and columns marked 0) 1) 2). The table contains the following values: - 0) 0 0 0 - 1) 0 0 1 - 2) 1 1 0 <start_of_image> Diagrams can be generated using tools like Graphviz and other popular charting libraries. ## Trees A tree is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes. - A diagram showing a tree-like structure with the root node at the top labeled A. Node B is a child of node A. Node C is also a child of node A. Node D is a child of node B. Node E is a child of node B. Node F is a child of node C. Node G is a child of node C. Node H is a child of node G. Node I is a child of node D. Node J is a child of node D. Node K is a child of node E. The text: 'Root' is annotated above the root node A. The text: 'Children' is annotated below node I. The text: 'Parent node' is annotated to the left of node D. The text: 'Subtree' is annotated to the right of node I. The text: 'Siblings' is annotated to the right of node G. The text: 'Leaf nodes' is annotated below node K and node H. ## Terminologies in trees: 1. **Root node:** The topmost node of a tree or the node which doesn't have any parent node. 2. **Parent node:** The node that has a direct connection to one or more child nodes. - For example, D, E and are the child nodes of . 3. **Leaf node:** The nodes which doesn't have any child nodes. - For example, are the leaf nodes. 4. **Sibling:** Children of the same parent node. - For example, are siblings. 5. **Level of a node:** The count of edges on the path from the root node to that particular node. The root node has level 0. 6. **Subtree:** A portion or part of a tree. ## Binary Tree A binary tree is a hierarchical structure in which each node has at most two children, referred to as the left child and the right child. - A binary tree is shown with the root node labelled 1. Node 2 is the left child of node 1. Node 3 is the right child of node 1. Node 4 is the left child of node 2 and node 5 is the right child of node 2. Node 6 is the left child of node 3 and node 7 is the right child of node 3. Node 8 is the left child of node 4 and node 9 is the right child of node 4. Node 10 is the left child of node 5 and node 11 is the right child of node 5. Node 12 is the left child of node 6 and node 13 is the right child of node 6. Node 14 is the right child of node 7. ## Recursion It's a function that calls itself to solve a smaller part of the big problem. **The key to recursion is that the problem is divided into smaller sub-problems until a base case is reached, which stops the recursion.** **Example:** 4! - 4! = 4 x 3! - 3! = 3 x 2! - 2! = 2 x 1! - 1! = 1 (Base case) ## Recursive definition of Binary Tree A binary tree is either: 1. Empty (null or None) 2. a node containing: - A value (data) - A left subtree (which is a binary tree) - A right subtree (which is a binary tree) **Each subtree is itself a binary tree, recursively defined in the same way until reaching empty trees (base case).** ## Applications of Binary Trees 1. **File Compression ZIP, JPEG and MP3** 2. **Scheduling Systems**, **Finding the shortest path** 3. **Organizational hierarchy** 4. **File system Directories** ## Permutation and Combination Ways of selecting items from a set. ### Permutation The arrangement of objects in a specific order. When order matters, it is called permutation ### Formula: P(n, r) = n! / (n-r)! - n = total No of objects - r = objects selected. ### Combination The selection of objects where the order does not matter (choose). ### Formula: C(n, r) = n! / r! (n-r)! ### Example 1: How many ways can you arrange 3 out of 5 books on a shelf? - P(n, r) = n! / (n-r)! - P(5, 3) = 5! / (5-3)! - = 5 x 4 x 3 x 2 x 1! / 2 x 1! - = 60 ### Example 2: How many ways can you select 3 people from a group of 5 for a team? - C(n, r) = n! / r! (n-r)! - C(5, 3) = 5! / 3! (5-3)! # Lecture # 05 Logic ## Logic: In discrete structures, logic is a fundamental area that focuses on reasoning and solving problems. Logic helps determining the truth or falsity of a statement. ## Proposition: A declarative statement that is either true or false. - The sky is blue - (True) - 2 + 2 = 5 (False) ## Types of propositions: ! * Simple proposition: A statement that cannot be broken down into smaller statements. It contains no logical connectives (OR, AND). It conveys a single idea that is either true or false. **Example:** *The earth orbits the sun.* * 2 is an even number.* * Compound proposition: Combining two or more simple propositions using logical connectives such as (AND, OR, NOT). **Examples:** *It is raining and it is cold.* *I will study or I will go to the gym.* ## Let's understand proposition: Is this a proposition? - y > 5 (**False**) - Ahmad is a name (**True**) - 7 x = 21 when = 4 (**False**) - 4 + 9 = 13 (**True**) - Answer the Question (No proposition) - y² = 4 is equal to 16 (**True**) # Date 2/oct/2024 Conjunction: (AND) If p and q are two statements, then the conjunction of p and q is the compound statement, denoted by P∧Q and read as p and q. The compound statement P∧Q is true when both P and Q are true. - **Example:** *Ali is a student and he is a topper of the class.* ## Truth table: Total No of rows = 2ⁿ | P | q | P∧Q | |----|----|------| | T | T | T | | T | F | F | | F | T | F | | F | F | F | ## Truth table for 3 statements : P, q, R statements # Date: 18 # Disconjunction (OR): If P and q are two statements, the disjunction of P and q is the compound statement denoted by Pvq. The statement Pvq is true if at least one of P or Q is true. - **Example:** *He will go to Peshawar or Lahore.* ## Truth table: | P | q | Pvq | |---|---|-----| | T | T | T | | T | F | T | | F | T | T | | F | F | F | # Date 19 Negation (NOT): If P is any proposition, the negative of P denoted by ~P or ¬P and read as *not P*, is a proposition, which is false when P is true and true when P is false. - **Example:** - P = Today is Tuesday; - ~P = Today is not Tuesday ## Truth table: | P | ¬P | |---|---| | T | F | | F | T | # Do It By Yourself! 1. 5 + 1 = 6 → 5 + 1 ≠ 6; 2. Some people have no scooter. → Every person has a scooter. # Date 20 Logical Equivalence: Refers to a situation where two statements or propositions always have the same truth value. ## Question 1: Prove that ¬(Pvq) = ¬P∧¬q ### Let’s construct a truth table: | P | q | Pvq | ¬(Pvq) | ¬P | ¬q | ¬P∧¬q | |----|----|-----|-------|----|----|-------| | T | T | T | F | F | F | F | | T | F | T | F | F | T | F | | F | T | T | F | T | F | F | | F | F | F | T | T | T | T | **Hence proved ¬(Pvq) = ¬P∧¬q. Thus they are logically equivalent.** # Do it by yourself: 1. ¬(¬P) = P 2. ¬(¬Pvq) = (P∧¬q) 3. ¬(P∧q) = (¬P)V(¬q) # Date 9/oct/24 Conditional Proposition: If P and Q are proposition, the compound proposition “if P then Q”, denoted by P→Q is called a conditional proposition or implication. The proposition P is called antecedent or hypothesis and the proposition Q is called consequent or conclusion. - **Example:** - If tomorrow is Sunday then today is Saturday. - If it rains then I will carry an umbrella. ## Truth table | P | Q | P→Q | |---|---|-----| | T | T | T | | T | F | F | | F | T | T | | F | F | T | # Solve it: Pv¬q→P # Date 22 Biconditional Statement: If P and Q are statements, then the compound statement “P if and only if Q”, denoted by P↔Q is called a biconditional statement. - **Example:** *He swims if and only if, the water is warm*. ## Truth table: | P | Q | P↔Q | |---|---|-----| | T | T | T | | T | F | F | | F | T | F | | F | F | T | # Solve it: ¬(P∧Q)↔(¬P)V(¬Q) ## Tautology A statement that is always true. ## Example: - R V (¬R) - ¬(R∧Q)→(¬R)V(¬Q) # Date 23 Symbolic logic: - Symbolic logic is a branch of logic that uses symbols to represent logical expressions and reasoning. ## Contradiction: A contradiction is a statement that is always false. - R Λ ¬(R) - ¬(¬PΛQ) ↔ (¬P)V(¬Q) **The negation of any tautology is a contradiction, and the negation of any contradiction is a tautology.** ## Symbolic logic 1. John is a great singer. (P) 2. John is a great singer and pilot. (P∧Q) 3. Dogs don’t like cats. (¬D) 4. If it is raining then the roads are wet. (P→Q) 5. John is studying hard and he is not the topper. (P∧¬Q) 6. I will jump off the mountain if and only if you do. (P↔Q) 7. School is closed if more than 2 feet of snow falls or if the wind chill is below -100. (Q∧R→P) # Lecuture # 06 Predicate Logic ## Predicate Logic Prepositional logic is not enough to express the meaning of all statements in mathematics, and natural language. - **Example:** *15 x>1 true or false?* *Is x a "great tennis player"? True or false?* ## Predicate: A predicate P(x) is a sentence that contains a finite number of variables, and becomes a proposition when specific values are substituted for the variables. Where P(x) is propositional function. X is a propositional variable. ## Question: Let P(x) denote the statement x ≥ 10, what are truth values of P(11) and P(5)? - P(x)=x≥10 - P(10) = 10 ≥ 10 (false) - P(11) = 11 ≥ 10 (True) ## Quantifiers Quantifiers are words that refer to quantities, such as “some” or “all”. It tells for how many elements a given predicate is true ## Types of Quantifiers: 1. Universal quantifier: The phrase “for all” denoted by ∀ is called universal quantifiers. 2. Existential quantifier: The phrase “there exists” denoted by ∃ is called existential quantifiers. ## Example 1: Let P(x) be a statement x+1>x - P(1) = 1+1>1 - P(1)=2>1 (T) - P(2)=2+1>2 - P(x) = 3>2 (+) P(x) is true for positive integers. ### ∀x P(x) " for all x +ve integers. ## Example 2: Let Q(x) be the statement x<2 - Q(1) = 1<2 (T) - Q(2) = 2<2 (False) Q(x) is true for x = 1. ### ∃x Q(n) *There exists some x for which Q(x) is true* ## Types of Quantifiers 1. **Universal Quantifier:** The phrase “for all” denoted by ∀ is called a universal quantifier. 2. **Existential Quantifier:** The phrase “there exists” denoted by ∃ is called an existential Quantifier. ## Question: Let D = {1, 2, 3, ....., 9} Determine the truth value of each of the following statements. - (∀x ∈D), x+4<15 - (∃x ∈D), x+4 = 10 - (∀x ∈D), x+4 ≤ 10 - (∃x ∈D), x+9 ≥ 15 # Do it by yourself # Date 16/oct/24 # A rule of inference: In inference, a rule or a transformation rule is a logical form, consisting of a function which takes premises, analyzes their syntax, and returns a conclusion. - **Example:** *If you have a current password, then you can log on to the network.* - The final statement of the argument must follow from the truth of the preceding statements or premises. ## Rules of Inference 1. **Modus Ponens:** The modus ponens is one of the most rules of inference and it states that if P and P→Q is true, then we can infer that Q will be true. It can be represented as: - **Example:** - Statement 1: If I am sleepy then I go to bed. (P→Q) - Statement 2: I’m sleepy. (P) - Conclusion: I go to bed (Q) -* Hence, we can say that if P→Q is true and P is true then Q will be true.* ## Truth Table | P | Q | P→Q | |---|---|-----| | T | T | T | |T | F | F | | F | T | T | | F | F | T | 2. **Modus Tollens:** The modus tollens rule states that if P→Q is true and ¬Q is true then ¬P will also be true. - **Example:** - Statement 1: If I am sleepy then I go to bed. (P→Q) - Statement 2: I do not go to the bed (¬Q) - Statement 3: I am not sleepy (¬P) ## Truth table: | P | Q | ¬P | ¬Q | P→Q | |---|---|---|---|-----| |T | T | F | F | T | |T | F | F | T | F | |F | T | T | F | T | |F | F | T | T | T | 3. **Hypothetical Syllogism:** The hypothetical syllogism rule states that if P→Q is true whenever P→Q, and Q→R is true. - **Example:** - Statement 1: If you have my home key, then you can unlock my home. (P→Q) - Statement 2: If you can unlock my home, then you can take my money. (Q→R) - Conclusion: If you have my home key then you can take my money (P→R) ## Truth Table: | P | Q | R | P→Q | Q→R | P→R | |---|---|---|---|---|---| | T | T | T | T | T | T | | T | T | F | T | F | F | | T | F | T | F | T | T | | T | F | F | F | T | T | | F | T | T | T | T | T | | F | T | F | T | F | T | | F | F | T | T | T | T | | F | F | F | T | T | T | 4. **Disjunctive Syllogism:** The disjunctive syllogism rule states that if Pvq is true and ¬P is true, then Q will be true. - **Example:** - Statement 1: Today is Sunday or Monday (Pvq) - Statement 2: Today is not Sunday. (¬P) - Conclusion: Today is Monday (Q) ## Truth Table: | P | Q | ¬P | Pvq | |---|---|---|---| | T | T | F | T | | T | F | F | T | | F | T | T | T | | F | F | T | F | 5. **Addition:** The addition rule is one of the common inference rule and it states that if P is true, then PVQ will be true. - **Example:** - Statement 1: I have a vanilla ice cream (P) - Statement 2: I have chocolate ice cream (Q) - Conclusion: I have vanilla or chocolate ice cream (P∨Q) ## Truth Table: | P | Q | Pvq | |---|---|-----| | T | T | T | | T | F | T | | F | T | T | | F | F | F | 6. **Simplification:** The simplification rule states that if P∧Q then P and Q will also be true. - **Example:** He studies hard and he is the best boy in the class (P∧Q) ## Truth Table | P | Q | P∧Q | |---|---|-----| | T | T | T | | T | F | F | | F | T | F | | F | F | F | 7. **Constructive Dilemma:** If (P→Q)∧(R→S) and PvR are two premises, we can use constructive dilemma to derive QvS. - **Draw truth table by yourself!** 8. **Destructive Dilemma:** If (P→Q)∧(R→S) and ¬Qv¬S are 2 premises, we can use destructive dilemma to derive ¬Pv¬R. - **Example:** - If it rains, I will take a shower (P→Q) - If it is hot outside, I will go for a shower (R→S) - Either it will rain or it is hot outside (PvR) - Conclusion: I will take a leave or I will go for a shower (QvS). - **Example:** - If it rains, I will take a shower (P→Q) - If it is hot outside, I will go for a shower (R→S) - Either I will not take a leave or I will not go for a shower (¬Qv¬S) - Therefore either it does not rain or it is not hot outside (¬Pv¬R) - **Draw truth table, try it!** # Date 24/oct/24 Sets A set is a collection of well-defined and distinct objects. Sets are denoted by capital letters (eg A, B, C) and their elements are listed within curly braces { }. - Set of Binary No = {0, 1} - Set of Fruits = {Apple, mango, Peach} ## Basic Terminologies: 1. **Element:** An object that belongs to a set. - A = {1, 2, 3, 4, 5, 6} - 6 ∈ A (True) - 9 ∈ A (False) - 3 ∉ A (False) 2. **Subset:** A set whose elements are all contained in another set. - A = {1, 2, 3, 4} - B = {1, 2, 3} ### Notation: B ⊂ A 3. **Empty Set:** A set with no elements. - Φ = { } 4. **Universal Set:** The set that contains all the elements under consideration. - **Example:** If you are considering natural numbers, the universal set might be U = {1, 2, 3.....} ## Operations on Sets: 1. **Union of Sets:** Union of two sets A and B is the set of elements which belong to A or to B or to both. - A= {2, 3,4}, B = {1, 3, 5, 7} - A∪B = {1, 2, 3, 4, 5, 7} 2. **Intersection of Sets:** Intersection of A and B is the set of elements which belong to both A and B, written as A∩B. - A = { 1, 2, 3, 5 }, B = { 2, 3, 5, 6 } - A∩B = { 2, 3, 5 } 3. **Difference of Two Sets:** If A and B are two sets, their difference: - A–B is the set of elements which belong to A but not to B set. - B–A is the set of elements which belong to B but not to A. - A = {2, 3, 4}, B = {1, 3, 5, 7} - A-B = {2, 4} - B-A = {1 ,5 , 7} **A-B = {x: x ∈A and x ∉ B}** **B-A = {x: x ∈B and x ∉ A}** 4. **Complement of a set:** The set that consists of all the elements from the universal set which are not already included in the given set S’ = U-S - **Example:** Find the complement of Set S = {4, 8, 12, 16}, where the universal set is all multiples of 4 that are smaller than 50? - U = {4,8,12,16,20,24,28,32,36,40,44,48} - S = {4, 8 , 12, 16} - S’ = U-S = {20, 24, 28, 32, 36, 40, 44, 48} - A Venn diagram represents the relationship between sets. Each set is represented as a circle. The overlapping area of the circles represents the intersection of the sets. - A Venn diagram is shown with a rectangle representing the universal set U. Inside the rectangle are two intersecting circles marked A and A’. The overlapping space is labeled A. The space outside both circles is labeled A’. ## Sets Identities: 1. (A’)’ = A 2. A∪A = A (Idempotent Law) 3. A∩A = A (Idempotent Law) 4. **Identity laws:** - A∪Φ = A - A∩U = A 5. **Commutative laws:** - A∪B = B∪A - A∩B = B∩A 6. **Associative laws:** - A∪(B∪C) = (A∪B)∪C - A∩(B∩C) = (A∩B)∩C 7. **Distributive laws:** - A∪(B∩C) = (A∪B)∩(A∪C) - A∩(B∪C) = ( A∩B)∪ (A∩C) 8. **De Morgan’s laws:** - (A∪B)’ = A’∩B’ - (A∩B)’ = A’∪B’ # Date 30/oct/24 Product rule or Cartesian Product The Cartesian product of two sets is defined as follows: if two sets {a1, a2, … ,an} and {b1, b2, … , bn} are equal if and only if they contain exactly the same elements in the same order. - **Example 1:** - A = {good, bad}, B = {Student, prof} - AxB = {(good, student), (good, prof), (bad, Student), (bad, prof)} - **Example 2:** - A = {x, y, z}, B = {a, b, c} -