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)

T

ttt

T

ttf

T

tft

F

tff

F

ftt

T

ftf

T

fft

T

fff

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:

PQ P|Q

F

tt

T

tf

T

ft

T

ff

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

you.)

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?

P Q

P

.

.

.

S

Q

.

.

.

T

S T

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

Remember

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.

198

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

elimination

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)

Remember

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

Q.

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