Sets
1. Given universal set 𝑈 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖, 𝑗}, 𝐴 = {𝑏, 𝑐, 𝑑, 𝑒}, 𝐵 = {𝑎, 𝑏, 𝑒, ℎ, 𝑖}, Draw Venn-
Diagram to represent the relationship between the given sets and find the following sets
(a). 𝐴𝑐 (b). 𝐴 − 𝐵 (c). 𝐵 − 𝐴 (d). 𝐴 ∩ 𝐵 (e). 𝐴 ∪ 𝐵 (f). (𝐴 − 𝐵)𝑐
2. Write the dual of the following
i. (𝑈 ∩ 𝐴) ∪ (𝐵 ∩ 𝐴) = 𝐴
ii. (𝐴 ∪ 𝐵 ∪ 𝐶)𝑐 = (𝐴 ∪ 𝐶)𝑐 ∩ (𝐴 ∪ 𝐵)𝑐
iii. (𝐴 ∩ 𝐵)𝑐 = 𝐴𝑐 ∪ 𝐵𝑐
iv. 𝐴 ∪ 𝐴𝑐 = 𝑈
v. 𝐴 ∪ (𝐵 ∩ 𝐶) = (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶)
3. Consider the following collection of the subsets of a set 𝑆 = {1,2,3,4,5,6,7,8,9} Which is not the
partition of S and why?
(i) {{1,2,3}, {4,5,6}, {6,7,8,9}}
(ii) {{1,2,3}, {4,5,6,7}, {8,9}}
(iii) {{1,2,3,4}, {5,6}, {6,7}, {8,9}}
(iv) {{1,2,3}, {4,5}, {6,7,8}, {8,9}}
4. 𝐴 = {1,2,3,4,5, }𝐵 = {4,5,6}𝐶 = {3,5} 𝑈 = {1,2,3,4,5,6,7} find the following
(I)𝐴 ∪ 𝐵 ∪ 𝐶 (II) (𝐴 ∪ 𝐵) − 𝐶
(III). 𝐴 ∩ (𝐵 ∩ 𝐶) (IV) 𝐵 − (𝐴 ∪ 𝐶) (V) 𝐴′ ∩ 𝐶
(VI) 𝐴′ ∪ 𝐵′ (VII) (𝐴 ∪ 𝐵)′ ∪ 𝐶
5. Write the power set and all possible partitions of the set {x,y,z,t}
6. Find the Cartesian product X x Y and Yx X, where X = {a, b, c}, Y = {7, 14, 21}.
7. Let A = {1,2,3,4}, P={1,2}, Q={2,3,4}, R={2,4}. Find the Min sets and Max sets generated by P, Q
and R.
8. Out of 1200 students at a college 582 took Economics, 627 took English, 543 took
Math’s, 217 took both Economics and English, 307 took both Economics and Math’s,
250 took both Math’s and English, 222 took all three courses, then how many students
took none of three subject?
9. In an examination 70% of student pass in C-programming and 60% pass in Computer
Architecture, while 25% students failed and 220 students pass in both the subjects.
Find total number of students.
10. In a class of CSE department 44 students got A+ in Discrete mathematics, 30 students
in Software Engineering while 28 in both subject. Find the number of students got A+
in
(i) Discrete Mathematics only
(ii) Software Engineering only
(iii) In Discrete Mathematics or in software engineering or in both
11. A survey of 550 T.V Watchers produced the following information.285 watch football
game,195 watch hockey game,115 watch cricket,45 watch football and cricket, 70
watch football and hockey,50 watch hockey and cricket. 100 do not watch any of three
games.
i. How many people watch exactly one of the three games?
ii. How many people watch all three games?
Relations
1. Let A be a set of integers and let ~ be the relation on A × A defined by (a,b)~ (c,d) if
a+d =b+c. Prove that ~ is a equivalence relation.
2. Let 𝑁 = {1,2,3 … . . } and let ⊠ be the relation on 𝑁 × 𝑁 defined by (𝑎, 𝑏) ⊠ (𝑐, 𝑑) if
𝑎𝑑 = 𝑏𝑐 , prove that ⊠ is an equivalence relation
3. Give an example of a relation which is
i. Neither reflexive nor Symmetric.
ii. Reflexive, Symmetric and not transitive
iii. Symmetric and transitive but not reflexive
4. Let L be a set of straight lines in a plane, Check 𝑅1 an equivalence relation or not
𝑅1 = {(𝑥, 𝑦): 𝑥, 𝑦 ∈ 𝐿𝑎𝑛𝑑𝑥 ⊥ 𝑦}
5. Show that the relation R in the set of integers Z given by R= {(a, b): 5 divides a-b} is
an equivalence relation.
6. Show whether the relation (x, y) ∈ R, if, x ≥ y defined on the set of +ve integers is a partial
order relation.
7. Show whether the relation (x, y) ∈ R, if, x divides y defined on the set of +ve integers is a
partial order relation.
Functions
1. Consider f:R→R given by f(x)=3x+[Link] that f is invertible .Find f o f-1.
2𝑥−7
2. Let f: R→R be defined by f(x) = . Prove that f is 1-1, onto, and hence find f-1.
3
3. Which of the following functions f: R→R are one-one, onto or both
(i) f(x)= -2x (ii) f(x)=x3-3x
5𝑥+3
4. Find the inverse of the function 𝑓(𝑥) = , x≠1/2
2𝑥−1
5. Consider f: R →R, g: R →R and h: R →R defined as f(x)=3x, g(y)=4y+5 and h(z)=cos 𝑧
wnere x, y, z in N, Show that h ο (g ο f) = (h ο g) ο f ?
4
6. Find Inverse of 𝑓(𝑥) = , x≠8
8−𝑥
1
7. If 𝑓: 𝑅 → 𝑅, where 𝑓(𝑥) = 𝑠𝑖𝑛𝑥 − 2 and 𝑔: 𝑅 − {3/2} → 𝑅 where 𝑔(𝑥) = 3−2𝑥 find that
(i) 𝑓𝑜𝑔
(ii) 𝑔𝑜𝑓
(iii) 𝑔𝑜𝑔
(iv) 𝑓𝑜𝑓
Mathematical Induction
1. Prove that 𝑛5 − 𝑛 is divisible by 5 when n is non-negative integer
𝑛(𝑛+1)
2. Prove by induction 1 + 2 + 3 + ⋯ . . … . . +𝑛 = 2
3. Show by Mathematical induction that 6𝑛+2 + 72𝑛+1 is divisible by 43 for each
positive integer 𝑛.
𝑛(𝑛+1)(𝑛+2)
4. Prove by induction 1.2 + 2.3 + ⋯ . . +𝑛(𝑛 + 1) = 3
5. Prove by Mathematical induction that x- y divides x – y for n ≥1
n n
Propositional Calculus
1. Let p be "It is cold" and q be "It is raining". Give a verbal sentence which
describes each of the following statements :
(a) ~ p (b) p ^ q (c) p v q
(d) q v ~p (e) ~ p ^ ~q (f) ~(~ q)
2. Let p be "He is tall" and q be "He is handsome". Write the following
statements in symbolical form using p and q.
(a) He is tall and handsome. (b) He is tall but not handsome.
(c) It is false that he is short or handsome. (d) He is neither tall nor handsome.
(e) He is tall or he is short and handsome. (f) It is not true that he is short or not
handsome.
[Link] the Truth Table for p v ~ q
4. Show that the propositions ~ (p ^ q) and ~ p v ~ q are logically equivalent.
5. Check following by using truth tables.
a) p v q ☰ ~( ~p ^ ~q)
b) ~ (p → q) ☰ p ^ ~ q.
[Link] the following formulae, check for tautology and contradiction.
(i) ~ (p → q) v (~p v (p ^ q))
(ii) (p → (q ^ r)) → ~ (p → q)
(iii) (p v q) v r ↔ p v (q v r)
(iv) p v ~ (p ^ q)
PROPOSITIONAL LOGIC
1. (a) It is not cold,
(b) It is cold and raining.
(c) It is cold or it is raining.
(d) It is raining or it is not cold.
(e) It is not cold and it is not raining.
(f) It is not true that it is not raining or it is false that it is not raining.
2. (a) p ^ q
(b) p ^ ~ q
(c)~(~p v q)
(d) ~ p ^ ~q
(e) p v (~ p ^ q)
(f) ~ (~ p v ~ q),
3. Truth Table
p q ~q p ∨ ~q
T T F T
T F T T
F T F F
F F T T
4. Truth Table
p q p∧q ~(p ∧ q) ~p ~q ~p ∨ ~q
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T
The columns for ~(p ∧ q) and ~p ∨ ~q are identical in all cases.
Therefore, ∼(p ∧ q) ≡ ∼p∨∼q
5. a) p∨q ☰ ∼(∼p∧∼q)
p q ~p ~q ~p ∧ ~q ~(~p ∧ ~q) p∨q
T T F F F T T
T F F T F T T
F T T F F T T
F F T T T F F
The columns for p ∨ q and ~(~p ∧ ~q) are identical.
b) ∼(p→q) ☰ p∧∼q
p q p→q ~(p → q) ~q p ∧ ~q
T T T F F F
T F F T T T
F T T F F F
F F T F T F
The columns for ~(p → q) and p ∧ ~q are identical.
6. i) ~ (p → q) v (~p v (p ^ q))
~ (p → q) v (~p v (p ^ q))
p q p→q ~(p→q) ~p p∧q ~p ∨ (p∧q)
T T T F F T T T
T F F T F F F T
F T T F T F T T
F F T F T F T T
Always True (tautology).
ii) (p → (q ^ r)) → ~ (p → q)
p q r q∧r p→(q∧r) p→q ~(p→q) Final
T T T T T T F F
T T F F F T F T
T F T F F F T T
T F F F F F T T
F T T T T T F F
F T F F T T F F
F F T F T T F F
F F F F T T F F
Neither tautology nor contradiction.
iii) (p v q) v r ↔ p v (q v r)
p q r (p∨q)∨r p∨(q∨r) Final
T T T T T T
T T F T T T
T F T T T T
T F F T T T
F T T T T T
F T F T T T
F F T T T T
F F F F F T
Always True (tautology).
iv) p v ~ (p ^ q)
p q p∧q ~(p∧q) Final
T T T F T
T F F T T
F T F T T
F F F T T
Always True (tautology).