Understanding Logic Networks and Boolean Algebra Statements

The question asks us to identify the true statements among four given options related to logic networks and Boolean algebras. Let's analyze each statement carefully.

Analysis of Statement (i): Universal Gates

Statement (i) says: "Every logic network is equivalent to one using just NAND gates or just NOR gates."

This statement concerns the concept of functional completeness in logic gates. A set of logic gates is functionally complete if any Boolean function can be implemented using only gates from this set. It is a well-known fact in digital logic that both NAND gates and NOR gates are individually functionally complete. This means:

• Any basic logic gate (AND, OR, NOT) can be constructed using only NAND gates. Since any logic network can be built from AND, OR, and NOT gates, any logic network can be built using only NAND gates.
• Similarly, any basic logic gate (AND, OR, NOT) can be constructed using only NOR gates. Therefore, any logic network can also be built using only NOR gates.

Based on this, statement (i) is true.

Analysis of Statement (ii): Graphical Representation

Statement (ii) says: "Boolean expressions and logic networks correspond to labelled acyclic digraphs."

Let's consider each part:

• Logic Networks: A logic network (or digital circuit) is a collection of gates interconnected by wires. This structure naturally forms a directed graph where gates are nodes and wires are edges showing the direction of signal flow. For standard combinational logic circuits (without feedback loops), this graph is acyclic. Nodes (gates) and edges can be "labelled" to indicate the type of gate or the signal name on a wire. Thus, logic networks correspond to labelled acyclic digraphs (directed acyclic graphs, or DAGs).
• Boolean Expressions: A Boolean expression represents a logic function using variables and operators (like AND, OR, NOT). These expressions can be represented graphically as expression trees, which are a specific type of directed acyclic graph. The leaves represent variables, and internal nodes represent operators, with edges showing the input/output relationship. The nodes are labelled by the variables or operators they represent.

Both logic networks and Boolean expressions can indeed be represented by labelled acyclic digraphs. Therefore, statement (ii) is true.

Analysis of Statement (iii): Isomorphism of Boolean Algebras

Statement (iii) says: "No two Boolean algebras with n atoms are isomorphic."

An atom in a Boolean algebra is a non-zero element $a$ such that the only element strictly less than $a$ is the zero element ($\text{0}$). The structure of finite Boolean algebras is well-understood. A fundamental result, a finite version of Stone's Representation Theorem, states that any finite Boolean algebra is isomorphic to the power set algebra $\mathcal{P}(S)$ for some finite set $S$. The number of atoms in a finite Boolean algebra is equal to the size of the set $S$. If a Boolean algebra has $n$ atoms, it is isomorphic to $\mathcal{P}(\{a_1, a_2, \dots, a_n\})$, where $a_i$ are its atoms. The size of such a Boolean algebra is $2^n$.

Crucially, any two sets with the same finite number of elements ($n$) are isomorphic. Consequently, their power set algebras $\mathcal{P}(S_1)$ and $\mathcal{P}(S_2)$ where $|S_1|=|S_2|=n$ are also isomorphic. This implies that any two Boolean algebras with $n$ atoms are isomorphic to each other (specifically, they are both isomorphic to $\mathcal{P}(\{1, 2, \dots, n\})$).

Statement (iii) claims that no two Boolean algebras with $n$ atoms are isomorphic, which contradicts this fact. Therefore, statement (iii) is false.

Analysis of Statement (iv): Unique Expression of Elements

Statement (iv) says: "Non-zero elements of finite Boolean algebras are not uniquely expressible as joins of atoms."

In any finite Boolean algebra, every non-zero element $x$ can be expressed as the join of the atoms $a$ such that $a \le x$. Moreover, this representation is unique. The set of atoms below $x$, $\{a \mid a \text{ is an atom and } a \le x\}$, uniquely determines the element $x$. The join of these atoms is precisely $x$. This is a key property derived from the structure of finite Boolean algebras, which are isomorphic to power set algebras where elements are sets and atoms correspond to singleton sets.

For example, in the power set algebra $\mathcal{P}(\{1, 2, 3\})$, the atoms are $\{1\}$, $\{2\}$, $\{3\}$. The element $\{1, 3\}$ can be expressed as the join (union) of atoms $\{1\} \cup \{3\}$. This representation is unique; no other set of atoms will join to give $\{1, 3\}$.

Statement (iv) claims that non-zero elements are not uniquely expressible as joins of atoms, which contradicts this unique expressibility. Therefore, statement (iv) is false.

Summary of Findings

Based on our analysis:

• Statement (i): True
• Statement (ii): True
• Statement (iii): False
• Statement (iv): False

The true statements are (i) and (ii).

Conclusion

Statements (i) and (ii) are true, while statements (iii) and (iv) are false. Therefore, the correct option includes only statements (i) and (ii).

Revision Table: Logic Networks and Boolean Algebra Facts

Additional Information: Exploring Concepts Further

Functional Completeness in Detail

A set of logical connectives or gates is functionally complete if it can be used to express all possible truth functions. For example, $\{ \land, \lor, \neg \}$ (AND, OR, NOT) is functionally complete. What makes NAND and NOR special is that each of them *alone* forms a functionally complete set. This is why they are often called "universal gates".

• Using only NAND: $\neg A = A \text{ NAND } A$; $A \land B = \neg (A \text{ NAND } B) = (A \text{ NAND } B) \text{ NAND } (A \text{ NAND } B)$; $A \lor B = (\neg A) \text{ NAND } (\neg B) = (A \text{ NAND } A) \text{ NAND } (B \text{ NAND } B)$.
• Using only NOR: $\neg A = A \text{ NOR } A$; $A \lor B = \neg (A \text{ NOR } B) = (A \text{ NOR } B) \text{ NOR } (A \text{ NOR } B)$; $A \land B = (\neg A) \text{ NOR } (\neg B) = (A \text{ NOR } A) \text{ NOR } (B \text{ NOR } B)$.

Digraphs for Logic and Expressions

Representing logic circuits and Boolean expressions as directed acyclic graphs (DAGs) is standard practice in areas like circuit design, optimization, and compilation. For circuits, gates are nodes, and connections are edges. Input nodes have no incoming edges, output nodes have no outgoing edges (or edges going to primary outputs). For Boolean expressions, an expression like $(A \land B) \lor C$ can be a tree structure:

      OR
     /  \
   AND   C
  /   \
 A     B

This is a labelled acyclic digraph. Shared subexpressions in a Boolean expression or logic network can lead to a DAG structure that is not strictly a tree, reducing redundancy.

Finite Boolean Algebras and Atoms

A Boolean algebra is a set $B$ with operations $\lor$ (join), $\land$ (meet), and $\neg$ (complement), and special elements $\text{0}$ (least element) and $\text{1}$ (greatest element), satisfying certain axioms (associativity, commutativity, absorption, distribution, complement laws, identity laws). A finite Boolean algebra always has $2^n$ elements for some non-negative integer $n$. The number $n$ is precisely the number of atoms in the algebra. Stone's theorem is a powerful result showing the deep connection between Boolean algebras and topology (for the general case) and set theory (for the finite case). The isomorphism between any finite Boolean algebra and a power set algebra $\mathcal{P}(S)$ of its atoms $\{a_1, \dots, a_n\}$ implies that the structure is completely determined by the number of atoms.