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 algebras are not uniquely expressible as joins of atoms.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. (i) and (ii) only
Explanation
NAND and NOR are each functionally complete (i true), and expressions/networks are labelled DAGs (ii true). Any two finite Boolean algebras with n atoms are isomorphic (both ≅ the power set of n elements), so (iii) is false, and every non-zero element is a unique join of atoms, so (iv) is false.
More Discrete Structures and Optimisation questions
- The relations ≤ and < on a Boolean algebra are defined as: x ≤ y if and only if x ∨ y = y; x < y means x ≤ y but x ≠ y; x ≥ y means y ≤ x;…
- In PERT/CPM, the merge event represents ___ of two or more events.
- Use the dual simplex method to solve: Maximize z = −2x₁ − 3x₂ subject to x₁ + x₂ ≥ 2, 2x₁ + x₂ ≤ 10, x₁ + x₂ ≤ 8, x₁, x₂ ≥ 0.
- If a graph G has no loops or parallel edges and has n ≥ 3 vertices, then G is Hamiltonian if (i) deg(v) ≥ n/3 for each vertex v (ii) deg(v)…
- Which of the following statements is false about convex minimization problem ?
- The following LPP: Maximize z = 100x₁ + 2x₂ + 5x₃ subject to 14x₁ + x₂ − 6x₃ + 3x₄ = 7, 32x₁ + x₂ − 12x₃ ≤ 10, 3x₁ − x₂ − x₃ ≤ 0, x₁, x₂, x…