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?

  • $\begingroup$ I don't understand the question. What are you trying to prove or find? $\endgroup$ – Code-Guru Feb 9 '14 at 1:54
  • $\begingroup$ 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 $\endgroup$ – Code-Guru Feb 9 '14 at 1:56
  • $\begingroup$ So what part of the problem are you having trouble with? $\endgroup$ – Code-Guru Feb 9 '14 at 1:57
  • $\begingroup$ part(b) is confused to me. I get a similar result like @eudoxyz but I dont understand the simplifying part $\endgroup$ – SonicFancy Feb 9 '14 at 21:12

(a) $$f(x_1;\dots ;x_n) = x_1 \vee \cdots \vee x_n$$

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!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.