To Be Handed in at Tutorial on 7Th Or 8Th Oct 2002

CSC205Homework 1

To be handed in at Tutorial on 7th or 8th Oct 2002

1. The marker to this question will award 2 marks, 1 mark or 0 marks.

The marker will award 0 marks if you write anything but a true proposition.

If you write a true proposition the marker will award either 2 marks or 1 mark.

(2 marks)

“Either I will receive 2 marks or 0 marks for this question.”

Or

“I will not receive 1 mark for this question”

{2 marks]

Any true proposition [1 mark]

Anything else [0 marks]

1. There are 4 tribes

Tribe A is totally accurate in their knowledge and beliefs and also totally truthful.

Tribe B is totally inaccurate in their knowledge and beliefs and also totally truthful.

Tribe C is totally accurate in their knowledge and beliefs and also totally untruthful.

Tribe D is totally inaccurate in their knowledge and beliefs and also totally untruthful.

A tribesman meets philosopher E who asks the tribesman “Which tribe do you belong to?”. The tribesman answers and the Philosopher says “OK from your answer I know which tribe you come from.”

The same tribesman meets philosopher F who asks the tribesman “Which tribe do you believe you belong to?”. The tribesman answers and the Philosopher says “OK from your answer I know which tribe you come from.”

From the above information determine the tribe which the tribesman comes from.(Show your reasoning)

(5 marks)

Look at the answers to each question

Q1 by Philosopher E

Tribe A answer A

Tribe B A or C or D

Tribe C A or B or D

Tribe D D

Therefore as Philosopher F had enough information the person must have either answered C and came from B or the person answered B and came from C.

Look at the answers to each question

Q1 by Philosopher E

Tribe A answer A

Tribe B B

Tribe C A or B or D

Tribe D A or B or C

Therefore as Philosopher F had enough information the person must have either answered C and came from D or the person answered D and came from C.

As both E and F had enough information, therefore the person is from tribe C.

[5 marks for totally correct]

[1 mark for an answer of C]

[2 marks for attempting to work out the various answers]

[1 mark for drawing some conclusions from the answers the student has]

1. 3.Translate into symbols the following compound statements statements

(a) If demand remains constant and costs increase, then either profits decrease or prices increase.

D is demand remains constant

C is costs increase

P is profits decrease

Q is prices increase

(D  C) -> (P v Q)

(b) We shall win the league, provided we change our manager now.

M is change manager

W is win the league

M -> W

(c) To win a gold medal, one has to be both talented and dedicated.

G is win a gold

P is talented

D is dedicated

G -> (P  D)

(note do not allow T as a proposition)

(d) Either the murderer has left the country or someone is harbouring him.

C is leave the country

H is harbouring

C v H

(e) If the murderer has not left the country, then someone is harbouring him.

C is leave the country

H is harbouring

¬C -> H

(1 mark for each ½ mark if they do not have defns)

(5 marks)

4. Using the axioms and inference rules of Propositional calculus prove the following

(a) ¬P -> (P -> Q)

¬Phypothesis

¬P -> (¬Q -> ¬P)axiom 1 with ¬P for P

¬Q for Q

¬Q -> ¬PModus Ponens on lines 1 and 2

(¬Q -> ¬P)->(P -> Q) Axiom 3

(P -> Q)Modus Ponens on lines 3 and 4

¬P -> (P -> Q)discharge of hypothesis

(2 marks)

(b) [(R -> S) -> (R -> R)]

R -> (S -> R)axiom 1

With R for P and S for Q

[R -> (S -> R)] -> [(R -> S) -> (R -> R)]

axiom 2

With R for P and S for Q

[(P -> Q) -> (P -> P)]

Modus Ponens on lines 1 and 2

(1 mark)

(c) A -> [B -> (A -> B)]

A hypothesis

B -> (A -> B) axiom 1 with B for P

and A for Q

A -> [B -> (A -> B)] discharge hypothesis

(1 mark)

(d){D  [C -> (D -> E)]} -> (C -> E)

{D  [C -> (D -> E)]}hypothesis

DConjunctive simplification

[C -> (D -> E)]}Conjunctive simplification

D -> (C -> D)axiom 1 with D for P and C for Q

(C -> D)Modus Ponens on lines 2 and 4

[C -> (D -> E)] -> [(C -> D) -> (C -> E)]

axiom 2 with C for P

and D for Q and E for R

[(C -> D) -> (C -> E)] Modus Ponens on lines 3 and 6

(C -> E)Modus Ponens on lines 5 and 7

{D  [C -> (D -> E)]} -> (C -> E)

discharge of hypothesis

(2 marks)

(e)[¬(G -> H)] -> (H -> G)

{hint use rewrites for ¬(G -> H) in terms of v and }

[¬(G -> H)]hypothesis 1

[¬(¬G v H)]rewriting implication

¬(¬G)  ¬Hde Morgan’s Law

¬(¬G)Conjunctive Simplification

GDouble Negative Equivalence

Hhypothesis 2

H -> GDischarge hypothesis 2

[¬(G -> H)] -> (H -> G)

Discharge hypothesis 1

(2 marks)

5. By truth table show that your XOR expression is equivalent to (A -> ¬B)  (¬A -> B).

A / B / A XOR B / A -> ¬B / ¬A -> B / (A -> ¬B¬A -> B)
T / T /

F

/ F / T /

F

T / F / T / T / T / T
F / T / T / T / T / T
F / F / F / T / F / F

Note that A XOR B and A -> ¬B)  (¬A -> B)

have the same values therefore the two are equivalent.

(2 marks, 1 mark for the truth table of each expression)

Prove the following using the rules of inference of propositional logic: [(A -> B)(C XOR B) C] -> ¬A

[(A -> B)(C XOR B) C]hypothesis

(A -> B)conjunctive simplification

(C XOR B)conjunctive simplification

Cconjunctive simplification

(C -> ¬B)  (¬C -> B)Rewrite of XOR

(C -> ¬B)conjunctive simplification

¬BModus Ponens on 4 and 6

¬AModus Tolens on 2 and 7

[(A -> B)(C XOR B) C] -> ¬Adischarge Hypothesis

(3 marks)