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.
Asked
Active
Viewed 68 times
0
-
The and-gate has four possible states, depending on what the values of the inputs are. For example, one possible state has $A$ true and $B$ and $C$ false. You are supposed to write a formula that characterizes all four possible states. – MJD Nov 13 '13 at 03:23
-
@MJD Thanks for the reply, sorry if this sounds stupid but I still don't get it. If an AND gate has three inputs, aren't there only 2 states, a true output and a false output. And it can only be true when all 3 inputs are true? – Ogen Nov 13 '13 at 03:26
-
The and-gate has two inputs, $A$ and $B$, and one output, $C$; the question says this. There are four states because you can set the two inputs any way you want, but having done so, you don't get to choose what $C$ is; the gate chooses for you. So of 8 possible assignments of values to $A$, $B$, and $C$, the presence of the and-gate constrains them so that there are only 4 that can actually be realized. Your job is to write the formula that expresses which 4 of the 8 possible assignments can be realized in the presence of the and gate. – MJD Nov 13 '13 at 04:02
1 Answers
0
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$.
Dilip Sarwate
- 25,197