# 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.