Witness (satisfying assignment): meaning and examples

A witness, or satisfying assignment, is one assignment of values to the variables that makes a formula true. It is the evidence the engine shows whenever a verdict depends on a single row existing.

Some claims are about one row (“there is a case where this holds”) and some are about all rows (“this holds in every case”). A witness settles the first kind: show the row, and the claim is established. A counterexample settles the negation of the second kind in the same way. Both are written as assignments, A = FALSE, B = TRUE, and the engine replays every one through its independent evaluator before display, so a witness on the page has been checked twice, by two different pieces of code.

The artefact on this page is the 4-row table of (A OR B) AND NOT A, whose output column reads false, true, false, false. The satisfiable check holds with the witness A = FALSE, B = TRUE: on that row A OR B is true and NOT A is true, so f is true. The contradiction check is violated with the same row as its counterexample, since one true row is all it takes to refute “always false”. The tautology check is violated with the counterexample A = FALSE, B = FALSE, row 0.

Witnesses turn an abstract verdict into a test case. A witness for “this rule can grant access” is an input that grants access, ready to be typed into a test; a witness for premise consistency is a scenario in which all the premises hold at once. The term is confused with a counterexample, which refutes rather than proves, and with a general proof, which a witness never is: one row shows that something can happen, never that it always does.

Example

f := (A OR B) AND NOT A · output

Exact checks

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

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

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

Truth table (4 rows)

Witness (satisfying assignment): meaning and examples
#	A	B	f
0	FALSE	FALSE	FALSE
1	FALSE	TRUE	TRUE
2	TRUE	FALSE	FALSE
3	TRUE	TRUE	FALSE

Plain-language reading

Beginnerf is true exactly when both of the following hold:
1. at least one of A or B is true (both may be true)
2. A is false
In every other case, f is false.
About the operators:
- AND is true only when all of its parts are true.
- OR is inclusive: it is true when at least one part is true, including when several are.
- NOT reverses a value: true becomes false and false becomes true.

Intermediatef is true exactly when both of the following hold:
1. at least one of A or B is true (both may be true)
2. A is false
In every other case, f is false.

Advancedf is true exactly when both of the following hold [conjunction ∧]:
1. at least one of A or B is true (both may be true) [inclusive disjunction ∨]
2. A is false [negation ¬]
In every other case, f is false.
Formal notation: (A ∨ B) ∧ ¬A

The common slip

Reading a witness as typical. A = FALSE, B = TRUE is one row that makes (A OR B) AND NOT A true; it says nothing about the other three rows, on which the formula is false. A witness proves possibility, not frequency.

Questions

Why does the engine replay witnesses?

Because the fast path that finds a row and the evaluator that checks it are separate code, and a witness is only shown if the evaluator agrees that the formula is true on it. A disagreement would be a bug to report, not a result to display.

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.