Paper 1:Discrete Mathematics Fall – 2020 Past Papers
Time Allowed: 3 hours
Total Marks: 70, Passing Marks (35)
Q.1 (a) Define the following terms (i) Biconditional (ii) Conjuction (iii) Imlication
(b) Show that the statement form is a tautology and the statement form
is a contradiction.
Q.2 (a) Construct the truth table for .
(b) Show that and are logically equivalent.
Q.3 (a) Define the following terms (i) onto function (ii) one-one function (iii) Bijective function
(b) Prove that
Q.4 (a) Define the following terms (i) Reflexive relation (ii) Symmetric relation (iii) Transitive relation
(b) Let and defined relations R, S and T on A as follows:’
, .
and . Are R, S and T reflexive? Symmetric? Transitive?
Q.5 (a) Find the number of combinations of 4 objects, A, B, C. D, taken 3 at a time.
(b) In a group of six people, must there be at least two who were born in the same Month.
Q6. (a) Define the following terms (i) Graphs (ii) Digraphs (iii) Divisibility
(b) Use the mathematical induction to prove that is divisible by 3 whenever n
is a positive integer.
Q7. (a) Define the following terms (i) Sample Space (ii) Event (iii) Probability
(b) A fair coin tossed three times. What is the probability to get at most one head in three tosses?
Q8. Write the brief note on (i) Tree traversal (ii) Quantifiers
(iii) Application of trees
Guess Paper 2:Discrete Mathematics Spring – 2020 Past Papers
Time Allowed: 3 hours
Total Marks: 70, Passing Marks (35)
Q.1 (a) Define the following terms (i) Conditional (ii) Biconditional (iii) Proposition
(b) Show that compound proposition is tautology.
Q.2 (a) Define the following terms (i) onto function (ii) one-one function
(iii) Bijective function
(b) Prove that
Q.3 (a) Define the following terms (i) Reflexive relation (ii) Symmetric relation
(iii) Transitive relation
(b) Let and
.Then find
Q.4 (a) Define the graphs and digraphs. Draw the digraph for the relation
(b) Let X= and R on X is
Determine R is an equivalence relation.
Q5. (a) Define the following terms (i) Sum rule (ii) Product rule
(iii) Pigeon Whole Principle
(b) A sales man living in Peshawar decides to make a sales trip to different 50 cities
Of Pakistan to sell his ware. Assume that he goes to one city after another and
Visit then all before returning to home. In how many different orders can he make
His trip.
.
Q6. (a) Define the following terms (i) Graph Isomorphism (ii) Euler and Hamiltonian Circuits.
(b) Draw the Cycles with 2, 3.4 vertices represented by respectively
Q7. (a) Define the following terms (i) Sample Space (ii) Event (iii) Probability
(b) A fair coin tossed three times. What is the probability to get at least one head in three tosses.
Q8. Write the brief note on (i) Recurrence Relation (ii) Connectivity in graphs
(iii) Application of trees
Guess Paper 3:Discrete Mathematics Fall – 2019 Past Papers
Time Allowed: 3 hours
Total Marks: 70, Passing Marks (35)
Q.1 (a) Define the following terms (i) Conjunction (ii) Disjunction (iii) Biconditional
(b) Construct a truth table for .
Q.2 (a) Define the following terms (i) Power set (ii) Proper subset
(iii) Function
(b) Prove that
Q.3 (a) Define the following terms (i) Reflexive (ii) Symmetric (iii) Transitive
(b) Let and .
Then find .
Q.4 (a) Define the graphs and digraphs. Draw the digraph for the relation
(b) Define the following terms (i) Congruence relation (ii) Equivalence relation
Q5. (a) Define the following terms (i) Permutation (ii) Combination
(iii) Pigeon Hole Principle
(b) Suppose that computer science department contains 5 faculty members, a
committee is formed consisting of 3 members. How many ways are there to form
the committee.
Q6. (a) Define the following terms (i) Bipartite graphs (ii) Simple and Complete graphs
(b) Draw the Cycles with 2, 3.4 vertices represented by respectively.
Q7. (a) Define the following terms (i) Sample Space (ii) Event (iii) Probability
(b) A fair coin tossed three times. What is the probability to get at least one tail in
three tosses.
Q8. Write the brief note on (i) Application of trees (ii) Tree Traversal
(iii) Graph Terminology
Paper 4:Discrete Mathematics Fall – 2020 Past Papers
Course Title: Discrete Structure
Discipline /Program: BSCS, BSSE
Total Marks: 18
Time allowed: 1 Hour
Question No 1: (3)
Consider the following statements from the list given below. Identify which statement is a proposition.
Man is mortal
Sun rises in the east
Two is less than five
X is a cat
May ALLAH bless you!
6 is a composite number
Question No 2: (3+2)
The given sentence is- “If 5x – 1 = 9, then x = 2.” Write the converse, inverse and contrapositive.
Prove it with the help of the truth table.
Question No 3: (2+3)
show that ˜(p → q)→ p is a tautology without using tables.
Find the negation of p → q
Question No 4: (5)
Show (p q, p r, q r, ∴ r) is a valid or invalid argument.
[OBJECTIVE]
Subject: Discrete Mathematics
Time Allowed: 15 Minutes
Max Marks: 10
NOTE: Attempt this Paper on this Question Sheet only. Please encircle the correct option. Division of marks is given in front of each question. This Paper will be collected back after expiry of time limit mentioned above.
Part-I Answer the following Questions, cutting and overwriting are not allowed. (10)
Let U= {1, 2, 3, …, 10}, X = {1, 2, 3, 4, 5} Y={y|y=2x,x ∈X}, Z={z| z* -92+ 14=0}.Enumerate Xc – Zc
{1,2} b. {7}
(3,4,5} d. {2,4,6}
If A= {1, 2, 3, 4}, then the number of elements in P (A) =…..
24 b. 23
2+ d. 27
The order pairs which are not present in a relation, must be present in
Inverse of that relation b. Composition of relation
Complementary relation of that relation d. None of these
The 8th term of the following geometric sequence
4, 12, 36, 108…
8748 b. 8768
12 d. 8766
1, 10, 102, 103, 104, 105,… is
Arithmetic series b. Geometric series
Arithmetic sequence d. Geometric sequence
The total number of one-to-one functions from a set with three elements to a set with two elements.
4 b.0 c. 1 d. 3
If f(x) =2x+I then its inverse =…………
x-l b. = (x-1)/2
1 + x d. None of these
The statement of the form pv~ p is…………..
Tautology b. Contradiction
Fallacy d. All of these
A collection of rules indicating how to form new set objects from those already known to be in the set is called
a Base b. Restriction
- Recursion d. Fallacy
- 10. Which term of the sequence 4,1,-2,… is -77
- 26 b. 27
- 28 d. None of these
[SUBJECTIVE]
Subject: Discrete Mathematics
Time Allowed: 2 Hours 45 Minutes
Max Marks: 50
NOTE: ATTEMPT THIS (SUBJECTIVE) ON SEPARATE ANSWER SHEET PROVIDED
Part-II Give Short Answers, Each question carries equal marks. (20)
Q#1: Let R be a binary relation on a set A. Prove that If R is reflexive, then R-1 is reflexive.
Q#2: Let f: R→R be defined by f(x) = x3 +5
Show that f is one-to-one and onto. Find a formula that defines the inverse function f-1.
Q#3: Find the sum of first π natural numbers.
Q#4: Define a relation L on the set of real numbers R be defined as follows:
For all x, y ∈R, x L y ⇄ x < y.
- Is L reflexive?
- Is L symmetric?
- Is L transitive?
Q#5: What is the minimum number of students in a class to be sure that two of them are born in the same month?
Part-III Give Long Answers, Each question carries equal marks. (30)
Q#1: Suppose R and S are binary relations on a set A.
- If R and S are reflexive, is R ∩ S reflexive?
- If R and S are symmetric, is R ∩ S symmetric?
- If R and S are transitive, is R ∩ S transitive?
Q#2: Show that ~(p®q) and p⇄q are logically equivalent.
Q#3: Let S be the function such that S(n) is the sum of the first positive integers. Give a recursive definition of S(n).
Q#4: Suppose f X-> Y and g: Y->Z and both of these are one-to-one and onto. Prove that (gof)-1 exists and that (gof)-1=f-1og-1.
Q#5: Show that the set 2Z of all even integers is countable.
[OBJECTIVE]
Subject: Discrete Mathematics (IT)
Time Allowed: 10 Minutes
Maximum Marks: 10
NOTE: Attempt this Paper on this Question Sheet only. Please encircle the correct option. Division of marks is given in front of each question. This Paper will be collected back after expiry of time limit mentioned above.
Part-I Encircle the right answer, cutting and overwriting is not allowed. (10)
The negation of the conditional statement Pp >4q is. a
¬p->q b. p ^ ¬g
q -> p d. ¬g > ¬p
If A= {1,2,3}, then the number of elements in P(A) = _______:
24 b. 23
26 d. 27
Consider the relation {(1,3), (1,4), (2,3), (2,4), (3,1), (3,4)}0n set A={1,2,3,4} is a. .
Symmetric b. Reflexive
Transitive d. Irreflexive
The 8th term of the following geometric sequence 4, 12, 36. 108, …
8748 b. 8768
12 d. 8766
1, 10, 102, 103, 104, 105,…is
Arithmetic series b. Geometric series
Arithmetic sequence d. Geometric sequence
The total number of one-to-one functions, from a set with three elements to a set with four elements is ________.
24 b. 16
12 d.9
If f(x) =2 x+ 1 then its inverse = ____________
x-1 b. (x-1)2
1 + x d. None of these
Compute the summation t=1Σ3 (2i – 1)
8 b. 3
9 d. 10
The number of distinct permutations that can be formed using the letters of the word “BENZENE” is
120 b. 420
240 d. None of the above
Which term of the sequence 4,1,-2,… is -77
26 b. 27
28 d. None of these
[SUBJECTIVE]
Subject: Discrete Mathematics (IT)
Time Allowed: 2 Hours 45 Minutes
Maximum Marks: 50
NOTE: ATTEMPT THIS (SUBJECTIVE) ON THE SEPARATE ANSWER SHEET PROVIDED.
Part-II Give short answers, Each answer carries equal marks. (20)
Q#1: How many integers from 1 through 1000 are multiples of 3 or multiples of 5?
Q#2: Use truth table to show that (p ⋀ ~q) ⋀ (~p ⋁ q) is a contradiction.
Q#3: For all subsets A and B of a universal set U, prove that (A – B) ⋃ (A ⋂ B) = A
Q#4: Suppose R and S are binary relations on a set A. If R and S are reflexive, is R ⋂ S reflexive? :
Q#5: Define symmetric relation.
Q#6: How many functions are there from a set with three elements to a set with four elements? ,
Q#7: Define g : Z -> Z by the rule g(n) =n2 for all n ∈ Z. Is g one-to-one? Prove or give a counter example.
Q#8: How many 2-permutation are there of {W, X, Y, Z}? Write them all.
Q#9: Define Recursion.
Q#10: Draw the graph of the binary relation C from R to R defined as follows: for all (x, y) ∈ R X R, (x, y) ∈ C x2 + y2 = 1
Part-III Give brief answers, Each answer carries equal marks. (30)
Q#1: Define a relation R on the set of all integers Z as follows: for all integers m and n, m R n ⇔ m ≡ n (mod 3) Prove that R is an equivalence relation,
Q#2: State and prove the DeMorgan’s Law.
Q#3: Prove that if n is an odd integer, then n3 +n is even.
Q#4: Use mathematical induction to prove that 1+3+5+…+(2n-1) = n2 forall integers n ≥ 1.
Q#5: Let f: R → R and g: R → R be defined by f(x) = 3x + 2 for all x ∈ R and g(x) = (x-2)/3 for all x ∈ R Show that f and g are inverse of each other.
