How to prove set equality based on the fact that the sets have identical truth tables?

164 Views Asked by At

Let $x \in A$ be logic statement $p$ and $x \in B$ be statement $q$. Prove that $(A \oplus B)'= A' \oplus B$ using the fact that LHS and RHS have identical truth tables.

For LHS: $$ (A \oplus B)' = (A' \cup B) \cap (B' \cup A)\iff \{x:(x\notin A \lor x \in B) \land (x \notin B \lor x \in A) \} \\\iff (\lnot p \lor q) \land (\lnot q \lor p) $$ While for RHS: $$ A' \oplus B = (A' \cap B') \cup (B \cap A) \iff \{x: (x \notin A \land x \notin B) \lor (x \in B \land x\in A)\} \\\iff (\lnot p \land \lnot q) \lor (p \land q) $$ Using Wolfram Alpha the logical statements have the same truth tables (LHS and RHS).

But as far as I know two sets are equal iff they have the same elements. How can I use the fact of identical truth tables to help me?

2

There are 2 best solutions below

4
On BEST ANSWER

The principle is that $\{x: P(x)\} = \{x: Q(x)\}$ if and only if $\forall x:( P(x)\leftrightarrow Q(x))$.   That is: the sets will be equal exactly when the predicates that construct them are identical.

The predicates describe which elements are(or are not) in the set, after all.

You should have $$\begin{align}(A\oplus B)' &= \{x: \neg((x\in A \wedge x\notin B)\vee(x\notin A\wedge x\in B))\} &&\text{by definition of }\oplus \\ &= \{x: \neg ((p\wedge \neg q)\vee(\neg p\wedge q))\} \\ &= \{x: (\neg p\vee q)\wedge(p\vee\neg q))\} \\ &~~\vdots &&\text{see table.}\\ & = \{x: (\neg p\wedge \neg q)\vee(p\wedge q)\}\\ &= \{x: (x\in A'\wedge x\notin B)\vee(x\notin A'\wedge x\in B)\} \\ &= (A'\oplus B) &&\text{by definition of }\oplus \end{align}$$

$\bbox[lemonchiffon,border:1pt solid blue]{\begin{array}{c:c|c:c:c:c|c:c} p & q & p\wedge q & p\wedge \neg q & \neg p\wedge q & \neg p\wedge \neg q & \neg( (p\wedge\neg q)\vee (\neg p\wedge q)) & (\neg p\wedge \neg q)\vee (p\wedge q)\\ \hline \top & \top & \top & \bot & \bot & \bot & \top & \top\\ \hdashline \top & \bot \\ \hdashline \bot & \top \\ \hdashline \bot &\bot \end{array}}$

0
On

Show that $$x\in(A\oplus B)'\iff x\in A'\oplus B$$ by using the definitions of $\oplus$ and ${}'$ to convert both sides into logical combinations of $p$ and $q$.