## 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

## 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 X^{c }– Z^{c}

{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) =…..

2^{4} b. 2^{3}

2^{+} d. 2^{7}

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, 10^{2}, 10^{3}, 10^{4}, 10^{5},… 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) = x^{3} +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^{-1}og^{-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) = _______:

2^{4} b. 2^{3}

2^{6} d. 2^{7}

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, 10^{2}, 10^{3}, 10^{4}, 10^{5},…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) =n^{2} 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 x^{2} + y^{2} = 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 n^{3} +n is even.

**Q#**4: Use mathematical induction to prove that 1+3+5+…+(2n-1) = n^{2} 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.