Examples of boolean functions in conjunctive normal form Give an $n$-variable Boolean function $f(x_1; x_2; \cdots ; x_n)$ in conjunctive normal form so that $f$ is $1$, respectively,
(a) If at least one of the $n$ variables is $1$;
(b) If at most one of the $n$ variables is $1$.
Can you guys help this and give briefly an explanation?
 A: (a) $$f(x_1;\dots ;x_n) = x_1 \vee \cdots \vee x_n$$
(b) 
You get the conjunctive normal form after successively applying the distributive property to the following: $$f(x_1;\dots ;x_n)= (\neg x_1 \wedge \cdots \wedge \neg x_n) \bigvee_{i \in \{1,\dotsc,n\}} (\neg x_1 \wedge \cdots \wedge x_i \wedge \cdots \wedge \neg x_n)$$
When looking at the truth table of $n$ variables, your function $f(x_1;\dots ;x_n)$ evaluates to $1$ exactly when all of the variables are $0$, or precisely one of them is $1$. This makes for a total of $n+1$ rows in the table. And as you know, the table has $2^n$ rows. Now there is a theorem which states that if an identity holds on $\mathcal{B}_2$ (two-element Boolean algebra), then it must hold on an arbitrary Boolean algebra. And there is another theorem which states that for every Boolean function $f:\{0,1\}^n \to \{0,1\}$ on $\mathcal{B}_2$, there is a corresponding term $g(x_1; \dots ;x_n)$ such that $g$ is equivalent to the canonical disjunctive normal form:
$$g(x_1;\dots ;x_n)= \bigvee_{f(\alpha_1,\dotsc,\alpha_n)=1} (x_1^{\alpha_1} \wedge \cdots \wedge x_n^{\alpha_n})$$
$\alpha \in \{0,1\}$ and $x^0 = \neg x$, $x^1=x$. 
This may seem confusing, but essentially it means that you're looking only at those rows in the table where $f$ evaluates to $1$, and then you make a canonical conjunction out of variables in that particular row. And in the end, you have the canonical disjunctive normal form by joining these with $\vee$. 
For example, imagine you have a function $f$ with three variables $x,y,z$, and this function evaluates to $1$ at exactly three places, say when: $x=0, y=0, z=0$; $x=0, y=1, z=1$; $x=1, y=0, z=0$. Then our corresponding term becomes: $f(x,y,z)=\neg x \neg y \neg z \vee \neg x y z \vee x \neg y \neg z$. 
This last theorem also works for making canonical conjunctive normal forms, because of the duality principle for Boolean algebras. But for your particular case this means you'd have $2^n - (n + 1)$ distinct conjuncts, and it's a bit trickier to represent in a concise form, because of the many possible cases where more than one variable is $1$. But it is exactly what you'll get after successive application of the distributive property to the above canonical disjunctive normal form!
