Answers

Lecture 01 - Sets & Venn Diagram

Important Concept Summary

1. Union ($A \cup B$): Elements in $A$ or $B$
2. Intersection ($A \cap B$): Elements common to both
3. Difference ($A - B$): Elements in $A$ but not in $B$
4. Venn diagrams help visualize overlaps
5. At least one = union, only = specific region, neither = outside all sets

Practice 01 - Questions

Out of 80 students: 60 pass Bangla, 40 pass English, 25 pass both.

• Tasks:

  • a) How many pass Bangla?
  • b) How many pass English?
  • c) How many pass both?
  • d) How many pass only Bangla?
  • e) How many pass only English?
  • f) How many pass at least one subject?
  • g) How many fail in both?
  • h) How many fail only one subject?
  • i) How many fail at least one subject?
  • j) How many fail at least two subjects?

• Answers:

  • a) 60
  • b) 40
  • c) 25
  • d) 35
  • e) 15
  • f) 75
  • g) 5
  • h) Fail only Bangla = 15, fail only English = 35 -> total 50
  • i) 55
  • j) 5

Practice 02 - Questions

800 surveyed.
Car only = 280, Bicycle only = 220, Both = 140.

• Tasks:

  • a) Car only?
  • b) Bicycle only?
  • c) Neither?
  • d) At least one?
  • e) Only one?

• Answers:

  • a) 280
  • b) 220
  • c) 160
  • d) 640
  • e) 500

Practice 03 - Questions

80 like Java, 60 like C++, 40 like Python.
Overlaps: JC++ = 20, C++P = 25, JP = 20, All = 12.

• Tasks:

  • 1. Total students?
  • 2. Only Java?
  • 3. Only C++?
  • 4. Only Python?

• Answers:

  • 1. 127
  • 2. 47
  • 3. 27
  • 4. 12

Lecture 02 - Mathematical Induction

Important Concept Summary

Mathematical Induction requires:

1. Base Step: Show formula holds for $n = 1$
2. Inductive Step: Assume true for $n = k$, prove true for $n = k + 1$

If both hold, formula is true for all natural numbers.

• Tasks:

  • 1. Prove: $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$
  • 2. Prove: $1 + 3 + 5 + \cdots + (2n-1) = n^2$
  • 3. Prove: $1^3 + 2^3 + \cdots + n^3 = \left[\frac{n(n+1)}{2}\right]^2$

• Answers:

  • All three statements are true by induction.

Lecture 03 - Propositional Logic (Part 1)

Important Concept Summary

1. Proposition: A declarative statement with TRUE or FALSE
2. Not a proposition: Questions, commands, exclamations, variable statements
3. $\neg p$: Negation = "It is not the case that $p$"
4. $p \wedge q$: Both must be true
5. $p \vee q$: At least one is true

• Tasks:

  • Identify whether each is a proposition and state truth value.

• Answers:

  • Kolkata is in Bangladesh -> Proposition (False)
  • Do your homework? -> Not a proposition
  • Bangladesh wins by 3 wickets -> Proposition (True)
  • 23 is an even number -> Proposition (False)
  • X is an odd number -> Not a proposition
  • $34 + 2 = 37$ -> Proposition (False)
  • May Allah bless you -> Not a proposition
  • Do it -> Not a proposition
  • Do you know me? -> Not a proposition
  • What is your good name? -> Not a proposition
  • Hurrah! We won -> Not a proposition

AND Practice - Questions

• Tasks:

  • 1. Express $p \wedge q$ in English (swimming + sharks).
  • 2. Express $p \wedge q$ in English (election + counting).

• Answers:

  • 1. "Swimming at the NJ shore is allowed, and sharks have been spotted."
  • 2. "The election is decided, and the votes have been counted."

Negation Practice - Questions

• Tasks:

  • Given: $p$ = "The election is decided", $q$ = "Votes counted".
  • 1a) $\neg p$
  • 1b) $\neg q$
  • 2a) $\neg q$ (sharks)
  • 2b) $\neg q$ (duplicate)

• Answers:

  • 1a) The election is not decided.
  • 1b) The votes have not been counted.
  • 2a) Sharks have not been spotted near the shore.
  • 2b) Same: Sharks have not been spotted near the shore.

Lecture 04 - Propositional Logic (Part 2)

Important Concept Summary

1. Truth tables evaluate all possible input cases.
2. Expression trees show operator hierarchy.
3. Combinational circuits translate logic into gates.
4. Logical equivalence means both expressions yield identical truth tables.

Truth Table Questions

• Tasks:
  • I. $\neg p \wedge (\neg q \vee r)$
  • II. $p \vee (\neg q \wedge \neg r)$
  • III. $((p \vee q) \to r) \to p$
  • IV. $(\neg q \wedge \neg r) \wedge (p \to (q \vee r))$

Final Column Answers Only

• Answers:

  • I. T, F, F, F, F, F, T, F
  • II. T, T, T, T, F, F, F, F
  • III. T, T, T, F, F, T, T, F
  • IV. F, F, F, F, F, F, F, F

• (All copied in order: $pqr =$ TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF)

Expression Tree Questions

• Tasks:
  • a) $\neg p \wedge (\neg q \vee r)$
  • b) $p \vee (\neg q \wedge \neg r)$
  • c) $((p \vee q) \to r) \to p$
  • d) $(\neg q \wedge \neg r) \wedge (p \to (q \vee r))$

Key Explanation

Expression tree simply follows operator precedence.

• Answers:
  • a) AND at root -> left: $\neg p$, right: $(\neg q \vee r)$
  • b) OR at root -> left: $p$, right: $(\neg q \wedge \neg r)$
  • c) Implication at root -> left: $((p \vee q) \to r)$, right: $p$
  • d) AND at root -> left: $(\neg q \wedge \neg r)$, right: $(p \to (q \vee r))$

Circuit -> Expression Questions

Page 15 diagram
Page 16 diagram

• Answers:
  • 1. $A \wedge \neg B$
  • 2. $((A \wedge B) \wedge (\neg B \vee C)) \vee D$
  • 3. $(p \wedge \neg q) \vee \neg r$

Expression -> Circuit Question

$(p \vee \neg r) \wedge (\neg p \vee (q \vee \neg r))$

• Answers:
  • Circuit contains:
    • Two OR gates
    • Two NOT gates
    • One AND gate
  • Direct translation of expression.

Word Problem -> Logic Questions

1) Rakib/Rahim/Rain

Statement, circuit, tree.

• Answers:
  • Logical expression:
    • $(\text{RakibEatsRice} \to \text{RahimEatsBurger}) \vee (\text{Raining} \to \neg \text{GoingToBazar})$

2) Overtime & Trump

Statement, circuit, tree.

• Answers:
  • Logical expression:
    • $(\text{WorkOvertime} \to \text{Paid1.5}) \wedge (\text{TrumpWins2024} \to \text{TrumpBecomesPresident})$

Logical Equivalence Questions

• Tasks:

  • 1. $p \to q$ and $\neg p \vee q$
  • 2. $\neg(p \vee q)$ and $\neg p \wedge \neg q$

• Answers:

  • 1. Both pairs are logically equivalent.
  • 2. Both pairs are logically equivalent.

Lecture 05 - Tautology, Contradiction, Contingency

Important Concept Summary

1. Tautology: Always true
2. Contradiction: Always false
3. Contingency: Sometimes true, sometimes false

Tautology Questions

• Check if following are tautologies:

  • 1. $((p \to q) \wedge (q \to r)) \to (p \to r)$
  • 2. $((p \vee q) \wedge (\neg p \vee r)) \to (q \vee r)$
  • 3. $(p \to q) \to r$ and $p \to (q \to r)$
  • 4. $(p \wedge q) \to r$ and $(p \to r) \wedge (q \to r)$
  • 5. $((\neg q) \wedge (p \to q)) \to \neg p$

• Answers:

  • All 5 are tautologies.

Contradiction Questions

• Tasks:

  • Same set of statements.

• Answers:

  • None of them are contradictions.

Lecture 07 & 08

• Tasks:
  • Read Lecture 7 and 8 from the PDF.
  • The PDFs do not contain any additional practice problems (only theory).
  • Please read Lecture 7 and 8 from the PDF as they are not included here.

Suggestions Answer

QUESTION 1 - CIRCUIT

Kindly practice circuit questions from the PDF.

QUESTION 2 - PIGEONHOLE PRINCIPLE

2(a)
A box contains 8 yellow, 12 green, and 15 purple balls. What is the minimum number of balls you must draw to guarantee having 5 balls of the same color?

Answer 2(a):
We want to force 5 of one color. Using generalized pigeonhole: to guarantee $k+1$ items in one of $n$ boxes you need $k \cdot n + 1$ draws where $k = 4$ and $n = 3$ colors.

Minimum $= 4 \times 3 + 1 = 13$ draws.

2(b)
A drawer has 20 black, 20 white, and 20 brown socks. Minimum to ensure 4 socks of the same color?

Answer 2(b):
$k+1 = 4 \Rightarrow k = 3$, $n = 3$ colors, so minimum $= 3 \times 3 + 1 = 10$ socks.

2(c)
A bag has 6 red, 9 blue, 11 orange marbles. Minimum to guarantee selecting 3 marbles of same color?

Answer 2(c):
$k+1 = 3 \Rightarrow k = 2$, $n = 3$, so minimum $= 2 \times 3 + 1 = 7$ marbles.

QUESTION 3 - RELATIONS

For each relation on $A = \{1,2,3,4\}$ determine Reflexive, Symmetric, Transitive.

Set 1 (first block on page 2)

$R_1 = \{(1,2), (2,3), (3,4)\}$

• Reflexive? No - missing $(1,1),(2,2),(3,3),(4,4)$.
• Symmetric? No - e.g. $(1,2)$ present but $(2,1)$ not.
• Transitive? No - $(1,2)$ and $(2,3)$ present but $(1,3)$ not present.

$R_2 = \{(1,1),(2,2),(3,3),(1,3),(3,1),(2,4)\}$

• Reflexive? No - $(4,4)$ missing.
• Symmetric? No - $(1,3)$ and $(3,1)$ are symmetric, but $(2,4)$ exists without $(4,2)$.
• Transitive? Yes - every valid chain closes inside relation.

$R_3 = \{(2,2),(3,3),(4,4),(1,4)\}$

• Reflexive? No - $(1,1)$ missing.
• Symmetric? No - $(1,4)$ present, $(4,1)$ absent.
• Transitive? Yes - only needed closure is $(1,4)$ with $(4,4)$ giving $(1,4)$, which is present.

$R_4 = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,1)\}$

• Reflexive? Yes - all $(a,a)$ present.
• Symmetric? No - $(1,2)$ is present but $(2,1)$ is not.
• Transitive? No - $(1,2)$ and $(2,3)$ would require $(1,3)$, which is missing.

$R_5 = \{(1,1),(2,3),(3,2),(4,4)\}$

• Reflexive? No - $(2,2)$ and $(3,3)$ missing.
• Symmetric? Yes - $(2,3)$ and $(3,2)$ are both present.
• Transitive? No - $(2,3)$ and $(3,2)$ would require $(2,2)$, which is missing.

Set 2 (second block on page 3)

$R_1 = \{(1,4),(4,2),(2,3),(3,1)\}$

• Reflexive? No - no diagonal pairs.
• Symmetric? No - e.g. $(1,4)$ present but $(4,1)$ not.
• Transitive? No - $(1,4)$ and $(4,2)$ would require $(1,2)$, which is missing.

$R_2 = \{(1,1),(2,2),(1,2),(2,1),(3,4)\}$

• Reflexive? No - $(3,3)$ and $(4,4)$ missing.
• Symmetric? No - $(3,4)$ lacks $(4,3)$.
• Transitive? Yes - every nontrivial chain closes.

$R_3 = \{(1,1),(2,2),(3,3),(4,4),(1,4),(4,3),(3,2)\}$

• Reflexive? Yes - all diagonal pairs present.
• Symmetric? No - $(1,4)$ present but $(4,1)$ not.
• Transitive? No - $(1,4)$ and $(4,3)$ would require $(1,3)$, which is missing.

$R_4 = \{(1,1),(2,2)\}$

• Reflexive? No - $(3,3)$ and $(4,4)$ missing.
• Symmetric? Yes - only diagonal pairs.
• Transitive? Yes - no failing chain.

$R_5 = \{(1,2),(2,1),(3,4),(4,3)\}$

• Reflexive? No - no diagonal pairs.
• Symmetric? Yes - all pairs come with reverse.
• Transitive? No - $(1,2)$ and $(2,1)$ would require $(1,1)$, which is missing.

Set 3 (third block)

$R_1 = \{(1,3),(3,2),(2,1)\}$

• Reflexive? No
• Symmetric? No - e.g. $(1,3)$ present but $(3,1)$ absent.
• Transitive? No - $(1,3)$ and $(3,2)$ would require $(1,2)$, which is absent.

$R_2 = \{(1,1),(3,3),(4,4),(2,4),(4,2)\}$

• Reflexive? No - $(2,2)$ missing.
• Symmetric? Yes - $(2,4)$ and $(4,2)$ are present.
• Transitive? No - $(2,4)$ and $(4,2)$ would require $(2,2)$, which is missing.

$R_3 = \{(1,2),(2,3),(3,4),(4,1)\}$

• Reflexive? No
• Symmetric? No
• Transitive? No - $(1,2)$ and $(2,3)$ would require $(1,3)$, which is missing.

$R_4 = \{(2,2),(3,3)\}$

• Reflexive? No
• Symmetric? Yes
• Transitive? Yes

$R_5 = \{(1,1),(2,2),(3,3),(1,2),(2,3)\}$

• Reflexive? No - $(4,4)$ missing.
• Symmetric? No - $(1,2)$ present but $(2,1)$ absent.
• Transitive? No - $(1,2)$ and $(2,3)$ would require $(1,3)$, which is missing.

QUESTION 4 - INDUCTION

Please practice PDF content; most reliable source.

QUESTION 5 - LOGICAL PROPOSITION (three sentences)

Problem 1

Sentence: "Either X or Y is true, but they cannot both be true."

(a) Logical expression

$$(X \vee Y) \wedge \neg(X \wedge Y)$$

Equivalent to exclusive OR: $X \oplus Y$.

(b) Expression tree

Root = $\wedge$

• Left child = $\vee$ with leaves $X$, $Y$
• Right child = $\neg$ whose child is $\wedge$ with leaves $X$, $Y$

(c) Truth table and classification

Classification: Contingency

(d) Logic circuit diagram (textual)

• OR gate combining $X$ and $Y$ -> output to AND gate.
• AND gate combining $X$ and $Y$ -> feed to NOT -> feed into second input of final AND.
• Final gate is AND: OR-output AND NOT(AND($X,Y$)).

(e) If new sentence: "X or Y, and both may be true"
New expression: $X \vee Y$.

Problem 2

Sentence: "If X is true then Y must be false, and at least one of them must be true."

(a) Logical expression

1st part: $X \to \neg Y$
2nd part: $X \vee Y$
Combined: $(X \to \neg Y) \wedge (X \vee Y)$

(b) Expression tree

Root = $\wedge$

• Left child = $\to$ with left $X$ and right $\neg Y$
• Right child = $\vee$ with leaves $X$, $Y$

(c) Truth table and classification

Expression is Contingency.

(d) Logic circuit

• Left part: $X \to \neg Y$, realizable as $\neg X \vee \neg Y$
• Right part: $\operatorname{OR}(X,Y)$
• Final: AND of both parts

(e) Replace implication with iff

New expression: $(X \leftrightarrow \neg Y) \wedge (X \vee Y)$

You can expand $X \leftrightarrow \neg Y$ as $(X \wedge \neg Y) \vee (\neg X \wedge Y)$.

Problem 3

Sentence: "X is true only if Y is false, and at least one of X or Y is false."

(a) Logical expression

"X only if Y is false" means $X \to \neg Y$.
"At least one of X or Y is false" is $\neg(X \wedge Y)$ or $\neg X \vee \neg Y$.

Combined:

$$(X \to \neg Y) \wedge (\neg X \vee \neg Y)$$

(b) Expression tree

Root = $\wedge$

• Left child = $\to$ ($X \to \neg Y$)
• Right child = $\vee$ ($\neg X \vee \neg Y$)

(c) Truth table and classification

Combined is true for three rows and false for one: Contingency.

(d) Logic circuit

• Build $X \to \neg Y$ as $\neg X \vee \neg Y$
• Build $\neg X \vee \neg Y$
• AND them

Since both conjuncts are same, whole formula simplifies to $\neg X \vee \neg Y$.

(e) Replace "only if" with "if and only if"

Now left part becomes $X \leftrightarrow \neg Y$. Combined expression:

$$(X \leftrightarrow \neg Y) \wedge (\neg X \vee \neg Y)$$

QUESTION 6 - TSP (Travelling Salesman Problem)

Graph edges:

• $a$-$b = 12$
• $b$-$d = 12$
• $b$-$c = 8$
• $a$-$c = 10$
• $c$-$d = 11$
• $c$-$e = 3$
• $e$-$d = 11$
• $e$-$f = 6$
• $f$-$g = 9$
• $g$-$c = 9$
• $a$-$g = 12$
• $e$-$g = 7$
• $d$-$f = 10$

We must start and end at $a$.

Candidate optimal cycle (intermediate attempts)

$$a \rightarrow c \rightarrow e \rightarrow f \rightarrow g \rightarrow c \rightarrow b \rightarrow d \rightarrow a$$

Invalid because $c$ repeats.

$$a \rightarrow c \rightarrow e \rightarrow f \rightarrow g \rightarrow d \rightarrow b \rightarrow a$$

Invalid because $g \to d$ is not an edge.

$$a \rightarrow c \rightarrow e \rightarrow d \rightarrow b \rightarrow a \rightarrow g \rightarrow f \rightarrow a$$

Invalid because vertices repeat.

Final verified tour

$$\boxed{a \rightarrow c \rightarrow b \rightarrow d \rightarrow f \rightarrow e \rightarrow g \rightarrow a}$$

Cost calculation

$$10 + 8 + 12 + 10 + 6 + 7 + 12 = 65$$

Final Answer

$$\boxed{\text{Minimum TSP tour cost } = 65}$$ $$\boxed{\text{Optimal path } = a \rightarrow c \rightarrow b \rightarrow d \rightarrow f \rightarrow e \rightarrow g \rightarrow a}$$

QUESTION 7 - SETS

Problem 1

Given:

• $n(F) = 50$, $n(C) = 40$, $n(B) = 35$
• $n(F \cap C) = 15$, $n(C \cap B) = 12$, $n(F \cap B) = 10$
• $n(F \cap C \cap B) = 5$

(a) Total number of people who like at least one sport

Use inclusion-exclusion:

$$n(F \cup C \cup B) = 50 + 40 + 35 - 15 - 12 - 10 + 5$$

Compute:

$50 + 40 + 35 = 125$
Subtract pairwise overlaps: $125 - (15 + 12 + 10) = 88$
Add triple overlap: $88 + 5 = 93$

Answer 7.1(a): 93

(b) People who like only Football

Compute pair-only values first:

• $F \cap C$ only $= 15 - 5 = 10$
• $F \cap B$ only $= 10 - 5 = 5$

Only Football:

$$50 - (10 + 5 + 5) = 30$$

Answer 7.1(b): 30

(c) People who like exactly two sports

Exactly two:

$$(F \cap C\ \text{only}) + (C \cap B\ \text{only}) + (F \cap B\ \text{only})$$

So:

$$10 + (12 - 5) + 5 = 22$$

Answer 7.1(c): 22

(d) Venn diagram counts

• Triple region = 5
• $F \cap C$ only = 10
• $C \cap B$ only = 7
• $F \cap B$ only = 5
• Only $F = 30$
• Only $C = 40 - (10 + 7 + 5) = 18$
• Only $B = 35 - (7 + 5 + 5) = 18$

Problem 2 (Tea/Coffee)

Given 300 students: $n(\text{Tea}) = 180$, $n(\text{Coffee}) = 120$, $n(\text{both}) = 70$.

(a) Tea only

$$180 - 70 = 110$$

(b) Coffee only

$$120 - 70 = 50$$

(c) Neither

$$300 - (110 + 50 + 70) = 70$$

---

IUS Preps - Your Academic Success Partner