Combinational logic: meaning and examples

Combinational logic is a circuit whose outputs depend only on its current inputs, with no memory and no feedback. Every combinational circuit is a set of Boolean functions, one per output, and so has a truth table.

The contrast is with sequential logic, where flip-flops or latches store state and the output depends on the history of the inputs as well. A combinational circuit can be described completely by a truth table with one column per output, by a formula per output, or by a gate network without loops; the three descriptions are interchangeable, and the engine's decision mode, with its named outputs, is exactly the formula-per-output view. Adders, multiplexers, decoders and comparators are the standard examples.

The artefact on this page is the full adder. Its two outputs are sum = A XOR B XOR Cin and carry_out = (A AND B) OR (Cin AND (A XOR B)). Over 8 rows the sum column reads false, true, true, false, true, false, false, true, true exactly when an odd number of inputs are true, and the carry column reads false, false, false, true, false, true, true, true, true when at least two inputs are true. The satisfiable check on sum holds with the witness A = FALSE, B = FALSE, Cin = TRUE.

Combinational logic is the part of hardware that the whole of this reference applies to directly: simplification, normal forms, Karnaugh maps and gate conversion all operate on it. In software, a pure function of its arguments is the same idea. The term is confused with sequential logic, with “combinatorial” (the mathematics of counting, a different word), and a multi-output circuit is sometimes mistaken for one function when it is several sharing inputs.

Example

sum := A XOR B XOR Cin · outputcarry_out := (A AND B) OR (Cin AND (A XOR B)) · output

Exact checks

Always true (tautology)? No Counterexample: A = F, B = F, Cin = F · Exhaustively checked and solver cross-checked · 1 rows

Always false (contradiction)? No Counterexample: A = F, B = F, Cin = T · Exhaustively checked and solver cross-checked · 2 rows

Can be true? Yes Example assignment: A = F, B = F, Cin = T · Exhaustively checked and solver cross-checked · 2 rows

Truth table (8 rows)

Combinational logic: meaning and examples
#	A	B	Cin	sum	carry_out
0	FALSE	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	TRUE	FALSE
2	FALSE	TRUE	FALSE	TRUE	FALSE
3	FALSE	TRUE	TRUE	FALSE	TRUE
4	TRUE	FALSE	FALSE	TRUE	FALSE
5	TRUE	FALSE	TRUE	FALSE	TRUE
6	TRUE	TRUE	FALSE	FALSE	TRUE
7	TRUE	TRUE	TRUE	TRUE	TRUE

Plain-language reading

Beginnersum is true exactly when an odd number of A, B, and Cin are true (1 or 3 of them).
In every other case, sum is false.
About the operators:
- A chain of XORs is true when an odd number of its parts are true. With three parts, all three being true also counts: it does not mean “exactly one”.

Intermediatesum is true exactly when an odd number of A, B, and Cin are true (1 or 3 of them).
In every other case, sum is false.

Advancedsum is true exactly when an odd number of A, B, and Cin are true (1 or 3 of them) [parity: n-ary exclusive disjunction ⊕].
In every other case, sum is false.
Formal notation: A ⊕ B ⊕ Cin

Logic diagram

The common slip

Expecting a single truth table column for a circuit with two outputs. The full adder has two functions over the same three inputs, and each needs its own column and its own checks; a property that holds of sum says nothing about carry_out. The checks on this page are for sum.

Questions

Why is a chain of two XORs the right sum for an adder?

Adding three bits gives an odd total exactly when one or three of them are 1, and a chain of XORs is true exactly when an odd number of its inputs are true. The engine's reading states that rule, including the case where all three are true.

Guides

Practice

Glossary

Generated from the Tangibool engine, semantics tangibool-semantics/1, engine 1.0.0, build 2026-11-07. Every table, map, simplification and verdict on these pages was computed by the Tangibool engine when the site was built, and every claim was re-checked by the same exact checker the app uses. Limits are stated where they apply. © 2026 Foreranger LTD.