PartI:
Understanding logical expressions (30 pt.)
(12 pt., 3 pt. each) Determine the truth value of each of the following statements if the domain consists of all integers. If it is true, find a different domain for which it is false. If it is false, find a different domain for which it is true. Justify your answer.
Example: I will pass the course if I come to class.
Answer:
Original statement: If I come to class, then I will pass the course.
Converse: If I pass the course, then I will come to class.
Inverse: If I do not come to class, then I will not pass the course.
Contrapositive: If I do not pass the course, then I will not come to class.
Example: βπ(π β€ ππ) Answer:
False. If π₯ = β1, then 2π₯ = β2 and β1 > β2.
True when the domain consists of all nonnegative integers. For all nonnegative integers π₯, π₯ β€ 2π₯.
βπ(π/π β€ π)
3. (12 pt., 3 pt. each) Let π©(π) be the statement βπ is a barista,β πͺ(π) be the statement βπ is a customer,β and πΊ(π, π) be the statement βπ served a drink to π.β If the domain of π and π consists of all people, express each of the following sentences in terms of π©(π), πͺ(π), πΊ(π, π), quantifiers, and logical operators.
Example: Some barista served every customer a drink. Answer:
βπ₯(π΅(π₯) β§ βπ¦(πΆ(π¦) β π(π₯, π¦)))
There is a barista who served a drink to exactly one customer.
(20 pt., 10 pt. each) Use the laws of propositional logic to prove that the following compound propositions are tautologies. π β (π β π) ((π β π) β§ (π β π)) β (π β π )
A compound proposition is said to be satisfiable if there is an assignment of truth values to its variables that makes it true. For example, π β§ π is true when π = π and π = π; thus, π β§ π is satisfiable.
When no such assignment exists, the compound proposition is said to be unsatisfiable. For example, π β§ Β¬π is always false; thus, π β§ Β¬π is unsatisfiable.
To show that a compound proposition is satisfiable, we need to find at least one assignment of truth values to its variables that makes it true. However, to show that a compound proposition is unsatisfiable, we need to show that every assignment of truth values to its variables makes it false.
6. (10 pt., 2.5 pt. each) Determine whether each of the following compound propositions is satisfiable or unsatisfiable. Justify your answer.
(π β Β¬π) β§ (Β¬π β π) β§ (π β Β¬π) β§ (π β π) β§ (Β¬π β Β¬π)
Part I: Understanding logical expressions (30 pt.)
1. (6 pt., 2 pt. each) Write each of the following conditional statements and the corresponding
converse, inverse, and contrapositive as English sentences in the form βif π, then π.β
Example: I will pass the course if I come to class.
Answer:
Original statement: If I come to class, then I will pass the course.
Converse: If I pass the course, then I will come to class.
Inverse: If I do not come to class, then I will not pass the course.
Contrapositive: If I do not pass the course, then I will not come to class.
a. Winning the lottery implies that you will become rich.
b. I sneeze whenever I smell pepper.
c. To make an omelet, it is necessary to break some eggs.
2. (12 pt., 3 pt. each) Determine the truth value of each of the following statements if the domain
consists of all integers. If it is true, find a different domain for which it is false. If it is false,
find a different domain for which it is true. Justify your answer.
Example: βπ(π β€ ππ) Answer:
False. If π₯ = β1, then 2π₯ = β2 and β1 > β2.
True when the domain consists of all nonnegative integers. For all nonnegative integers π₯, π₯
β€ 2π₯.
a.
b. βπ(π + π = π)
c. βπ(π π’π¬ ππ’ππ‘ππ« ππ―ππ§ π¨π« π¨ππ)
d. βπ(π/π β€ π)
3. (12 pt., 3 pt. each) Let π©(π) be the statement βπ is a barista,β πͺ(π) be the statement βπ is a
customer,β and πΊ(π, π) be the statement βπ served a drink to π.β If the domain of π and π
consists of all people, express each of the following sentences in terms of π©(π), πͺ(π), πΊ(π,
π), quantifiers, and logical operators.
Example: Some barista served every customer a drink. Answer:
βπ₯(π΅(π₯) β§ βπ¦(πΆ(π¦) β π(π₯, π¦)))
a. Some barista served every other barista a drink.
b. There are two different customers who were served a drink by the same barista.
c. No customer served a drink to anyone.
d. There is a barista who served a drink to exactly one customer.
Part II: Proving logical equivalence using laws of propositional logic (60 pt.)
4. (40 pt., 10 pt. each) Use the laws of propositional logic to prove that the following compound
propositions are logically equivalent.
a. Β¬(π β§ π) β§ Β¬(π β§ Β¬π) and Β¬π
b. (π β§ Β¬π) β Β¬π and (π β§ π) β π
c. π β π and Β¬π β Β¬π
d. Β¬(Β¬π β¨ ((Β¬π β¨ π) β§ Β¬π)) and π β§ (π β π)
5. (20 pt., 10 pt. each) Use the laws of propositional logic to prove that the following compound
propositions are tautologies.
a. π β (π β π)
b. ((π β π) β§ (π β π)) β (π β π )
Additional Topics: Satisfiability (10 pt.)
A compound proposition is said to be satisfiable if there is an assignment of truth values to its variables
that makes it true. For example, π β§ π is true when π = π and π = π; thus, π β§ π is satisfiable.
When no such assignment exists, the compound proposition is said to be unsatisfiable. For example,
π β§ Β¬π is always false; thus, π β§ Β¬π is unsatisfiable.
To show that a compound proposition is satisfiable, we need to find at least one assignment of truth
values to its variables that makes it true. However, to show that a compound proposition is unsatisfiable,
we need to show that every assignment of truth values to its variables makes it false.
6. (10 pt., 2.5 pt. each) Determine whether each of the following compound propositions is
satisfiable or unsatisfiable. Justify your answer.
a. (π β π) β§ (Β¬π β π)
b. Β¬(π β§ π) β§ Β¬(π β§ Β¬π) β§ Β¬(Β¬π β§ Β¬π)
c. (π β¨ π) β§ (Β¬π β¨ π) β§ (π β¨ Β¬π) β§ (Β¬π β¨ Β¬π)
d. (π β Β¬π) β§ (Β¬π β π) β§ (π β Β¬π) β§ (π β π) β§ (Β¬π β Β¬π)
