Discrete Mathematics
Terminology and Symbols
Learning Objectives:
- Understand notations related to set representation and operations.
- Perform the operations of union, intersection, complement, and difference on sets.
- Be able to draw and interpret Venn diagrams of set relations and operations and use Venn diagrams to solve problems.
Number Sets:
N = {1, 2, . . .}, the set of Natural numbers;W = {0,1,2,...}, the set of whole numbers
Z = {0,1,−1,2,−2,...}, the set of Integers;
Q =${\dfrac{p}{q}}$ :p,q∈Z, q $\neq$ 0,the set of Rational numbers;
R = the set of Real numbers; and
C = the set of Complex numbers.
We will use $\phi$ to denote an empty set.
Operations on Sets:
Union: Denoted by $\cup$ symbol, such as $A \cup B$.Intersection: Denoted by $\cap$ symbol, such as $A \cap B$
Symbols Used in Set Theory:
- To list the elements in a set, we use { } brackets.
- Subset : $\subseteq$
- Not subset: $\nsubseteq$
- Proper subset: $\subset$
- Not Proper subset: $\not\subset$
Solved Example: 9206-01
If A = {1, 2, 3} and B = {3, 6, 8} then $(A\cap B) \times A$ is:
A. {(1, 3), (2, 3), (3, 3)}
B. {(3, 1), (3, 2), (3, 3)}
C. {(1, 3), (3, 1), (3, 2)}
D. None of these
\begin{align*} (A \cap B) &= \{3\}\\ (A \cap B) \times A &= \{(3,1),(3,2),(3,3)\} \end{align*}
Correct Answer: B
Solved Example: 9206-02
If P = {1, 2, 7} and Q = {x : x ∈ R and x$^2$ - 9x + 14 = 0} then which of the following is true ?
A. P = Q
B. P ⊂ Q
C. Q ⊂ P
D. P is equivalent to Q
Correct Answer: C
Solved Example: 9206-03
If P ∩ Q = P then P ∪ Q is equal to?
A. P
B. Q
C. $\phi$
D. P'
Correct Answer: B
Matrix of Relation
Relation Matrix
- A relation R from a finite set A to a finite set B can be represented by a matrix called the relation matrix of R.
- Let A ={a$_1$,a$_2$,a$_3$…a$_m$} and B= {b$_1$,b$_2$,b$_3$……b$_n$} be finite set containing m and n elements, respectively, and R be the relation from A to B.
- Then R can be represented by an m x n matrix $M_r = [r_{ij}]$, which is defined as follows: \begin{align*} r_{ij} &= 1, \mathrm{\ if\ } a_i\ R\ b_j \\ r_{ij} &= 0, \mathrm{\ if\ } a_i \mathrm{\ does\ not\ } R\ b_j \end{align*} Note that the matrix MR has the elements as 1’s and 0’s.
Solved Example: 9159-01
Which of the following is/are the type(s) of relation?
A. Reflexive relation
B. Irreflexive relation
C. Symmetric relation
D. All of the above
Correct Answer: D
Digraph
Important Points:
- Digraph = Directed graph
- It is a diagram composed of points called vertices (nodes) and arrows called arcs going from a vertex to a vertex.
Types of Graphs:
- Simple graphs: These are graphs without multiple edges or self-loops.
- Directed graphs: Edges have directions: An edge is an ordered pair of nodes.
- Weighted graphs: is a graph for which each edge has an associated weight.
A graph is connected if you can get from any node to any other by following a sequence of edges and any two nodes are connected by a path.
A directed graph is strongly connected if there is a directed path from any node to any node.
- In-degree: Number of edges entering
- Out-degree: Number of edges leaving
- Degree: In-degree + out-degree
A graph can also be represented by Adjacency list or Adjacency Matrix.
Solved Example: 9248-01
A directed graph or digraph can have directed cycle in which:
A. Starting node and ending node are different
B. Starting node and ending node are same
C. Minimum four vertices can be there
D. Ending node does not exist
Correct Answer: B