Value: 12.5%
InstructionsThere are 100 points, worth 12.5% of your final mark; the points available per question are
given following the question number. PleaseWRITE CLEARLY, and make sure you check your answers as best
you can. (It would be wise to write in pencil, so that mistakescan be erased, thus avoiding confusion both for
you and for us.) When explanations are called for, keep them concise. Dont forget to leave sufficient space for
comments and corrections. DO NOT USE COVER PAGES OF YOUR OWN, NOR ANY CARDBOARD OR PLASTIC
COVERS: Following the assignment itself is OUR OWNcover sheet; please fill this out andSTAPLEthe pages
together with this cover page on top. Dont forget to fill in your name, McGill ID, and your TAs name as well.
Please also consult theLATE POLICYoutlined on the Course Description. Last, but not least,PLEASE MAKE
(AND KEEP) A COPY OF YOUR ASSIGNMENT SHEET: with close to 300 students, we will have to deal with
something approximating 1000 sheets of paper, and some pages inevitably get misplaced.
NB.
NOTE.It should be remembered that the Assignments and Mid-Term Exam are notjust assessment tests, but
have apedagogicalfunction, in that theyre designed to push you to look into things which you might not
already have looked at sufficiently closely. You may discussthe questions with your colleagues, but be sure to
compose the answers yourselves, for two reasons: first, because it is the honest thing to do, and the rules of
academic integrity require you to do so; second, because otherwise you cannot be sure you actually understand
the answers.
1. (25) Questions about FOL languages.
(10) (a) Suppose we have an FOL with names/constants a,b,c,d,e, function symbols
f(x),g(x),h(x,y), predicate symbols: P(x),Q(x),R(x,y),x=y, and the three connectives
,?,?(and where 6= is used as shorthand for the negation of an identity. For each of
the following, indicate whether they are simple termsorcomplex termsoratomic sen-tencesornon-atomic sentences, and explain why, pointing out allthe reasons why they
fail to be so, if indeed they do. (State also whether there arethe right number of brackets.
If a bracket is missing, the expression is not properly formed.)
1. a?P(b)
2. P(h(a,h(g(b),c)))
3. R(g(a),h(c,d))?b6=f(h(d,e))
4. c
5. c(d)
6. g(f(h(f(a),g(b))))
7. f(g(c))6=d
8. P(a)?Q(c)
9. Q(b)?((Q(c)?R(a,b))?(P(b)?
R(b,a)))
10. P(z) =Q(c)
(5) (b) Do question 1.17 from p. 36 of the textbook.
(5) (c) Do question 1.20 from p. 39 of the textbook.
(5) (d) Do question 1.21 from p. 39 of the textbook.
First Assignment, September 2015 2
2. (60) Questions from Chapters 24 of the textbook. You can use any of the programsTarskis World,
FitchandBoolein doing these, but please copy out yourFitchproofs and your truth-tables by hand
(or computer) to submit to us. If you design a counterexampleworld inTarskis World, you can print
a picture (e.g., screen shot) of this world, but then below this picture, explain briefly but carefully
why the sentences youre considering are true/false respectively in this world. If you submit a truth-table, be sure to point out which column is relevant for answering the question. Remember, you should
really study the sections which come before each of these exercises, and perhaps try other, surrounding
exercises as practice.
(10) (a) Do question 2.20 from p. 62 of the textbook.
(10) (b) Do question 2.26 from p. 66 of the textbook.
(10) (c) Do question 3.17 from p. 82 of the textbook; use the notion of logical equivalence in
explaining this.
(10) (d) Do question 4.3 from pp. 104 of the textbook.
(10) (e) Do question 4.6 from pp. 104 of the textbook.
(10) (f) Do question 4.19 from p. 109 of the textbook.
3. (15) This sort of question is very useful practice for manipulating truth-values, in particular for looking
at the consequences of committments to truth-valuesWITHOUTusing truth-tables.Read theNOTE
below before you tackle them. Note also that the answers to each part areindependent. So, if in (a)
you find that Granger is a Knight, that doesnt mean shes a Knight in (b).
On a strange island (Voldemorts Island), Voldemort has cast a spell which makes the inhabitants either
Knaves, who always lie, or Knights, who always tell the truth; on this island he has imprisoned Harry
Potter and some of his Hogwarts cronies. Two prisoners on theisland are said to be of the same type
if they are both Knights or both Knaves (or both Ordinaries, if thats relevant). Answer the following
questions, explaining your answers briefly but as preciselyas you can.
(3.75) (a) Suppose a visitor to the Island encounters Harry Potter and
Hermione Granger, and says to Hermione Are both of you
Knaves?, and she answers At least one of is. What are they both?
(3.75) (b) Harry Potter, Hermione Granger and Draco Malfoy are all inhabi-tants of the Island. Harry and Draco make the following statements:
Harry: Draco Malfoy is a Knave.
Draco: Harry Potter and Hermione Granger are of different types.
What is Hermione, a Knight or a Knave?
(3.75) (c) We dont know if Severus Snape is on the Island or not.
However, Luna Lovegood and Ron Weasley try to help by saying:
Luna: If either Ron or I are Knights, then Snape is on the Island.
Ron: If either Luna or I are Knaves, then Snape is on the Island.
Is Snape on the Island? Say what each of Luna and Ron is, a
Knights or a Knave.
(3.75) (d) For this question, assume that Voldemorts spell has also created
a category ofOrdinaries, who sometimes lie and sometimes tell
the truth. Now assume that Hermione has become an Ordinary, but
she lies only on Mondays (andeverythingshe says on Mondays is
false), otherwise she tells the truth. One day she says, Today is
Monday and Im not a mathematician. Was it really Monday? Is
she a mathematician or not? Explain.
NB.
First Assignment, September 2015 3
NOTEIn tackling these questions, there are some things to remember.
1. IfAis a not a Knight, then Amust be a Knave, and conversely, i.e.,Ais a Knight if and only if Ais not
a Knave, andAis a Knave if and only if Ais not a Knight. There is a clear parallel between this and our
assumption here that a sentence istrueif and only if it is not false, and false if and only if it is not true.
2. Ais a Knight if and only if everything Asays is true, and correspondinglyAis a Knave if and only if
everything Asays is false. Hence, its important to realise that discovering just onetruth uttered by A
is enough to conclude that Ais a Knight, for if Awere a Knave, she couldnt even say one true thing.
Analogously for Knaves. Thus, ifAis a Knight, and Asays thatBis lying when she says S, then truly B
lies, and soSis false (so not-Sis true), andBis a Knave. On the other hand, ifAis a Knave, and says that
Bis lying when she says S(in other words, says thatSis false), thenSmust betrue, and so Bis a Knight.
We might sum this up in the following way: Suppose thatAstatesS. Then we have seen that, whatever S
is,Ais a Knight if and only if Sis true. Notice that Sis true if and only if S; so if we now abbreviate the
proposition Ais a Knight by K, we have Kif and only if S, in other words, that KandSare logically
equivalent. This means that we can quite happily skip back and forth betweenKandS(or between K
andS) in reasoning about truth-values.
3. Moreover, ifAandBcontradict each other, then it should be clear thatoneof them must be a Knight and
the other a Knave. (Think of it in this simple way: if one saysPand the otherP, then one of them must
speak the truth, and is therefore a Knight, and the other one must speak falsely, and is therefore a Knave.
Be clear how this extends to contradictory statementsgenerally.)
4. Given 1. and 2., the way to proceed is to pick a character, sayA(the problem may give you some reason to
focus on a certain character from the group, for instance, because you may not have as much or indeed any
information about the others), assumethatAis a Knight (or a Knave), and then follow the consequences
through. If you reach a contradiction, then you know that the original assumption must be wrong, soA
must be a Knave (or a Knight, if you started from the assumption of Knavehood). Now you can proceed to
try to get information about BandCand so on, possibly now directly, or you might have to adopt another
assumption, say thatBis a Knave. However, if you dont reach a contradiction from your assumption
thatAis a Knight (or whatever you have assumed), then you have not ruled out thatAis a Knight (if that
is what you assumed), so you have to try to see whether the other possibility (Ais a Knave in this case)
leads to a contradiction, which would mean that Ais certainly a Knight.
5. Note that what youre doing in proceeding this way is making anassumptionabout the truth-value of a
sentence, then analysing and tracking through the consequences of that, just as you do with the games
introduced in Chapter 3 of the textbook. If youve made the wrong assumption, then you will eventually
come across some incompatibility, just as when you play the game inTarskis World, the computer will
try, if it can, to trip you up, i.e., show that youve committed yourself to something unsustainable. At
this point, you know that the opposite assumption must be right, so you turn your attention to another
sentence, etc.
As a simple example, consider the following: SupposeAsays Either I am a Knave orBis a Knight; what are
AandB? IfAis a Knave, then what he says is false, which means that not-(EitherAis a Knave orBis a Knight)
is true. This means that bothAis a Knave and Bis a Knight are false, which means that Ais a Knight and
Bis a Knave are both true, which means that Ais a Knight and Bis a Knave. But we have assumed thatAis a
Knave, so we have bothAis a Knave and Ais a Knight, which is a contradiction.
Hence, the assumptionAis a Knave leads to a contradiction, so Amust be a Knight. Now ifAis a Knight
Either I am a Knave orBis a Knight said by Amust be true; but Ais a Knave is false, since we know that A
is a Knight, so the other disjunct (Bis a Knight) mustbe true in order to make the whole sentence true; hence
Bis a Knight, and the question is now fully answered.
A word about the complication of Ordinaries. Normally, if you know (or assume) thatAis an ordinary, you
cant conclude that anythingAsays is either true or false; it might be either. But it so happens that, in the case
First Assignment, September 2015 4
of Hermione in 3(d) , youre told much more about her ordinariness, and this makes it fairly easy to integrate
the question into the Knights/Knaves pattern. Youre told in effect that Hermione is a Knaveon Monday, but a
Knight from Tuesday to Sunday. So here start from the assumption that its a particular day in the week, and
then various things will follow. (Note that there is an assertion made about the day of the week.)
PHIL 210A
Introduction to Deductive Logic
First Assignment
Due Date: Wednesday, 7th October 2015, in class.
NAME(Last, First):
MCGILL ID:
TA: Raymond Aldred
Nick Dunn
David Gaber
Tim Juvshik
Question Mark
1(a) [10]
1(b) [5]
1(c) [5]
1(d) [5]
2(a) [10]
2(b) [10]
2(c) [10]
2(d) [10]
2(e) [10]
2(f) [10]
3(a) [3.75]
3(b) [3.75]
3(c) [3.75]
3(d) [3.75]
Total
%TOTAL