Does a valid implication prove its antecedent?

No. It states the relationship without establishing the antecedent's truth.

Can one counterexample disprove entailment?

Yes, when it satisfies every premise and falsifies the conclusion.

Does an inconsistent premise set entail everything in classical logic?

Yes; there is no interpretation satisfying all those premises.

AI Glossary / Mathematics and optimization / Advanced

Deduction theorem

Definition

The deduction theorem connects reasoning from an assumption with reasoning about an implication. In the semantic form used here, a sentence α entails a sentence β exactly when the implication α → β is logically valid. Entailment means that every interpretation satisfying the premise also satisfies the conclusion. Validity means truth in every interpretation. The theorem lets an inference question be expressed as a validity question about one formula.

What it means

The distinction is between saying that a conclusion follows when certain premises hold and saying that a conditional statement holds in every permitted interpretation. The theorem connects these claims without asserting that the premises hold in the world.
A related proof-theoretic form, in suitable classical proof systems, moves an assumption into the antecedent of a proved implication: Γ together with α proves β if and only if Γ proves α → β. Here Γ denotes background premises. Semantic entailment and formal provability are different notions; soundness and completeness explain their relationship for a system.

How it works

In classical propositional logic, α → β is false only when α is true and β is false. That is exactly the kind of interpretation that would disprove α's entailment of β. The absence of such a counterexample establishes both sides of the semantic theorem.
For finitely many premises, combine them with conjunction. Checking whether α₁, …, αₙ entail β is equivalent to checking whether (α₁ ∧ … ∧ αₙ) → β is valid. An alternative is to ask whether the premises together with ¬β are satisfiable. A satisfying assignment is a counterexample; unsatisfiability establishes the entailment in this setting.

Three practical examples

A rule-system designer checks whether a collection of configuration rules guarantees a requested condition. The rules become the antecedent and the requested condition the consequent of a validity test.
A theorem-proving exercise establishes a conditional result by temporarily assuming its antecedent, deriving the consequent and then discharging the temporary assumption under the proof system's rules.
A software-verification example translates a collection of propositional assumptions into a counterexample search. Finding an assignment where the assumptions hold but the required conclusion fails reveals a gap in the proposed inference.

Think of it this way

Think of packaging a promise with its conditions attached. Instead of handing over the conclusion alone, you hand over the statement that the conclusion follows if those conditions are met. The packaging preserves the dependency. Removing a condition is a separate change that needs justification; a valid conditional does not supply evidence that its condition has been fulfilled.

Worked example

Let s mean that a request is signed, c that its certificate is current, and a that it is accepted. Suppose the sole background rule is (s ∧ c) → a: a signed request with a current certificate is accepted. These propositions form an illustrative logical model, not a description of a real security policy.
Under this background rule, temporarily assume s. Within that assumption, temporarily assume c. Conjunction gives s ∧ c, and the background rule yields a. Discharging the c assumption gives c → a while s remains assumed. Discharging s then gives s → (c → a), still relative to the background rule.
The corresponding single validity claim is [(s ∧ c) → a] → [s → (c → a)]. There are eight truth assignments for the three propositions. Checking them all confirms that the formula is true in every assignment. Intuitively, the two nested antecedents preserve both requirements.
Now consider the attempted shortcut s → a. The background rule does not entail it. Set s to true, c to false and a to false. The background rule is true because s ∧ c is false, but s → a is false. This one counterexample disproves the shortcut.
The valid derivation therefore retains the certificate condition. It does not conclude that every signed request is accepted, nor does it conclude that any particular request is signed or accepted.

Illustrative case study

In a fictional workflow project, a team receives a proposed rule summary stating, “If the request is signed, it is accepted.” The underlying specification also requires a current certificate, as in the worked example.
A reviewer represents the proposed summary as a conclusion and asks whether it follows from the specification. The signed-but-not-current counterexample passes the original implication while failing the summary. This shows that the summary discarded a necessary assumption for that inference.
The team restores the missing condition and separately checks whether the rules are consistent. If the premises contradicted one another, classical entailment could make every conclusion follow vacuously. A successful validity check would then fail to demonstrate that any realistic request satisfies the specification. The team treats consistency, inference correctness and actual request data as distinct checks with different purposes.

Common misconceptions and mistakes

Entailment is not the same as a material implication being true in one observed situation. The relevant implication must be valid across all interpretations of the formal setting. Nor does entailment generally run backward: α entailing β does not establish that β entails α.
Discharging an assumption does not make it an unconditional fact. Keep track of the background premises that remain. Finally, proof-theoretic deduction theorems depend on the logic and its inference rules; quantified settings require attention to their conditions rather than an unrestricted transfer of a propositional proof pattern.

Business use

The theorem helps analysts express what a rule set actually guarantees and locate missing assumptions in proposed summaries. Make propositions and background rules explicit, preserve the direction of implications and retain counterexamples when a claim fails. Check that the formal premises reflect the intended process. Logical validity establishes a relationship within the model; it cannot independently verify whether the model's descriptions match an operational system.

Check your understanding

Which assignment defeats the shortcut?

Answer: Signed true, current false and accepted false.

Why does the original rule remain true there?

Answer: Its conjunctive antecedent is false.

What did the nested implication preserve?

Answer: Both conditions required to derive acceptance from the background rule.

Related terms

Validity
Satisfiability
Logical entailment
material implication
conditional proof
assumption discharge
counterexample
soundness

Learn next

Practice converting finite-premise entailment problems into validity and counterexample tests. Then compare semantic arguments with formal proofs that explicitly track temporary assumptions.

Validity

Sources

AIMA glossary, deduction theorem: semantic connection between entailment and valid implication. https://github.com/aimacode/aima-glossary/blob/master/glossary.md Stanford Introduction to Logic, Lesson 3, especially section 3.6: finite-premise formulation and the connection with unsatisfiability. https://logical.stanford.edu/intrologic/sections/section_03.html?section=1 The request-rule proof, eight-assignment check and fictional workflow case are original teaching illustrations.

Previous: Deconvolutional Network Next: Deductive classifier