Mathematical-Reasoning · Unit 17 · Video 1 · Interactive Practice

De Morgan's Law for Unions and Cycles of Conditionals

IKey Formulas

Formula	Name	Where it comes from
$\neg(P \vee Q) \equiv \neg P \wedge \neg Q$	De Morgan's law (logic)	Negating an or gives an and
$(A \cup B)^c = A^c \cap B^c$	De Morgan's law for a union	$x \notin A \cup B \iff x \notin A$ and $x \notin B$
$(A \cap B)^c = A^c \cup B^c$	De Morgan's law for an intersection	Seen earlier with Venn diagrams
$\big[(X \to Y) \wedge (Y \to Z)\big] \to (X \to Z)$	Chaining conditionals	A tautology: true in all 8 rows

Key Insight: A cycle $P \to Q$ , $Q \to R$ , $R \to P$ makes $P$ , $Q$ , $R$ equivalent with three proofs instead of six: each missing direction is a chain of the other two conditionals.

IIComplement of a Union, Region by Region

Two set expressions are the same set exactly when they shade the same regions of the Venn diagram.

Left diagram Right diagram

💡 Challenge: find the expression on the list that names the same set as $A^c \cup B^c$ , and check that it is not $(A \cup B)^c$ .

IIIChaining Conditionals: the Truth Table

The statement $\big[(X \to Y) \wedge (Y \to Z)\big] \to (X \to Z)$ is true in every one of the eight rows.

Column 0

IVA Cycle of Three Conditionals

Which proven conditionals make $P$ , $Q$ and $R$ equivalent? Chaining supplies every conditional the proven ones imply.

Proven conditionals

VQuiz Questions

Problem 1 · Complement of a Union

Given: subsets $A$ and $B$ of a universal set $U$ — which set equals $(A \cup B)^c$ for every choice of $A$ and $B$ ?

✅ Correct!

x \notin A \cup B

means NOT (

x \in A

x \in B

), which is

x \notin A

and

x \notin B

: the complement turns the union into an intersection.

❌ Close, but the operation must flip too.

A^c \cup B^c

is regions 1, 3, 4, which is

(A \cap B)^c

. The set

(A \cup B)^c

is region 4 alone.

❌ Not quite. The complement applies to both sets: an element outside

A \cup B

is outside

A

AND outside

B

Show solution

For $x \in U$ , by the definition of union and De Morgan's law for statements:

x \notin A \cup B \iff \neg(x \in A \vee x \in B) \iff (x \notin A) \wedge (x \notin B) \iff x \in A^c \cap B^c.

In the Venn diagram both $(A \cup B)^c$ and $A^c \cap B^c$ are region 4. The other options are $A^c \cup B^c$ (regions 1, 3, 4), $A^c \cap B$ (region 3) and $A \cup B^c$ (regions 1, 2, 4).

Problem 2 · Compute It Both Ways

Given: $U = \{1, 2, \ldots, 10\}$ , $A = \{1, 2, 3, 4, 5\}$ , $B = \{4, 5, 6, 7\}$ — find $A^c \cap B^c$ .

✅ Correct!

A \cup B = \{1, \ldots, 7\}

, so

(A \cup B)^c = \{8, 9, 10\}

, the same set, as De Morgan's law predicts.

❌ Not quite.

\{4, 5\} = A \cap B

, the elements in both sets.

A^c \cap B^c

wants the elements in neither.

❌ That is $A^c \cup B^c$ . You took the union of the complements; it equals

(A \cap B)^c = U - \{4, 5\}

. Intersect instead: keep only elements outside both sets.

❌ Not quite.

\{1, 2, 3, 6, 7\}

is the elements in exactly one of

A

B

(regions 1 and 3). Elements of

A^c \cap B^c

are in neither.

Show solution

A^c = \{6, 7, 8, 9, 10\}, \qquad B^c = \{1, 2, 3, 8, 9, 10\}

A^c \cap B^c = \{8, 9, 10\}

Check with the other side: $A \cup B = \{1, 2, 3, 4, 5, 6, 7\}$ , so $(A \cup B)^c = \{8, 9, 10\}$ . The two agree, as $(A \cup B)^c = A^c \cap B^c$ requires.

Problem 3 · The Rows Where X → Z Fails

Given: $H = (X \to Y) \wedge (Y \to Z)$ . In the truth table for $H \to (X \to Z)$ , look at the rows where $X$ is true and $Z$ is false (rows 2 and 4) — which statement is correct?

✅ Correct! Row 2 breaks

Y \to Z

and row 4 breaks

X \to Y

, so the hypothesis fails exactly where the conclusion fails.

❌ Not quite. With

Y

true and

Z

false,

Y \to Z

T \to F

, which is false, so

H

is false in row 2.

❌ Not quite. With

X

true and

Y

false,

X \to Y

T \to F

, which is false, so

H

is false in row 4.

❌ A false conclusion is not enough. A conditional is false only when its hypothesis is true AND its conclusion is false; here the hypothesis

H

is false too.

Show solution

Take $X = T$ , $Z = F$ , so $X \to Z$ is $T \to F = F$ .

Row 2 ( $Y = T$ ): $X \to Y = T$ but $Y \to Z = T \to F = F$ , so $H = F$ .

Row 4 ( $Y = F$ ): $X \to Y = T \to F = F$ , so $H = F$ .

In both rows $H \to (X \to Z)$ is $F \to F = T$ . These were the only rows where it could have failed, so the statement is a tautology.

Problem 4 · Which Conditionals Are Enough?

Given: statements $P$ , $Q$ , $R$ — decide what each list of three proven conditionals establishes.

Which three conditionals prove that $P$ , $Q$ , $R$ are equivalent?

With $P \to Q$ , $Q \to R$ and $R \to Q$ proven, which biconditionals follow?

✅ Correct!

P \to R \to Q \to P

is a cycle (in the other direction), so it proves all three biconditionals. In the second list no conditional leads back to

P

, so only

Q \leftrightarrow R

holds.

❌ That chain never closes.

P \to R

already follows from

P \to Q

and

Q \to R

; nothing leads back from

R

, so no converse is proved.

❌ Not quite. Look for a list where every statement has an arrow leaving it and the arrows return to the start; check which statement is never reached.

❌ Nothing leads back to $P$ . No proven conditional ends at

P

, so no chain gives

Q \to P

R \to P

❌ Not quite. Chain the proven conditionals: you get

P \to Q

P \to R

Q \to R

R \to Q

. Which pairs have both directions?

Show solution

First list. In (b), $P \to R$ , $R \to Q$ , $Q \to P$ form a cycle. Each missing direction is a chain: $R \to Q$ and $Q \to P$ give $R \to P$ ; $Q \to P$ and $P \to R$ give $Q \to R$ ; $P \to R$ and $R \to Q$ give $P \to Q$ . All three biconditionals follow.

(a) never reaches $P$ or $Q$ from $R$ . (c) has no arrow leaving $Q$ , so neither $Q \to P$ nor $Q \to R$ follows. (d) never reaches $Q$ , so it gives only $R \leftrightarrow P$ .

Second list. Chaining $P \to Q$ with $Q \to R$ gives $P \to R$ . Nothing leads to $P$ , so $Q \to P$ and $R \to P$ are unproved. Both $Q \to R$ and $R \to Q$ are proven, so the only biconditional is $Q \leftrightarrow R$ .

Solved: 0 / 4