Discrete Mathematical Structures

1. Define all type of operators .

2. Define Logical Equivalence .
3. Get the contra positive of the statement “If it is raining then I get wet”
4. Define Converse, Inverse, Contra positive.
5. Define the conjunction operator with one example.
6. Given that the value of p  q is false, determine the value of ( p  q )q .
7. Construct the truth table for the compound proposition (𝑝 → 𝑞) → (𝑞 → 𝑝).
8. What are the contra positive, the converse and the inverse of the conditional statement
“If you work hard then you will be rewarded”
9. What compound proposition with example
10. Construct a truth table (p → r ) ^ (q →r ) ≅ (p v q)
11. How many row appear in a truth table of (q v p) v (~s v r ) → ~ t
12. Show that ( p ^ q ) → (p v q) is a tautology
13. Define Universal quantification and Existential quantification.
14. Write the statement in symbolic form “Some real numbers are rational”.
15. Rewrite the following using quantifiers “Every student in the class studied calculus”
16. Define reflexive and symmetric relation with example.
17. Define symmetric and transitive relations with examples.
18. let R = {(2,1),(2,3),(3,1),(3,4),(4,1),(4,3) } find 2
19. Explain Reflexive, Symmetric and transitive Closure relation
20. Explain Partial Order Relation with one example
21. Find the Reflexive and transitive relation of set A={1,2,3,4}
22. Draw an Hasse diagram with 6 vertices.
23. What is Maximal, Minimal, Greatest and Least elements of a set? Show it be Hasse
diagram.
24. Define poset.
25. Define lattice.
26. What do you mean by Boolean Lattice?
27. Write the recursive definition of the following sequences 1, 3, 5, 7, 9, . . .
28. Write the recursive definition of the following sequences 2, 4, 8, 16, . . .
29. Define Group, Semigroup and Monoid.
30. Define semigroup and monoid. Give an example of a semigroup which is not a monoid.
 31. Define abelian group,
32. Define complete bipartite graph with example
33. Define regular graph with example.
34. Draw a graph of 4 vertices having 3 Degree
35. If in a group ,a2=a then prove that a= e

Long Question:

1. Show that (𝑝 → (𝑞 → 𝑟)) → ((𝑝 → 𝑞) → (𝑝 → 𝑟)) is a tautology.

2. Prove that [ ( p v q) ⋀ ( p⟶ r) ⋀ ( q⟶ r) ] ⟶r is a tautology.
3.
4. Without using truth table show that 𝑝 → (𝑞 → 𝑝) ⟺ ¬𝑝 → (𝑝 → 𝑞).
5. Construct the truth table of the formula (𝑝 ∨ 𝑞) ∧ (𝑝 → 𝑟) ∧ (𝑞 → 𝑟).
6. Show that ~ (p ⋁ (∼ p ⋀ q) ) and ~ p ⋀ ~ q are logically equivalent
7. Using mathematical induction prove that for every non-negative integer
1 + 2 + 22 + ⋯ … … … . +2n = 2n+1 − 1
8. Using mathematical induction prove that for every non-negative integer
3+3.5+3.52+3.53+. . . . …. +3.5n = 3(5n+1 -1)/4
9. Using principle of mathematical induction, prove that 72𝑛 + 23𝑛−3 . 3𝑛−1 is divisible
by 25 for all positive integers.
10. Prove by mathematical induction that 6n+2 + 72𝑛+1 is divisible by 43, for each
positive integer n.
11. Prove by Method of Induction n3 –n is divisible by 6
12. Prove by Method of Induction n < 2n for all positive integer of n
13. Prove by Method of Induction 3n < n! at n ≥ 6
14. Prove that (n + 1)3 ≥ 3n if n is a positive integer with n ≤ 4
15. Show that √2 is airrational number by method of contradiction
16. Prove that if n is an integer and 3n + 2 is odd, then n is odd by contraposition method.
17. Show that n is integer and n3 + 5 is odd then n is even proof by contraposition
method .
18. Solve the recurrence relation 𝑎𝑛 = 7𝑎𝑛−1 − 12 𝑎𝑛−2 + 𝑛2𝑛 , 𝑎0 = 1, 𝑎1 = −10
19. Solve the recurrence relation 𝑎𝑛 = −5𝑎𝑛−1 − 6 𝑎𝑛−2 + 42 4𝑛 and the initial value
𝑎0 = 56, 𝑎1 = 278
20. Solve the recurrence relation 𝑎𝑛 = 5𝑎𝑛−1 − 6 𝑎𝑛−2 + 𝑛2𝑛
21. Solve the recurrence relation 𝑎𝑛 = −6𝑎𝑛−1 − 9 𝑎𝑛−2 , a0=4 , a1 = 1
22. Solve the recurrence relation 𝑎𝑛 = 6𝑎𝑛−1 − 9 𝑎𝑛−2 + 3𝑛
23. Solve the recurrence relation 𝑎𝑛 = −6𝑎𝑛−1 − 9 𝑎𝑛−2 an = -4an-1 - 4 an-2 + n 4n
24. Solve the recurrence relation an = 7an-1 - 10an-2 + 8n + 6 , n ≥ 2, a0=1, a1 = 2
25. Solve the recurrence relation 𝑎𝑛 = 8𝑎𝑛−1 + 10𝑛−1 , 𝑎0 = 1, 𝑎1 = 9 by using
generating functions.
26. Solve the recurrence relation 𝑓𝑛 = 𝑓𝑛−1 + 𝑓𝑛−2 , 𝑓0 = 0, 𝑓1 = 1 by using generating
functions.
27. Use generating functions to solve the recurrence relation 𝑎𝑛 = 3𝑎𝑛−1 + 4𝑛−1 with the
initial condition 𝑎0 = 1
28. Solve the recurrence relation by generating function an = 7an-1 - 10an-2 n ≥ 1
with the initial value a0=10 , a1 =11
29. A total of 1232 students have taken a course in Spanish, 879 have taken a course in
French, and 114 have taken a course in Russian. Further, 103 have taken courses in
both Spanish and Russian, 23 have taken courses in both Spanish and French and 14
have taken courses in both French and Russian. If 2092 students have taken atleast one
of Spanish, French and Russian, how many students have taken a course in all three
languages?
30. In a class of 50 students, there are 2 choices for optional subjects. It is found that 18
students have physics as an optional subject but not chemistry and 25 students have
chemistry as an optional subject but not physics.
i. How many students have both optional subjects?
ii. How many students have chemistry as an optional subject?
iii. How many students have physics as an optional subject
31. In A survey of 100 students, it was found that 30 studied Mathematics, 54 studied
Statistics, 25 studied Operations Research, 1 studied all the three subjects, 20 studied
Mathematics and Statistics, 3 studied Mathematics and Operation Research and 15
studied Statistics and Operation Research. Find how many students studied none of
these subjects and how many students studied only Mathematics?
32. Find the number of integers between 1 to 250 that are not divisible by any of the
integers 2,3,5 and 7
33. Determine the number of positive integer n, 1 ≤ 𝑛 ≤ 2000 that are not divisible by 2, 3
or 5 but are divisible by 7
34. Let 𝐴 = {1,2,3,4} and 𝑅 = {(1,3), (3,2), (2,4), (3,1), (4,1)}. Find the transitive closure
of R using Warshall’s algorithm.
35. Let 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑 } and 𝑅 = {(a, c), (b, d), (c, a), (d, b), (e, d)}. Find the transitive
closure of R using Warshall’s algorithm.
36. Let 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑 } and 𝑅 = {(a, d), (b, a), (b, c), (c, a), (c, d)(d, c)}. Find the
transitive closure of R using Warshall’s algorithm.
37. Let 𝑅 be a relation on set of real numbers such that 𝑎 𝑅 𝑏 if and only if 𝑎 − 𝑏 is an
integer. Show that 𝑅 is an equivalence relation.
38. Let R be a relation on a set of positive integers such that 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑥, 𝑦 ∈ 𝑧 + , 𝑥𝑅𝑦 if
and only if 𝑥 ≡ 𝑦(𝑚𝑜𝑑 𝑛). Prove that R is an equivalence relation
39. Let 𝑅 be a relation defined on set 𝐴 such that𝑅 = {(𝑎, 𝑏): 𝑎 divides 𝑏}. Show that 𝑅 is
a partial ordering relation.
40. Let R be a relation defined on a set of positive integers such that for all x , y ∈ Z+ , xRy
if and only if x + y is an even number. Prove that R is an equivalence relation.
41. Draw the Hasse diagram of ({3,4,5,60,120,240,360,720},/) . Find the least element,
greatest element, maximal element, minimal element, lower bounds, upper bounds, glb,
lub of the set {3,4,5}.
42. Draw the Hasse diagram of ({1,2,3,9,10,30},/) . Find the least element, greatest
element, maximal element, minimal element, lower bounds, upper bounds, glb, lub of
the set {2,3,9}.
43. Draw the Hasse diagram of ({3,5,9, 15, 24, 45},/) . Find the least element, greatest
element, maximal element, minimal element, lower bounds, upper bounds, glb, lub of
the set {3,5}.
44. Draw the Hasse diagram of ({2, 3, 4, 9, 12, 18, 36}, |). Find the least element, greatest
element, maximal element, minimal element, lower bounds, upper bounds, glb, and lub
of the following sets {12,18}.
45. Determine whether (P (S), ⊆) is a lattice where S is a set 𝑆 = {𝑎, 𝑏, 𝑐 }
46. State whether the poset ({1,2,3,6,12,18,36},/) is a lattice or not. Show your work.
47. Prove that the fourth roots of unity {1, −1, 𝑖, −𝑖} form an abelian multiplicative
group.
48. Prove that the set {1, 2, 3, 4,5, } not group under multiplicative modulo 6.
49. Check the set R = {0 , 1 , 2 , 3 , 4 , 5} is a under multiplicative modulo 6
50. Check the set R = {0 , 1 , 2 , 3 , 4 , 5} is a commutative group with respect to
addition modulo 6.
51. An undirected graph has an even number of vertices of odd degree.
𝑛(𝑛−1)
52. Prove that the maximum number of edges in a simple graph with n vertices is .
2
53. Define a complete bipartite graph draw 𝐾2, 3 𝑎𝑛𝑑 𝐾3,3
54. Draw simple graph with five vertices of the 1, 2, 2, 3, 4 degrees.