Consider combinational logic networks and finite Boolean algebras. Which of the following statements are true? (i) Every logic network is equivalent to one using just NAND gates or just NOR gates. (ii) Boolean expressions and logic networks correspond to labelled acyclic digraphs. (iii) No two Boolean algebras with n atoms are isomorphic.
(i) and (ii) only
(i) is true because NAND alone and NOR alone are each functionally complete. (ii) is true because combinational circuits have no feedback cycles; their gates and connections form labelled directed acyclic graphs, while Boolean expressions can be represented by expression trees.
(iii) is false: every finite Boolean algebra with n atoms is isomorphic to the power-set algebra on an n-element set, so any two such algebras are isomorphic. (iv) is false: every nonzero element is uniquely determined by the set of atoms below it and is their join. Thus only (i) and (ii) are true.
Important Questions from Basic Gates
Which of the following gates gives output 1 when any one of the input is 1?
Minimum number of NAND gates required to implement the following binary equation $Y = (A+B)(\overline{C \cdot D})$
Which of the following logic gates has output low when one of the inputs is high?
A + B = Y is the Boolean function for
The NAND gate output will be low if the two inputs are-
