9.1 Counter Examples

Class: CSE 16 Subject: computer-science discrete-math Date: 2024-11-14 Teacher: Prof. Musacchio

Disproof

How to disprove ∀ x ∈ S, P(x).

• Produce an example of an $x\in S$ that makes $P(x)$ false.

How to disprove P(x) ⇒ Q(x).

• Produce an example of an $x$ that makes $P(x$) true and $Q(x)$ false.

Example: Either prove or disprove the following conjecture.

• Conjecture If $A,B$ and $C$ are sets, then $A-(B\cap C)=(A-B)\cap (A-C)$.
  • Disproof. This conjecture is false because of the following counterexample.
  • Let $A=\{1,2,3\}$, $B=\{1,2\}$ and $C=\{2,3\}$. Notice that $A-(B\cap C)=\{1,3\}$ and $(A-B)\cap (A-C)=\varnothing$, so $A-(B\cap C)\ne (A-B)\cap (A-C)$.