Module: Sentential logic
Quote of the page
An intellectual is someone whose mind watches itself.
- Albert Camus
Armed with truth-tables we can now use them to classify WFFs in SL according to their different logical status :
A tautology is any WFF in SL that is true under all assignments of truth-values to its sentence letters. Examples:
An inconsistent WFF is any WFF in SL that is false under all assignments of truth-values to its sentences letters:
If a WFF is not inconsistent, then it is consistent. In other words, there is always at least one assignment where the WFF is true.
A contingent WFF is any WFF in SL that is not inconsistent and not a tautology. In other words, there is at least one assignment under which it is true, and at least another assignment under which it is false. All single sentence letters are of course contingent. These WFFs are also contingent : (P&Q), (P∨Q), ~(P→~Q).
True or false?
Determine whether these WFFs are tautological, contingent, or inconsistent:
Apart from talking about the properties of individual WFFs, we can also use truth-tables to identify logical relations between WFFs in SL.
Earlier we talk about a single WFF being consistent or inconsistent. Actually we can also talk about consistency as the property of a set of one or more WFFs. A set of WFF is said to be consistent (with each other) when there is at least one assignment of truth-value under which all the WFFs in the set are true. Otherwise the set of WFFs is inconsistent - there is not even one single assignment of truth-values that would make all the WFFs true.
Suppose we have a WFF φ and a set of (one or more) WFF ψ1...ψn. We define entailment as follows :
ψ1...ψn entail φ if and only if there is no assignment of truth-value under which ψ1...ψn are true and φ is false.
So for example, ~P entails ~~~P. To show this we draw their truth-tables together :
When P is true, ~P is false, and so is ~~~P. When P is F, ~P is true, and so is ~~~P. Since there is no assignment where ~P is true and ~~~P is false, the first entails the second.
Another example :
This tells us that (P↔Q), ~P entail ~Q. Note that under the second assignment, (P↔Q) and ~P are both F and ~Q is T. This does not show that there is no entailment. To prove entailment in this example, you need to ensure that when the first two WFFs are true, the third WFF must also be true. So the last assignment is the one to check.
You should be able to work out for yourself that these claims are true :
In symbolic notation, we indicate entailment and failure of entailment as follows :
Entailment : ψ1...ψn ⊧ φ No Entailment : ψ1...ψn ⊭ φ
Equivalently we might also say :
You might perhaps realize by now that entailment provides a more precise definition of validity in SL. An argument is valid when and only when it is impossible for the premises to be true and the conclusion to be false at the same time. What this means when the argument is an argument in SL is that the premises entail the conclusion in the way just defined.
Notice that an argument in a formal system of logic is often called a sequent. So a valid argument in SL is called a "valid sequent", and an invalid argument in SL is called an "invalid sequent".
Now that we know what entailment is, we can easily prove these two theorems :
Theorem 1 : For any WFF φ, φ ⊧ φ.
Proof : Since φ is identical to itself, there cannot be any assignment where φ is true and φ is false. So φ entails φ.
Theorem 2 : For any WFFs φ1 ... φn and any tautology ψ, φ1 ... φn ⊧ ψ.
In other words, a tautology is entailed by any set of WFFs. Proof : Given that ψ is a tautology, it is true under all assignments. So there is no assignment where ψ is false and φ1 ... φn are true, whatever φ1 ... φn are.
Logical equivalence can be defined in terms of entailment as follows :
For any WFFs φ and ψ, φ is logically equivalent to ψ if and only if φ ⊧ ψ and ψ ⊧ φ.
We might use this symbol "≡" to express logical equivalence :
φ is logically equivalent to ψ : φ ≡ ψ
Obviously, these claims are all true :
We can show that some connectives can be defined in terms of others, e.g.
(P→Q) ≡ (~P∨Q)
(P&Q) ≡ ~(~P∨~Q)
(P∨Q) ≡ ~(~P&~Q)
(P↔Q) ≡ ((P→Q)&(Q→P))
You would probably find it surprising that given our definition of entailment, inconsistent WFFs entail every WFF. So for example, the following sequent is valid :
P, ~P ⊧ Q
This sequent is valid because there is no assignment under which P, ~P are true and Q is false. There is no such assignment simply because P, ~P cannot be true! By the same reasoning, the sequent will still be valid whatever WFF you replace Q with.
No doubt you might find it hard to accept that from an inconsistent sentence, everything follows. Here is a way of understanding why we might want to live with a definition of entailment that has such a consequence. First of all, presumably we want the following sequent to be valid :
The earth is round ⊧ Either the earth is round, or pigs can fly.
On the other hand, we also want this sequent to be valid :
Either the earth is round, or pigs can fly. The earth is not round. ⊧ Pigs can fly.
If these two sequents are valid, then surely we should also have a valid sequent when we put the two together :
The earth is round. The earth is not round. ⊧ Pigs can fly.
Of course, you can replace "pigs can fly" with any statement you want. This shows that as long as we accept that (1) from any statement "P" we can conclude "(PvQ)", and (2) from "(PvQ)" and "~P" we can conclude "Q", then we would have to accept that "P" & "~P" entail all statements!
If you still find it strange that from an inconsistent sentence, everything follows, you might be interested in this (supposedly true) story about the famous philosopher / logician Bertrand Russell. He was asked the question, You mean from the statement 2+2=5 it follows that you are the Pope? Can you prove it? Russell said yes and then came up with this proof on the spot:
Now, Russell continues, the Pope and I are two. Since two equals one, then the Pope and I are one. Hence I am the Pope.
Are these statements true or false?