Discrete Structures
(BS and ADP – IT – 1st)
(BS – IT – 3rd)
Short Questions. Attempt all. (2 Marks Each)
1. State DeMorgan’s Law for propositional logic
2. Construct the truth table for p conditional q
3. Define tautology and give one example
4. Write the contrapositive of the statement “If it rains, then the ground is wet”
5. Symbolize the statement “Everyone loves ice cream or someone does not like cake”
6. Define a simple graph
7. State the handshaking theorem regarding the sum of degrees of a graph
8. How many edges are there in a complete graph of 6 vertices?
9. In how many distinct ways can the letters of the word APPLE be arranged?
10. Evaluate 10P2.
11. In how many ways can the committee of 3 people be chosen from a group of 10 people?
12. Expand (x + y)3 using binomial theorem.
13. State the general formula of binomial theorem.
14. Find the sum of all binomial coefficients of (a+b)8
15. State the Pigeonhole Principle.
16. In a group of 13 people, show that at least two of them must have birthdays in the same month of the
year.
17. If 21 objects are distributed into 10 boxes, what is the minimum number of objects in the box with the
most objects?
18. Define Contradiction and give an example using a propositional variable p.
19. In how many ways can 5 distinct items be arranged in a circle?
20. How many terms are there in the expansion of (3a + 2b)18?
Long Questions. Attempt any three. (20 marks each)
1. Test the validity of the statement using propositional logic and truth tables: “If I study, I will pass the
exam. If I pass the exam, I will get a job. Therefore, if I do not get a job, I did not study.”
2. Consider a graph G with vertices V = {a, b, c, d, e}. Draw the graph and find its adjacency matrix if the
edges are {(a, b), (a, c), (b, d), (c, d), (d, e), (e, a)}. Mention the types of edges being discussed.
3. A committee of 5 members is to be formed from 6 men and 4 women. Find the number of ways to form
a committee if:
a. There are no restrictions
b. The committee must include at least two women.
c. The committee must include at least one woman.
4. Find the term independent of x in the expansion of:
9
2 1
(2 x − ) .
x