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.