# 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 ¬ | `-` , `~` , `not` |

and ∧ | `/\` , `&` , `and` |

or ∨ | `\/` , `|` , `or` |

if then → | `->` , `>` , `only if` |

if and only if ↔ | `<->` , `<>` , `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 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.

For the next exercise, put in the premise on line 1 (i.e., `A & (B & C) :PR`

) and then try to find a proof of *A* ∧ *C*.

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

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 16 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: →E). 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 *A* → *B* you need a separate proof in which *A* 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* is valid. Your last line has to be *A* → *C*. 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:

Now let's combine all the rules we have so far to show that *A* → (*B* → *C*)∴ (*A* ∧ *B*) → (*A* ∧ *C*) is valid.

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!

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:

## 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, 𝒬. 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.)

Now read chapter 16, 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 ¬*A* if we can show that
assuming *A* leads to a contradiction, in other words, if we can
construct a subproof with assumption *A* 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, as 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.15, 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.)