Questions

Lecture 01 - Sets & Venn Diagram

Practice 01

• Given: 80 students; Bangla pass 60, English pass 40, both 25.
• Tasks:
  1. Pass in Bangla?
  2. Pass in English?
  3. Pass both / pass only two / pass at least two?
  4. Pass only Bangla / Bangla but fail English / fail English?
  5. Pass only English / English but fail Bangla / fail Bangla?
  6. Pass in total / pass at least one?
  7. Fail in total / fail both?
  8. Fail only one?
  9. Fail at least one?
  10. Fail at least two?

Practice 02

• Given: Survey of 800 people; car only 280, bicycle only 220, both 140.
• Tasks: a) Car only count b) Bicycle only count c) Neither d) At least one e) Only one

Practice 03

• Given: Students liking languages - Java 80, C++ 60, Python 40; overlaps: Java & C++ 20, C++ & Python 25, Java & Python 20, all three 12.
• Tasks:
  1. Number liking at least one
  2. Only Java
  3. Only C++
  4. Only Python

Lecture 02 - Mathematical Induction

Core Proof Tasks

• Given/Tasks:
  1. Prove $1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}$.
  2. For all $n \ge 1$, prove $1 + 3 + 5 + \cdots + (2n - 1) = n^2$.
  3. For all $n \ge 1$, prove $1^3 + 2^3 + 3^3 + \cdots + n^3 = \left[\frac{n(n + 1)}{2}\right]^2$.

Lecture 03 - Propositional Logic (Part 1)

Proposition Identification

• Tasks: Decide if each is a proposition and its truth value.
• Given:
  • Kolkata is in Bangladesh.
  • Do your homework on discrete mathematics?
  • Bangladesh wins the match by 3 wickets.
  • 23 is an even number.
  • X is an odd number.
  • $34 + 2 = 37$
  • May Allah bless you!
  • Do it.
  • Do you know me?
  • What is your good name?
  • Hurrah! We have won the game.

AND Section

• Given:
  1. $p$ = "Swimming at the New Jersey shore is allowed"; $q$ = "Sharks have been spotted near the shore".
  2. $p$ = "The election is decided"; $q$ = "The votes have been counted".
• Tasks: Express $p \wedge q$ in English for each.

Negation Section

• Given:
  1. $p$ = "The election is decided"; $q$ = "The votes have been counted".
  2. $p$ = "Swimming at the New Jersey shore is allowed"; $q$ = "Sharks have been spotted near the shore".
• Tasks:
  • For (1): a) $\neg p$ b) $\neg q$
  • For (2): a) $\neg q$ b) $\neg q$ (duplicated in source)

Lecture 04 - Propositional Logic (Part 2)

Truth Table Practice

• Tasks: Build truth tables for
  • $\neg p \wedge (\neg q \vee r)$
  • $p \vee (\neg q \wedge \neg r)$
  • $((p \vee q) \to r) \to p$
  • $(\neg q \wedge \neg r) \wedge (p \to (q \vee r))$

Expression Trees

• Tasks: Draw expression trees for
  • $\neg p \wedge (\neg q \vee r)$
  • $p \vee (\neg q \wedge \neg r)$
  • $((p \vee q) \to r) \to p$
  • $(\neg q \wedge \neg r) \wedge (p \to (q \vee r))$

Combinational Circuits

• Tasks:
  • Derive logical expressions from given circuits (see diagrams pages 15-16).
  • Draw a circuit for $(p \vee \neg r) \wedge (\neg p \vee (q \vee \neg r))$.

Word Problems -> Logic + Circuit + Tree

• Given:
  1. If Rakib eats rice then Rahim eats burger, or if it is raining then we are not going to the Bazar.
  2. If you work overtime, then you are paid time-and-a-half; if Donald Trump wins the 2024 election, then he becomes president.
• Tasks (for each): Form logical statement, draw circuit, draw expression tree.

Logical Equivalence

• Tasks:
  1. Show $p \to q \equiv \neg p \vee q$.
  2. Show $\neg(p \vee q) \equiv \neg p \wedge \neg q$.

Lecture 05 - Propositional Logic (Part 3)

Tautology Checks

• Tasks: Show each is a tautology
  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. Determine whether $((\neg q) \wedge (p \to q)) \to \neg p$ is a tautology.

Contradiction Checks

• Tasks: Determine whether each is a contradiction
  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$
• Notes: Same statements as above; focus here on contradiction status.

Lecture 07 & 08

• Notes: PDFs contain theory only; no additional practice problems provided. Read Lectures 7 and 8 in the PDF.

Circuit Question

For each of the three circuits:

• (a) Write the logical expression corresponding to the given combinational circuit
• (b) Make a truth table and decide what kind of formula it is (tautology, contradiction, contingency)

Circuit 1

• Tasks:
  • Write the logical expression
  • Make truth table
  • Classify formula

Circuit 2

• Tasks:
  • Write the logical expression
  • Make truth table
  • Classify formula

Circuit 3

(Image from page 1)

Tasks:

1. Write the logical expression
2. Make truth table
3. Classify formula

Pigeonhole Principle Question

• (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?

• (b) A drawer has 20 black socks, 20 white socks, and 20 brown socks.

  • What is the minimum number of socks you must pull out to ensure having 4 socks of the same color?

(c) A bag contains 6 red marbles, 9 blue marbles, and 11 orange marbles.

What is the minimum number of marbles needed to guarantee selecting 3 marbles of the same color?

Relations Question

For each of the following relations on $A = \{1, 2, 3, 4\}$, determine whether the relation is Reflexive, Symmetric, and/or Transitive.

Set 1

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

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

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

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

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

Set 2

Determine reflexive, symmetric, transitive:

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

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

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

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

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

Set 3

Determine reflexive, symmetric, transitive:

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

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

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

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

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

Induction Question

This section provides no explicit statement, but you will be expected to:

• Prove a given formula using mathematical induction. The specific formula will be given by your teacher or assignment context.

Logical Proposition Question

There are three separate sentences, each requiring:

(a) Logical expression
(b) Expression tree
(c) Truth table + classify (tautology/contradiction/contingency)
(d) Logic circuit diagram
(e) Modify expression based on new condition

Problem 1

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

Tasks:
(a) Logical expression
(b) Expression tree
(c) Truth table + classification
(d) Circuit diagram
(e) New expression if: "X or Y, and both may be true"

Problem 2

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

Tasks:
(a) Logical expression
(b) Expression tree
(c) Truth table + classification
(d) Logic circuit
(e) Replace $\to$ with $\leftrightarrow$ ("if and only if")

Problem 3

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

Tasks:
(a) Logical expression
(b) Expression tree
(c) Truth table + classification
(d) Logic circuit
(e) Replace "only if" with "if and only if"

TSP Question

Set Problems Question

Given weighted graph (image on page 6):

Tasks:
Find the minimum path and weight using TSP.

TSP Question

Set Problems Question

Problem 1

A group of people:

• 50 like Football ($F$)
• 40 like Cricket ($C$)
• 35 like Basketball ($B$)
• 15 like both $F$ and $C$
• 12 like both $C$ and $B$
• 10 like both $F$ and $B$
• 5 like all three

Find:
(a) Number who like at least one sport
(b) Number who like only Football
(c) Number who like exactly two sports
(d) Draw the Venn diagram

Problem 2

In a survey of 300 students:

• 180 like Tea
• 120 like Coffee
• 70 like both

Find:
(a) Tea only
(b) Coffee only
(c) Neither

---

IUS Preps - Your Academic Success Partner