Assignment-1

CS 2214: Discrete structures for computing

1. Construct a compund proposition s using the propositions p, q, r and the

connectives ∨, ∧, ¬ such that

(i.) s = T if and only if (p = q = T, r = F) and (p = F, q = r = T).

(ii.) s = T if and only if exactly one of p, q or r are true.

Justify your answers using truth tables.

2. Decide which of the following propositions are tautology, contradiction

or satisfiable with justification. The justification should use truth tables

and/or laws of propositional logic:

(i.) (p ∧ q ∧ r) → (p ∧ q) ∨ r

(ii.) p → ¬p

(iii.) ((p → q) ∧ q) → p

3. Decide if the following sentences are equivalent. Use appropriate labeling

of propositions and use logical reasoning to justify your conclusion.

(i.) If Gail scored a 100 in the final and got more than 80% in the assignments then she will get an A in the course.

(ii.) If Gail scored a 100 in the final then she got less than 80% on the

assignments or she will get an A in the course.

Note: Here ‘or’ is used in the sense of disjunction, not exclusive or.

4. Prove the validity or invalidity of the following argument. If it is valid

then prove it using rules of inference. If it is invalid give appropriate

justification. Assume the domain for all statements is the set of all family

members in a large family.

If someone in the family eats tuna then they eat salmon.

There is someone in the family who eats shrimp.

No one in the family eats both shrimp and salmon.

Therefore, there is someone in the family who does not eat tuna.

1