Problem Set 1: Logic & Sets

Work each problem on your own paper or in a markdown file. Show your reasoning: full credit requires a justified argument, not just a final answer.

Notation reminder: $\wedge$ (and), $\vee$ (or), $\neg$ (not), $\Rightarrow$ (implies), $\iff$ (iff), $\forall$ (for all), $\exists$ (there exists).

Problem 1: Truth Table

Construct a truth table for the following expression and determine whether it is a tautology, contradiction, or contingency:

$$(p\Rightarrow q)\iff (\neg p\vee q)$$

Problem 2: Logical Equivalence

Use the laws of logical equivalence (not a truth table) to show that:

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

Label each step with the name of the law used (e.g. De Morgan's, distribution, double negation).

Problem 3: Quantifier Negation

Rewrite the negation of each statement so that the $\neg$ symbol appears only immediately before a predicate.

(a) $\forall x \in \mathbb{Z},; (x > 0 \Rightarrow x^2 > 0)$

(b) $\exists n \in \mathbb{N},; \forall m \in \mathbb{N},; n < m$

(c) $\forall \epsilon > 0,; \exists \delta > 0,; \forall x \in \mathbb{R},; (|x - a| < \delta \Rightarrow |f(x) - L| < \epsilon)$

Problem 4: Set Identities

Let $A,B,C$ be subsets of a universal set $U$. Prove each identity. You may use a set-builder / element-chasing argument or the algebra of sets.

(a) $A\setminus (B\cup C)=(A\setminus B)\cap (A\setminus C)$

(b) $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

Problem 5: Power Set & Cardinality

Let $A=\{1,2,3\}$ and $B=\{x,y\}$.

(a) List the elements of $𝒫(A)$. How many are there? State the general formula for $|𝒫(S)|$ when $|S|=n$.

(b) List the elements of $A\times B$. Confirm that $|A\times B|=|A|\cdot |B|$.

(c) True or false, with justification: $𝒫(A\cup B)=𝒫(A)\cup 𝒫(B)$.

Problem 6: Inclusion-Exclusion

In a class of $60$ students:

• $35$ are enrolled in Discrete Math
• $28$ are enrolled in Linear Algebra
• $12$ are enrolled in both

Let $D$ be the set of Discrete Math students and $L$ the set of Linear Algebra students.

(a) Compute $|D\cup L|$ using the identity $|D\cup L|=|D|+|L|-|D\cap L|$.

(b) How many students are enrolled in neither course?

(c) Draw a labeled Venn diagram that reflects your answer.

Submission

• Place your solutions in problem-set-1.md (or .pdf if you prefer to write by hand and scan).
• Cite any theorem or identity you invoke by name.
• Acceptable use of LLM assistance: see the course syllabus. In short, you may use LLMs to explore ideas but every submitted step must be one you can reconstruct and defend on paper.