Homework: Conjunctive Normal Form

Question

The way I understand CNF is as an expression containing AND's of OR's. So an AND-GATE with 3 inputs (A, B and C) should just be A AND B AND C. But apparently this is incorrect. Any guidance would be greatly appreciated, thank you.

Answer 1

The CNF has one term for each set of values of the inputs $A$ and $B$ for which the output $C$ has value $0$. Since $C = 0$ whenever at least one of $A$ and $B$ have value $0$, we have that

$$C = ({A} \vee {B})\wedge ({A} \vee \bar{B})\wedge (\bar{A} \vee {B}).$$ The first term on the right has value $0$ when $A = B = 0$, the second when $A = 0, B = 1$, and the third when $A = 1, B = 0$. Thus, in all these cases, one of the terms "being ANDed together" has value $0$ and hence the AND gives $0$. The only case when all three terms on the right have value $1$ is $A = B = 1$, and thus $C$ equals $1$ exactly when $A=B=1$.