Tutorial 1

Tutorial 1

1. If p represents the statement “Priscilla goes to the party”, q represents the statement “Queenie

goes to the party”, and r represents the statement “Rose goes to the party”, analyse the logical
forms of the following statements:
(a) If Queenie goes to the party, then Priscilla and Rose will go.
(b) Rose will go to the party if and only if Priscilla goes but Queenie does not.
(c) Rose will go to the party if at least one of Priscilla or Queenie goes.

2. Analyse the logical forms of the following statements:

(a) Either John went to the store, or we’re out of eggs.
(b) Either Bill is at work and Jane isn’t, or Jane is at work and Bill isn’t.

3. What English sentences are represented by the following expressions?

(a)  s  l   s , where s stands for “John is stupid” and l stands for “John is lazy.”

(b) s   l  s  , where s and l have the same meanings as before.

(c)  s  l   s , with s and l still as before.

4. Analyse the logical forms of the following statements:

(a) We’ll have either a reading assignment or homework problems, but we won’t both have home-
work problems and a test.
(b) You won’t go skiing, or you will and there won’t be any snow.

(c) 7 is not less than or equal to 2.

5. Which of the following expressions are well-formed formulas?

(a)  p  r 

(b)  p q  r 

(c) p  p

(d)  p  q   p  r 

1
 Tutorial 1

6. Let p stand for the statement “I will buy the pants” and s for the statement “I will buy the
shirt.” What English sentences are represented by the following expressions?
(a) p  s

(b) p  s

(c)  p  s 

7. How many lines will there be in the truth table for a statement containing n letters?

8. Find a formula involving the connectives   and  that has the following truth
table:

p q ??

0 0 1
0 1 0
1 0 1
1 1 1

Use truth tables to demonstrate the following tautologies known as De Morgan’s Laws:
9.  p  q    p  q 
10.  p  q    p  q 

Use truth tables to demonstrate the following tautologies:

11.  p  q    p  q 

12.  p  q    p  q 

13. Use a truth table to demonstrate that the distribution law  p   q  r      p  q    p  r  

is a tautology.

2
 Tutorial 1

14. Use truth table to demonstrate the following tautologies:

(a)   p  q    p  r     p   q  r  

(b)   p  r    q  r      p  q   r 

15. Use truth tables to determine the models in which the following formulas are true.
(a)  p  q   q

(b) p   q  q 

16. Use a truth table to demonstrate that Peirce’s Law   p  q   p   p is a tautology.

17. Identify the premises and conclusions of the following arguments, and analyse their logical
forms.
(a) Jane and Pete won’t both win the math prize. Pete will win either the math prize or the chem-
istry prize. Jane will win the math prize. Therefore, Pete will win the chemistry prize.
(b) Either John or Bill is telling the truth. Either Sam or Bill is lying. Therefore, either John is tell-
ing the truth or Sam is lying.
(c) Either sales will go up and the boss will be happy, or expenses will go up and the boss won’t
be happy. Therefore, sales and expenses will not both go up.
Which of the above arguments do you think are valid? (Use your own deductive reasoning skills,
rather than constructing a truth table or proof tree.)

18. Use a proof tree to show that

p  q q  r pr


is a valid argument.

19. Use a proof tree to show that

p  q  p p (Peirce’s Law)


is a valid argument.

3
 Tutorial 1

The arguments is Questions 20 and 21 are called Distribution Laws. Prove them.

20. (a)  p  q    p  r  p   q  r  (b) p   q  r  p  q  p  r


21. (a) p   q  r   p  q    p  r  (b)  p  q    p  r  p  q  r



22. Show that
 p  q  r  q r  p r
is a valid argument. 

23. Prove that

p  q  r p  r  q  r


is a valid argument.

24. Show that

(a) p  q  p  q 


(b)  p  q  pq


are valid arguments.

25. Find a countermodel for the following argument

 p  q   r p  r qr


26. Find a countermodel for the following argument

p  q  r q  p  r


27. Use proof trees to determine whether the following arguments are valid. If the argument is
invalid give the countermodel.
(a) Either John isn’t stupid and he is lazy, or he’s stupid. John is stupid. Therefore, John isn’t lazy.
(b) The butler and the cook are not both innocent. Either the butler is lying or the cook is innocent.
Therefore, the butler is either lying or guilty.

4
 Tutorial 1

28. Use a proof tree to determine the validity of A B  A.


29. Use a proof tree to show that  A  A   B is a tautology, no matter what B is. This is called
“vacuous implication.”

30. Use trees to prove

 B  B   A  B  A    B  A  and  B  A    B  A   B  B   A .



Hence (or otherwise) prove
 B  A    B  A  A and A  B  A    B  A  .


5
 Tutorial 1

ANSWERS
1.
(a) q   p  r 
(b) r   p  q 
(c)  q  p   r

2.
(a) If p is “John went to the store” and q is “We’re out of eggs” then the statement becomes p  q .
(b) If b is “Bill is at work and j is “Jane is at work” then the statement becomes
 b  j    j  b  .

3.
(a) Either John isn’t stupid and he is lazy, or he’s stupid.
(b) John isn’t stupid, and either he’s lazy or he’s stupid.
(c) Either John isn’t both stupid and lazy, or John is stupid.

4.
(a) If r is “We’ll have a reading assignment”, h is “We’ll have homework problems”, and t is
“We’ll have a test” then the statement becomes  r  h    h  t  .
(b) If g is “You’ll go skiing” and s is “There will be snow” then the statement becomes
g   g  s  .
(c)   7  2    7=2   .

5. (a) and (c)

6.
(a) I won’t buy the pants and I won’t buy the shirt.
(b) Either I won’t buy the pants or I won’t buy the shirt.
(c) I won’t buy the pants without the shirt.

6
 Tutorial 1

n
7. 2

8. p  q

9.

p q  p  q  p  q

0 0 1 0 1 1 1 1
0 1 0 1 1 1 0 0
1 0 0 1 1 0 0 1
1 1 0 1 1 0 0 0

10.

p q  p  q  p  q

0 0 1 0 1 1 1 1
0 1 1 0 1 1 1 0
1 0 1 0 1 0 1 1
1 1 0 1 1 0 0 0

11.

p q pq  p  q

0 0 1 1 1 1 0
0 1 1 1 1 1 1
1 0 0 1 0 0 0
1 1 1 1 0 1 1

7
 Tutorial 1

12.

p q  p  q  p  q

0 0 0 1 1 0 0 1
0 1 0 1 1 0 0 0
1 0 1 0 1 1 1 1
1 1 0 1 1 1 0 0

13.

p q r p  q  r  p  q  p  r

0 0 0 0 0 0 1 0 0 0
0 0 1 0 0 0 1 0 0 1
0 1 0 0 0 0 1 1 0 0
0 1 1 0 1 1 1 1 1 1
1 0 0 1 1 0 1 1 1 1
1 0 1 1 1 0 1 1 1 1
1 1 0 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1

14. (a)

p q r p  q  p  r  p  q  r

0 0 0 1 1 1 1 0 1 0
0 0 1 1 1 1 1 0 1 0
0 1 0 1 1 1 1 0 1 0
0 1 1 1 1 1 1 0 1 1
1 0 0 0 0 0 1 1 0 0
1 0 1 0 0 1 1 1 0 0
1 1 0 1 0 0 1 1 0 0
1 1 1 1 1 1 1 1 1 1

8
 Tutorial 1

(b)

p q r p  r  q  r  p  q  r

0 0 0 1 1 1 1 0 1 0
0 0 1 1 1 1 1 0 1 1
0 1 0 1 0 0 1 1 0 0
0 1 1 1 1 1 1 1 1 1
1 0 0 0 0 1 1 1 0 0
1 0 1 1 1 1 1 1 1 1
1 1 0 0 0 0 1 1 0 0
1 1 1 1 1 1 1 1 1 1

15. (a)

p q p  q  q

0 0 1 1 0 1 1
0 1 1 1 1 0 0
1 0 0 0 0 0 1
1 1 0 1 1 0 0

The formula is only true when both p and q are false.

(b)

p q p  q  q 

0 0 1 1 0 0 1
0 1 1 1 1 0 0
1 0 0 0 0 0 1
1 1 0 0 1 0 0

The formula is true when p is false.

9
 Tutorial 1

16.

p q p  q  p  p

0 0 1 0 0 1 0
0 1 1 0 0 1 0
1 0 0 1 1 1 1
1 1 1 1 1 1 1

17.
(a) Premises: Jane and Pete won’t both win the math prize. Pete will win either the math prize or
the chemistry prize. Jane will win the math prize.
Conclusion: Therefore, Pete will win the chemistry prize.
To analyse the logical form let jm represent “Jane will win the math prize,” pm represent “Pete will
win the math prize,” and pc represent “Pete will win the chemistry prize.” Then the argument be-
comes  jm  pm  pm  pc jm pc


(b) Premises: Either John or Bill is telling the truth. Either Sam or Bill is lying.
Conclusion: Therefore, either John is telling the truth or Sam is lying.
To analyse the logical form let j represent “John is telling the truth,” b represent “Bill is telling the
truth,” and s represent “Sam is telling the truth.” Then the argument becomes
j  b s  b j  s


(c) Premises: Either sales will go up and the boss will be happy, or expenses will go up and the boss
won’t be happy.
Conclusion: Therefore, sales and expenses will not both go up.
To analyse the logical form let s represent “sales will go up,” b represent “the boss will be happy,”
and e represent “expenses will go up.” Then the argument becomes
 s  b    e  b   s  e 


The arguments in (a) and (b) seem valid.

18-24. Proof trees can be used to establish the validity of these arguments.

10
 Tutorial 1

25. Any model in which r and p are false and q is true is a countermodel.

26. Any model in which p is true and q is false is a countermodel.

27. (a) is invalid, with countermodel John is both stupid and lazy (b) is valid.

28. A proof tree will establish the validity of this argument, which is known as “weakening” since
B  A is a weaker statement than A . Notice that B can be anything at all. In particular: B can be
A , hence A A  A . This make sense in Mathematics, but in natural language it looks


weird. For example, if A is “I have a banana” then A A  A is “Suppose I have a banana.


If I don’t have a banana then I have a banana.”

29. A proof tree can be used to establish this tautology.

30. Proof trees establish the validity of these arguments.

References
• How to Prove It: A Structured Approach (2nd Edition), D.J. Velleman (Cambridge University
Press 2006)

11