Thursday 29 July 2010

Symbolic Logic, Dale Jacquette, Wadsworth, 2001, Chpt. 8, Ex. III, problem 15

The task is to prove the tautology:├ (∃x)[(Fx • ¬ Gx) ∨¬ Gx] ⊃(∃y)[(Fy ∨¬ Gy) • ¬ Gy].
  1. ├ (∃x)[(Fx • ¬ Gx) ∨¬ Gx] ⊃(∃y)[(Fy ∨¬ Gy) • ¬ Gy]
  2. * (∃x)[(Fx • ¬ Gx) ∨¬ Gx] / ACP
  3. * * ¬ (∃y)[(Fy ∨¬ Gy) • ¬ Gy] / AIP
  4. * * (y)[(Fy ∨¬ Gy) ⊃Gy] / 3QC
  5. * * (Fa • ¬ Ga) ∨¬ Ga / 2EI x/a
  6. * * (Fa ∨¬ Ga) • (¬ Ga ∨¬ Ga) / 5DeM
  7. * * ¬ Ga / 6Simp.
  8. * * Fa ∨¬ Ga / 6Simp.
  9. * * (Fa ∨¬ Ga) ⊃Ga / 4UI y/a
  10. * * Ga / 8,9MP
  11. * * Ga • ¬ Ga / 10,7Conj.
  12. * ¬ ¬ (∃y)[(Fy ∨¬ Gy) • ¬ Gy] /IP
  13. * (∃y)[(Fy ∨¬ Gy) • ¬ Gy] / 12DN
  14. (∃x)[(Fx • ¬ Gx) ∨¬ Gx] ⊃(∃y)[(Fy ∨¬ Gy) • ¬ Gy]

Thursday 22 July 2010

Taken to its logical conclusion

More often than not, the expression ‘taken to its logical conclusion’ serves to point up the absurdity of a piece of reasoning we come across. But the phrase should be used carefully lest it should turn out the reasoning is fine but we are wrong. Some obvious examples:

The converse of a statement: All A are B, is not equivalent to: All B are A, although some B are A indeed.

If 2 is an integer and every integer is a rational number and every rational number is a real number, then 2 is a real number. It figures by the law of hypothetical syllogism. It doesn’t work in reverse, for the simple reason that the sentence: if it is a real number, then it is 2, will be true in one case and false in the infinity minus 1 cases.

But who can resist an occasional daft wish or piece of advice, such as the one about a buckled railway line I heard last week (further down)?

The golden standard I suppose is set by the rhyme: There is a hole in my bucket, dear Liza, dear Liza. Of course, fixing it requires the use of the bucket at some stage, and so the loop closes.

The all-time favourites are: I wish there were no Mondays, and I need a holiday to get over a holiday.

In the intense heat we are experiencing now, rail lines tend to buckle. A train I was on came to a halt before such a buckled rail, and various suggestions on how to fix it were bandied about as the passengers piled out. The mood among the crowd ranged from rage to light-hearted banter, and somewhere along this spectrum an idea was born: let’s unscrew a rail immediately behind the train to replace the buckled one immediately in front of the train. It can’t have been offered other than in jest, but the heat and the prospect of a long wait made it seem strangely viable at the time.

I have seen it done before in the old west movies, where the tracks were blown up by train robbers. But the thought hadn’t crossed my mind. Yet, taken to its logical conclusion, this is an answer to the ailing railway infrastructure. Consider the savings to be made by a railway company if they ran a service from one destination to another by having just enough track laid to extend a little in front of the train and a little behind the train! Twenty burly passengers get off, relay the track by removing the rails at the back and putting them down in front, the train moves on a few meters and stops again. It’s a DIY railway line! It could even take you to places where there are no railway stations! Not fast, but logical!

A logical variation of the idea involves the last carriage of a train being fitted with a spare rail, in the manner of cars carrying a spare wheel, so that a buckled rail could be replaced without leaving a gap in the line. The possibilities are endless.

There is a parallel there to The Tower of Hanoi problem, in terms of the time required if not the logic, with disks gradually increasing in size placed on one of three pegs. The monks must shift the disks from one peg to another by removing only one at a time and never placing a larger disk on a smaller one. The answer to how long it would take to move 64 disks can be found on Wikipedia.

The Logic Book, M. Bergmann, J. Moor, J. Nelson, McGraw Hill, 2004, 10.5E, problem 5(b), p. 563

The following set of sentences is inconsistent: {¬ Fa , ¬ (∃x)(¬ Fx ∨¬ Fx)} and so much needs to be proved. Hint: working only with the assumptions given, we easily derive a contradiction.


  1. ¬ Fa / Assumption
  2. ¬ (∃x)(¬ Fx ∨¬ Fx) / Assumption
  3. (x) ¬ (¬ Fx ∨¬ Fx) / 2QC
  4. (x)(Fx • Fx) / 3DeM
  5. (x)Fx / 4Taut.
  6. Fa / 5UI x/a
  7. Fa • ¬ Fa / 6,1Conj.

Thursday 15 July 2010

The Destributive Laws

The ability to spot the distributive laws and the facility in using them are perhaps the points through which the fault lines run at the earliest stages between those of us who seem to be blessed with a head for algebraic manipulations and those who aren’t.

Briefly, the distributive law of multiplication over addition and multiplication over subtraction state:

a (b + c) = ab + ac
a (b – c) = ab – ac

The corresponding laws of reasoning are:

p or (q and r) is equivalent to p or q and p or r
p and (q or r) is equivalent to p and q or p and r

While factoring a polynomial of the kind:

(y^3) + 3(y^2) - 5y - 15 = (y^2)(y + 3) - 5(y + 3) = (y + 3)[(y^2) - 5]

we look for a common factor that can be removed or, if we can’t see one, we look for a pattern which might allow us to extract it. Likewise with statements of natural language. The statement:

Either I have the answer wrong or there is a printing error and the sum was never meant to work out.

is equivalent to:

I have the answer wrong or there is a printing error, and I have the answer wrong or the sum was never meant to work out.

Where the pattern is harder to spot, or the mind is more reluctant to accept it, is in a statement like:

If you fail an exam or you pay your own fees, then you know the price of education.

which translates as:

If you fail an exam then you know the price of education, and if you pay your own fees then you know the price of education.

This grouping or uncoupling as the case may be is a skill which must be picked up early and honed to perfection through constant practice. Memory, like with DeMorgan’s laws, is notoriously fickle, and just won’t hold the equivalences. Either you see them or you don’t, but I guarantee that the skill is not innate.

Symbolic Logic, Dale Jacquette, Wadsworth, 2001, Chpt. 8, Ex. III, problem 14, p. 434

We are to prove a tautology. Note that we can generalize by UG on line 18 to (x)Fx because we are now outside the scope of the assumption made on line 14.

├ ¬ (∃x)[Fx • (Ga ⊃Ha)] ≡ [(¬ Ga ∨Ha) ⊃ ¬ (∃x)Fx]

  1. ¬ (∃x)[Fx • (Ga ⊃Ha)] ⊃[(¬ Ga ∨Ha) ⊃ ¬ (∃x)Fx]
  2. * ¬ (∃x)[Fx • (Ga ⊃Ha)] / ACP
  3. * (x)[Fx ⊃¬ (Ga ⊃Ha)] / 2QC
  4. * * (∃x)Fx / ACP
  5. * * Fm / 4EI x/m
  6. * * Fm ⊃¬ (Ga ⊃Ha) / 3UI x/m
  7. * * ¬ (Ga ⊃Ha) / 5,6MP
  8. * (∃x)Fx ⊃¬ (Ga ⊃Ha) / 4-7CP
  9. * (Ga ⊃Ha) ⊃¬ (∃x)Fx / 8Contrap.
  10. * (¬ Ga ∨Ha) ⊃ ¬ (∃x)Fx / 9MI
  11. ¬ (∃x)[Fx • (Ga ⊃Ha)] ⊃[(¬ Ga ∨Ha) ⊃ ¬ (∃x)Fx] / 2-10CP
  12. [(¬ Ga ∨Ha) ⊃ ¬ (∃x)Fx] ⊃¬ (∃x)[Fx • (Ga ⊃Ha)]
  13. * (¬ Ga ∨Ha) ⊃ ¬ (∃x)Fx / ACP
  14. * * Fx / ACP
  15. * * (∃x)Fx / 14EG
  16. * * ¬ (¬ Ga ∨Ha) / 15,13MT
  17. * Fx ⊃¬ (¬ Ga ∨Ha) / 14-16CP
  18. * (x)[Fx ⊃¬ (¬ Ga ∨Ha)] / 17UG
  19. * (x)[¬ Fx ∨¬ (¬ Ga ∨Ha)] / 18MI
  20. * (x) ¬ [Fx • (Ga ⊃Ha)] / 19DeM
  21. * ¬ (∃x)[Fx • (Ga ⊃Ha)] / 20QC
  22. [(¬ Ga ∨Ha) ⊃ ¬ (∃x)Fx] ⊃¬ (∃x)[Fx • (Ga ⊃Ha)] / 13-21CP
  23. {¬ (∃x)[Fx • (Ga ⊃Ha)] ⊃[(¬ Ga ∨Ha) ⊃ ¬ (∃x)Fx]} • {[(¬ Ga ∨Ha) ⊃ ¬ (∃x)Fx] ⊃¬ (∃x)[Fx • (Ga ⊃Ha)]} / 11,22Conj.
  24. ¬ (∃x)[Fx • (Ga ⊃Ha)] ≡ [(¬ Ga ∨Ha) ⊃ ¬ (∃x)Fx] / 23BE

Thursday 8 July 2010

Symbolic Logic, Irving M. Copi, 5th edition, p. 150, problem 8

The argument is put thus:
Anyone who has climbed Mt Blanc is braver than anyone who has not. Of all those on our team, only the youngest has climbed Mr Blanc. Everyone on our team is a veteran. Therefore, the bravest member of our team is a veteran.
(Cx: has climbed Mt Blanc, Tx: is on our team, Vx: is a veteran, Bxy: is braver than y, Oxy: is older than y)
  1. (x)[Cx ⊃(y)(¬ Cy ⊃Bxy)]
  2. (∃x){Tx • (y){[Ty • ¬ (y = x)] ⊃(Oyx • ¬ Cx)} • Cx}
  3. (x)(Tx ⊃Vx)
  4. ∴ (∃x){Tx • (y){[Ty • ¬ (y = x)] ⊃Bxy} • Vx}
  5. * ¬ (∃x){Tx • (y){[Ty • ¬ (y = x)] ⊃Bxy} • Vx} / AIP
  6. * (x){{Tx • (y){[Ty • ¬ (y = x)] ⊃Bxy} ⊃¬ Vx} / 5QC
  7. * Tm • (y){[Ty • ¬ (y = m)] ⊃(Oym • ¬ Cm)} • Cm / 2EI x/m
  8. * Tm / 7Simp.
  9. * Cm / 7Simp.
  10. * Tm ⊃Vm / 3UI x/m
  11. * Vm / 8,10MP
  12. * {Tm • (y){[Ty • ¬ (y = m)] ⊃Bmy}} ⊃¬ Vm / 6UI x/m
  13. * ¬ {Tm • (y){[Ty • ¬ (y = m)] ⊃Bmy}} / 11,12MT
  14. * ¬ Tm ∨ ¬ (y){[Ty • ¬ (y = m) ⊃Bmy } / 13MI
  15. * ¬ (y){[Ty • ¬ (y = m) ⊃Bmy } / 8,14DS
  16. * (∃y)[Ty • ¬ (y = m) • ¬ Bmy) / 15QC
  17. * Ta • ¬ (a = m) • ¬ Bma / 16EI y/a
  18. * ¬ Bma / 17Simp.
  19. * Cm ⊃(y)(¬ Cy ⊃Bmy) / 1UI x/m
  20. * (y)(¬ Cy ⊃Bmy) / 9,19MP
  21. * ¬ Ca ⊃Bma / 20UI y/a
  22. * Ca / 18,21MT
  23. * Ta • ¬ (a = m) / 17Simp.
  24. * (y){[Ty • ¬ (y = m)] ⊃(Oym • ¬ Cm)} / 7Simp.
  25. * [Ta • ¬ (a = m)] ⊃(Oam • ¬ Cm)} / 24UI y/a
  26. * Oam • ¬ Cm / 23,25MP
  27. * ¬ Cm / 26Simp.
  28. * Cm • ¬ Cm / 22,27Conj.
  29. ¬ ¬ (∃x){Tx • (y){[Ty • ¬ (y = x)] ⊃Bxy} • Vx} / 5-28IP
  30. (∃x){Tx • (y){[Ty • ¬ (y = x)] ⊃Bxy} • Vx} / 29DN

Thursday 1 July 2010

Understanding Symbolic Logic, Virginia Klenk, 5th edition, Pearson Prentice Hall, 2008, Unit 18, 1(q), p. 354

Construct a proof for the following argument. Strategy: setting up a conditional proof practically solves the problem.
  1. ¬ (∃x)(Fx • Gx)
  2. (x)[(Fx • ¬ Gx) ⊃¬ (∃y)(Tyx • Hxy)]
  3. (x)[(y)(Hxy ⊃Zxy) ⊃Gx]
  4. ∴(x)[Fx ⊃(∃y) ¬ (Tyx ∨Zxy)]
  5. * Fx / ACP
  6. * (x)(Fx ⊃¬ Gx) / 1QC
  7. * Fx ⊃¬ Gx / 6UI x/x
  8. * ¬ Gx / 5,7MP
  9. * Fx • ¬ Gx / 5,8Conj.
  10. * (Fx • ¬ Gx) ⊃¬ (∃y)(Tyx • Hxy) / 2UI x/x
  11. * ¬ (∃y)(Tyx • Hxy) / 9,10MP
  12. * (y)(Tyx ⊃¬ Hxy) / 11QC
  13. * (y)(Hxy ⊃Zxy) ⊃Gx / 3UI x/x
  14. * ¬ (y)(Hxy ⊃Zxy) / 8,13MT
  15. * (∃y)(Hxy • ¬ Zxy) / 14QC
  16. * Hxm • ¬ Zxm / 15EI y/m
  17. * Hxm / 16 Simp.
  18. * Tmx ⊃¬ Hxm / 12UI y/m
  19. * ¬ Tmx / 17,18MT
  20. * ¬ Zxm / 16Simp.
  21. * ¬ Tmx • ¬ Zxm / 19,20Conj.
  22. * ¬ (Tmx ∨ Zxm) / 21DeM
  23. * (∃y) ¬ (Tyx ∨ Zxy) / 22EG
  24. Fx ⊃ (∃y) ¬ (Tyx ∨ Zxy) / 5-23CP
  25. (x)[Fx ⊃ (∃y) ¬ (Tyx ∨ Zxy)] / 24UG