Discrete Structures · Unit 1 · 7 hrs
Basic Discrete Structures
Exam-focused notes for Basic Discrete Structures (Discrete Structures, CSC165): what the TU syllabus asks and how it has actually been tested, with 9 solved past questions from this unit.
What this unit covers
- Sets
- Sets and Subsets
- Power Set
- Cartesian Product
- Set Operations
- Venn Diagram
- Inclusion-Exclusion Principle
- Computer Representation of Sets
- Functions
- Basic Concept
- Injective and Bijective Functions
- Inverse and Composite Functions
- Graph of Functions
- Functions for Computer Science (Ceiling Function, Floor Function, Boolean Function, Exponential Function)
- Fuzzy Sets and Membership Functions
- Fuzzy Set Operations
- Sequences and Summations
- Basic Concept of Sequences
- Geometric and Arithmetic Progression
- Single and Double Summation
Injective and Bijective Functions
Determine whether the function f(x) = x-1 from set of integers to the set of integers is injective, surjective or bijective. Write the type of Fuzzy set operations with their definition. Give the floor and ceiling value of 1.2 and -1.2.[10]
- Function: $f(x) = x - 1$, with $f: \mathbb{Z} \to \mathbb{Z}$ (integers to integers) - Task 2: Types of fuzzy set operations with definitions - Values for floor/ceiling: $1.2$ and $-1.2$ All data present. Proceeding to solve. --- Assume $f(x1) = f(x2)$: $...
Full solved answer →How do you plot the function on graph? Determine whether the function $f(x) = x^2$ is injective, surjective or bijective with reasons. Solve the recurrence relation $a_n = 6a_{n-1} + 9a_{n-2}$ with initial conditions $a_0 = 1, a_1 = 6$. [10]
- Function: $f(x) = x^2$ (domain and codomain taken as $\mathbb{R} \to \mathbb{R}$) - Recurrence: $an = 6a{n-1} + 9a{n-2}$ - Initial conditions: $a0 = 1$, $a1 = 6$ --- Steps: 1. Choose several $x$-values from the domain. 2. Compute $f(x)$ for each to form o...
Full solved answer →Inclusion-Exclusion Principle
Explain the principle of inclusion and exclusion. How many integers from 1 to 30 are multiples of 2 or 3? [5]
- Range of integers: 1 to 30 - Divisibility conditions: multiples of 2 or multiples of 3 The Principle of Inclusion and Exclusion is a counting technique for finding the number of elements in the union of finite sets. When we add the sizes of individual set...
Full solved answer →Define ceiling and floor function. Why do we need Inclusion - Exclusion principle? Make it clear with suitable example. [5]
--- The floor function for any real number x is defined as the greatest integer less than or equal to x. It is denoted by ⌊x⌋. Examples: - ⌊3.5⌋ = 3 - ⌊-2.4⌋ = -3 (since -3 is the greatest integer less than or equal to -2.4) - ⌊3.143⌋ = 3 --- The ceiling fu...
Full solved answer →Functions for Computer Science
Give the example of ceiling, floor and boolean function. How do you plot the graph of the function? [5]
The floor function for any real number x is defined as the greatest integer less than or equal to x. It is denoted by ⌊x⌋. Expression Value Reason --------- ⌊3.5⌋ 3 Greatest integer ≤ 3.5 is 3 ⌊-2.4⌋ -3 Greatest integer ≤ -2.4 is -3 ⌊3.143⌋ 3 Greatest integ...
Full solved answer →Venn Diagram
Represent any three set operations using Venn-diagram. Give a recursive defined function to find the factorial of any given positive integer. [5]
--- The union of sets A and B contains all elements that belong to A or B (or both). A ∪ B = { x x ∈ A or x ∈ B } The entire shaded area of both circles represents A ∪ B. --- The intersection of sets A and B contains only the elements common to both A and B...
Full solved answer →Computer Representation of Sets
Consider a set U = {1,2,3,4,5,6,7,8,9,10}. What will be the computer representation for set containing the numbers which are multiple of 3 not exceeding 6? Describe injective, surjective and bijective function with examples.[10]
- Universal set $U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ - Required set: numbers that are multiples of 3 not exceeding 6 --- Step 1 - Identify the required set Multiples of 3 that are $\leq 6$: - $3 \times 1 = 3$ ✓ - $3 \times 2 = 6$ ✓ - $3 \times 3 = 9$ (ex...
Full solved answer →Basic Concept
Define function. Let $f_1$ and $f_2$ be function from $\mathbb{R}$ to $\mathbb{R}$ such that $f_1(x) = x^2$ and $f_2(x) = x - x^2$. What are the functions $f_1 + f_2$ and $f_1 \cdot f_2$? [5]
- $f1, f2 : \mathbb{R} \to \mathbb{R}$ - $f1(x) = x^2$ - $f2(x) = x - x^2$ - Required: $f1 + f2$ and $f1 \cdot f2$ All data present. --- A function $f$ from a set $A$ to a set $B$ is an assignment that maps to each element $x \in A$ exactly one element $f(x...
Full solved answer →Fuzzy Sets and Membership Functions
Explain fuzzy set with example. How do you find complement of a fuzzy set? [5]
A fuzzy set is a set where each element has a degree of membership (also called membership value) that ranges between 0 and 1, rather than the classical (crisp) set where an element either belongs or does not belong to a set. In a classical set, membership ...
Full solved answer →Make Unit 1 stick
Practice CSC165 with flashcards & quizzes