# 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?

• I don't understand the question. What are you trying to prove or find? – Code-Guru Feb 9 '14 at 1:54
• Never mind, the edit has significantly changed the meaning of the problem by changing the word "Give" to "Given". Unfortunately, I do not have enough rep to change it back. @mathematics2x2life – Code-Guru Feb 9 '14 at 1:56
• So what part of the problem are you having trouble with? – Code-Guru Feb 9 '14 at 1:57
• part(b) is confused to me. I get a similar result like @eudoxyz but I dont understand the simplifying part – SonicFancy Feb 9 '14 at 21:12

(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!

• can you explain the part (b) some more? – SonicFancy Feb 9 '14 at 21:11
• Sure. Explanation now added in the answer. – eudoxyz Feb 10 '14 at 1:57