You may recognise AND, OR, and NOT symbols yet lose the connection between voltage levels, bits, truth tables, expressions, and the circuit finally built. One three-variable function restores that chain end to end. F(A,B,C)=Σm(1,3,5,6,7) has eight truth-table rows, a five-term canonical SOP, a three-term canonical POS, a K-map with two overlapping groups, and a circuit of one AND gate feeding one OR gate, and all of those forms are the same function: F=C+AB. GATE-style problems and technical interviews test exactly these conversions, and the wider route is organised under GATE CS Exam Preparation Courses & Test Series.
Digital systems begin with a two-state abstraction
A physical signal can take many values, but digital logic maps valid ranges to two discrete symbols. Think of a switch as open or closed, then label those logical states 0 and 1. These are abstractions, not a promise that every circuit uses exactly 0 V and 5 V.
A bit holds one binary value. A binary word is a group of bits. Inputs enter a logic function, which maps each input combination to an output. For inputs A, B, and C, there are 2^3 = 8 combinations, from 000 to 111. Four inputs would give 2^4 = 16 combinations.
A combinational circuit depends only on current inputs, as a full adder does. A sequential circuit also depends on stored state, as a flip-flop or counter does.
Boolean variables, operators, and logic gates
A Boolean variable is restricted to {0,1}. Here A' means NOT A, AB or A.B means A AND B, A+B means A OR B, and A XOR B means exclusive OR. The + sign and juxtaposition are logical operators, not ordinary integer arithmetic.
NOT reverses one input: 0 -> 1 and 1 -> 0. The main two-input gates are:
AB | AND | OR | XOR | NAND | NOR | XNOR |
|---|---|---|---|---|---|---|
00 | 0 | 0 | 0 | 1 | 1 | 1 |
01 | 0 | 1 | 1 | 1 | 0 | 0 |
10 | 0 | 1 | 1 | 1 | 0 | 0 |
11 | 1 | 1 | 0 | 0 | 0 | 1 |
For two inputs, XOR is 1 when exactly one input is 1. Each operator has a gate symbol. A network evaluates inputs into intermediate signals and then an output. NAND and NOR are universal because either gate type alone can reproduce NOT, AND, and OR.
Boolean algebra laws make simplification reliable
The basic identities can be checked by substituting X=0 and X=1:
Identity:
X+0=X,X.1=X. For example,1+0=1.Domination:
X+1=1,X.0=0. For example,0+1=1.Idempotence:
X+X=X,X.X=X. For example,1.1=1.Complement:
X+X'=1,X.X'=0. For example,0+1=1.Involution:
(X')'=X. Complementing0twice returns0.
Also use commutative (X+Y=Y+X, XY=YX), associative ((X+Y)+Z=X+(Y+Z), (XY)Z=X(YZ)), distributive (X(Y+Z)=XY+XZ, X+YZ=(X+Y)(X+Z)), and absorption (X+XY=X, X(X+Y)=X) laws. The second distributive form often surprises learners coming from ordinary algebra, so check it at X=0, Y=1, Z=0: X+YZ=0+0=0, and (X+Y)(X+Z)=(0+1)(0+0)=1.0=0.
De Morgan's laws keep the complement's scope visible: (X+Y)'=X'Y' and (XY)'=X'+Y'. At X=1, Y=0, (1+0)'=0, while 1'.0'=0.1=0. Duality swaps + with ., and 0 with 1, turning one identity into another valid identity. Evaluate complements first, AND second, and OR last, unless brackets change the order.
Five equivalent ways to specify one Boolean function
Consider the rule: output 1 when C=1, or when both A=1 and B=1. Its direct expression is F=C+AB. The same function can be given as a verbal rule, truth table, Boolean expression, canonical form, or gate diagram.
A minterm is a product containing every variable once and is 1 on one row. With order A,B,C, m1=001=A'B'C, m5=101=AB'C, and m6=110=ABC'. A maxterm is a sum that is 0 on one row. For row 010, M2=(A+B'+C).
Treat ABC as a binary number with A as the most significant bit. Ones at rows 1,3,5,6,7 give F=Σm(1,3,5,6,7). Zeros at 0,2,4 give the equivalent F=ΠM(0,2,4). Continue with the Boolean Algebra and K-map Minimization Guide for prime implicants and don't-care conditions.
Worked example: from eight rows to F=C+AB
Let F(A,B,C)=Σm(1,3,5,6,7). Build the truth table in binary order:
A | B | C | F |
|---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
The canonical SOP is A'B'C + A'BC + AB'C + ABC' + ABC. The zero rows produce the canonical POS (A+B+C)(A+B'+C)(A'+B+C).
Place the rows on a three-variable K-map with rows AB=00,01,11,10 in Gray order and columns C=0,1. Group m1,m3,m7,m5, the full C=1 column, to obtain C. Group m6,m7 across row AB=11 to obtain AB. Overlap at m7 is valid, so F=C+AB.
Check three different rows:
At
110,F=0+(1.1)=1, matchingm6.At
100,F=0+(1.0)=0, so 4 is correctly absent fromΣm(1,3,5,6,7).At
011,F=1+(0.1)=1, matchingm3.
The simplified circuit needs one 2-input AND gate for X=AB, followed by one 2-input OR gate for F=C+X. Input C goes directly to the OR gate.
How GATE-style questions and interviews test these basics
These five questions all resolve from the same eight rows:
How many rows do three inputs produce?
2^3=8, because each input has two choices.What is the minterm at
101?m5=AB'C, since onlyBis 0.How do the zero rows read?
F=ΠM(0,2,4), because those are precisely the three rows where F is 0.What is F at
110?1, becauseAB=1even thoughC=0.What is the simplified function?
C+AB, from the fullC=1group and theAB=11pair.
Do not confuse input combinations with functions. For n inputs, there are 2^n rows. Assigning either output to every row creates 2^(2^n) possible functions. At n=3, that means 2^3=8 rows and 2^8=256 functions.
Problems can ask you to match an expression to a table, use a law, convert Σm to ΠM, trace gates, count functions, or distinguish combinational logic from stored state. Interviews may ask why X+X'=1, how to build a rule with gates, or how OR differs from XOR. Use the GATE Test Series as a timed-practice next step.
Common Boolean algebra traps and their corrections
In Boolean OR, 1+1=1, not 2. Juxtaposed 11 means 1 AND 1 only when Boolean notation is intended. De Morgan gives (A+B)'=A'B', not A'+B'. OR and XOR differ at A=B=1: OR is 1, XOR is 0.
Every canonical minterm or maxterm contains every variable exactly once. The binary input gives the index, not the number of complements, so m6=ABC' and M2=A+B'+C. K-map labels use Gray order 00,01,11,10, not binary order 00,01,10,11.
When reading a circuit, evaluate intermediate wires before the final gate, trace inversion bubbles, and do not treat stored state as ordinary combinational wiring. The next application layer is Combinational Circuits: MUX, Decoders, Adders, where Boolean functions become reusable building blocks.
Digital systems and Boolean basics in one minute
Digital logic maps valid physical ranges to symbols.
ninputs give2^ntruth-table rows.Gates implement Boolean operators.
Boolean laws change an expression without changing its function.
A truth table is the final equivalence check.
Canonical SOP lists 1-rows, while canonical POS lists 0-rows.
F=Σm(1,3,5,6,7)simplifies toF=C+AB.
KnowledgeGate's question bank carries about 60 questions on digital fundamentals and Boolean algebra for further practice. Use GATE Guidance by Sanchit Sir for a structured, subject-wise route through the wider syllabus. K-map minimization and combinational circuits are the two branches that follow directly from F=C+AB.
Finally, rebuild the eight-row truth table and derive C+AB without looking. If every representation agrees, the topic has become a method rather than a list of symbols.
