2

I believe there are 3 parts to this.

1) $(A\setminus B) \cup (A\setminus C) = B \Rightarrow A=B $

2) $(A\setminus B) \cup (A\setminus C) = B \Rightarrow (B \cap C) = \emptyset$

3) $A=B \wedge (B \cap C) = \emptyset \Rightarrow (A\setminus B) \cup (A\setminus C) = B$

I can do the the parts labelled 1 and 3 but cannot show part 2. Anyone who can explain how you do the 2nd part ie show $(A\setminus B) \cup (A\setminus C) = B \Rightarrow (B \cap C) = \emptyset$ ?

AlexR
  • 24,905
Namch
  • 39

4 Answers4

1

You have that $(A/B) \cup (A/C)=B$. Then clearly, $B \subseteq A/C$ since it couldn't be in $A/B$ because you just removed all of $B$. So then if $B \subseteq A/C$, that is intuitively, saying, "none of $B$ is in $C$." i.e. $B \cap C = \emptyset$

inkievoyd
  • 1,795
  • 14
  • 25
0

Hint: Let $(A-B)\cup (A-C)=B$ hold true and assume that there is $x \in B \cap C$. This means in particular that $x\in B$ and $x \in C$. Hence $$x \notin A-B$$ and for the same reason $$x\notin A-C$$ Therefore $$x\notin (A-B)\cup (A-C)$$ but on the other hand $x\in B$ which a contradiction to the assumption that $$(A-B)\cup (A-C)=B$$

Jimmy R.
  • 35,868
0

Since you already showed (1), we can use it to ease the proof of (2):

$$(A\setminus B) \cup (A\setminus C) \stackrel{(1)}= (B\setminus B) \cup (B\setminus C) = B \setminus C \stackrel{\text{req.}}= B$$ Now $B\setminus C = B \cap C^C$ by definition, so we have $B \cap C^C = B \Rightarrow B \subset C^C \Rightarrow B \cap C = \emptyset$ as claimed.

AlexR
  • 24,905
0

An systematic solution:

In the table below, every column represents some subexpression and holds truth values meaning "belongs to this set". The rows exhaust all $2^3$ combinations.

The $7^{th}$ column is the LHS of the equivalence and the $11^{th}$ is the RHS. As you can see, they are identical.

A B C A/B A/C  +  =B  A=B B.C =0  and
0 0 0  0   0   0   1   1   0   1   1
1 0 0  1   1   1   0   0   0   1   0
0 1 0  0   0   0   0   0   0   1   0
1 1 0  0   1   1   1   1   0   1   1
0 0 1  0   0   0   1   1   0   1   1
1 0 1  1   0   1   0   0   0   1   0
0 1 1  0   0   0   0   0   1   0   0
1 1 1  0   0   0   0   1   1   0   0

(+ for $\cup$, . for $\cap$)

Grouping all rows in a single hexadecimal number:

A  B  C  A/B A/C  +  =B  A=B B.C =0  and
55 33 0F 44  50  54  98  99  03  FC  98

(/ is and not, + is or, . is and, = is not xor, bitwise)

  • Nice one but in my opinion it would take too long if this was an exam question. – Namch Nov 10 '14 at 15:00
  • For an expression involving $n$ variables and $k$ operators, you will compute $2^n k$ bits, in an automated way. This is to be compared to the symbolic approach. Using a binary or hexadecimal calculator, takes less than a minute ($k$ operations). –  Nov 10 '14 at 15:37