Computer Science A67

Homework Assignment # 1

Question 1. Deductive Reasoning [24 marks] For each of the following arguments:

• If the argument is valid:

1.  Prove the argument is valid by using a truth table. The truth table must be in the format we used in class, and the variables must appear in alphabetical order.

2.  Prove the argument is valid by using Rules of Inference.

• If the argument is not valid, provide an assignment of truth values to variables that proves the argument is not valid.

Part (a) [6 marks]

To graduate from UTSC, it is necessary forme to complete either a specialist program or a double-major program. To graduate from UTSC, it is necessary for me to earn 20 credits. I have not completed a specialist program. I have completed a double-major program. I earned 20 credits. Therefore, I can graduate from UTSC.

Let G stand for “I can graduate from UTSC”, S stand for “I completed a specialist program”, M stand for “I completed a double-major program”, and C stand for “I earned 20 credits” .

Part (b) [6 marks]

If Jones is convicted, he will go to prison. Jones will be convicted, if Smith testifies against him and Smith saw what happened. Smith will testify against him.  Therefore, if Smith saw what happened, then Jones will goto prison.

Let C stand for “Jones is convicted”, P stand for “Jones will go to prison”, T stand for “Smith testifies against him”, and S stand for “Smith saw what happened” .

Part (c) [6 marks]

Either the maid, the butler, the gardener, or the delivery person is guilty. The maid and the delivery person are not both guilty. The butler and the gardener are not both guilty. If the butler is guilty, then so is the maid. If the delivery person is not guilty, then the gardener is. Therefore, the butler is not guilty.

Let M stand for  “the maid is guilty”, B stand for  “the butler is guilty”, G stand for  “the gardener is guilty”, and D stand for “the delivery person is guilty” .

Part (d) [6 marks]

Either the butler or the cook or the delivery person is guilty. If the butler is guilty, then the cook is not.  If the cook is guilty, then the delivery person is not. The delivery person is not guilty. Therefore, the butler is guilty.

Let B stand for “the butler is guilty”, C stand for “the cook is guilty”, D stand for “the delivery person is guilty” .

Question 2. Logical Equivalence [18 marks]

For each of the following pairs of expressions, either prove that the two expressions are equivalent or prove that they are not. Do not use truth tables.

1.  (a → b) Λ (a → c) and a → (b Λ c)

2.  (a → b) V (a → c) and a → (b V c)

3.  (a → c) Λ (b → c) and  (a Λ b) → c

4.  (a → c) Λ (b → c) and  (a V b) → c

5.  (a → c) V (b → c) and  (a Λ b) → c

6.  (a → c) V (b → c) and  (a V b) → c

Question 3. Logical Equivalence [10 marks]

Prove that each of the following is a tautology. Do not use truth tables.

1.  P 艹 P

2.  ((a → b) Λ (b → c)) → (a → c)

3.  ((a → b) Λ (→b → →a)) 艹 (a → b)

4.  (a Λ (a → b)) → b

Question 4. Sets and Venn Diagrams [16 marks]

Part (a) [4 marks]

Use Venn diagrams to verify the following identities.

1.  (A U B) \ C = (A \ C) U (B \ C)

2.  A U (B \ C) = (A U B) \ (C \ A)

Part (b) [4 marks]

Given the two Venn diagrams above, what can you conclude about the sets (A U B) \ C and A U (B \ C)?  Is one of these sets is necessarily a subset of the other?

Part (c) [4 marks]

Give an example of sets A, B, and C for which (A U B) \ C A U (B \ C).

Part (d) [4 marks]

Verify the identities in part (a), by writing out (using logical symbols) what it means for an object x to be an element of each set and then using logical equivalences.