Practice Problems: Proofs for TFL
The following are some practice problems on natural deduction proofs for TFL; i.e., they cover Part IV of forall x: Calgary.
When writing sentences of TFL, remember you can use the following ways to enter connectives that are easier to do with a keyboard:
not ¬ | - , ~ |
and ∧ | /\ , & |
or ∨ | \/ |
if then → | -> , > |
if and only if ↔︎ | <-> , <> |
contradiction ⊥ | !? , _|_ |
The rules for ∧
To justify a sentence of the form 𝒫 ∧ 𝒬, you need both 𝒫 and 𝒬, separately, say with line numbers m and n. Then write as justification "∧I m, n" (replacing m, n with the actual line numbers, of course).
You can use 𝒫 ∧ 𝒬 to justify either 𝒫 or 𝒬 (whichever one you need, but only one per line). If 𝒫 ∧ 𝒬 appears on line number n, write "∧E n" next to 𝒫 (or 𝒬, as the case may be) as the justification.
Suppose you wanted to give a proof of the argument A ∧ B∴ B ∧ A. You would start your proof in the proof editor
by listing the premises at the top. In this case there is just one
premise, A ∧ B, which then is on line number 1. In Carnap, you
indicate that a line is a premise by writing :PR
to the right.
Carnap will render the proof nicely, off to the right. For instance,
it will draw a line under the last premise. Now you will have to write
the steps leading to the conclusion underneath. Each line will have a
sentence in it, and a justification separated by a colon :
to the
right. For instance, to justify line 2 by ∧E from line 1 you'd enter
:/\E 1
next to the sentence A
being justified. (Note: there must be
no space between :
and /\E
.)
Fill in the missing justifications in the proof outline below. A line
will get a +
next to it once you have entered a correct
justification. If the justification is incorrect, you'll get a ?
or
a ✗
. Carnap will try to tell you what's wrong: hover the cursor over
the ?
or ✗
to see a hint.
Note that this roundabout way is necessary, since B ∧ A and A ∧ B are different sentences. You first have to break A ∧ B apart and then put it back together. But note that once you have both A and B on separate lines, you can put them back together in any order, so you can get B ∧ A using ∧I (which you want here), and also A ∧ B (which you don't want). You can also cite a line twice, if you want to justify A ∧ A, for instance.
For the next exercise, write the premise on line 1 (i.e., A /\ (B /\ C) :PR
) and then try to find a proof of A ∧ C as the last line.
A tip: ∧ E only breaks apart the exact conjunction into its two components—in this case, you can only get A and B ∧ C from line 1 using ∧E. To get C, you have to apply ∧E again.
The elimination rule for →
The elimination rule for → is modus ponens: you can justify 𝒬 if you already have both 𝒫 → 𝒬 and 𝒫, on separate previous lines.
In the next exercise you should prove C ∧ D from the premises A ∧ B, A → C, and B → D. You'll need the →E rule twice to justify C and then D, but before you can use it, you have to prove the antecedents of the conditionals you cite. We've filled in some sentences and justifications; you do the rest!
Proof construction strategies
We've already told you how the proof goes, but at this stage you may rightly wonder: well, how do you come up with the lines in the first place, other than guessing wildly? Chapter 17 describes some strategies that you should always try to use. For instance, the very first strategy is to "work backward" from a conjunction. It applies in this case. You want to prove C ∧ D. So your last line will have to be C ∧ D. When you start a proof from scratch, you should therefore not only put in the premises at the top, but also the last line at the bottom, like so:
Now to "work backwards" from C ∧ D means that you will put into
your partial proof whatever is needed in order for you to correctly
apply the ∧I rule on the last line. (It's always the I rule for
the main operator of the sentence you want to prove, in this case
that's ∧.) So you should write, between the premises and the
last line, the corresponding sentences you'd need as justifications
for ∧I. In this case, that's C and D. (Go on, do it: replace
the ?
by two lines containing C and D.)
C and D are now your new "goals". You will also have to justify those, before you can use them to justify the last line. Let's focus on C. It has no main operator, so you cannot work backwards from it. But you can work forwards from the premises. You'll note that C is also the consequent of the conditional A → C on line 2. Working forwards from a conditional means: put in your proof whatever you'd need to justify your goal (here: C) from the sentence you have (here: A → C) by the E rule for the main operator of the sentence you're working forward from (here: →). Since to use →E to justify C from A → C also requires you to have proved A, that's what you enter. (Go on, write A on a new line above C.)
You'll now note that you can justify A by ∧E from premise 1. Then you can justify C by →E. Now you go through the same process with D: working forward from the premise on line 3 you enter B above D. You can justify B by ∧E from line 1, D by →E from B and premise 3. Finally, now you can justify the last line C ∧ D by ∧I.
Here's another longer exercise, without hints:
The introduction rule for →
The →I rule requires a new idea, namely that of a subproof. To
justify a conditional 𝒫 → 𝒬 you need a
separate proof in which 𝒫 is an assumption made in
addition to the premises of the entire proof. In Carnap, a subproof is
made by indenting the lines that make up the subproof, and by
justifying its first line (the assumption of the subproof) by :AS
.
Let's prove that A → B, B → C ⊢ A → C. Your last line has
to be A → C, and it must not be indented at all. To prove it,
you work backward: To use →I to justify A → C, you need (above
the last line) a subproof with assumption A and last line C. So
you start your proof like this:
Be careful when you write subproofs: the lines in a subproof all have
to be indented the exact same amount. Carnap's pretty rendering is
often misleading here. This proof box has some extra lines in the
proof box itself to make that clear: try adding or removing a space
before the C
to see what happens.
Also, now that subproofs are involved, it's important to remember that the very last line of your proof should never be indented, i.e., never be inside a subproof.
Now let's combine all the rules we have so far to show that A → (B → C) ⊢ (A ∧ B) → (A ∧ C). Start by writing the
premise and conclusion as the first and last line, then construct a
subproof in between that you can use to justify the conclusion using
→I. For this to work, its assumption must be the antecedent of (A ∧ B) → (A ∧ C) and its last line the consequent. Remember,
the assumption should have :AS
as its justification on the right.
The rules for ∨
The ∨I rule is very simple: you can justify 𝒫 ∨ 𝒬 if you have 𝒫 (and also if you have 𝒬). So it's like the reverse of the ∧E rule.
The ∨E rule is more complicated. It requires two subproofs. To
justify some sentence ℛ using a disjunction 𝒫 ∨ 𝒬 you need in addition two subproofs, one that derives
ℛ from the assumption 𝒫, and one that derives
ℛ from the assumption 𝒬. (To tell Carnap where
one subproof ends and the next one starts, type --
on a line by
itself. The --
should be indented the same amout as the
sentences in the surrounding (sub)proof.)
Note that the sentence ℛ can be anything. It may even be one of the disjuncts, e.g, 𝒬. But, and this is important, the last sentence in both subproofs must be the same, and also identical to the sentence you are justifying using ∨E.
Reiteration
The reiteration rule R is a very simple rule that sometimes comes in handy. It allows you to simply repeat a previous line. For instance, we need it if we want to prove that A → A is a tautology. This involves proving A → A, but our proof has no premises at all.
Working strategically is especially important when you prove tautologies like this one. You start by writing down A → A as the last line of your proof. (Since there are no premises it will start off also being the first line of your proof!) Then construct your proof above the sentence you're proving. Work backward from your goal sentence (here: A → A) by writing down what the I rule for the main connective (here: →I) requires as a justification. In our case, we will need a subproof with assumption A and last line A. Now use the R rule!
Carnap will put a ⊤ to the left of ⊢ if you're expected to give a proof with no premises at all.
Here's another example: If B is true, then A → B is true. After all, the conditional A → B is true iff either A is false or B is true. So the argument B∴ A → B is valid.
You'll often need to do subproofs inside a bigger subproof. Here's an example that illustrates this:
Let's look at an example where we use A ∨ B and ∨E to justify B (i.e., B plays both the role of 𝒬 and ℛ). You will still need two subproofs in this case, although one is very simple (and just involves the assumption B and a single use of the R rule.)
Let's now prove A from A ∨ A. Here A plays both the role of 𝒫, 𝒬 and ℛ at the same time. You can do two subproofs in this case, both the same, and involving just the assumption A and a single use of the R rule. Or you can just make one subproof, but cite it twice in the ∨E rule.
Now (re)read chapter 17, and let's apply the strategies to give a proof of something harder:
Rules for ¬
To deal with ¬, we introduce a new symbol into our language: ⊥. It works just like a sentence letter, except that we think of it as a sentence letter that is always false. It's read as "contradiction". Naturally, we let it be justified in a proof if we have somehow arrived at an outright contradiction: a pair of sentences 𝒫 and ¬𝒫. That's the ¬E rule: we can use ¬𝒫 to justify ⊥ if we also have 𝒫.
The ¬I rule allows us to justify ¬𝒫 if we can show that assuming 𝒫 leads to a contradiction, in other words, if we can construct a subproof with assumption 𝒫 and last line ⊥.
Finally, we have a weird rule, called "explosion" X. We can use ⊥ to justify anything.
The rules ¬E and X finally allow us to justify disjunctive syllogism.
Here's another example where the X rule is needed: a conditional A → B is true iff either A is false or B is true. Since A is false iff ¬A is true, that means the argument ¬A∴ A → B is valid. Let's prove it!
To see how the ¬I rule works, let's prove A → ¬¬A:
Here's another relatively easy one: the law of contraposition. This one will require triple-nested subproofs!
Now something a bit more challenging: one direction of one of De Morgan's laws.
Now let's try the other direction, but this time as a tautology:
Indirect proof
The final rule of natural deduction is indirect proof, IP. It works like ¬I, except the roles of 𝒫 and ¬𝒫 are reversed. In other words, a subproof with assumption ¬𝒫 that leads to ⊥ allows you to justify 𝒫. You should use IP if all the other rules and strategies don't lead to a solution.
First, an easy exercise: the converse of contraposition. It's like IV.17, but you'll need IP instead of ¬I.
A harder example is A ∨ ¬A:
A proof box for you to play in!
Want to use Carnap to construct and check an arbitrary proof? You can do that in this "playground" proof editor. Use it for any of the exercises from Part IV in the book, for instance. (It will accept derived rules, too.)
Your proof is correct if all lines have a +
next to them. Since
Carnap does not know what you're trying to prove, it will tell you
in the top line what you have proved.