ASSIGNMENT 1
Sub: Discrete Mathematical Structure Code: BCS405A
Sem : 4th Sem
1) Let p, q and r be propositions having truth values 0, 0 and 1 respectively. Find the truth values
if the following compound propositions:
(ⅰ)(p ˅ q) ˅ r(ⅱ)(p ˄ q) ˄ r (ⅲ)(p ˄ q) → r (ⅳ)p → (q ˄ r) (ⅴ)p ˄ (q → r)
(ⅵ)p → (q →¬ r)
2) Prove that for any proposition p, q, r the compound proposition
[(p ˅ q) ˄ {(p → r) ˄ (q → r)}] → r is tautology.
3) Explain laws of logic.
(ⅰ). ∃x, [p(x) ⅴ q(x)]
4) Negate and simplify each of the following.
(ⅳ). ∃x, [p(x) ⅴ q(x)] → r(x)
(ⅱ). Ɐ x, [p(x) ˄ ¬ q(x)]
(ⅲ). Ɐ x, [p(x) → q(x)]
5) Write duals of the following propositions.
(i) q → p (ii) (p ⅴ q) ˄ r (iii) (p ˄ q) ⅴT0
(iv) p → (q ˄ r)
(i). p ↑ (q ↑ r) ⇔ ¬ pⅴ (q ˄ r)
6) For any propositions p, q, r Prove the following
(ii).(p ↑ q) ↑ r⇔ (p ˄ q) ⅴ¬ r
7) Give (ⅰ) direct proof (ⅱ) indirect proof (ⅲ) proof by contradiction for the following statement: “if n
is an odd integer, then n+9 is an even integer”.
8) State the converse inverse and contrapositive of the given statement: “If the triangle is not isosceles,
then it is not equilateral”.
9) Test the validity of the following argument
If I study, then I’ll not fail in the examination.
If I do not watch tv in the evenings, I will study.
∴ I must have watched tv in the evenings.
I failed in the examination.
10) Define the following:
(1) Open statement (2)Quantifiers (3)Universal quantifiers
11) Prove by mathematical induction that, for all positive integers 𝑛≥1,
(4) Existential quantifiers (5)Converse, Inverse and Contrapositive (6)Duality
1+2+3+⋯⋯⋯+𝑛=1/2(𝑛+1).
12) Prove by mathematical induction that, for all positive integers 𝑛≥1,
1∙2+2∙3+3∙4+⋯⋯⋯+(𝑛+1)=1/3𝑛(𝑛+1)(𝑛+2).
13) Cars of a particular manufacturer come in 4 models, 12 colours, 3 engine sizes and 2 transmission
types (a) how many distinct cars can be manufactured? (b) of these how many have the same colour?
14) Find the number of proper divisors of 441000.
15) A bit is either 0 or 1. A byte is a sequence of 8 bits. Find (i) the number of bytes. (ii) the number of
bytes that begin with 11 and end with 11. (iii) The number of bytes that begin with 11 and do not
end with 11. (iv) the number of bytes that begin with 11 or end with 11.
16) Find the number of permutations of the letters of the word MASSASAUGA. In how many of these,
all four ‘A’s are together? How many of them begin with S?
17) Four different mathematics books, five different computer science books and two different control
theory books are to be arranged in a shelf. How many different arrangements are possible if (a) The
books in each particular subject must be together? (b) Only mathematics books must be together?
18) A certain question paper contains two parts A and B each containing 4 questions. How many
19) Prove the following identities: 𝐶(𝑛,𝑟−1)+𝐶(𝑛,𝑟)=𝐶(𝑛+1,𝑟)
different ways a student can answer 5 questions by selecting at least 2 questions from each part?
20) Find the coefficient of : 𝑥9𝑦3 in the expansion of (2𝑥−3𝑦)12
21) Let A={1,2,3,4} & let R be the relation on A defined by xRy iff y=2x, then solve
I. Write down R as a set of ordered pairs.
II. Draw the graph of R.
22) With example identify types of Function.
23) Let A= {1, 2, 3, 4}, R= {(1, 3),(1, 1),(3, 1),(1, 2),(3, 3),(4, 4)} be the relation on A. Determine
whether the relation R is reflexive, irreflexive, symmetric, antisymmetric or transitive.
24) With example identify types of Relation.
25) Let A= { 1,2,3,4,5,6}, B={6,7,8,9,10} and f be a function from A to B defined by f= {(1,7)
(2,7),(3,8)(4,6)(5,9)(6,9)}. Then find f-1(6), f-1(9).
26) Let A={1,3,5} ,B={2,3} & C={4,6} then solve, i) AxB ii) (AUB)xC
