

Introduction to Logic

Tools for Thought


Properties and Relationships 
Before we end this lesson, it is worth noting that there are some strong connections between logical properties like validity and satisfiability and the logical relationships introduced in the preceding three sections.

First of all, there is a connection between the logical equivalence of two sentences and the validity of the biconditional sentence built from the two sentences. In particular, we have the following theorem expressing this connection.
Equivalence Theorem: A sentence φ and a sentence ψ are logically equivalent if and only if the sentence (φ ⇔ ψ) is valid.
Why is this true? Consider the definition of logical equivalence. Two sentences are logically equivalent if and only if they are satisfied by the same set of truth assignments. Now recall the semantics of sentences involving the biconditional operator. A biconditional is true if and only if the truth values of the conditional sentences are the same. Clearly, if two sentences are logically equivalent, they are satisfied by the same truth assignments, and so the corresponding biconditional must be valid. Conversely, if a biconditional is valid, the two component sentences must be satisfied by the same truth assignments and so they are logically equivalent.

There is a similar connection between logical entailment between two sentences and the validity of the corresponding implication. And there is a natural extension to cases of logical entailment involving finite sets of sentences. The following theorem summarizes these results.
Deduction Theorem: A sentence φ logically entails a sentence ψ if and only if (φ ⇒ ψ) is valid. More generally, a finite set of sentences {φ_{1}, ... , φ_{n}} logically entails φ if and only if the compound sentence (φ_{1} ∧ ... ∧ φ_{n} ⇒ φ) is valid.
If a sentence φ logically entails a sentence ψ, it means that any truth assignment that satisfies φ also satisfies ψ. Looking at the semantics of implications, we see that an implication is true if and only if every truth assignment that makes the antecedent true also makes the consequent true. Consequently, logical entailment holds exactly when the corresponding implication is valid.

There is also a connection between logical entailment and unsatisfiability. In particular, if a set Δ of sentences logically entails a sentence φ, then Δ together with the negation of φ must be unsatisfiable. The reverse is also true.
Unsatisfiability Theorem: A set Δ of sentences logically entails a sentence φ if and only if the set of sentences Δ ∪ {¬φ} is unsatisfiable.
Suppose that Δ logically entails φ. If a truth assignment satisfies Δ, then it must also satisfy φ. But then it cannot satisfy ¬φ. Therefore, Δ ∪ {¬φ} is unsatisfiable. Suppose that Δ∪{¬φ} is unsatisfiable. Then every truth assignment that satisfies Δ must fail to satisfy ¬φ, i.e. it must satisfy φ. Therefore, Δ must logically entail φ.
An interesting consequence of this result is that we can determine logical entailment by checking for unsatisfiability. This turns out to be useful in various logical proof methods, as described in the following lessons.

Finally, consider the definition of logical consistency. A sentence φ is logically consistent with a sentence ψ if and only if there is a truth assignment that satisfies both φ and ψ. This is equivalent to saying that the sentence (φ ∧ ψ) is satisfiable.
Consistency Theorem: A sentence φ is logically consistent with a sentence ψ if and only if the sentence (φ ∧ ψ) is satisfiable. More generally, a sentence φ is logically consistent with a finite set of sentences {φ_{1}, ... , φ_{n}} if and only if the compound sentence (φ_{1} ∧ ... ∧ φ_{n} ∧ φ) is satisfiable.

In thinking about these various connections, the main thing to keep in mind is that logical properties and logical relationships are metalevel. They are things we assert in talking about logical sentences; they are not sentences within our formal language. By contrast, implications and biconditionals and conjunctions are statements within our formal language; they are not metalevel statements. What the preceding paragraphs tell us is that we can implicitly express some logical relationships within our formal language by writing the corresponding biconditionals and implications and conjunctions and checking for the logical properties of these sentences.

Use the arrow keys to navigate.
Press the escape key to toggle all / one.

