How does validity differ from satisfiability?

Satisfiability needs at least one model; validity requires every interpretation to be a model.

Can validity be tested using a satisfiability solver?

For a suitable propositional encoding, a formula is valid exactly when its negation is unsatisfiable.

Does missing a proof establish invalidity?

No. A search may fail or time out without finding either a proof or a countermodel.

AI Glossary / Graphs and symbolic AI / Advanced

Validity

Definition

In classical logic, validity is truth under every interpretation allowed by the logic. A valid formula cannot be made false by changing the interpretation of its nonlogical symbols. An argument is valid when no interpretation makes all its premises true and its conclusion false. Validity is distinct from a statement being true in one particular situation.

What it means

Logical validity concerns what follows from a formal structure, rather than whether a business record or factual claim happens to be correct. For example, “P or not P” is valid in classical propositional logic because it is true for either truth value of P. The isolated statement P can be true, but it is not valid: assigning P false supplies a counterexample.
An argument's validity does not establish the truth of its premises. A valid argument with true premises is sound in the usual terminology. This distinction matters when an AI system reasons correctly from an inaccurate rule or incorrectly recorded observation. Good inference cannot independently repair the information it starts with.

How it works

For a propositional formula with n distinct variables, a truth table can examine all 2^n truth assignments. The formula is valid if every row evaluates to true. One false row is sufficient to show invalidity.
For a finite set of premises, argument validity can be checked by testing the implication from their conjunction to the conclusion. Equivalently, search for a model of the premises together with the negation of the conclusion. If that conjunction is unsatisfiable, no countermodel exists.
Proof systems provide another route: sound inference rules preserve truth, and appropriate completeness results connect provability to semantic validity. The procedure and guarantees depend on the chosen logic. A finite propositional truth-table check should not be presented as a universal method for every language containing quantifiers or other operators.

Three practical examples

A policy checker examines whether formal approval conditions imply a proposed authorization. A countermodel exposes a combination of conditions under which the premises hold but the authorization does not follow.
A workflow designer checks a claimed consequence of several process rules. The logical check can validate the inference while leaving a separate question about whether the written rules accurately describe operations.
An AI reasoning evaluation distinguishes a persuasive explanation from a valid deduction. Testing possible assignments may reveal an unsupported reversal of an implication that sounds plausible in ordinary language.

Think of it this way

A valid argument is like a connection that never carries true premises to a false conclusion under the specified semantics. That guarantee is conditional on the premises. Checking the connection does not certify that the information supplied at its starting point is true.

Worked example

Consider a toy workflow with P meaning “the request uses the standard route,” Q meaning “the request is approved,” and R meaning “the request is registered.” The rules are P→Q and Q→R. We want to know whether P→R follows.
The corresponding formula is ((P→Q) AND (Q→R))→(P→R). There are three variables, so a full truth table has eight rows. Every row makes this formula true. If P is true and both rules hold, Q must be true and then R must be true. If P is false, P→R is already true under material implication. Rows where the premise conjunction is false also satisfy the outer implication.
Now consider the reverse claim that registration establishes use of the standard route. Add R to the premises and propose conclusion P. The assignment P=false, Q=false, R=true makes P→Q, Q→R, and R all true while P is false. It is therefore a countermodel, proving this reverse argument invalid. Another countermodel is P=false, Q=true, R=true.
The countermodels do not assert that either combination actually occurred. They show that the stated rules do not exclude it. Establishing the reverse inference would require additional justified premises, not merely repetition of the forward rules.

Illustrative case study

In a fictional service portal, a reporting assistant sees the rule “standard-route requests are approved” and concludes that every approved request followed the standard route. The conclusion looks reasonable because most familiar examples use that route.
A reviewer constructs an alternative-route request that is approved. This situation satisfies the original rule but contradicts the assistant's conclusion. The team corrects the inference and checks whether a separate policy actually prohibits alternative approval routes. It finds no such policy in the modeled rules.
The revised explanation states what the available premises support and what remains unestablished. The review separates two tasks: verifying the logical inference and checking the factual and policy evidence. Neither a fluent explanation nor many confirming examples substitute for ruling out countermodels.

Common misconceptions and mistakes

“Valid means true in the current situation.” Validity requires truth across every permitted interpretation.
“One successful example proves validity.” It proves only that the formula is satisfiable in that example.
“An invalid argument must have a false conclusion.” Its conclusion can happen to be true without following from the premises.
“Valid reasoning proves the premises correct.” Validity concerns the connection between premises and conclusion.
“An if - then rule always works backward.” Its converse requires independent justification.

Business use

Validity checks can help review rule-based decisions, authorization logic, and explanations generated from formal premises. Preserve the exact premises and the intended meanings of their symbols so that a passing logical check can be interpreted correctly.
When a check fails, retain the countermodel as a concrete review case. Determine whether it reveals a faulty inference, a missing rule, or an unrealistic interpretation that should be excluded by an explicit assumption. Do not add assumptions solely to force a preferred conclusion. Also check that the premises are mutually consistent: in classical logic, inconsistent premises entail every conclusion, which makes an unchecked entailment result uninformative for practical decision-making.

Check your understanding

How many truth assignments does the worked formula have?

Answer: Eight, because it contains three propositional variables.

Why does the reverse argument fail?

Answer: At least one assignment makes all its premises true and its conclusion false.

What extra requirement makes a valid argument sound?

Answer: Its premises must also be true.

Related terms

Satisfiability
Completeness
Logical entailment
tautology
countermodel
soundness
material implication
truth table

Learn next

Compare a formula's validity with entailment from a knowledge base. Then practice constructing countermodels and checking whether the premises themselves are consistent.

Knowledge base

Sources

University of Texas at Austin, Representation, Reasoning, and Propositional Logic: https://www.cs.utexas.edu/~mooney/cs343/slides/logic.pdf University of Vermont, Propositional Logic, validity and entailment sections: https://www.uvm.edu/~cbcafier/cs-fundamentals/05_logic/propositional_logic.html

Previous: Validation set Next: Value alignment