৪৯তম বিসিএস ⎯ তথ্য ও যোগাযোগ প্রযুক্তি [২৮১]

A function from a set A (domain) to a set B (codomain) must satisfy two conditions:

Every element of set A must have an image in set B. 
That means for each element of A, there must be exactly one ordered pair (a,b) where a∈A and b∈B.

No element of A can be mapped to more than one element of B.
That means if (a,b₁) and (a,b₂) both exist, then b₁=b₂.

Now, f={(1,a),(2,a),(3,b)}
• Each element of A={1,2,3} appears once only.
• All are mapped to elements in B={a,b}.

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen.

Check Reflexivity:
A relation R on A is reflexive if for every a∈A, (a,a)∈R.

Here, 
A={1,2,3}.
R contains (1,1),(2,2),(3,3).
All reflexive pairs are present.
So, R is reflexive.

Check Symmetry:
A relation R is symmetric if whenever (a,b)∈R, then (b,a)∈R.
In R, only pairs of the form (a,a) exist.

For example, 
(1,1) implies (1,1) (already in R).
Symmetry holds trivially because no cross pairs exist.
So,R is symmetric.

Check Transitivity:
A relation R is transitive if whenever (a,b)∈R and (b,c)∈R, then (a,c)∈R.
Example: 
(1,1) and (1,1) give (1,1) which is in R.

Similarly, 
(2,2) and (2,2) give (2,2).
(3,3) and (3,3) give (3,3).
All transitive conditions are satisfied.
So, R is transitive.

Final R is Reflexive, symmetric, and transitive

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

A regular language is one that can be expressed using a regular expression or recognized by a finite automaton (DFA/NFA).
Finite automata have no memory beyond their finite states, so they cannot “count” arbitrarily.

Example:
Strings: ε, a, b, aa, ab, aab → all accepted

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

• DFA can maintain finite state count, e.g., even/odd parity
• Other languages require unbounded memory → not DFA-recognizable

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

A Pushdown Automaton (PDA) is exactly the machine model for context-free languages (CFLs).
• NPDA ⇔ Context-Free Grammar (CFG): Every language accepted by a (non-deterministic) PDA is context-free, and every context-free language can be generated by a CFG and accepted by some PDA.
• Deterministic PDAs (DPDA) accept a strict subset called deterministic CFLs (DCFLs).

Example:
L = {a^n b^n | n ≥ 0} → context-free, accepted by PDA

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

For a finite simple graph G with n≥1 vertices, the following are equivalent and define a tree:
i. Connected and acyclic.
ii. Connected with exactly n−1 edges.
iii. Acyclic with exactly n−1 edges.
iv. Minimal connected: removing any edge disconnects it.
v. Maximal acyclic: adding any edge creates exactly one cycle.

States (2)+(acyclic), which is a standard definition.

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

Euler’s Theorem: A connected graph has an Eulerian circuit (a closed walk using every edge exactly once) iff every vertex has even degree.
Here, all degrees are even ⇒ the graph is Eulerian ⇒ (a) is true.

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

In a complete graph Kn, every pair of distinct vertices is connected by exactly one edge.
• The number of unordered pairs of n vertices is n(n−1).
• Equivalently (Handshaking Lemma): each vertex has degree n−1, so ∑degrees=n(n−1)=2∣E∣ ⇒ ∣E∣= n(n−1)/ 2. 

Example:
K₁: 0 edges (1.0/2 = 0)
K₂:1 edge  (2.1/2 = 1)
K₃: 3 edges  (3.2/2 = 3)
K_4: 6 edges (4.3/2 = 6)

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

This grammar generates strings where the number of 'a's is equal to the number of 'b's. The production S → aSb adds an 'a' at the beginning and a 'b' at the end, maintaining the balance. The production S → ε allows the empty string, which corresponds to the case where there are zero 'a's and zero 'b's.

Example:
• If n = 1, the grammar generates ab.
• If n = 2, the grammar generates aabb.

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

The pumping lemma for regular languages is used to prove that certain languages are not regular. The pumping lemma states that for any regular language, there exists a pumping length such that strings longer than this length can be "pumped" (i.e., parts of the string can be repeated) without leaving the language. If no such pumping length can be found, the language is not regular.

Example:
The language {a^n b^n | n ≥ 0} is not regular, and the pumping lemma can be used to prove this.

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

The power set of a set S, denoted P(S), is the set of all subsets of S, including the empty set and S itself. If S = {1, 2}, then the power set P(S) = {∅, {1}, {2}, {1, 2}}.

Example:
If S = {a, b}, then P(S) = {∅, {a}, {b}, {a, b}}.

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

The intersection of two sets A and B, denoted by A ∩ B, consists of all elements that are common to both sets. In other words, it includes only the elements that appear in both sets.

Example:
Let A = {1, 2, 3} and B = {3, 4, 5}.
Then, A ∩ B = {3}.

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

The cardinality of a set, denoted |A|, is the number of elements in the set. It indicates the size or volume of the set.
If A = {1, 2, 3}, then the cardinality of A is |A| = 3.

Example:
For the set A = {a, b, c}, the cardinality |A| = 3.

Source: Discrete Mathematics with Applications by Susanna S. Epp.

The union of sets A and B, denoted A ∪ B, includes all elements that are in either A, B, or both. In this case, the union of A = {1, 2, 3} and B = {2, 3, 4} results in {1, 2, 3, 4}.

Example:
A = {1, 2, 3}
B = {2, 3, 4}
A ∪ B = {1, 2, 3, 4}

Source: Discrete Mathematics and Its Applications by Kenneth H. Rosen

A relation is symmetric if, for every pair (a, b) in the relation, (b, a) is also in the relation. However, it is not necessarily transitive.

Example:
if person A is a friend of person B, and person B is a friend of person C, it doesn't necessarily mean that person A is a friend of person C, so the relation "is a friend of" is symmetric but not transitive.

Source: Discrete Mathematics with Applications by Susanna S. Epp.

The function f(x)=x² is defined for all real numbers, so its domain is R (the set of all real numbers).
For the codomain, f(x)=x² produces real values, including both positive numbers and zero (i.e., f(x)≥0). However, the function is commonly considered to have the codomain as the set of all real numbers R, since it can output any real number, even though only non-negative numbers are produced for real inputs.

Example:
f(2) = 4, f(-2) = 4; both are real numbers, so the codomain is R.

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

The statement "If it rains, then the ground is wet" is a conditional statement, represented as P → Q where P is "it rains" and Q is "the ground is wet." The negation of a conditional statement P → Q is P ∧ ¬Q

Example:
If P = "It rains" and Q = "The ground is wet", the negation is P ∧ ¬Q, which means "It rains, and the ground is not wet."

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

A tautology is a logical expression that is always true. The expression P∨¬P is a tautology because it states that either P is true, or P is not true, which covers all possible cases. This is always true, regardless of the truth value of P.

Example:
If P is true, then P∨¬P is true.
If P is false, then ¬P is true, and thus P∨¬P is still true.

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

In mathematical induction, we begin by proving the statement for n = 1. For this problem, we check if the formula holds when n = 1: 
 n(n+1)/2 = 1(1+1)/2 =1
Since both sides are equal, the base case holds.

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

Each of the statements listed can be proven using mathematical induction:
  i. The sum of the first n odd numbers is n².
  ii. The sum of the first n even numbers is 2n.
  iii. The product of the first n numbers is n!.

These are typical examples where induction can be applied.

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

In a proof by contradiction, we assume that the statement we want to prove is false. If this assumption leads to a logical contradiction (something known to be false or impossible), then the original statement must be true.

Example:
Prove that √2 is irrational.
Assume √2 is rational → can be expressed as p/q in lowest terms → leads to contradiction that both p and q are even. Therefore, √2 is irrational.

Source: Discrete Mathematics and Its Applications by Kenneth H. Rosen

Proof by contradiction is a proof technique where you assume the opposite of the statement you want to prove, and show that this assumption leads to a contradiction, thereby proving the original statement.

Assume the opposite: there exists a largest prime p. Consider N=p₁p₂…p_n+1. 
N is not divisible by any primes in the list → contradiction. Hence, there is no largest prime.

To prove "There is no largest prime number" by contradiction, you assume the opposite, that there is a largest prime number. Then, you can derive a contradiction by constructing a number that cannot be divisible by any prime number, showing that your assumption is false

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

Recursion defines a function in terms of itself. To prevent infinite recursion, there must be a base case that terminates the recursion. The base case provides the simplest instance of the problem, for which the answer is known directly.

Source: Discrete Mathematics with Applications by Susanna S. Epp.

Considering the recursive formula,
i.  a₀=1,
ii.  a_n=3a_n−1 + 2 for n≥1
Now, using the recursive formula when n=1,
 a₁  = 3a₁₋₁ + 2 
= 3a₀ + 2
= 3 × 1 + 2  [ a₀ = 1]
= 3 +2
= 5
∴ a₁ = 5

Again using the recursive formula when n=2,
a₂ = 3a_2-1 + 2
= 3a₁ + 2 
= 3  × 5 + 2
= 15+2
= 17
∴ a₂ = 17

The answer is 17.

Source: Discrete Mathematics with Applications by Susanna S. Epp.

The number of ways to arrange the letters of the word "COMPUTER" can be calculated as the factorial of the number of letters.
Since "COMPUTER" has 8 distinct letters, the number of arrangements is 8!=8×7×6×5×4×3×2×1=3628800.

Example:
For the word "BOOK", there are 4 letters, and since "O" repeats, the formula is:
Number of arrangements = 4! / 2! = 24/2 =12.

Source: Discrete Mathematics & Its Applications (Eighth Edition) by Kenneth H. Rosen

This is a combination problem, as the order of selection doesn't matter. The number of ways to select 3 students from 10 is given by:
10! /{3!(10−3)!}= 10! /(3! × 7!) = (10×9×8)/(3×2×1)  =120.

Source: Discrete Mathematics and Its Applications by Kenneth H. Rosen.

The number of ways to arrange n distinct people in n chairs is given by the factorial of n, i.e.
5!=5×4×3×2×1=120.

Example:
If you have 3 people, the number of ways to arrange them in 3 chairs is: 
3!=3×2×1=6.

Source: Discrete Mathematics with Applications by Susanna S. Epp.

First, find the total number of ways to select a committee of 3 people from 14 individuals (8 men + 6 women) without any restriction:
14!/ {3! × (14-3)!} = (14×13×12​)/(3×2×1)=364.

Then, subtract the number of ways to select a committee with no women (only men). This is the number of ways to choose 3 men from 8:
8!/ {3! × (8-3)!} = (8×7×6​)/(3×2×1)=56.

Therefore, the number of ways to select a committee with at least one woman is:
364−56=260.
The answer is 260

Source: Discrete Mathematics & Its Applications (8th Edi.) by Kenneth H. Rosen

For a 3-digit number, the first digit can be any of the 5 digits (1, 2, 3, 4, 5), so there are 5 choices for the first digit. Once the first digit is selected, there are 4 remaining digits to choose from for the second digit. After selecting the second digit, there are 3 remaining digits for the third digit. Therefore, the total number of 3-digit numbers is: 5×4×3=60.

Example:
For the digits 1, 2, and 3, the number of 2-digit numbers that can be formed without repetition is:
3×2=6.

Source: Discrete Mathematics with Applications by Susanna S. Epp

The problem can be viewed as distributing 3 indistinguishable balls into 2 boxes. The possible distributions are:
• 3 balls in the first box and 0 balls in the second box.
• 2 balls in the first box and 1 ball in the second box.
• 1 ball in the first box and 2 balls in the second box.
• 0 balls in the first box and 3 balls in the second box.

Thus, there are 4 possible distributions.

Example:
For 2 balls and 2 boxes, the possible distributions are:
• 2 balls in one box, 0 balls in the other.
• 1 ball in each box.

Thus, 2 possible distributions.

Source: Discrete Mathematics and Its Applications  (8th Ed.) by Kenneth H. Rosen.

In circular arrangements, the number of distinct ways to arrange n people in a circle is given by (n−1)!.
For 4 people: (4−1)!=3!=3×2×1=6.

Example:
For 3 people in a circle, the number of distinct arrangements is (3−1)!=2!=2×1=2.

Source: Discrete Mathematics with Applications by Susanna S. Epp.

we can use the principle of inclusion-exclusion. The principle helps us find the number of elements in the union of two sets.

Given  that,
Total number of students = 30
Number of students who have taken mathematics (M) =18
Number of students who have taken physics (P) = 15
Number of students who have taken both subjects (M∩P) = 10

Here,
The number of students who have taken either mathematics or physics is the number of students in the union of the two sets M∪P, which can be found using the inclusion-exclusion principle:
M∪P=M+P−M∩P
M∪P =18+15−10
         =23
The number of students who have taken either mathematics or physics is 23.

Source: Discrete Mathematics and Its Applications  (8th Ed.) by Kenneth H. Rosen.

Find the total number of 4-digit numbers divisible by 3:
A 4-digit number is between 1000 and 9999. The divisibility rule for 3 states that a number is divisible by 3 if the sum of its digits is divisible by 3. We need to find how many 4-digit numbers are divisible by 3.
First 4-digit number divisible by 3:
The first 4-digit number divisible by 3 is 1002 (since 1000 is not divisible by 3, and 1002 is the next multiple of 3).
Last 4-digit number divisible by 3:
The last 4-digit number divisible by 3 is 9999.

The total number of 4-digit numbers divisible by 3 is found by dividing the range from 1002 to 9999 by 3:
Number of multiples of 3= (9999−1002)/3 +1=
8997 /3+1=2999+1=3000

Find the total number of 4-digit numbers divisible by 5:
Now, we need to find how many 4-digit numbers are divisible by 5.
First 4-digit number divisible by 5:
The first 4-digit number divisible by 5 is 1000.
Last 4-digit number divisible by 5:
The last 4-digit number divisible by 5 is 9995.
The total number of 4-digit numbers divisible by 5 is:
Number of multiples of 5= (9995−1000)/5+1= 8995/5 +1=1799+1=1800

Find the total number of 4-digit numbers divisible by both 3 and 5 (i.e., divisible by 15):
For numbers divisible by both 3 and 5, we find the number of multiples of 15.
First 4-digit number divisible by 15:
The first 4-digit number divisible by 15 is 1005.
Last 4-digit number divisible by 15:
The last 4-digit number divisible by 15 is 9990.
The total number of 4-digit numbers divisible by 15 is:
Number of multiples of 15= (9990−1005)/15+1=8985/15+1=599+1=600

Apply the principle of inclusion-exclusion:
Now, we use the principle of inclusion-exclusion to find the number of 4-digit numbers divisible by 3 or 5:
Total divisible by 3 or 5=(Divisible by 3)+(Divisible by 5)−(Divisible by 15)
∴ Total divisible by 3 or 5=3000+1800−600=4200
The answer is 4200.

Source: Discrete Mathematics and Its Applications  (8th Ed.) by Kenneth H. Rosen.

We apply the Inclusion-Exclusion Principle:
Total ways to select 2 cards from 52: 
52! / 2! × (52-2)! 
= 52! / (50!×2!)
= 52 × 51/2 
= 1326.

Total ways to select 2 non-heart cards (since there are 39 non-heart cards):
 39! / 2!×(39-2)!
= 39! / (37!×2!)
= 39×38/2
= 741.

Now apply the Inclusion-Exclusion principle,
At least one heart 
= [Total ways to select 2 cards from 52] - [Total ways to select 2 non-heart cards]
= 1326−741
= 585.

Source: Discrete Mathematics and Its Applications  (8th Ed.) by Kenneth H. Rosen.

There are several methods to solve recurrence relations:
Substitution method: We guess the form of the solution and use mathematical induction to verify it.
Iteration method: We expand the recurrence relation step by step to find a pattern.
Characteristic equation method: Used for solving linear recurrence relations with constant coefficients, typically used for problems like Fibonacci numbers.

Example:
To solve T(n)=2T(n−1)+1 with base case T(1)=1, the iteration method might give us the pattern T(n)=2ⁿ−1.

Source: Discrete Mathematics and Its Applications  (8th Ed.) by Kenneth H. Rosen.

The factorial function is recursively defined as:
n!=n×(n−1)! with base case 0!=1.

Example:
3!=3×2×1=6,
4!=4×3!=4×6=24.

Source: Discrete Mathematics and Its Applications  (8th Ed.) by Kenneth H. Rosen.

A ring is an algebraic structure consisting of a set equipped with two operations: addition and multiplication. It must satisfy the following conditions:
Additive Group: The set is an abelian group under addition (i.e., addition is commutative and associative, and there is an additive identity element).
Multiplication: The set is closed under multiplication, and multiplication is associative.
Distributivity: Multiplication distributes over addition, i.e., a∗(b+c)=a∗b+a∗c and (a+b)∗c=a∗c+b∗c.

Note that a ring does not necessarily require the existence of a multiplicative identity or commutative multiplication.

Example:
The set of integers Z with usual addition and multiplication is a ring.

Source: Discrete Mathematics and Its Applications  (8th Ed.) by Kenneth H. Rosen.

The set of real numbers R with the operation of addition satisfies the group properties:
i. Closure: The sum of two real numbers is a real number.
ii. Associativity: Addition of real numbers is associative.
iii. Identity: The additive identity is 0.
iv. Inverse: Every real number has an additive inverse.
Additionally, addition is commutative, meaning a+b=b+a. Hence, R forms an abelian group.

Example:
The set of rational numbers Q under addition is also an abelian group.

Source: Discrete Mathematics and Its Applications  (8th Ed.) by Kenneth H. Rosen.

The set of non-zero integers Z^∗ under multiplication is not a group because:
It does not have an identity element under multiplication (there is no integer such that multiplying it with any other integer gives the other integer back, i.e., there is no multiplicative identity).

Example:
The set of non-zero real numbers R^∗ under multiplication is a group, and it is also abelian.

Source: Discrete Mathematics and Its Applications  (8th Ed.) by Kenneth H. Rosen.

The degree of a vertex in a graph is defined as the number of edges incident to the vertex, i.e., the number of edges that have the vertex as one of their endpoints.

Example:
In a graph with 5 vertices and 6 edges, if vertex v₁ is connected to vertices v₂, v₃, and v₄, then the degree of v₁ is 3.

Source: Discrete Mathematics with Applications by Susanna S. Epp.

To find the maximum number of edges that can be drawn in a simple graph with 6 vertices, we use the following facts:
• A simple graph is one in which there are no loops (edges from a vertex to itself) and no multiple edges between any pair of vertices.
• The maximum number of edges in a simple graph occurs when every possible edge between distinct vertices is present.

Now, the maximum number of edges in a simple graph with n vertices is given by the formula for the complete graph;
Maximum edges = n(n−1)/2
Where,
n is the number of vertices.

Here, For n=6 (6 vertices):
Maximum edges
= 6(6−1)/2 
= 6×5/2
= 15
The maximum number of edges that can be drawn in a simple graph with 6 vertices is 15.

Source: Discrete Mathematics with Applications by Susanna S. Epp.

A simple graph cannot have loops (edges that connect a vertex to itself). Option C represents a graph with a loop, which violates the condition for being a simple graph.

Example:
A graph with two vertices and no edges or one edge is simple, but a graph with a loop at one vertex is not.

Source: Discrete Mathematics and Its Applications by Susanna S. Epp.

A path in a graph is a sequence of vertices where each vertex is connected to the next by an edge. It does not necessarily need to visit each vertex exactly once or return to the starting vertex.

Example:
In the graph with vertices A,B,C,D and edges (A,B),(B,C),(C,D), the path A→B→C→D is valid.

Source: Discrete Mathematics and Its Applications  (8th Ed.) by Kenneth H. Rosen.

If there is a path from A to B and a path from B to C, we can combine these two paths to create a new path from A to C.

Example:
If A→B→C, then we have a path from A to C.

Source: Discrete Mathematics and Its Applications by Susanna S. Epp.

A Hamiltonian cycle is a cycle that visits every vertex exactly once and returns to the starting vertex. It does not revisit any vertex except the starting one.

Example:
In a graph with 4 vertices, a Hamiltonian cycle could be A→B→C→D→A, where each vertex is visited exactly once.

Source: Discrete Mathematics and Its Applications by Susanna S. Epp.

In Context-Free Grammar (CFG), every production rule has a single non-terminal symbol on the left-hand side. CFGs are used to describe context-free languages and are more powerful than regular grammars, as they can describe languages that regular expressions cannot.

Example:
A CFG for a simple arithmetic expression can have rules like: E→E+T∣E−T∣T
where E and T are non-terminal symbols.

Source: Discrete Mathematics and Its Applications by Susanna S. Epp.

In a deterministic finite automaton (DFA), for every state and every input symbol, there is exactly one transition to another state (or possibly the same state). This is what makes the automaton deterministic. There are no choices or ambiguity in the transitions.

Example:
For a DFA with states q₁, q₂ and input alphabet {a,b}, if the automaton is in state q₁ and reads an input a, it must transition to a specific state, say q₂, and cannot transition to multiple states.

Source: Discrete Mathematics and Its Applications by Susanna S. Epp.

The main difference between a deterministic finite automaton (DFA) and a non-deterministic finite automaton (NFA) is that in a DFA, there is exactly one transition for each input symbol from each state, whereas in an NFA, there can be multiple transitions for the same input symbol from the same state, including epsilon transitions.

Example:
In an NFA, from state q₁ on input a, it can transition to either q₂ or q₃, while in a DFA, there must be exactly one transition.

Source: Discrete Mathematics and Its Applications by Susanna S. Epp.

A universal Turing machine is a theoretical machine capable of simulating the operation of any other Turing machine. It reads the description of another Turing machine and its input, then simulates the behavior of that machine on the given input.

Example:
A universal Turing machine can simulate a Turing machine that recognizes a language like palindromes, even though it is not specifically built for this task.

Source: Discrete Mathematics and Its Applications by Susanna S. Epp.