. 37
( 107 .)


‚ simplify the sentence we came up with to express ™(P, Q, R) (if P then Q, else R), so that it
becomes a disjunction of two sentences, each of which is a conjunction of two literals. Submit
your solution as a Tarski™s World sentence ¬le.

Chapter 7
Truth-functional completeness / 195

7.28 (Expressing another ternary connective) Start a new sentence ¬le using Tarski™s World. Use the
‚ method we have developed to express the ternary connective ™ de¬ned in the following truth
table, and enter this as the ¬rst sentence in your ¬le. Then see if you can simplify the result
as much as possible. Enter the simpli¬ed form as your second sentence. (This sentence should
have no more than two occurrences each of P, Q, and R, and no more than six occurrences of
the Boolean connectives, ∨, § and ¬.)
P Q R ™(P, Q, R)

7.29 (She¬er stroke) Another binary connective that is truth-functionally complete on its own is
 called the She¬er stroke, named after H. M. She¬er, one of the logicians who discovered and
studied it. It is also known as nand by analogy with nor. Here is its truth table:

Show how to express ¬P, P § Q, and P ∨ Q using the She¬er stroke. (We remind you that
nowadays, the symbol | has been appropriated as an alternative for ∨. Don™t let that confuse

7.30 (Putting monkeys to work) Suppose we have the single binary connective ’, plus the symbol
 for absurdity ⊥. Using just these expressions, see if you can ¬nd a way to express ¬P, P § Q,
and P ∨ Q. [Hint: Don™t forget what you learned in Exercise 7.21.]

7.31 (Another non-truth-functional connective) Show that truth value at a particular time of the
 sentence Max is home whenever Claire is at the library is not determined by the truth values
of the atomic sentences Max is home and Claire is at the library at that same time. That is,
show that whenever is not truth functional.

Section 7.4
196 / Conditionals

7.32 (Exclusive disjunction) Suppose we had introduced to express exclusive disjunction. Is the
 following a valid method of proof for this connective?





If you say yes, justify your answer; if no, give an example where the method sanctions an
invalid inference.
State valid introduction and elimination rules for using the same format we use to state
the introduction and elimination rules of F . You may need more than one of each.

Section 7.5
Alternative notation
As with the other truth-functional connectives, there are alternative notations
for the material conditional and biconditional. The most common alternative
to P ’ Q is P ⊃ Q. Polish notation for the conditional is Cpq. The most com-
mon alternative to P ” Q is P ≡ Q. The Polish notation for the biconditional
is Epq.

Chapter 7
Alternative notation / 197


The following table summarizes the alternative notations discussed so far.

Our notation Common equivalents
¬P ∼ P, P, !P, Np
P§Q P&Q, P&&Q, P · Q, PQ, Kpq
P∨Q P | Q, P Q, Apq
P’Q P ⊃ Q, Cpq
P”Q P ≡ Q, Epq

Section 7.5
Chapter 8

The Logic of Conditionals

One thing the theorem on page 193 tells us is that introducing the material
conditional and biconditional symbols did not increase the expressive power of
fol. Since ’ and ” can be de¬ned using the Boolean connectives, we could
always eliminate them from claims or proofs by means of these de¬nitions.
Thus, for example, if we wanted to prove P ’ Q we could just prove ¬P ∨ Q,
and then use the de¬nition. In practice, though, this is a terrible idea. It is far
more natural to use rules that involve these symbols directly, and the resulting
proofs are simpler and easier to understand.1
The material conditional, in particular, is an extremely useful symbol to
have. For example, many claims and theorems that we will run across can
only be expressed naturally using the conditional. In fact, quite a few of the
examples we™ve already used are more naturally stated as conditional claims.
Thus in an earlier exercise we asked you to prove Even(n — m) from the premise
Odd(n + m). But really, the fact we were interested in was that, no matter
what numbers n and m you pick, the following conditional claim is true:

Odd(n + m) ’ Even(n — m)

Given the importance of conditional claims, and the frequency you™ll en-
counter them, we need to learn how to prove these claims.

Section 8.1
Informal methods of proof
As before, we will ¬rst look at informal proofs involving conditionals and later
incorporate the key methods into the system F . Among the informal methods,
we distinguish simple valid steps from more important methods of proof.

Valid steps
The most common valid proof step involving ’ goes by the Latin name modus
modus ponens or
conditional elimination ponens, or by the English conditional elimination. The rule says that if you
1 In
Exercise 8.38 we ask you to construct proofs of (P § Q) ’ P and the equivalent
¬(P § Q) ∨ P, so that you can see for yourself how much simpler the ¬rst is than the second.

Informal methods of proof / 199

have established both P ’ Q and P, then you can infer Q. This rule is obvi-
ously valid, as a review of the truth table for ’ shows, since if P ’ Q and P
are both true, then so must be Q.
There is a similar proof step for the biconditional, since the biconditional
is logically equivalent to a conjunction of two conditionals. If you have estab-
lished either P ” Q or Q ” P, then if you can establish P, you can infer Q. biconditional
This is called biconditional elimination.
In addition to these simple rules, there are a number of useful equivalences
involving our new symbols. One of the most important is known as the Law of
Contraposition. It states that P ’ Q is logically equivalent to ¬Q ’ ¬P. This contraposition
latter conditional is known as the contrapositive of the original conditional. It
is easy to see that the original conditional is equivalent to the contrapositive,
since the latter is true if and only if ¬Q is true and ¬P is false, which is
to say, when P is true and Q is false. Contraposition is a particularly useful
equivalence since it is often easier to prove the contrapositive of a conditional
than the conditional itself. We™ll see an example of this in a moment.
Here are some logical equivalences to bear in mind, beginning with contra-
position. Make sure you understand them all and see why they are equivalent.
Use Boole to construct truth tables for any you don™t immediately see.
P’Q ” ¬Q ’ ¬P
P’Q ” ¬P ∨ Q
¬(P ’ Q) ” P § ¬Q
P”Q ” (P ’ Q) § (Q ’ P)
P”Q ” (P § Q) ∨ (¬P § ¬Q)


Let P and Q be any sentences of fol.

1. Modus ponens: From P ’ Q and P, infer Q.

2. Biconditional elimination: From P and either P ” Q or Q ” P, infer

3. Contraposition: P ’ Q ” ¬Q ’ ¬P

The method of conditional proof
One of the most important methods of proof is that of conditional proof, a
method that allows you to prove a conditional statement. Suppose you want

Section 8.1
200 / The Logic of Conditionals

to prove the conditional claim P ’ Q. What you do is temporarily assume
the antecedent, P, of your desired conditional. Then if, with this additional
assumption, you are able to prove Q, conditional proof allows you to infer that
conditional proof
P ’ Q follows from the original premises.
Let™s look at a simple example that uses both modus ponens and condi-
tional proof. We will show that Tet(a) ’ Tet(c) is a logical consequence of
the two premises Tet(a) ’ Tet(b) and Tet(b) ’ Tet(c). In other words, we™ll
show that the operator ’ is transitive. This may seem obvious, but the proof
is a good illustration of the method of conditional proof.
Proof: We are given, as premises, Tet(a) ’ Tet(b) and Tet(b) ’ Tet(c).
We want to prove Tet(a) ’ Tet(c). With an eye toward using condi-
tional proof, let us assume, in addition to our premises, that Tet(a)
is true. Then, by applying modus ponens using our ¬rst premise,
we can conclude Tet(b). Using modus ponens again, this time with
our second premise, we get Tet(c). So we have established the conse-
quent, Tet(c), of our desired conditional on the basis of our assump-
tion of Tet(a). But then the rule of conditional proof assures us that
Tet(a) ’ Tet(c) follows from the initial premises alone.
Conditional proof is clearly a valid form of reasoning, one that we use all
the time. If Q follows logically from some premises plus the additional assump-
tion P, then we can be sure that if those premises are true, the conditional
P ’ Q must be true as well. After all, the conditional can only be false if P is
true and Q is false, and our conditional proof shows that, given the premises,
this can never happen.
Let™s look at a more interesting example. This example will use both con-
ditional proof and proof by contradiction. We will prove:
Even(n2 ) ’ Even(n)
Proof: The method of conditional proof tells us that we can proceed
by assuming Even(n2 ) and proving Even(n). So assume that n2 is
even. To prove that n is even, we will use proof by contradiction.
Thus, assume that n is not even, that is, that it is odd. Then we can
express n as 2m + 1, for some m. But then we see that:
n2 (2m + 1)2
4m2 + 4m + 1
2(2m2 + 2m) + 1
But this shows that n2 is odd, contradicting our ¬rst assumption.
This contradiction shows that n is not odd, i.e., that it is even. Thus,
by conditional proof, we have established Even(n2 ) ’ Even(n).

Chapter 8


. 37
( 107 .)