Coursify

When is an Inference Algorithm “Completed”? Soundness, Completeness, and Truth-Preservation

When is an Inference Algorithm “Completed”? Soundness, Completeness, and Truth-Preservation

Verified Sources
Nov 3, 2026

“Inference algorithm is completed only if …” is best understood through the standard meta-properties of proof systems: soundness (proofs are truth-preserving / entailment-preserving) and completeness (all entailments are provable). A proof system (or inference algorithm) is sound if whenever it derives a conclusion from premises, that conclusion is semantically entailed by the premises; it is complete if whenever a conclusion is semantically entailed by the premises, the system can derive it. Soundness is explicitly characterized in terms of preserving entailment/validity (no invalid arguments get derived), while completeness is the converse (every valid entailment has a derivation).3

In the multiple-choice options:

  • (i) “it can derive any sentence” corresponds to an overly strong notion (deriving any arbitrary sentence without regard to whether it follows from the premises). This is not the usual definition of completeness.
  • (ii) “it can derive any sentence that is an entailed version” matches the standard idea of completeness: if a sentence is entailed by the premises, it should be derivable.2
  • (iii) “it is truth preserving” matches soundness (truth of premises guarantees truth of conclusion, equivalently: conclusions are semantically entailed by premises).
  • (iv) combines both, matching the standard requirement for an inference system to be both correct (sound) and fully expressive (complete).

Therefore, the correct condition is (iv): it must both (a) derive every entailed sentence (completeness) and (b) never derive non-entailed sentences (truth-preserving / soundness).3

Key learning terms introduced below will let you connect each option to a formal property:

  • Soundness
  • Completeness
  • Entailment
  • Truth-preserving

Footnotes

  1. Soundness and Completeness (CS 2800, Spring 2016) - Lecture notes defining soundness/completeness as relations between provability and truth/entailment. ↩

  2. Chapter 22 Soundness and completeness ‣ Part IV Natural deduction for TFL ‣ forall x: Calgary - Explains soundness (rules preserve entailment) and completeness (derivation of every semantically valid argument). ↩ ↩2 ↩3

  3. Logical Consequence (Stanford Encyclopedia of Philosophy) - Discusses proof-centered vs model-centered consequence and soundness/completeness theorems aligning them in extension. ↩ ↩2 ↩3

  4. 5.1: Core Concepts - Humanities LibreTexts (Truth Preservation) - Defines truth preservation as “true premises guarantee true conclusion,” matching validity/soundness intuition. ↩

  5. Soundness - Wikipedia - Formal definition of soundness: derivability implies semantic validity/entailment. ↩

Soundness and Completeness (overview)

Map each option (i)–(iv) to soundness/completeness criteria

  1. 1
    Step 1

    “Completed only if …” in logic/proof systems refers to both correctness (soundness) and exhaustiveness (completeness), i.e., agreement between syntactic derivability and semantic entailment.

  2. 2
    Step 2

    Truth-preserving corresponds to soundness: no derivation should take true premises to a false conclusion; equivalently, proofs imply semantic entailment.

  3. 3
    Step 3

    This corresponds to completeness: every semantically valid/entailed conclusion has a derivation.

  4. 4
    Step 4

    (i) “any sentence” ignores dependence on the premises; soundness/completeness are about entailment from premises, not generating arbitrary sentences.

  5. 5
    Step 5

    A system that is both truth-preserving (sound) and able to derive every entailed version (complete) matches (iv).

Core logic: soundness vs completeness vs truth-preservation

Soundness is stated (in standard formulations) as: if the system proves Γ⊢φ\Gamma \vdash \varphi, then semantically Γ⊨φ\Gamma \models \varphi. This is exactly the “no loss of truth” idea, i.e., inference is truth-preserving.3 Completeness is the converse: if Γ⊨φ\Gamma \models \varphi, then Γ⊢φ\Gamma \vdash \varphi.3

This already resolves the choices:

  • (ii) completeness direction only: “derive any sentence that is an entailed version” aligns with Γ⊨φ⇒Γ⊢φ\Gamma \models \varphi \Rightarrow \Gamma \vdash \varphi.2
  • (iii) soundness direction only: “truth preserving” aligns with Γ⊢φ⇒Γ⊨φ\Gamma \vdash \varphi \Rightarrow \Gamma \models \varphi.3
  • (iv) both directions: Γ⊢φ⇔Γ⊨φ\Gamma \vdash \varphi \Leftrightarrow \Gamma \models \varphi, i.e., the algorithm is simultaneously truth-preserving and can derive every entailed sentence.3

Footnotes

  1. Chapter 22 Soundness and completeness ‣ Part IV Natural deduction for TFL ‣ forall x: Calgary - Explains soundness (rules preserve entailment) and completeness (derivation of every semantically valid argument). ↩ ↩2 ↩3 ↩4 ↩5

  2. 5.1: Core Concepts - Humanities LibreTexts (Truth Preservation) - Defines truth preservation as “true premises guarantee true conclusion,” matching validity/soundness intuition. ↩ ↩2

  3. Soundness - Wikipedia - Formal definition of soundness: derivability implies semantic validity/entailment. ↩ ↩2 ↩3 ↩4

  4. Logical Consequence (Stanford Encyclopedia of Philosophy) - Discusses proof-centered vs model-centered consequence and soundness/completeness theorems aligning them in extension. ↩ ↩2

  5. Soundness and Completeness (CS 2800, Spring 2016) - Lecture notes defining soundness/completeness as relations between provability and truth/entailment. ↩

Option-to-property alignment (soundness/completeness)

Each option matches part of the standard soundness/completeness requirements for an inference system.

Common confusion checks

Pro Tip

When you see “only if” with inference algorithms and “completed,” translate it to a biconditional between provability and semantic entailment: soundness (provability ⇒ entailment) plus completeness (entailment ⇒ provability).2

Footnotes

  1. Chapter 22 Soundness and completeness ‣ Part IV Natural deduction for TFL ‣ forall x: Calgary - Explains soundness (rules preserve entailment) and completeness (derivation of every semantically valid argument). ↩

  2. Logical Consequence (Stanford Encyclopedia of Philosophy) - Discusses proof-centered vs model-centered consequence and soundness/completeness theorems aligning them in extension. ↩

Pitfall: mixing “derivable” with “entailed”

If an inference system is not sound, it may still be able to derive entailed sentences (even all of them) but could also derive some non-entailed sentences. That’s why (ii) alone or (iii) alone is insufficient for (iv)’s combined requirement.2

Footnotes

  1. Chapter 22 Soundness and completeness ‣ Part IV Natural deduction for TFL ‣ forall x: Calgary - Explains soundness (rules preserve entailment) and completeness (derivation of every semantically valid argument). ↩

  2. 5.1: Core Concepts - Humanities LibreTexts (Truth Preservation) - Defines truth preservation as “true premises guarantee true conclusion,” matching validity/soundness intuition. ↩

How the properties certify an inference algorithm

Check correctness

Soundness stage

Verify every inference rule preserves semantic validity/truth (derivations imply entailment)."

Check coverage

Completeness stage

Verify that every semantically valid/entailed conclusion has some derivation."

Both directions

Completion

Together they give the intended “completed” alignment: only entailed conclusions are derivable, and all entailed conclusions are derivable."

Knowledge Check

Question 1 of 4
Q1Single choice

Which option matches the standard definition of completeness for an inference/proof system?

Explore Related Topics

1

Knowledge-Based Agents: Inference from Percepts and Prior Knowledge (True/False)

2

Correctness of CFL Closure / Automaton Statements (CFLs, DPDA, Complement)

3

Rice’s Theorem (Undecidability of All Nontrivial Semantic Properties)

Browse all research articles