Boolean algebra and basic simplification

Contract and goals

Boolean variables take values 0 and 1. Here + means OR, adjacency or · means AND, and a prime means complement: A′ means NOT A. These are Boolean operators, not ordinary integer addition and multiplication. In particular 1+1=1 in Boolean algebra; it does not mean an arithmetic sum of two. We use ⊕ for XOR and explicit parentheses to avoid ambiguity. Evaluate complements first, then AND, then OR when parentheses do not specify otherwise.

Prerequisites: reading truth tables and binary digits. By the end, you should be able to expand a small truth table, apply identities with their conditions, distinguish XOR from OR, and simplify a combinational expression without changing its output. We work with ideal, two-valued, steady-state logic; timing, electrical behavior, hazards and unknown values are outside this model. Algebraic simplification here does not claim minimum area or fastest physical hardware. Karnaugh maps and systematic minimization need later lessons.

1. Operators and truth tables

NOT has one input; AND, OR and XOR below have two. AND is 1 only when both inputs are 1. OR is 1 when at least one is 1. XOR is 1 when exactly one is 1. The truth table lists all input assignments, so it defines the function completely.

A	B	AB	A+B	A⊕B	A′
0	0	0	0	0	1
0	1	0	1	1	1
1	0	0	1	1	0
1	1	1	1	0	0

Two expressions are equivalent exactly when their outputs agree for every assignment to their distinct variables. Two variables require four rows; three require eight. Repeating A several times in an expression does not introduce another independent input. A single mismatch disproves equivalence; a few matching rows do not prove it.

2. Laws you can justify by cases

Identity: A+0=A and A·1=A. Domination: A+1=1 and A·0=0. Idempotence: A+A=A and AA=A. Complement: A+A′=1 and AA′=0. Double complement: (A′)′=A. Check A=0 and A=1 to verify these laws directly.

AND and OR are commutative and associative. Thus A+B=B+A and (AB)C=A(BC). Two distributive laws hold: A(B+C)=AB+AC, and A+BC=(A+B)(A+C). The second law is a distinctive Boolean identity; do not import ordinary arithmetic intuition without checking it. For A=1 both sides of the second law are 1, while for A=0 both sides reduce to BC.

Absorption: A+AB=A. Factor A to get A(1+B)=A·1=A. Its dual is A(A+B)=A. “Dual” exchanges AND and OR and exchanges 0 and 1 throughout an identity; it does not mean complementing each variable. Absorption removes a redundant term, not an arbitrary term that happens to contain a familiar letter.

3. De Morgan and the scope of complement

De Morgan's laws are (AB)′=A′+B′ and (A+B)′=A′B′. Complementing a grouped expression changes the operator and complements every operand. For example, (A+BC)′=A′(BC)′=A′(B′+C′). Only changing + to AND gives the wrong function; only complementing letters also gives the wrong function.

Worked example: simplify (A′B′)′. De Morgan gives (A′)′+(B′)′=A+B. At A=B=1 the original is NOT(0 AND 0)=1, matching OR. The expression A′+B′ instead gives 0 there, proving that dropping the outer complement is not valid.

For more than two operands, apply the same law repeatedly: (ABC)′=A′+B′+C′. A prime applies to its immediate variable or parenthesized group. The expressions A′B and (AB)′ therefore have different truth tables.

4. Worked algebraic reduction

Let F=AB+AB′+A′B. Group the first two terms: AB+AB′=A(B+B′)=A. Then F=A+A′B. Use the second distributive law: A+A′B=(A+A′)(A+B)=1·(A+B)=A+B.

This is an exact functional equivalence. Check every row: at 00, all product terms are zero; at 01, A′B is one; at 10, AB′ is one; at 11, AB is one. The output sequence 0,1,1,1 is OR. Only four rows are needed because there are two distinct inputs, regardless of factoring or how many times those inputs occur in the expression.

A tempting but false step is A+A′B=A+B′. Set A=0,B=1: the left side is 1 but the proposed right side is 0. A counterexample is often faster than trying to identify which invented “law” was used.

5. XOR and parity

XOR has the sum-of-products expression A⊕B=A′B+AB′. The two product terms describe disjoint cases: only B is 1, or only A is 1. OR adds the extra 11 case; therefore A+B and A⊕B are not interchangeable.

XOR satisfies A⊕0=A, A⊕1=A′ and A⊕A=0. It is associative, so A⊕B⊕C is 1 exactly when an odd number of the three inputs are 1. This is odd parity, not “exactly one”: input 111 also produces 1. That distinction will matter for the sum bit of a full adder.

XNOR is the complement of XOR. For two inputs it is 1 when the inputs match, so it can act as a one-bit equality test. For several bits, equality of two words requires all corresponding bit comparisons to match, not a single XOR of every bit in both words.

6. From a truth table to an expression

A minterm is an AND of every input variable exactly once, complemented or uncomplemented. For a row with A=0,B=1,C=0, its minterm is A′BC′. It is 1 only on that row: each literal tests one required bit. OR the minterms of all rows with output 1 to obtain a canonical sum of products (SOP).

Worked example: let F(A,B,C)=1 on rows 001, 011, 101 and 111, with A the most significant index bit. The canonical SOP is A′B′C+A′BC+AB′C+ABC. Group by C: C(A′B′+A′B+AB′+AB)=C. The rows were exactly those with C=1, which explains the simplification directly. If all rows are zero, the empty OR is taken as 0; if every row is one, the function is 1.

“SOP” alone does not require every product term to mention every variable. AB+C is an SOP but is not canonical in variables A,B,C. Canonical means the complete-variable condition in each minterm. A maxterm-based product-of-sums construction is a complementary topic, not required for this first construction.

Reliable workflow and common traps

Write the operator convention, input variables and grouping. Derive each step from a valid identity, then compare complete truth tables as an independent check. Record whether an expression is merely equivalent or proven optimal under a stated cost model. Do not cancel terms as if Boolean expressions were fractions, use A+A=2A, replace OR by XOR, or move a complement without applying De Morgan to the whole group.

Original practice: six single-correct MCQs

These are original foundation questions, not previous-year questions. Choose exactly one option for each.

C01. Which expression is equivalent to A+AB for all Boolean A and B?

A. A+B B. AB C. B D. A

Answer: D

A is incorrect: at A=0,B=1 it gives 1, whereas A+AB gives 0.

B is incorrect: at A=1,B=0 it gives 0, whereas A+AB gives 1.

C is incorrect: at A=1,B=0 it gives 0, whereas the original gives 1.

D is correct by absorption: A+AB=A(1+B)=A.

C02. Apply De Morgan to (A+BC)′. Which result is equivalent?

A. A′+B′C′ B. A′(B′+C′) C. A′B′C′ D. A+B′+C′

Answer: B

A is incorrect: the outer OR must become AND; at A=0,B=C=1 this expression is 1 but the original is 0.

B is correct: (A+BC)′=A′(BC)′=A′(B′+C′).

C is incorrect: complementing BC yields B′+C′, not B′C′; at A=0,B=0,C=1 this choice gives 0 but the original gives 1.

D is incorrect: A must also be complemented; at A=1,B=C=1 this choice gives 1 but the original gives 0.

C03. For which listed assignment do A+B and A⊕B differ?

A. A=0, B=0 B. A=0, B=1 C. A=1, B=1 D. A=1, B=0

Answer: C

A is incorrect: both OR and XOR give 0 at 00.

B is incorrect: both OR and XOR give 1 at 01.

C is correct: at 11, OR is 1 but XOR is 0.

D is incorrect: both OR and XOR give 1 at 10.

C04. With variable order A,B,C, which minterm is 1 only on the row 101?

A. AB′C B. A′BC C. ABC′ D. A+B′+C

Answer: A

A is correct: A=1 requires A, B=0 requires B′, and C=1 requires C; their AND selects exactly 101.

B is incorrect: A′BC selects row 011, not 101.

C is incorrect: ABC′ selects row 110, not 101.

D is incorrect: this is an OR term; it is also 1 on many other rows, such as 100.

C05. How many input rows must be checked to prove two expressions involving only distinct variables A, B and C equivalent by a complete truth table?

A. 3 B. 6 C. 9 D. 8

Answer: D

A is incorrect: 3 counts variables, not their binary assignments.

B is incorrect: 2×3 is not the number of independent choices; the choices multiply.

C is incorrect: 3² would model different choices and is not 2³.

D is correct: each of three independent inputs has two values, giving 2³=8 rows; repeated occurrences do not add inputs.

C06. Which condition makes A⊕B⊕C equal to 1?

A. Exactly one input is 1. B. An odd number of inputs are 1. C. At least one input is 1. D. An even number of inputs are 1.

Answer: B

A is incorrect: it omits 111, which also has XOR value 1.

B is correct: one or three 1s give odd parity and XOR value 1.

C is incorrect: two 1s also satisfy this condition but give XOR value 0.

D is incorrect: zero or two 1s give XOR value 0, not 1.

Syllabus alignment and scope

This is an introductory lesson within Digital Logic, not complete GATE CS Digital Logic coverage. The official GATE 2027 CS syllabus includes Boolean algebra and minimization, combinational and sequential design, and number representation and arithmetic. Karnaugh maps, tabular minimization, sequential design, signed-number arithmetic and floating-point arithmetic require further lessons. The syllabus verifies relevance; examples and questions here are original.

Official GATE 2027 CS syllabus, Section 2 (checked 2026-10-14).

Technical convention reference; original worked examples and practice: MIT Computation Structures combinational logic.