Completeness and Soundness in Propositional Logic
SUMMARY
This class addresses the relationship between completeness and soundness in propositional logic. Although deduction techniques and semantics in propositional logic have been widely discussed, little attention has been paid to the relationship between these two facets. Soundness refers to the property of a logical system where, whenever an expression G can be inferred from a set of expressions Γ, G is consequently a (semantic) consequence of Γ. On the other hand, completeness refers to the property of a logical system where, if G is a semantic consequence of a set of expressions Γ, then there exists a formal proof with premises Γ from which G can be inferred. It is shown that propositional logic is sound and complete, and a detailed explanation of each property is presented. In particular, it is shown how soundness derives from the constitution of the deductive system of propositional logic, and how completeness is inferred in a simple way. This analysis is of great importance for understanding how propositional logic works and for applying it effectively in various fields of knowledge.
LEARNING OBJECTIVES:
By the end of this class, the student will be able to:
- Distinguish between soundness and completeness in a logical system.
- Apply the truth table for Łukasiewicz’s axioms to demonstrate the soundness of propositional logic.
- Explain how modus ponens can be rewritten using the semantic version of the deduction theorem.
- Understand that soundness and completeness are related and can be inferred from one another.
- Analyze the concept of tautology and its relationship with theorems in propositional logic.
INDEX
COMPLETENESS AND SOUNDNESS IN PROPOSITIONAL LOGIC
PROPOSITIONAL LOGIC IS SOUND
PROPOSITIONAL LOGIC IS COMPLETE
Completeness and Soundness in Propositional Logic
At this point, it is time to talk about the completeness and soundness of propositional logic. It turns out that so far, a lot has been said about deduction techniques and the semantics of propositional logic, but everything has been done in a way that makes them seem like two completely independent facets without any relation to each other. The reality is completely opposite.
SOUNDNESS: On one hand, a logical system is said to be sound when, whenever an expression G can be inferred from a set of expressions \Gamma, it follows that G is a (semantic) consequence of \Gamma |
COMPLETENESS: On the other hand, it is said to be complete when, if G is a semantic consequence of a set of expressions \Gamma, then there exists a formal proof with premises \Gamma from which G can be inferred. |
Reviewing these ideas, we will see that completeness and soundness are satisfied for propositional logic.
Propositional Logic is Sound
It is easy to obtain the soundness of propositional logic by observing the constitution of its deductive system. If we make the truth table for Łukasiewicz’s axioms, we will see that they have a structure such that they always yield true as a truth value, that is:
| \models (\alpha \rightarrow (\beta \rightarrow \alpha)) |
| \models ((\alpha \rightarrow (\beta \rightarrow \gamma))\rightarrow ((\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma))) |
| \models ((\neg\beta \rightarrow \neg\alpha)\rightarrow(\alpha \rightarrow \beta)) |
Similarly, modus ponens can be rewritten as \{\alpha,(\alpha\rightarrow \beta)\}\models \beta. which can be obtained using the semantic version of the deduction theorem. In fact, by this means we have that \{(\alpha\rightarrow \beta)\}\models (\alpha\rightarrow \beta), and then \models ((\alpha\rightarrow \beta)\rightarrow (\alpha\rightarrow \beta)), which of course is a more than obvious tautology.
Propositional Logic is Complete
The completeness of propositional logic tells us that, if B is a semantic consequence of A, then B is inferred from A. In other words: all true expressions have a proof. This is what we call completeness. This can be inferred in a simple way.
This can be inferred in a simple way. Suppose that B cannot be inferred from A, or rather \neg(A\vdash B), by the deduction theorem this is equivalent to saying that: \neg (\vdash A\rightarrow B); now, if we resort to soundness, this leads us to \neg(\models A \rightarrow B), which by the contrapositive of the deduction theorem (semantic version) is equivalent to \neg(A\models B). In summary, what we have is that
\neg(A\vdash B) \Rightarrow \neg(A\models B)
Which is equivalent to saying
(A\models B) \Rightarrow (A\vdash B)
This means that, if A models B, then B is inferred from A. And if we use the respective deduction theorems, we can obtain
(\models A\rightarrow B) \Rightarrow (\vdash A \rightarrow B)
That is: if an expression is a tautology, then it is a theorem; and as we have seen, theorems are the result of a proof.