# Can someone help me prove that: ((A cap B)⊕A)′=A′ cup B.

Can someone help me prove that:
$\left(\left(A\cap B\right)\oplus A{\right)}^{\prime }={A}^{\prime }\cup B$
A′ is A complement.
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

berouweek
Step 1
$\begin{array}{}\text{aka Xor}& p\oplus q\equiv \left(p\wedge \mathrm{¬}q\right)\vee \left(\mathrm{¬}p\wedge q\right)\equiv \left(p\vee q\right)\wedge \left(\mathrm{¬}p\vee \mathrm{¬}q\right)\end{array}$
This set notation '$\oplus$' corresponding to xor in logic.
Any $x\in \left(\left(A\cap B\right)\oplus A{\right)}^{\prime }$ if and only if:
$\mathrm{¬}\left(\left(x\in A\wedge x\in B\right)\oplus x\in A\right)$
Since $\mathrm{¬}\left(\left(p\wedge q\right)\oplus p\right)↔\left(\mathrm{¬}p\vee q\right)$ is a tautology,
It's clearly equivalent to $x\notin A\vee x\in B$, hence proved…
Apply def. of Xor:
$\mathrm{¬}\left(\left(\left(x\in A\wedge x\in B\right)\wedge x\notin A\right)\vee \left(\mathrm{¬}\left(x\in A\wedge x\in B\right)\wedge x\in A\right)\right)$
Apply Commutative law & Associative law:
$\mathrm{¬}\left(\left(\left(x\in A\wedge x\notin A\right)\wedge x\in B\right)\vee \left(\mathrm{¬}\left(x\in A\wedge x\in B\right)\wedge x\in A\right)\right)$
Apply Negation law:
$\mathrm{¬}\left(\left(\mathrm{\perp }\wedge x\in B\right)\vee \left(\mathrm{¬}\left(x\in A\wedge x\in B\right)\wedge x\in A\right)\right)$
Apply Domination law:
$\mathrm{¬}\left(\mathrm{\perp }\vee \left(\mathrm{¬}\left(x\in A\wedge x\in B\right)\wedge x\in A\right)\right)$
Apply Identity law:
$\mathrm{¬}\left(\mathrm{¬}\left(x\in A\wedge x\in B\right)\wedge x\in A\right)$
Apply De Morgan's law:
$\mathrm{¬}\left(\left(x\notin A\vee x\notin B\right)\wedge x\in A\right)$
Apply Distributive law:
$\mathrm{¬}\left(\left(x\notin A\wedge x\in A\right)\vee \left(x\notin B\wedge x\in A\right)\right)$
Apply Negation law:
$\mathrm{¬}\left(\mathrm{\perp }\vee \left(x\notin B\wedge x\in A\right)\right)$
Apply Domination law:
$\mathrm{¬}\left(x\notin B\wedge x\in A\right)$
Apply De Morgan's law:
$x\in B\vee x\notin A$
Apply Commutative law:
$x\notin A\vee x\in B$
This hold if and only if $x\in {A}^{\prime }\cup B$
Step 2
Hence we proved $\begin{array}{}◻& \left(\left(A\cap B\right)\oplus A{\right)}^{\prime }={A}^{\prime }\cup B\end{array}$
###### Did you like this example?
iarc6io
Step 1
Note that $\oplus$ denotes the symmetric difference between two sets. In other words,
$P\oplus Q=\left(P-Q\right)\cup \left(Q-P\right)=\left(P\cap {Q}^{\prime }\right)\cup \left(Q\cap {P}^{\prime }\right)$
Step 2
Using this definition as well as set identities, we have the following proof:
$\left(\left(A\cap B\right)\oplus A{\right)}^{\prime }$
$=\left[\left(\left(A\cap B\right)\cap {A}^{\prime }\right)\cup \left(A\cap \left(A\cap B{\right)}^{\prime }\right){\right]}^{\prime }$ ----- by definition of $\oplus$
$=\left[\left(\left(B\cap A\right)\cap {A}^{\prime }\right)\cup \left(A\cap \left(A\cap B{\right)}^{\prime }\right){\right]}^{\prime }$ ----- by the commutative law
$=\left[\left(B\cap \left(A\cap {A}^{\prime }\right)\right)\cup \left(A\cap \left(A\cap B{\right)}^{\prime }\right){\right]}^{\prime }$ ----- by the associative law
$=\left[\left(B\cap \mathrm{\varnothing }\right)\cup \left(A\cap \left(A\cap B{\right)}^{\prime }\right){\right]}^{\prime }$ ----- by the complement law
$=\left[\mathrm{\varnothing }\cup \left(A\cap \left(A\cap B{\right)}^{\prime }\right){\right]}^{\prime }$ ----- by the domination law
$=\left[A\cap \left(A\cap B{\right)}^{\prime }{\right]}^{\prime }$ ----- by the identity law
$={A}^{\prime }\cup \left(A\cap B{\right)}^{″}$ ----- by DeMorgan's law
$={A}^{\prime }\cup \left(A\cap B\right)$ ----- by the double complement law
$=\left({A}^{\prime }\cup A\right)\cap \left({A}^{\prime }\cup B\right)$ ----- by the distributive law
$=U\cap \left({A}^{\prime }\cup B\right)$ ----- by the complement law
$={A}^{\prime }\cup B$ ----- by the identity law
###### Did you like this example?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee