Does a counterexample always mean the real system is wrong?

No. It may expose a defect in the system design, the property or the abstraction used to represent it.

Is model checking always exhaustive?

Some methods are exhaustive for a finite model; bounded or approximate methods require explicitly stated limits.

Can it prove a neural network is accurate?

Not in the ordinary statistical sense. Formal methods may verify specified properties under constraints, while predictive accuracy still requires suitable empirical evaluation.

AI Glossary / Statistics and probability / Intermediate

Model checking

Definition

Model checking is a method of determining whether a formally specified property holds in the interpretations or system behaviors represented by a model. In the logical-AI sense used here, it can establish entailment by checking that a query is true in every interpretation satisfying a knowledge base. In system verification, related techniques check properties over states and transitions. This entry concerns formal logical checking, rather than statistical goodness-of-fit checking or measuring a machine-learning predictor's accuracy on test data. The meaning of model is therefore a formal interpretation or system representation.

What it means

A set of rules may appear to support a conclusion without actually requiring it. Model checking examines the allowed possibilities systematically. To show that a knowledge base entails a query, every interpretation consistent with the knowledge base must also satisfy the query. Finding one consistent interpretation where the query is false disproves entailment. For a transition system, a counterexample may instead be a sequence of states violating a property. These conclusions are relative to the formal assumptions: an omitted real-world behavior cannot be detected merely by checking an incomplete representation.

How it works

Define the logical language, variables, constraints and property to be checked. For a small propositional knowledge base, enumerate truth assignments, retain those satisfying the rules, and test the query in each retained assignment. Larger problems use more efficient representations and search techniques rather than a literal full truth table. In transition-system verification, include initial states and permitted transitions and specify whether the property concerns reachability, invariants or temporal behavior. Report a verified result, counterexample or bounded/inconclusive outcome precisely, including the assumptions and limits of the analysis.

Three practical examples

Rule-based AI: check whether a conclusion follows from a finite set of encoded facts and implications.
Workflow verification: examine whether a formal process model can reach a state that violates a required condition.
Configuration analysis: find combinations of settings that satisfy the rules but contradict a claimed guarantee. These checks complement testing and requirements review; they do not automatically validate whether the rules capture stakeholder needs.

Think of it this way

Think of checking every arrangement permitted by a rulebook before saying that a conclusion must hold. One valid arrangement that contradicts the conclusion is enough to refute the claim. But if the rulebook accidentally excludes an important real-world arrangement, a successful check says nothing about that omitted case. The strength of the result depends on both exhaustive reasoning and faithful modeling.

Worked example

Use three Boolean propositions P, Q and R. Let the knowledge base contain P implies Q and Q implies R. There are eight possible truth assignments. Exactly four satisfy both rules: (false,false,false), (false,false,true), (false,true,true) and (true,true,true). In all four, P implies R is true, so that implication is entailed. However, R itself is not entailed, because the first assignment satisfies the knowledge base while R is false. Adding the fact P leaves only (true,true,true), after which R is entailed. This original enumeration distinguishes a conditional conclusion from an unconditional fact. It also shows why the assignment with all propositions false is a valid counterexample to R, even though it does not contradict either implication.

Illustrative case study

In a fictional case, Hazel Automation encodes approval rules for an internal workflow. A team claims that every released request must have a recorded review. Model checking finds a permitted state sequence in which an exception path skips the review record. Engineers revise the transition rules and repeat the check, then test the actual implementation against the revised specification. They document the modeled exception paths and external assumptions rather than describing the result as proof that every possible real-world failure has been eliminated.

Common misconceptions and mistakes

A model checker does not automatically know the intended requirements. A property can pass because the model is overly restrictive or because its triggering condition is never reachable. In classical logic, an inconsistent knowledge base entails every formula vacuously, so satisfiability should also be checked. Exhaustive enumeration can grow exponentially with the number of Boolean variables. Bounded checking only covers its stated bounds unless additional reasoning establishes completeness. Formal model checking is different from training an ML model, evaluating predictive accuracy or testing statistical residual assumptions.

Business use

Businesses can apply model checking to well-specified rules, protocols and control flows where rare combinations are difficult to cover by examples alone. Begin with concrete properties and a clear model boundary. Review counterexamples with domain experts to determine whether they reveal a real defect or a modeling mistake. Preserve assumptions, property definitions and tool outcomes in the change record. Link formal results to implementation tests and operational monitoring, because correctness of an abstract model and correctness of its deployed realization are distinct responsibilities.

Check your understanding

Why do the two implications fail to establish R by itself?

Answer: P, Q and R can all be false while both implications remain true. That consistent interpretation is a counterexample to unconditional R. Once P is added as a fact, the implication chain forces Q and then R.

Related terms

Interpretation
Satisfiability
Knowledge base
Logical entailment
counterexample
formal verification
transition system
invariant
bounded model checking

Learn next

Learn truth-table entailment and the role of satisfiability, then compare explicit enumeration with SAT-based reasoning. For system verification, study state-space models, temporal properties, abstraction and the distinction between bounded evidence and a complete verification result.

Sources

Russell and Norvig, Artificial Intelligence: A Modern Approach, Chapter 7 teaching slides on models and entailment: https://aima.cs.berkeley.edu/slides-pdf/chapter07.pdf . Source worklist glossary: https://github.com/aimacode/aima-glossary/blob/master/glossary.md . The three-proposition enumeration and fictional workflow case above are original.

Previous: Model-Centric ML Next: Model debugging