Monday, 28 September 2009

Symbolic Logic, Irving M. Copi, Prentice Hall, 1979, 5th edition, Part II, exercise 8, p.134

Old man Copi has left a number of quirky brain teasers in his Symbolic Logic (1979), which has been the core of college level logic courses in some universities. Professor Peter Suber, from Earlham College, posted answers to many of them in his course hand-outs for the academic year 1996-97: http://www.earlham.edu/~peters/courses/log/loghome.htm At one point though, he gives up saying: 'I haven't had time to finish this set of exercises. I hope to do soon ...' (Polyadic Predicate Logic). When I last emailed him, he said he had retired. He left off at what is in my edition Part II, exercise 8, p. 134. Symbolize the following argument and construct a formal proof of validity:


There is a professor who is liked by every student who likes at least one professor. Every student likes some professor or other. Therefore, there is a professor who is liked by all students.

  1. (∃x){Px • (y){[Sy • (∃z)(Pz • Lyz)] ⊃Lyx]}
  2. (y)[Sy ⊃(∃x)(Px • Lyx)]
  3. ∴(∃x)[Px • (y)(Sy ⊃Lyx)]
  4. Pa • (y){[Sy • (∃z)(Pz • Lyz)] ⊃Lya] / 1EI
  5. Pa / 4Simp
  6. (y){[Sy • (∃z)(Pz • Lyz)] ⊃Lya] / 4Simp
  7. * Sy / ACP
  8. * Sy ⊃(∃x)(Px • Lyx) / 2UI
  9. * (∃x)(Px • Lyx) / 7,8MP
  10. * Pm • Lym / 9EI
  11. * (∃z)(Pz • Lyz) / 10EG
  12. * Sy • (∃z)(Pz • Lyz) / 7,11Conj
  13. * [Sy • (∃z)(Pz • Lyz)] ⊃Lya / 6UI
  14. * Lya / 12,13MP
  15. Sy ⊃Lya / 7-14CP
  16. (y)(Sy ⊃Lya) / 15UG
  17. Pa • (y)(Sy ⊃Lya) /5,16Conj
  18. (∃x)[Px • (y)(Sy ⊃Lyx)] / 17EG
The least obvious strategy here perhaps involves a change of variable, from 'x' on line 9 to 'z' on line 11 by first instantiating it to a constant, other than 'a', by Existential Instantiation and then generalising it back to a variable by Existential Generalisation.

Sunday, 20 September 2009

A Concise Introduction to Logic, 9th edition, P. Hurley, 8.7, III (10)

This problem is solved in the book but I thought to incude it in my answers because my translation of the last premise is slightly different than Hurley's and because the conclusion can be derived without having to use Indirect Proof. The problem:
The tallest building in North America is the Sears Tower. The tallest building in North America is located in Chicago. If one thing is taller than another, then the latter is not taller than the former. Therefore, the Sears Tower is located in Chicago. (Bx: x is a building in North America; Txy: x is taller than y; Cx: x is located in Chicago; s: the Sears Tower)
Hurley translates the last premise as (x)(y)(Txy ⊃¬ Tyx). I show that we will get the same result if we make explicit the fact that x and y are not the same things: (x)(y){[¬(x=y) • Txy] ⊃¬ Tyx}.
  1. (x){[Bx • ¬ (x=s)] ⊃Tsx} • Bs
  2. (∃x){Bx • (y){[By • ¬ (y=x)] ⊃Txy} • Cx}
  3. (x)(y){[¬(x=y) • Txy] ⊃¬ Tyx}
  4. ∴Cs
  5. Ba • (y){[By • ¬ (y=a)] ⊃Tay} • Ca / 2 EI
  6. (y){[By • ¬ (y=a)] ⊃Tay / 5 Simp
  7. [Bs • ¬ (s=a)] ⊃Tas / 6 UI
  8. Bs ⊃[¬ (s=a) ⊃Tas] / 7 Exp
  9. Bx / 1 Simp
  10. ¬ (s=a) ⊃Tas / 9, 8 MP
  11. [Ba • ¬ (a=s)] ⊃Tsa / 1 UI
  12. (y){[¬(a=y) • Tay] ⊃¬ Tya / 3 UI
  13. [¬(a=s) • Tas] ⊃¬ Tsa / 12 UI
  14. Tsa ⊃¬ [¬(a=s) • Tas] / 13 Contrap
  15. [Ba • ¬ (a=s)] ⊃¬ [¬(a=s) • Tas] / 11, 14 HS
  16. ¬ [Ba • ¬ (a=s)] ∨¬ [¬(a=s) • Tas] / 15 Impl
  17. [¬ Ba ∨ (a=s)] ∨[(a=s) ∨¬ Tas] / 16 DeM
  18. ¬ Ba ∨ [(a=s) ∨(a=s) ∨¬ Tas] / 17 Assoc
  19. Ba / 5 Simp
  20. (a=s) ∨(a=s) ∨¬ Tas / 18, 19 DS
  21. (a=s) ∨¬ Tas / 20 Taut
  22. ¬ Tas ∨(a=s) / 21 Comm
  23. Tas ⊃ (a=s) / 22 Impl
  24. ¬ (s=a) ⊃(a=s) / 10, 23 HS
  25. (s=a) ∨ (a=s) / 24 Impl
  26. (a=s) ∨(a=s) / Id
  27. a=s / Taut
  28. Ca / 5 Simp
  29. Cs / Id

Saturday, 19 September 2009

Comma or no comma?

What can be an unfathomable point of the English syntax – use of commas with relative clauses – is actually quite straightforward if you apply a bit of logic. Relative clauses are something of a speciality of predicate logic, in fact. The problem touches on the question of anaphora – more about which another time.

There is a correlation between the scope of the quantifier and the use of commas, which looks like this:

narrow scope of quantifier – comma required
wide scope of quantifier – no comma

Some examples:

(1) Merchants flatter politicians, who are corrupt.

(2) Merchants flatter any politician who is corrupt.

(3) A merchant will flatter any politician who can help him.

(1.1) (x)[Mx ⊃ (∃y)(Py • Fxy)] • (y)(Py ⊃ Cy)

(2.1) (x){Mx ⊃ (y)[(Py • Cy) ⊃ Fxy)]}

(3.1) (x){Mx ⊃ (y)[(Py • Hyx) ⊃ Fxy)]}


Sentence (1.1) – narrow scope of quantifier over ‘merchant’ – says that each merchant flatters some politician and that all politicians are corrupt. The main connective is a conjunction, which means that if there is at least one politician who is not corrupt, the sentence is false.

Sentence (2.1) – wide scope of quantifier over ‘merchant’ – says that each merchant flatters corrupt politicians. The main connective is a conditional, which means that the fact that there may be some politicians who are not corrupt and whom merchants flatter does not falsify the sentence.

Sentence (3.1) – wide scope of quantifier over ‘merchant’ – leaves us no option really, because if the pronoun ‘him’ is to be a bound variable, the scope of quantification over ‘a merchant’ must extend to ‘him’.

The same applies to commas around relative clauses modifying the subject of the sentence:

(4) Merchants, who buy off politicians, are corrupt.

(5) Merchants who buy off politicians are corrupt.

(4.1) (x)(Mx ⊃ Cx) • (x)[Mx ⊃ (∃y)(Py • Bxy)]

(5.1) (x){[Mx • (∃y)(Py • Bxy)] ⊃ Cx}

Monday, 14 September 2009

Understanding Symbolic Logic, V. Klenk, Prentice Hall 2008, Unit 18, Ex.1(o)

  1. (x)[(Px • ¬ Rxx) ⊃(y)(Py ⊃¬ Ryx)]
  2. (x){Px ⊃ (y)[(Py • ¬ Rxy) ⊃¬ Hxy]}
  3. ∴(x){[Px • (y)(Py ⊃¬ Rxy)] ⊃¬ (∃z)(Pz • Hzx)}
  4. * Px • (y)(Py ⊃¬ Rxy) / ACP
  5. * Px / 4 Simp
  6. * (y)(Py ⊃¬ Rxy) / 4 Simp
  7. * Px ⊃¬ Rxx / 6 UI
  8. * ¬ Rxx / 5, 7 MP
  9. * Px • ¬ Rxx / 5, 8 Conj
  10. * (Px • ¬ Rxx) ⊃(y)(Py ⊃¬ Ryx) / 1 UI
  11. * (y)(Py ⊃¬ Ryx) / 9, 10 MP
  12. * * Pz / ACP
  13. * * Pz ⊃¬ Rzx / 11 UI
  14. * * ¬ Rzx / 12, 13 MP
  15. * * Pz ⊃(y)[(Py • ¬ Rzy) ⊃¬ Hzy] / 2 UI
  16. * * (y)[(Py • ¬ Rzy) ⊃¬ Hzy] / 12, 15 MP
  17. * * (Px • ¬ Rzx) ⊃¬ Hzx / 16 UI
  18. * * Px • ¬ Rzx / 5, 14 Conj
  19. * * ¬ Hzx / 17, 18 MP
  20. * Pz ⊃¬ Hzx / 12 - 19 CP
  21. * (z)(Pz ⊃¬ Hzx) / 20 UG
  22. * ¬ (∃z)(Pz • Hzx) / CQ
  23. [Px • (y)(Py ⊃¬ Rxy)] ⊃¬ (∃z)(Pz • Hzx) / 4 - 22 CP
  24. (x){[Px • (y)(Py ⊃¬ Rxy)] ⊃¬ (∃z)(Pz • Hzx)} / 23 UG


Comment

This deduction calls for multiple variable rewrite, including on lines 7, 13, and 17.

This is the first in my series of worked solutions to deduction problems left unanswered in logic course books. The aim is strictly educational and the answers are meant to help those who study on their own.

I haven’t worked out yet how to use the blogger tools to show the scope of assumptions in the way I find most clear – by indentation, or how to show step descriptions to the right of my work. So until I do that, I mark the scope of each new assumption with a star (*) to the left of the assumption, and separate the step descriptions with a forward stroke. It looks messy but I'd rather explain what I am doing on the line I'm doing it than add the comments below or not at all. When an assumption is discharged, the star is taken off. Most other notation is pretty standard. CP stands for discharge of conditional proof, CQ - change of quantifier (justified by one of the four equivalences).

Thursday, 10 September 2009

Tutorial on existence

I am constantly reminded what a challenge the basic building blocks of English are for students who study it. After all, nothing is more basic and few things are more complex than the verb ‘to be’. What sentence can you make up from members of the set A:

A = {lion, white, is}

Trivially:

(1) A lion is white.

(2) There is a white lion.

(3) The lion is white.


Sentence (2) we are told implies existence. I agree fully, but such explanation is misleading without qualification. Students and teachers may be led to believe that (1) and (3) do not imply existence, which is false. They do! OK, (1) is not much of a sentence, and (2) is only a slight improvement on (1), but what is a matter of elegance in grammar may sometimes be an irrelevance in logic.

The question is, what does it mean to say that (2) implies existence? And what about (1) and (3)?

One way to tackle the problem is by responding with ‘So what?’ to someone uttering (2) to you, out of the blue. If your response is indeed ‘So what?’, or ‘Why are you telling me this?’, you already know what it means for ‘there is’ to express existence. The point is existence is so basic we don’t need to talk about it. If there is a white lion, let’im be.

Language, however, wrongfoots you. It gives you (2) and (3), never mind (1), with a verb ‘to be’ sitting squarely in the middle. Some philosophers call it referential tautology. The implication of existence is already present in my uttering the word ‘lion’. The verb ‘to be’ or ‘to exist’ adds nothing.

In first-order logic (2), as (1), can be represented as:

(2.1) (∃x)(Lx • Wx)


where Lx – ‘x’ is a lion, and Wx – ‘x’ is white, and where ∃ is an existential quantifier. The sentence thus reads: there exists an ‘x’ such that ‘x’ is a lion and ‘x’ is white. We have in fact used the word ‘is’ in our paraphrase, but nothing in our symbolic translation corresponds to it! To say that ‘Lions exist’, ‘Some lions exist’, ‘There is at least one lion,’ or, if you can bear it, that ‘Lions are,’ or else that ‘There are lions,’ is simply: (∃x)Lx.

Note that the plural in the preceding paragraph is no more than a variant of ‘There is a lion’ or ‘A lion is,’, which is true. It is a kind of minimal or limiting plural. It definitely does not suggest that ‘All lions exist,’ for when put like this the sentence is meaningless in English. The universal sentence (x)Lx, which can be paraphrased: for any ‘x’, ‘x’ is a lion, or everything is a lion, is clearly false. The existential and the universal would have the same truth value if and only if there was only one object in the universe, and that object was not necessarily a lion either.

(3.1) (∃x)[Lx • (y)(Ly ⊃ y = x) • Wx]


Translation (3.1) is just like (2.1) except for the bit in the middle, and is a representation of sentence (3): The lion is white. Just like (2.1) it is says that there exists an ‘x’ such that ‘x’ is a lion and ‘x’ is white, but it also adds (the bit in the middle) that if any ‘y’ is a lion then that ‘y’ is identical to our ‘x’, and this is what makes our lion ‘unique’, ‘the only lion’, or simply ‘the lion’.

Summing up, all three sentences assert existence, it is just that (1) and (2) assert nothing but the existence of white lions. Sentence (3) tells us more: it tells us that there is a unique lion. Logical notation thus makes explicit to a non-English speaker what the English language doesn’t by merely replacing ‘a’ with ‘the’: it adds one extra piece of information – the uniqueness claim.

And if (1) and (2) do not sound interesting, that is precisely because, when taken out of context, they tell you about nothing other than that somewhere a white lion exits – something you didn’t expect to be told without first asking about it. Sentences about existence become interesting only when we have reason to doubt existence: There is life on Mars; There is a God; and so on.

Tuesday, 8 September 2009

Getting started

Welcome to If English then Logic, a blog aimed at promoting English through logic and logic through English. I will share my interests in the English language, my fascination with language in general, logic and philosophy. Specifically:

- students of English as a foreign language may find an alternative in my back-to-first-principles approach to the tyranny of Cambridge exams, business English, and learn-quick schemes (called ‘methods’). I will expand on this more, share examples and, time permitting, exercises.
- students of first-order logic will find answers to exercises that are notoriously omitted from logic textbooks for reasons of space. They can take up rather a lot of it. I will trawl through the books used in university logic courses and post those answers which I find more difficult or more interesting for some reason.
- I will tackle some formal logic symbolization problems and look at how logic can improve – though never take over – your understanding of a language like English.
- Finally, I will post my thoughts and observations prompted by current work, marrying my principle interests and looking beyond for inspiration.

Wherever I know the source of my information, I credit it accordingly. I do the same with opinions, unless they are mine. Any errors and omissions are entirely mine. Feel free to point them out.