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

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?

• Your have a logical (or at least notational) flaw here: "one set equals some other set is logically equivalent to some set, is logically equivalent to a statement" make s no sense. – Hagen von Eitzen Mar 31 '18 at 10:04
• @HagenvonEitzen I wanted to say that $(A \oplus B)'$ means that/is equivalent to the logical statement. I'm not sure what notation should be used for this. – Yos Mar 31 '18 at 10:06
• The notation is that the set construction is the set, so for instance : $$A\cap B {~= \{x: x\in A\wedge x\in B\} \\~= \{x: p\wedge q\}}$$ That is: the union of sets A and B is the set of entities for which the statement $p\wedge q$ is satisfied. – Graham Kemp Mar 31 '18 at 10:27

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}}$

• If I complete the "why" step in your explanation then I wouldn't need truth tables. As far as I understand I should arrive to the step when $(A \oplus B)'=...= \{x : (\lnot p \lor q) \land (\lnot q \lor p)\}$ and then separately $(A' \oplus B) = ... = (\lnot p \land \lnot q) \lor (p \land q)$ and then I can say that because the truth tables are equal therefore the two sets are equal because as you mentioned $\{x: P(x)\} = \{x: Q(x)\}$ iff $\forall x:( P(x)\leftrightarrow Q(x))$ – Yos Mar 31 '18 at 10:38
• You don't need truth tables, @Yos . Use distribution. – Graham Kemp Mar 31 '18 at 11:19
• That's definitely one way to solve it but in the OP I'm explicitly asking for a way to solve it using truth tables. – Yos Mar 31 '18 at 11:19
• @Yos Then just fill in a truth table and verify the relevant columns have the same value in every row. – Graham Kemp Mar 31 '18 at 11:31

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$.