Which of the following statements are true ? (i) Every logic network is…
2018
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 diagraphs.
(iii) No two Boolean algebras with n atoms are isomorphic.
(iv) Non-zero elements of finite Boolean algebras are not uniquely expressible as joins of atoms
Choose the correct answer from the code given below :
- A.
(i) and (iv) Only
- B.
(i), (ii) and (iii) Only
- C.
(i) and (ii) Only
- D.
(ii), (iii) and (iv) Only
Attempted by 1493 students.
Show answer & explanation
Correct answer: C
Correct answer: the selection that includes statements (i) and (ii) only.
Statement (i): True. NAND and NOR are each functionally complete, so any Boolean function or logic network can be implemented using only NAND gates or only NOR gates.
Statement (ii): True. Boolean expressions and combinational logic circuits can be represented as labelled acyclic directed graphs (nodes labelled by operations or gates, directed edges for signal flow). Sharing subexpressions or fan-out yields a DAG rather than a strict tree.
Statement (iii): False. Finite Boolean algebras with the same number of atoms are isomorphic; concretely, any Boolean algebra with n atoms is isomorphic to the power set algebra of an n-element set.
Statement (iv): False. In a finite Boolean algebra every non-zero element is an (unique) join of the atoms that lie below it; finite Boolean algebras are atomic and elements decompose uniquely into joins of atoms.
Therefore, only statements (i) and (ii) are correct.
A video solution is available for this question — log in and enroll to watch it.