Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

Boolean Algebra Theory

Field: Logic Design

Sequence of Expressions

Let (B,∧,∨,¬)(\text{B}, \land, \lor, \neg) be the Boolean algebra defined over the set B={0,1}\text{B} = \{0, 1\}. The structure must satisfy the following axioms for all A,B∈BA, B \in \text{B}: \n1. Commutativity: A∧B=B∧AA \land B = B \land A and A∨B=B∨AA \lor B = B \lor A.\n2. Associativity: (A∧B)∧C=A∧(B∧C)(A \land B) \land C = A \land (B \land C) and (A∨B)∨C=A∨(B∨C)(A \lor B) \lor C = A \lor (B \lor C).\n3. Distributivity: A∧(B∨C)=(A∧B)∨(A∧C)A \land (B \lor C) = (A \land B) \lor (A \land C) and A∨(B∧C)=(A∨B)∧(A∨C)A \lor (B \land C) = (A \lor B) \land (A \lor C).\n4. Identity: A∧1=AA \land 1 = A and A∨0=AA \lor 0 = A.\n5. Complement: A∧¬A=0A \land \neg A = 0 and A∨¬A=1A \lor \neg A = 1.\n6. Absorption: A∧(A∨B)=AA \land (A \lor B) = A and A∨(A∧B)=AA \lor (A \land B) = A.
For any Boolean variables AA and BB, the following identities hold: \n1. Complement of Conjunction: ¬(A∧B)=¬A∨¬B\neg(A \land B) = \neg A \lor \neg B.\n2. Complement of Disjunction: ¬(A∨B)=¬A∧¬B\neg(A \lor B) = \neg A \land \neg B.
Let f:{0,1}n→{0,1}f: \{0, 1\}^n \to \{0, 1\} be an arbitrary Boolean function. Then ff can be uniquely represented in the canonical Sum-of-Products (SOP) form, f(x)=∑I∈MmIf(\mathbf{x}) = \sum_{I \in M} m_I, where MM is the set of minterms xI\mathbf{x}_I such that f(xI)=1f(\mathbf{x}_I) = 1. Equivalently, ff can be uniquely represented in the Product-of-Sums (POS) form, f(x)=∏J∈M′(xJ+1)f(\mathbf{x}) = \prod_{J \in M'} (\mathbf{x}_J + 1), where M′M' is the set of maxterms xJ\mathbf{x}_J such that f(xJ)=0f(\mathbf{x}_J) = 0.
Given a Boolean function f(x1,…,xn)f(x_1, \dots, x_n) defined by its minterms ∑mi\sum m_i, the K-Map method identifies the minimal set of prime implicants by grouping adjacent '1's in the truth table representation. Adjacency is defined by Hamming distance 1 (or 2k2^k grouping). The minimal SOP expression is formed by the union of the essential prime implicants, min(f)=∑Pi\text{min}(f) = \sum P_i, where PiP_i are the prime implicants covering all minterms of ff with the minimum possible cardinality.
Let ff be a Boolean function defined by a set of minterms MM. The algorithm proceeds by: \n1. Initial Grouping: Partition MM into groups GkG_k based on the number of '1's (Hamming weight kk).\n2. Iterative Combination: Repeatedly combine terms Ta,Tb∈GkT_a, T_b \in G_k if they differ in exactly one position jj. The resulting term TabT_{ab} is formed by replacing the differing variable with a dash (wildcard). The new set of terms Gk−1G_{k-1} is formed by these combinations.\n3. Prime Implicant Identification: The set of prime implicants PI\text{PI} consists of all terms generated in the final iteration that cannot be combined further. The minimal SOP form is found by selecting the essential prime implicants (EPIs) using a covering matrix approach.
Define the fundamental Boolean operations Y=f(A,B)Y = f(A, B) using the following formal definitions: \n1. AND Gate (Conjunction): Y=A∧B={1if A=1 and B=10otherwiseY = A \land B = \begin{cases} 1 & \text{if } A=1 \text{ and } B=1 \\ 0 & \text{otherwise} \end{cases}\n2. OR Gate (Disjunction): Y=A∨B={0if A=0 and B=01otherwiseY = A \lor B = \begin{cases} 0 & \text{if } A=0 \text{ and } B=0 \\ 1 & \text{otherwise} \end{cases}\n3. NOT Gate (Negation): Y=¬A=1−AY = \neg A = 1 - A (assuming B={0,1}\text{B} = \{0, 1\}). These operations are idempotent, commutative, and associative.
Definition

Truth Table

Let f:{0,1}n→{0,1}f: \{0, 1\}^n \to \{0, 1\} be a Boolean function mapping an nn-bit input vector x=(x1,…,xn)\mathbf{x} = (x_1, \dots, x_n) to a single output bit. The truth table is a systematic enumeration of the 2n2^n possible input assignments xi\mathbf{x}_i (where ii ranges from 00 to 2n−12^n-1) and the corresponding output value f(xi)f(\mathbf{x}_i), thereby defining the function's complete behavior: f(x)=∑i=02n−1f(xi)⋅Minterm(xi)f(\mathbf{x}) = \sum_{i=0}^{2^n-1} f(\mathbf{x}_i) \cdot \text{Minterm}(\mathbf{x}_i).
Let ff be a Boolean function. The minimal SOP form is defined as f=∑Pif = \sum P_i, where PiP_i are prime implicants, and the set of PiP_i is minimal such that ∑Pi\sum P_i covers all minterms where f=1f=1. The minimal POS form is defined as f=∏Qjf = \prod Q_j, where QjQ_j are prime implicants (maxterms), and the set of QjQ_j is minimal such that ∏Qj\prod Q_j covers all maxterms where f=0f=0. Minimality requires that no prime implicant can be removed without changing the function's truth value.
A Finite State Machine (FSM) is formally defined as a 5-tuple ⟨Q,Σ,Input,Output,δ⟩\langle Q, \Sigma, \text{Input}, \text{Output}, \delta \rangle, where: \n1. QQ is the finite set of states. \n2. Σ\Sigma is the finite input alphabet. \n3. Input:Σ→Input\text{Input}: \Sigma \to \text{Input} maps inputs to output labels. \n4. Output:Q×Σ→Output\text{Output}: Q \times \Sigma \to \text{Output} defines the output based on the current state and input. \n5. δ:Q×Σ→Q\delta: Q \times \Sigma \to Q is the transition function, determining the next state qnext=δ(qcurrent,input)q_{next} = \delta(q_{current}, \text{input}). The machine's behavior is determined by the sequence of states q0,q1,q2,…q_0, q_1, q_2, \dots.
Let A,B,CA, B, C be Boolean variables. The fundamental laws governing simplification include:\n1. Idempotence: A∧A=AA \land A = A and A∨A=AA \lor A = A.\n2. Complementarity: A∧¬A=0A \land \neg A = 0 and A∨¬A=1A \lor \neg A = 1.\n3. Commutativity: A∧B=B∧AA \land B = B \land A and A∨B=B∨AA \lor B = B \lor A.\n4. Associativity: (A∧B)∧C=A∧(B∧C)(A \land B) \land C = A \land (B \land C) and (A∨B)∨C=A∨(B∨C)(A \lor B) \lor C = A \lor (B \lor C).\n5. Absorption: A∧(A∨B)=AA \land (A \lor B) = A and A∨(A∧B)=AA \lor (A \land B) = A.\n6. Distributivity: A∧(B∨C)=(A∧B)∨(A∧C)A \land (B \lor C) = (A \land B) \lor (A \land C) and A∨(BlandC)=(A∨B)∧(A∨C)A \lor (B land C) = (A \lor B) \land (A \lor C).\nThese laws ensure that any complex expression can be reduced to its minimal equivalent form.