9. “… if and only if …”, Using Theorems
9.1 A historical example
The philosopher David Hume (17111776) is remembered for being a brilliant skeptical empiricist. A person is a skeptic about a topic if that person both has very strict standards for what constitutes knowledge about that topic and also believes we cannot meet those strict standards. Empiricism is the view that we primarily gain knowledge through experience, particular experiences of our senses. In his book, An Inquiry Concerning Human Understanding, Hume lays out his principles for knowledge, and then advises us to clean up our libraries:
When we run over libraries, persuaded of these principles, what havoc must we make? If we take in our hand any volume of divinity or school metaphysics, for instance, let us ask, Does it contain any abstract reasoning concerning quantity or number? No. Does it contain any experimental reasoning concerning matter of fact and existence? No. Commit it then to the flames, for it can contain nothing but sophistry and illusion.^{[11]}
Hume felt that the only sources of knowledge were logical or mathematical reasoning (which he calls above “abstract reasoning concerning quantity or number”) or sense experience (“experimental reasoning concerning matter of fact and existence”). Hume is led to argue that any claims not based upon one or the other method is worthless.
We can reconstruct Hume’s argument in the following way. Suppose t is some topic about which we claim to have knowledge. Suppose that we did not get this knowledge from experience or logic. Written in English, we can reconstruct his argument in the following way:
We have knowledge about t if and only if our claims about t are learned from experimental reasoning or from logic or mathematics.
Our claims about t are not learned from experimental reasoning.
Our claims about t are not learned from logic or mathematics.
_____
We do not have knowledge about t.
What does that phrase “if and only if” mean? Philosophers think that it, and several synonymous phrases, are used often in reasoning. Leaving “if and only” unexplained for now, we can use the following translation key to write up the argument in a mix of our propositional logic and English.
P: We have knowledge about t.
Q: Our claims about t are learned from experimental reasoning.
R: Our claims about t are learned from logic or mathematics.
And so we have:
P if and only if (QvR)
~Q
~R
_____
~P
Our task is to add to our logical language an equivalent to “if and only if”. Then we can evaluate this reformulation of Hume’s argument.
9.2 The biconditional
Before we introduce a symbol synonymous with “if and only if”, and then lay out its syntax and semantics, we should start with an observation. A phrase like “P if and only if Q” appears to be an abbreviated way of saying “P if Q and P only if Q”. Once we notice this, we do not have to try to discern the meaning of “if and only if” using our expert understanding of English. Instead, we can discern the meaning of “if and only if” using our already rigorous definitions of “if”, “and”, and “only if”. Specifically, “P if Q and P only if Q” will be translated “((Q→P)&(P→Q))”. (If this is unclear to you, go back and review section 2.2.) Now, let us make a truth table for this formula.
P  Q  (Q  →  P)  (P  →  Q)  ((Q  →  P)  & 
(P 
→  Q)) 

T  T  T  T 
T 
T  T 
T 
T  T 
T 
T 
T 
T 
T 
T  F  F  T 
T 
T  F 
F 
F  T 
T 
F 
T 
F 
F 
F  T  T  F 
F 
F  T 
T 
T  F 
F 
F 
F 
T 
T 
F  F  F  T 
F 
F  T 
F 
F  T 
F 
T 
F 
T 
F 
We have settled the semantics for “if and only if”. We can now introduce a new symbol for this expression. It is traditional to use the double arrow, “↔”. We can now express the syntax and semantics of “↔”.
If Φ and Ψ are sentences, then
(Φ↔Ψ)
is a sentence. This kind of sentence is typically called a “”.
The semantics is given by the following truth table.
Φ  Ψ  (Φ↔Ψ) 

T  T  T 
T  F  F 
F  T  F 
F  F  T 
One pleasing result of our account of the biconditional is that it allows us to succinctly explain the syntactic notion of logical equivalence. We say that two sentences Φ and Ψ are “equivalent” or “logically equivalent” if (Φ↔Ψ) is a theorem.
Take a look at 9.8 How to Make a Biconditional Proof and How to Prove a Theorem for more information on making biconditionals and proofs.
9.3 Alternative phrases
In English, it appears that there are several phrases that usually have the same meaning as the biconditional. Each of the following sentences would be translated as (P↔Q).
P if and only if Q.
P just in case Q.
P is necessary and sufficient for Q.
P is equivalent to Q.
9.4 Reasoning with the biconditional
How can we reason using a biconditional? At first, it would seem to offer little guidance. If I know that (P↔Q), I know that P and Q have the same truth value, but from that sentence alone I do not know if they are both true or both false. Nonetheless, we can take advantage of the semantics for the biconditional to observe that if we also know the truth value of one of the sentences constituting the biconditional, then we can derive the truth value of the other sentence. This suggests a straightforward set of rules. These will actually be four rules, but we will group them together under a single name, “equivalence”:
(Φ↔Ψ)
Φ
_____
Ψ
and
(Φ↔Ψ)
Ψ
_____
Φ
and
(Φ↔Ψ)
~Φ
_____
~Ψ
and
(Φ↔Ψ)
~Ψ
_____
~Φ
What if we instead are trying to show a biconditional? Here we can return to the insight that the biconditional (Φ↔Ψ) is equivalent to ((Φ→Ψ)&(Ψ→Φ)). If we could prove both (Φ→Ψ) and (Ψ→Φ), we will know that (Φ↔Ψ) must be true.
We can call this rule “bicondition”. It has the following form:
(Φ→Ψ)
(Ψ→Φ)
_____
(Φ↔Ψ)
This means that often when we aim to prove a biconditional, we will undertake two conditional derivations to derive two conditionals, and then use the bicondition rule. The biconditional proof has the following form:
9.5 Returning to Hume
We can now see if we are able to prove Hume’s argument. Given now the new biconditional symbol, we can begin a direct proof with our three premises.
We have already observed that we think (QvR) is false because ~Q and ~R. So let’s prove ~(QvR). This sentence cannot be proved directly, given the premises we have; and it cannot be proven with a conditional proof, since it is not a conditional. So let’s try an indirect proof. We believe that ~(QvR) is true, so we’ll assume the denial of this and show a contradiction.
Hume’s argument, at least as we reconstructed it, is valid.
Is Hume’s argument sound? Whether it is sound depends upon the first premise above (since the second and third premises are abstractions about some topic t). Most specifically, it depends upon the claim that we have knowledge about something just in case we can show it with experiment or logic. Hume argues we should distrust—indeed, we should burn texts containing—claims that are not from experiment and observation, or from logic and math. But consider this claim: we have knowledge about a topic t if and only if our claims about t are learned from experiment or our claims about t are learned from logic or mathematics.
Did Hume discover this claim through experiments? Or did he discover it through logic? What fate would Hume’s book suffer, if we took his advice?
9.6 Some examples
It can be helpful to prove some theorems that make use of the biconditional, in order to illustrate how we can reason with the biconditional.
Here is a useful principle. If two sentences have the same truth value as a third sentence, then they have the same truth value as each other. We state this as (((P↔Q)&(R↔Q))→(P↔R)). To illustrate reasoning with the biconditional, let us prove this theorem.
This theorem is a conditional, so it will require a conditional derivation. The consequent of the conditional is a biconditional, so we will expect to need two conditional derivations, one to prove (P→R) and one to prove (R→P). The proof will look like this. Study it closely.
We have mentioned before the principles that we associate with the mathematician Augustus De Morgan (18061871), and which today are called “De Morgan’s Laws” or the “De Morgan Equivalences”. These are the recognition that ~(PvQ) and (~P&~Q) are equivalent, and also that ~(P&Q) and (~Pv~Q) are equivalent. We can now express these with the biconditional. The following are theorems of our logic:
(~(PvQ)↔(~P&~Q))
(~(P&Q)↔(~Pv~Q))
We will prove the second of these theorems. This is perhaps the most difficult proof we have seen; it requires nested indirect proofs, and a fair amount of cleverness in finding what the relevant contradiction will be.
9.7 Using theorems
Every sentence of our logic is, in semantic terms, one of three kinds. It is either a tautology, a , or a . We have already defined “tautology” (a sentence that must be true) and “contradictory sentence” (a sentence that must be false). A contingent sentence is a sentence that is neither a tautology nor a contradictory sentence. Thus, a contingent sentence is a sentence that might be true, or might be false.
Here is an example of each kind of sentence:
(Pv~P)
(P↔~P)
P
The first is a , the second is a contradictory sentence, and the third is contingent. We can see this with a truth table.
P  (P 
v 
~ 
P)  (P  ↔  ~ 
P) 

T  T 
T 
F 
T  T  F 
F 
T 
F  F 
T 
T 
F  F  F 
T 
F 
Notice that the negation of a tautology is a contradiction, the negation of a contradiction is a tautology, and the negation of a contingent sentence is a contingent sentence.
~(Pv~P)
~(P↔~P)
~P
P  ~  P 
(P  v 
~ 
P)  ~  (P 
v 
~ 
P)  (P  ↔  ~  P)  ~  (P 
↔  ~  P) 

T  F  T 
T  T 
F 
T 
F  T 
T 
F 
T 
T  F 
F 
T 
T  T 
F 
F 
T 
F  T  F 
F  T 
T 
F 
F  F 
T 
T 
F 
F  F 
T 
F 
T  T 
F 
T 
F 
There are also important semantic relationships between sentences. A set of sentences is consistent when it is possible for all the members of the set to be true at the same time. A set of sentences is inconsistent when it is not possible for them to be true at the same time.
Here is an example of each kind of relationship:
 P, (P→Q), Q
 P, (P→Q), ~Q
The first set of sentences is consistent. We can see this with a truth table.
P  Q  (P  →  Q)  Q 

T  T  T  T  T  T 
T  F  T  F  F  F 
F  T  F  T  T  T 
F  F  F  T  F  F 
Notice the first row where P, (P→Q), and Q are all true.
The second set of sentences is inconsistent. We can see this with a truth table.
P  Q  (P  →  Q)  ~  Q 

T  T  T  T  T  F  T 
T  F  T  F  F  T  F 
F  T  F  T  T  F  T 
F  F  F  T  F  T  F 
Notice that there is no row where P, (P→Q), and Q are all true.
A moment’s reflection will reveal that it would be quite a disaster if either a contradictory sentence or a contingent sentence were a theorem of our propositional logic. Our logic was designed to produce only valid arguments. Arguments that have no premises, we observed, should have conclusions that must be true (again, this follows because a sentence that can be proved with no premises could be proved with any premises, and so it had better be true no matter what premises we use). If a theorem were contradictory, we would know that we could prove a falsehood. If a theorem were contingent, then sometimes we could prove a falsehood (that is, we could prove a sentence that is under some conditions false). And, given that we have adopted indirect derivation as a proof method, it follows that once we have a contradiction or a contradictory sentence in an argument, we can prove anything.
Theorems can be very useful to us in arguments. Suppose we know that neither Smith nor Jones will go to London, and we want to prove, therefore, that Jones will not go to London. If we allowed ourselves to use one of De Morgan’s theorems, we could make quick work of the argument. Assume the following key.
P: Smith will go to London.
Q: Jones will go to London.
And we have the following argument:
This proof was made very easy by our use of the theorem at line 2.
There are two things to note about this. First, we should allow ourselves to do this, because if we know that a sentence is a theorem, then we know that we could prove that theorem in a subproof. That is, we could replace line 2 above with a long subproof that proves (~(P v Q)↔(~P&~Q)), which we could then use. But if we are certain that (~(P v Q)↔(~P&~Q)) is a theorem, we should not need to do this proof again and again, each time that we want to make use of the theorem.
The second issue that we should recognize is more subtle. There are infinitely many sentences of the form of our theorem, and we should be able to use those also. For example, the following sentences would each have a proof identical to our proof of the theorem (~(P v Q)↔(~P&~Q)), except that the letters would be different:
(~(R v S) ↔ (~R&~S))
(~(T v U) ↔ (~T&~U))
(~(V v W) ↔ (~V&~W))
This is hopefully obvious. Take the proof of (~(P v Q)↔(~P&~Q)), and in that proof replace each instance of P with R and each instance of Q with S, and you would have a proof of (~(R v S)↔(~R&~S)).
But here is something that perhaps is less obvious. Each of the following can be thought of as similar to the theorem (~(PvQ)↔(~P&~Q)).
(~((P&Q) v (R&S))↔(~(P&Q) &~(R&S)))
(~(Tv(Q v V))↔(~T&~(Q v V))
(~((Q↔P) v (~R→~Q))↔(~(Q↔P)&~(~R→~Q)))
For example, if one took a proof of (~(P v Q)↔(~P&~Q)) and replaced each initial instance of P with (Q↔P) and each initial instance of Q with (~R→~Q), then one would have a proof of the theorem (~((Q↔P)v(~R→~Q))↔(~(Q↔P)&~(~R→~Q))).
We could capture this insight in two ways. We could state theorems of our metalanguage and allow that these have instances. Thus, we could take (~(Φ v Ψ) ↔ (~Φ&~Ψ)) as a metalanguage theorem, in which we could replace each Φ with a sentence and each Ψ with a sentence and get a particular instance of a theorem. An alternative is to allow that from a theorem we can produce other theorems through substitution. For ease, we will take this second strategy.
Our rule will be this. Once we prove a theorem, we can cite it in a proof at any time. Our justification is that the claim is a theorem. We allow substitution of any atomic sentence in the theorem with any other sentence if and only if we replace each initial instance of that atomic sentence in the theorem with the same sentence.
Before we consider an example, it is beneficial to list some useful theorems. There are infinitely many theorems of our language, but these sixteen are often very helpful. A few we have proved. The others can be proved as an exercise.
Rules of Replacement
DeMorgans  Distribution 
~(Φ&Ψ) ↔ (~Φ v~Ψ)
~(ΦvΨ) ↔ (~Φ &~Ψ) 
(Φ&(Ψvμ)) ↔ ((Φ&Ψ)v(Φ&μ))
(Φv(Ψ&μ)) ↔ ((ΦvΨ) & (Φvμ)) 
Commutation  Association 
(Φ&Ψ) ↔ (Ψ&Φ)
(ΦvΨ) ↔ (ΨvΦ) 
((Φ&Ψ)&μ)↔ (Φ&(Ψ&μ))
((ΦvΨ)vμ)↔ (Φv(Ψvμ)) 
Absorption  Transposition (T10) 
Φ v (Φ&Ψ) ↔ Φ
Φ & (ΦvΨ) ↔ Φ 
(Φ →Ψ) ↔ (~Ψ → ~Φ)) 
Tautology  Exportation 
Φ↔(ΦvΦ)
Φ↔(Φ&Φ) 
((Φ& Ψ)→μ)↔((Φ →(Ψ→μ)) 
Material Implication  Material Equivalence 
(Φ→Ψ)↔ (~ΦvΨ)  (Φ↔ Ψ) ↔((Φ →Ψ) & (Ψ → Φ))
(Φ↔ Ψ) ↔((Φ →Ψ) & (Ψ → Φ)) 
Common and useful theorems
T1  T2 
(Φv~Φ)  (~Φ → (Φ → Ψ)) 
T3  T4 
(Φ → (Ψ → P))  ((Φ →( Ψ →X)) → ((Φ → Ψ) → (Φ →X))) 
T5  T6 
((~Φ →~ Ψ) → ((~Φ → Ψ) → Φ))  (~(Φ ↔ Ψ) ↔ (Φ ↔ ~ Ψ)) 
Some examples will make the advantage of using theorems clear. Consider a different argument, building on the one above. We know that neither is it the case that if Smith goes to London, he will go to Berlin, nor is it the case that if Jones goes to London he will go to Berlin. We want to prove that it is not the case that Jones will go to Berlin. We add the following to our key:
R: Smith will go to Berlin.
S: Jones will go to Berlin.
And we have the following argument:
Using theorems made this proof much shorter than it might otherwise be. Also, theorems often make a proof easier to follow, since we recognize the theorems as tautologies—as sentences that must be true.
9.8 How to Make a Biconditional Proof and How to Prove a Theorem
Direct Proofs
A biconditional proof (or deduction): allows us to prove equivalences. The biconditional asserts if the antecedent is true, then the consequent is true, and if the consequent is true, then the antecendent is true. That is, they claim that the antecedent and the consequent are logically equivalent. A biconditional proof assumes the antecedent of a conditional, then uses a series of discrete truthpreserving steps to move from the antecedent to the consequent, and then assumes consequent, then uses a series of discrete truthpreserving steps to move from the consequent to the antecedent, thereby proving that the antecedent and the consequent are logically equivalent. Each step is either a rule of inference or a rule of replacement such that whenever you have a sentence of one form you may replace it with a sentence of another form.
A theorem proof: allows us to prove truths of logic. To prove a theorem, we show that it follows from the rules of logic alone. A theorem proof uses a series of discrete truthpreserving steps to show that the theorem must be true. There are no non derived sentences in a theorem proof. Each step is either a rule of inference or a rule of replacement such that whenever you have a sentence of one form you may replace it with a sentence of another form.
Notation: Each line of a proof must be enumerated and justified.
 Enumerate each line of a proof.
 Justify each sentence of a proof in a justification column to the right.
 For each nonderived sentence of a proof, write “premise” or “assumption.”
 For each derived sentence of a proof, write the name of the inference rule or replacement rule used, and the sentence(s) used to infer the derived sentence, in numerical order.
 Draw a horizontal line, a “fitch bar,” between nonderived sentences (e.g. premises and assumptions) and derived sentences.
 Draw a vertical “scope” line to the left of any nonderived sentences.
Terms, Conventions and the Accessibility Rule:
Derived Sentence: a sentence obtained by applying a inference rule or a replacement rule.
Scope Line: a vertical scope line indicates the beginning and end of a proof or subproof.
Fitch Bar: a horizontal fitch bar separates nonderived sentences, assumptions and premises, from derived sentences.
Subproof: a proof within a proof. Subproofs are necessary for conditional proofs and indirect proofs.
Open a subproof: a subproof begins with an assumption, which must be justified by the citing “assumption for …” and the rule one hopes to use.
End a subproof: a subproof ends by using the rule indicated on the justification for the assumption, and citing the entire subproof.
Discharged Assumption: the assumption of a successfully ended subproof.
Open Assumption: assumption that has not been discharged.
Closed Assumption: assumption that has been discharged.
Accessibility Rule: sentence is accessible if it can be used to infer a new sentence at a given line in a proof. A sentence is accessible if it is an open assumption or falls within the scope of an open assumption.
Biconditional proof examples: Proof that the following arguments are valid:

 Premises: (P→Q), (Q→P). Conclusion: (P↔Q)
Note that not all parts are labelled in the above image; all vertical lines are scope lines, all horizontal are fitch bars, and all subsections of the main proof are subproofs.
Notice that conditional proof is truthpreserving. Whenever (P→Q) and (Q→P) true, (P↔Q) must be true.P Q (P → Q) (Q → P) (P ↔ Q) T T T T T T T T T T T T F T F F F T T T F F F T F T T T F F F F T F F F T F F T F F T F  Premises: (P&P) (PvP) Conclusion: (P&P) ↔(PvP)
Note that not all parts are labelled in the above image; all vertical lines are scope lines, all horizontal are fitch bars, and all subsections of the main proof are subproofs.
Notice that conditional proof is truthpreserving. Whenever (P&P)(PvP) are true, (P&P)↔(PvP) must be true.P (P & P) (P v P) (P & P) ↔ (P v P) T T T T T T T T T T T T T T F F F F F F F F F F F F F F
 Premises: (P→Q), (Q→P). Conclusion: (P↔Q)
Theorem proof examples: Proof of the following theorems:
 Theorem: (P→(PvQ))
Note that not all parts are labelled in the above image; all vertical lines are scope lines, all horizontal are fitch bars, and all subsections of the main proof are subproofs.
Notice that (P→(PvQ)) must be true.P Q (P → (P v Q) T T T T T T T T F T T T T F F T F T F T T F F F T F F F  Theorem: (Pv~P)
Note that not all parts are labelled in the above image; all vertical lines are scope lines, all horizontal are fitch bars, and all subsections of the main proof are subproofs.
Notice that (P→(PvQ)) must be true.P (P v ~ P T T T F T F F T T F
9.9 Key Concepts
Using Theorems
↔: symbol for the biconditional.
Biconditional: A dependent sentence of the form P if and only if Q. For example, it is raining if and only if it is cloudy. We write “P if and only if Q” as (P ↔ Q). The sentence (P ↔ Q) means: P and Q have the same truthvalue. Consider the truth table for (P ↔ Q):
P  Q  (P  ↔  Q) 

T  T  T  T  T 
T  F  T  F  F 
F  T  F  F  T 
F  F  F  T  F 
Look at the column for the main connective, biconditional: the sentence is true when P and Q have the same truthvalue, and false when they have different truth values.
Biconditional Logical Equivalence: Notice that the biconditional is symmetrical.
P  Q  (P  ↔  Q)  (Q  ↔  P) 

T  T  T  T  T  T  T  T 
T  F  T  F  F  F  F  T 
F  T  F  F  T  T  F  F 
F  F  F  T  F  F  T  F 
Look at the main logical connectives for (P↔Q) and (Q↔P). They are identical, so (P↔Q) and (Q↔P) are logically equivalent.
Contingent sentence: A sentence that is neither a tautology nor a contradictory sentence. A contingent sentence is a sentence that might be true, or might be false. A sentence is contingent in propositional logic if the column under its main connective is true on at least one and false on at least one row of a complete truth table. Consider P.
P  P 

T  T 
F  F 
Look at the column for the main sentence, P: on at least one row it is true, and on at least one row, the sentence is false, so it is a contingent sentence.
Negating a contingent sentence: notice that the negation of a contingent sentence is a contingent sentence. Consider ~ P.
P  P  ~ 

T  F  T 
F  T  F 
Look at the column for the main connective, negation: on at least one row it is true, and on at least one row, it is false, so it is a contingent sentence.
Tautology: A sentence that must be true. A sentence is a tautology in propositional logic if the column under its main connective is true on every row of a complete truth table Consider (P↔~P)
P  (P  v  ~  P) 

T  T  F  F  T 
F  F  F  T  F 
Look at the column for the main connective, disjunction: on every row, the sentence is true, so it is a tautology.
Negating a tautology: Notice that the negation of a tautology is a contradiction
P  ~  (P  v  ~  P) 

T  F  T  T  F  T 
F  F  F  T  T  F 
Contradictory sentence: A sentence that must be false. A sentence is a contradiction in propositional logic if the column under its main connective is false on every row of a complete truth table. Consider (P↔~P)
P  (P  ↔  ~  P) 

T  T  F  F  T 
F  F  F  T  F 
Look at the column for the main connective, biconditional: on every row, the sentence is false, so it is a contradictory sentence.
Negating a contradiction: Notice that the negation of a tautology is a contradiction
P  ~  (P  ↔  ~  P) 

T  T  T  F  F  T 
F  F  F  F  T  F 
Look at the column for the main connective, negation: on every row, the sentence is true, so it is a tautology.
Consistency: A set of sentences in English is consistent if it is possible for them all to be true at once. A set of sentences is logically consistent in propositional logic if there is at least one line of a complete truth table on which all of the sentences are true. E.g. ~(PvQ) and (~P→~Q).
P  Q  ~  (P  v  Q)  (~  P  →  ~  Q) 

T  T  F  T  T  T  F  T  T  F  T 
T  F  F  T  T  F  F  T  T  T  F 
F  T  F  F  T  T  T  F  F  F  T 
F  F  T  F  F  F  T  F  T  T  F 
Look at the columns for the main connectives; negation for the first sentence, conditional for the second. On the final row, both are T. Since there is at least one line of a complete truth table on which all of the sentences are true, the sentences are logically consistent.
Inconsistency: A set of sentences in English is inconsistent if it is not possible for them all to be true at once. A set of sentences is logically inconsistent in propositional logic if there is no line of a complete truth table on which all of the sentences are true. E.g. ~(PvQ) and (PvQ)
P  Q  ~  (P  v  Q)  (P  v  Q) 

T  T  F  T  T  T  T  T  T 
T  F  F  T  T  F  T  T  F 
F  T  F  F  T  T  F  T  T 
F  F  T  F  F  F  F  F  F 
Look at the columns for the main connectives; negation for the first sentence, conditional for the second. Since there is no line on which both of the sentences are true, the sentences are logically inconsistent.
Translation Key: “Biconditional”
Translation Key  
Logic  English 
(P↔Q)  P if and only if Q
P just in case Q whenever P, Q and whenever Q, P P is necessary and sufficient for Q. P implies Q, and Q implies P Q, provided that P and P, provided that Q P is equivalent to Q. …and so on 
Notes:
 Atomic sentences are always in the affirmative.
 If the meaning of a complex English sentence cannot be captured by a dependent sentence, translate it as an atomic sentence.
 Negations attach to only one sentence (that sentence may be atomic or dependent).
 Conditionals, conjunctions, disjunctions, and biconditionals each connect two and only two sentences (those sentences may be atomic or dependent).
 There are only two kinds of syntactically acceptable sentences in propositional logic. 1) Atomic sentences, such as P; Q; R; S, and so on, represented by capital letters, or 2) dependent sentences such as (P→Q); ~P; (P&Q); (PvQ); (P↔Q), and combinations thereof, such as ((PvQ) & ~ (P&Q)).
Rules of Inference: “Biconditional”
Equivalence:
If (Φ↔Ψ) and Φ are true, then Ψ must be true.
If (Φ↔Ψ) and Ψ are true, then Φ must be true.
If (Φ↔Ψ) and ¬Φ are true, then ¬Ψ must be true.
If (Φ↔Ψ) and ¬Ψ are true, then ¬Φ must be true.
(Φ↔Ψ)
Φ Ψ 
and  (Φ↔Ψ)
Ψ Φ 
and

(Φ↔Ψ)
~Φ ~Ψ 
and

(Φ↔Ψ) ~Ψ ~Φ

Bicondition: If (Φ→Ψ) and (Ψ→Φ) are true, then (Φ↔Ψ) must be true.
Biconditional proof: If (Φ→Ψ) and (Ψ→Φ) are true, then (Φ↔Ψ) must be true.
Rules of Replacement: common and useful theorems
The following laws (or equivalences) are well established theorems, which can be used to substitute one sentence for another. These are the recognition that ~(PvQ) and (~P&~Q) are equivalent, and also that ~(P&Q) and (~Pv~Q) are equivalent. The following are theorems of our logic:
Commutation  Association  Distribution 
(P&Q) ↔ (Q & P)
(PvQ) ↔ (Q v P) 
((P&Q)&R)↔ (P&(Q&R))
((PvQ)vR)↔ (Pv(QvR)) 
(P & (Q v R)) ↔ ((P&Q) v (P v R)) 
Idempotence  Absorption  DeMorgans 
(P&P) ↔ P
(PvP) ↔ P 
P v (P&Q) ↔ P
P & (PvQ) ↔ P 
~(P&Q) ↔ (~P v~Q)
~(PvQ) ↔ (~P &~Q) 
9.10 Exercises
Within this section, you will find two types of problems for the chapter material. Firstly there are interactive exercises that randomly test your knowledge. Secondly, there is a comprehensive list of exercise questions with all answers at the back of the text.
Interactive Exercises
A. Fill out the truth table for the following biconditionals.
B. Tautologies, contradictions and contingent sentences. True or False? Each of the following is possible.
C. Identify the following claims as tautology, contradiction, or contingent sentence.
D. Truth tables tautologies, contradictions and contingent sentences. Determine whether each sentence is a tautology, a contradiction, or a contingent sentence. Justify your answer with a complete truth table.
E. Consistency and inconsistency. Determine whether each set of sentences is consistent or inconsistent. Justify your answer with a complete truth table.
F. Truth table logical equivalence. Determine whether each pair of sentences is logically equivalent. Justify your answer with a complete truth table.
G. Prove each of the following arguments is valid.
Coming soon! Until then refer to section G of the Full Exercise Question Sets below.
H. Prove each of the following theorems. (They can be proven without any premises).
Coming soon! Until then refer to section H of the Full Exercise Question Sets below.
Full Exercise Question Sets

Fill out the truth table for the following biconditionals.

P Q (P ↔ Q) 
P Q (Q ↔ P)


Tautologies, contradictions and contingent sentences. True or False? Each of the following is possible.
 A valid argument, the conclusion of which is a contradiction
 An invalid argument, the conclusion of which is a tautology
 A valid argument, the conclusion of which is a tautology
 An invalid argument, the conclusion of which is a contradiction
 A tautology that is contingent
 Two logically equivalent sentences, both of which are tautologies
 Two logically equivalent sentences, one of which is a tautology and one of which is contingent
 Two logically equivalent sentences that together are an inconsistent set
 A consistent set of sentences that contains a contradiction
 An inconsistent set of sentences that contains a tautology

Identify the following claims as tautology, contradiction, or contingent sentence.
 If Caesar crossed the Rubicon, then someone has.
 Even though Caesar crossed the Rubicon, no one has ever crossed the Rubicon.
 If anyone has ever crossed the Rubicon, it was Caesar.

Truth tables tautologies, contradictions and contingent sentences. Determine whether each sentence is a tautology, a contradiction, or a contingent sentence. Justify your answer with a complete truth table.
 (P → P)
 (~Q & Q)
 (R → ~R)
 (D V~D)
 ((P ↔ Q) ↔ ~(P ↔ ~Q))
 ((P&Q) ∨ (Q & P))
 ((P → Q) ∨ (Q → P))
 ~(P → (Q → P))
 ((P&Q) → (Q ∨ P))
 (P ↔ (P → (Q & ~Q)))
 (~(P ∨ Q) ↔ (~P & ~Q))
 (~(P&Q) ↔ P)
 (((P&Q) & ~(P&Q)) & R)
 (P → (Q ∨ R))
 (((P&Q) & R) → Q)
 ((P & ~P) → (Q ∨ R))
 ~((R ∨ P) ∨ Q)
 ((Q & R) ↔ (P ↔ (P ∨ R)))

Consistency and inconsistency. Determine whether each set of sentences is consistent or inconsistent. Justify your answer with a complete truth table.
 (P → P), (~P → ~P), (P & P), (P ∨ P)
 (P&Q), (R → ~Q), R
 (P ∨ Q), (P → R), (Q → R)
 (P → Q), (Q → R), P, ~R
 (Q & (R ∨ P)), (P → Q), ~(Q ∨ R)
 (P ∨ Q), (Q ∨ R), (R → ~P)
 (P ↔ (Q ∨ R)), (R → ~P), (P → ~Q)

Truth table logical equivalence. Determine whether each pair of sentences is logically equivalent. Justify your answer with a complete truth table.
 (P → P), (P ↔ P)
 (P ↔ ~Q), (~P ↔ Q)
 (P & ~P), (~Q ↔ Q)
 (P ↔ Q), (~Q ↔~P)
 (P ↔ Q) (~Q ↔~P)

Prove each of the following arguments is valid.
 Premises: (P ∨ Q), (Q ∨ R), ~Q. Conclusion: P & R
 Premises: (P ↔ Q), (Q ↔ R), Conclusion: (P ↔ R)
 Premise: (P → (P & ~P), Conclusion: ~P
 Premises: P, ~Q. Conclusion: ~(P↔Q)
 Premises: (~PvQ), (Pv~Q). Conclusion: (P↔Q)
 Premises: (P↔Q), (R↔S) . Conclusion: ((P&R) ↔ (Q&S))
 Premises: (P → ~Q), (R & P), (Q v (S & T)) Conclusion: T
 Premises: (Q↔~P), (Q v ~P). Conclusion: Q
 Premise: (P&Q). Conclusion: (P↔Q)

Prove each of the following theorems. (They can be proven without any premises).
 ~(P&~P) (principle of bivalence)
 ~((P→~P)&(~P→P))
 (~P→~(P&Q)).
 ((P&~Q)→~(P→Q))
 (P→ (Q→P))
 (P&Q) → ((P v R) & (Q v R))
 (P v ~P)
 (~(P→Q) ↔ (P&~Q))
 (~P → (P → Q))
 (P → (Q → P))
 ((P→(Q→R)) → ((P→Q) → (P→R)))
 ((~P→~Q) → ((~P→Q) →P))
 ((P&Q) ↔~(~Pv~Q))
 ((P→Q) ↔~(P&~Q))

Answer each of the questions below and justify your answer
 Suppose that P and Q are logically equivalent. What can you say about (P ↔ Q)?
 Suppose that ((P&Q) → R) is contingent. What can you say about the argument “premises: P, Q. Conclusion: R”?
 Suppose that P is a contradiction. What can you say about the argument “Premises: P, Q. Conclusion: R”?
 Suppose that R is a tautology. What can you say about the argument “Premises: P, Q. Conclusion: R”?
 Suppose that P and Q are logically equivalent. What can you say about (P ∨ Q)?
 Suppose that P and Q are not logically equivalent. What can you say about (P ∨ Q)
[11] From Hume’s Enquiry Concerning Human Understanding, p.161 in SelbyBigge and Nidditch (1995 [1777]).
A dependent sentence of the form P if and only if Q.
A sentence that must be false.
A sentence that can be either true or false.
A sentence of propositional logic that must be true.