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