> Source URL: /demos/discrete-demo/logic.problems
---
title: "Problem Set 1: Logic & Sets"
topic: Propositional Logic, Predicate Logic, Sets
estimated_time: 45-60 minutes
---

<style>body { font-family: sans-serif; }</style>

# 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**: $\land$ (and), $\lor$ (or), $\neg$ (not), $\Rightarrow$ (implies), $\Leftrightarrow$ (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) \Leftrightarrow (\neg p \lor q)
$$

---

## Problem 2: Logical Equivalence

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

$$
\neg (p \land (\neg p \lor q)) \;\equiv\; \neg p \lor \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 $\mathcal{P}(A)$. How many are there? State the general formula for $|\mathcal{P}(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: $\mathcal{P}(A \cup B) = \mathcal{P}(A) \cup \mathcal{P}(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.


---

## Backlinks

The following sources link to this document:

- [Logic Problems](/demos/discrete-demo/index.demo.llm.md)