# Homework Help: Constructing Proofs help

1. Mar 9, 2005

### SpatialVacancy

Constructing Proofs help!!

Here is the problem:

Given a set $$S$$ and subset $$A$$, the characteristic function of A, denoted $$\chi_A$$, is the function defined from $$S$$ to $$\mathbb{Z}$$ with the property that for all $$u \ \epsilon \ S$$:

$$\chi_A(u)= \begin{cases} 1 & \text{if u  \epsilon \ A} \\ 0 & \text{if u  is not \ \epsilon \ A} \end{cases}$$

Show that each of the following holds for all subsets $$A$$ and $$B$$ of $$S$$ and all $$u \ \epsilon \ S$$.

a. $$\chi_{A \cap B}(u)= \chi_A (u) \cdot \chi_B (u)$$
b. $$\chi_{A \cup B}(u)= \chi_A (u) + \chi_B (u) - \chi_A (u) \cdot \chi_B (u)$$

2. Mar 10, 2005

### Galileo

The brute straightforward way is:
Compute both sides of the equations for all cases:
(I) u is in A and B
(II) u is in A or B, but not both.
(III) u is not in A and not in B.

3. Mar 10, 2005

### xanthym

.
You might present the proof in "Truth Table" format and show equivalence via Table equality. For example:
Code (Text):

.
.[COLOR=Blue]-----------------------> [B]Χ(A ∩ B)[/B][/COLOR]

Member
B
YES         NO

YES       [B][COLOR=Red]1 [/COLOR]         0[/B]
Member
A
NO        [B]0          0[/B]

.[COLOR=Blue]----------------------> [B]Χ(A)*Χ(B)[/B][/COLOR]

Member
B
YES         NO

YES    (1)*(1)    (1)*(0)
Member            [B][COLOR=Red]1[/COLOR]          0 [/B]
A
NO     (0)*(1)    (0)*(0)
[B]0          0[/B]

Last edited: Mar 10, 2005