Questions: Soundness and Completeness of Propositional Logic

Question 1

Which statement correctly distinguishes soundness from completeness for propositional logic?

• A. Soundness: every valid formula is provable (⊨ φ ⟹ ⊢ φ); Completeness: every provable formula is valid (⊢ φ ⟹ ⊨ φ)
• B. Soundness: every provable formula is valid (⊢ φ ⟹ ⊨ φ); Completeness: every valid formula is provable (⊨ φ ⟹ ⊢ φ)
• C. Soundness and completeness are the same property stated in different terms
• D. Soundness concerns the axioms; completeness concerns the inference rules

Answer: (B)

Soundness goes from syntax to semantics: if you can derive φ (⊢ φ), then φ is logically valid (⊨ φ). It says the proof system never proves falsehoods. Completeness goes from semantics to syntax: if φ is logically valid (⊨ φ), then it is provable (⊢ φ). It says the proof system never misses a truth. The two directions are converses, not the same claim.

Question 2

A proof system for propositional logic that includes most valid natural deduction rules plus additional rules that derive some non-tautologies is very likely to be complete.

• T. True
• F. False

Answer: False

Adding rules that derive non-tautologies breaks soundness — the system can now prove formulas that are not valid. A system can only be meaningfully 'complete' if it is also sound; an unsound system trivially 'proves' everything (including contradictions) and the notion of completeness loses its meaning. Completeness is only a virtue in the context of a sound system.

Question 3

Why is it necessary to prove both soundness AND completeness, rather than just one of them?

Model answer: Soundness alone guarantees the proof system is trustworthy (no false theorems) but leaves open that some valid formulas may be unprovable — the system could be too weak. Completeness alone guarantees no valid formula is missed but does not prevent the system from also proving invalid formulas — it could be too permissive. Together they establish a perfect correspondence: ⊢ φ if and only if ⊨ φ. The proof system is neither too weak nor too strong — it captures exactly the valid formulas.

The joint result ⊢ φ ⟺ ⊨ φ means that provability and logical truth coincide. This is what makes the proof system a reliable decision procedure for validity: you can work entirely syntactically (manipulating symbols) and be guaranteed your conclusions match semantic reality (truth under all assignments).