Combination Sets

Question

A combination on $n$ objects can be represented by an $n$ bit binary vector, $(X_n, X_{n-1}, \dots, X_2, X_1)$, where each bit, $X_k \in \{1, 0\}$, expresses whether the corresponding object is included in the combination or not. A set of combinations can be represented by a set of the $n$ bit binary vectors. We call such sets combination sets. Combination sets can be regarded as subsets of the power set on $n$ object.

We can represent a combination set with a Boolean function by using n input variables for each bit of the vector. The output value of the function expresses whether each combination specified by the input variables are included in the set or not. Such Boolean functions are called characteristic functions. The operations of sets, such as union, intersection, and difference, can be executed by logic operations on characteristic functions.

Can anyone please make me understand this combination sets with an example?

Can anyone please make me understand this characteristic functions with an example?

Answer 1

Here is the example. Let $n=4$, and let the objects be (in order) $Alice, Bob, Carol, Dan$.

Then the combination $\{ Alice, Carol \}$ is represented by the vector $(1, 0, 1, 0)$.

The first $1$ means that $Alice$ (the first object) is in the combination. The second digit is $0$: this means that $Bob$ (the second object)is not in the combination.

And so on.

In the same way, every binary vector represents a combination. For example the vector $(0,1,1,1)$ represents the combination $\{ Bob, Carol, Dan\}$.

Answer 2

The characteristic function corresponding to a subset $A\subset \{0,1\}^n$ is a function $\mathsf 1_A:\{0,1\}^n\to\{0,1\}$ where $\mathsf 1_A(x)= 1$ if $x\in A$ and $\mathsf 1_A(x) = 0$ if $x\notin A$. The union $A\cup B$ can be represented by $\mathsf 1_A\vee \mathsf 1_B$, the intersection $A\cap B$ by $\mathsf 1_A\wedge \mathsf 1_B$, and the complement $\{0,1\}^n\setminus C$ by $\mathsf 1_{\{0,1\}^n}\wedge\lnot \mathsf 1_C$.