4

Given $n$ Boolean variables $x_1, x_2, \ldots , x_n$, write a function $f(x_1, x_2, \ldots , x_n$) in conjunctive normal form such that “$f = 1$ if and only if exactly one of the $n$ variables is $1$”.

is some one know this question?

Michael Hardy
  • 1
tywtyw2002
  • 89

2 Answers2

1

Start with the DNF which is the disjunction of $n$ conjunctions, each of which has exactly one of the variables without a not and the rest with a not. Then expand that by distributing the or over the internal ands of the conjunctions.

What you'll end up with is a conjunction of disjunctions, and for $n$ variables there will be $2^n-n$ such disjunctions. These disjunctions will be all those obtained by either having all variables with no "not" or having two or more variables with "not".

For example for three variables you will have $2^3-3=5$ terms, the term $$(x_1 \lor x_2 \lor x_3),$$ the three terms having two nots, such as $$x_1 \lor \lnot x_2 \lor \lnot x_3$$ and two others like it, and finally the term with three nots $$\lnot x_1 \lor \lnot x_2 \lor \lnot x_3.$$ The final CNF form will be obtained by putting all five of the above disjunctions together by placing "and" between them.

coffeemath
  • 29,884
  • 2
  • 31
  • 52
0

actually I think you mean one not. two nots would satisfy the condition of one and only one 1, making the function one, which is not in the disjunctive form.

Cole
  • 1
  • Is this answer in response to the question of the OP? If so I don't see anywhere in the OP a reference to "one not" or to "two nots". If it is directed at the answer I gave, your answer would better be a comment on that answer, so it is clear what you refer to. Once this is addressed, I may give a response, provided your comment/answer indeed referred to the answer I gave above. – coffeemath Feb 22 '13 at 02:14