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:
- A.
I and II only
- B.
II and IV only
- C.
I, II and III only
- D.
I and IV only
Attempted by 254 students.
Show answer & explanation
Correct answer: A
I. Every logic network is equivalent to one using just NAND gates or just NOR gates.
True. NAND and NOR are known as universal gates. Any Boolean function (and thus any logic network) can be implemented using only NAND gates or only NOR gates.
II. Boolean expressions and logic networks correspond to labelled acyclic digraphs.
True. Logic networks are represented as Directed Acyclic Graphs (DAGs), where nodes represent gates or inputs, and edges represent the flow of signals. Since logic flows from inputs to outputs without circular dependency in standard combinational logic, they are acyclic.
III. No two Boolean algebras with n atoms are isomorphic.
False. According to Stone's Representation Theorem for finite Boolean algebras, every finite Boolean algebra is isomorphic to the power set of its atoms. If two Boolean algebras have the same number of atoms (n), they both have 2n elements and are, in fact, isomorphic to each other.
IV. Non-zero elements of finite Boolean algebra are not uniquely expressible as joins of atoms.
False. In a finite Boolean algebra, every non-zero element x can be uniquely expressed as the join (OR) of the set of atoms {a : a <= x}. This is a fundamental property of atomic Boolean algebras.