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 digraphs.
III. No two Boolean algebras with n atoms are isomorphic.
IV. Non-zero elements of finite Boolean algebra are not uniquely expressible as joins of atoms.
Choose the correct answer from the code given below:
Answer: A. I and II only — ConceptA gate set is functionally complete when every Boolean function can be built using only gates from that set. NAND alone and NOR alone are each…
- A.
I and II only
- B.
II and IV only
- C.
I, II and III only
- D.
I and IV only
Attempted by 407 students.
Show answer & explanation
Correct answer: A
Concept
A gate set is functionally complete when every Boolean function can be built using only gates from that set. NAND alone and NOR alone are each functionally complete, while a combinational logic network is naturally represented by a labelled directed acyclic graph.
With NAND alone: NOT A = A NAND A; A AND B = NOT(A NAND B); A OR B = (NOT A) NAND (NOT B).
With NOR alone: NOT A = A NOR A; A OR B = NOT(A NOR B); A AND B = (NOT A) NOR (NOT B).
A finite Boolean algebra is atomic. If it has n atoms, it is isomorphic to the power-set algebra of an n-element set, and each element is the join of one unique subset of those atoms.
Application
Statement I — true. NAND and NOR can each implement NOT, AND, and OR, so either gate type alone can realize any Boolean logic network.
Statement II — true. For a combinational expression or network, vertices represent labelled inputs or gates and directed edges carry signals toward the output. With no feedback cycle, the representation is a labelled acyclic digraph.
Statement III — false. Every finite Boolean algebra with n atoms has the same power-set structure up to relabelling of atoms; therefore any two such algebras are isomorphic.
Statement IV — false. For any element x, the atoms below x form a uniquely determined set, and their join equals x. Hence the atom-join expression is unique.
Cross-check
An n-atom finite Boolean algebra has 2n elements. Mapping each element to the set of atoms below it gives the power-set isomorphism and simultaneously proves unique atom decomposition.
Therefore, the true statements are I and II only.