Scribd
Upload
16 views1 page

CSC 165 Homework 2 Solutions

This document provides sample solutions to homework problems for a course. It includes solutions to logic problems involving concepts like tautology, satisfiability, and validity. The solutions use formal logic notation and derivations to prove statements true or false.

Uploaded by

Raj Shetty
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views1 page

CSC 165 Homework 2 Solutions

This document provides sample solutions to homework problems for a course. It includes solutions to logic problems involving concepts like tautology, satisfiability, and validity. The solutions use formal logic notation and derivations to prove statements true or false.

Uploaded by

Raj Shetty
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CSC 165 H1Y Worth: 3%

Homework Exercise # 2 Sample Solutions

Summer 2012

Due: By 3pm on Tuesday June 5.

1. (a) x P, T (x) S(x) i. Every tautology is satisable. ii. This is true. A tautology is true for any interpretation, so it will be true for at least one, which means it is satisable. (If we want to be pedantic, we can also mention that every formula will have at least one value: so there will be an interpretation in which it is true) (b) x P, T (x) S(x) i. There is a statement that is not a tautology, but is satisable. ii. This is true. An example is P Q, which is satisable (because it is true, for example, when P is true and Q is true), but is not a tautology (because it is false when both P and Q are false) (c) x P, S(x) U (x) i. There is a statement which is both satisable and unsatisable. ii. This is false. Satisable statement needs to be true for at least one interpretation, and unsatisable is always false. (d) x P, T (x) U (x) i. A statement is unsatisable exactly when it is not a tautology ii. This is false. A counterexample is P Q. It is not a tautology, but not unsatisable (see part 1(b)ii). (e) x P, (T (x) S(x)) (S(x) U (x)) i. If a statement is a tautology but not satisable, then it is neither satisable, nor unsatisable. ii. This is true. The antecedent (T (s) S(x)) is always false (see part 1(a)ii). So, the implication is always true, and thus the whole statement is true. 2. (a) ((P Q) R) (P R) (Q R) This is false. A counterexample is: P is true, and R and Q are false. Then the left hand side is (T F ) F , which is F F , which is vacuously true. The right hand side is (T F ) (F F ), which is F T which is false. (b) ((P Q) Q) P Q This is true. Here is the derivation:

(P Q) Q) (P Q) (Q P ) Q (P Q) (Q P ) Q (P Q) ((Q Q) (P Q)) (P Q) P Q ((P P ) (Q P )) Q (Q P ) Q P (Q Q) P Q

(Biconditional) (Implication twice) (Distributivity) (Identity) (Distributivity) (Identity) (Commutativity, Associativity) (Idempotency)

Note that Commutativity and Associativity are sometimes applied together with other operators. If you are not sure about your steps, you are encouraged to include these as separate steps, but this is not required.

Dept. of Computer Science, University of Toronto, St. George Campus

Page 1 of 1

You might also like