Description

Connected Arguments
CS/MATH 113 Discrete Mathematics
Propositional Logic
1. Prove or disprove the following claims using truth tables. In each case, explicitly state yourconclusion and how it is supported by the truth table.
(a) 5 points ¬(p ∨ q) ≡¬p ∧¬q.
Solution:
p q p ∨ q ¬(p ∨ q) ¬p ¬q ¬p ∧¬q (¬(p ∨ q)) ⇐⇒ (¬p ∧¬q)
F F F T T T T T
F T T F T F F T
T F T F F T F T
T T T F F F F T
Both the statements ¬(p ∨ q) and ¬p ∧¬q have the same truth values under any assignment of truth value to their atomic parts, thus they are logically equivalent.
(b) 5 points (p ∨ q) =⇒ ¬r ≡ (¬p ∧¬q) ∧¬r.
Solution: For ease of notation, let
A : (p ∨ q) =⇒ ¬r
B : (¬p ∧¬q) ∧¬r
So we have to prove that A ≡ B.
p q r ¬p ¬q ¬r p ∨ q ¬p ∧¬q A B A ⇐⇒ B
F F F T T T F T T T T
F F T T T F F T T F F
F T F T F T T F T F F
F T T T F F T F F F T
T F F F T T T F T F F
T F T F T F T F F F T
T T F F F T T F T F F
T T T F F F T F F F T

1
The statements A and B are not logically equivalent as they have different truth values under the same assignmets of truth values to their atomic parts.
2. We want to write the statement, “A person is popular only if they are cool or funny”, inpropositional logic.
(a) 5 points Identify three simple propositions, p,q, and r, needed for the representation and write out the corresponding expression that uses them to represent the given sentence.
Solution: p: “A person is popualar” q: “A person is cool” r: “A person is funny” p =⇒ (q ∨ r)
(b) 5 points For your expression identified above, write the converse, contrapositive, and inverse in propositional logic as well as complete English sentences.
Solution:

Converse (q ∨ r) =⇒ p A person is cool or funny only if they are popular
Contrapositive ¬(q ∨ r) =⇒ ¬p A person is neither cool nor funny only if they are not popular
Inverse ¬p =⇒ ¬(q ∨ r) A person is not popular only if they are not cool nor they are funny

3. 5 points A small company makes widgets in a variety of constituent materials (aluminum, copper, iron), colors (red, green, blue, grey), and finishes (matte, textured, coated). Although there are many combinations of widget features, the company markets only a subset of the possible combinations. The following sentences are constraints that characterize the possibilities.
1. aluminum ∨ copper ∨ iron
2. aluminum =⇒ grey
3. copper ∧¬ coated =⇒ red
4. coated ∧¬ copper =⇒ green
5. green ∨ blue ⇐⇒ ¬ textured ∧¬ iron
Suppose that a customer places an order for a copper widget that is both green and blue with a matte finish.
(a) 5 points Using the propositions above, express the order as a compound proposition in logical notation.
Solution: The propositions are as follows: M(x) : material x from materials
C(x) : color x from colors
F(x) : finish x from finishes
Then the order can be expressed in compound porposition as: M(copper) ∧ (C(green) ∧ C(blue)) ∧ F(matte)
(b) 5 points Determine which constraints are satisfied and which are violated for the order, and provide an explanation.
Solution:

aluminum ∨ copper ∨ iron Satisfied The widget is of copper, and the condition has the logical operator “OR” in between, thus the constraint is satisfied.
aluminum =⇒ grey Satisfied The widget is not aluminum so it implies that the color is not grey. Hence, the con-
straint is satisfied
copper ∧¬ coated =⇒ red Violated As per the order, the widget should be of copper with a matte finish and green and blue color. However, according to this constrait, if a widget is made of copper and is not coated, then it is of red color. Thus the constraint is violated.
coated ∧¬ copper =⇒ green Satisfied As per the order, the widget is of copper, and is matte finish and has green and blue color. The negation of the constraint means that it is not coated, or it is made of copper and it is not green in color. Thus the condition is satisfied as per the order.
green ∨ blue ⇐⇒ ¬ textured ∧¬ iron Satisfied According to the constraint, if the color is green or blue, then the widget is not textured and not made of iron. Moreover, if a widget is not textured and not made of iron, then it has a color of green or blue (double implication). As per the order, the color is green and blue, and it is not textured neither it is made of iron, thus the constraint is satisfied.

4. 5 points You are given four cards each of which has a number on one side and a letter on another. You place them on a table in front of you and the four cards read: A 5 2 J. Which cards would you turn over in order to test the following rule?
Cards with 5 on one side have J on the other side.
Explain your choice.

5. An argument is said to be valid if its conclusion can be inferred from its premises. An argument that is not valid is called an invalid argument, or a fallacy. For each of the arguments below, identify the simple propositions involved, write the premises and conclusion(s) in logical notation using the identified simple propositions, and decide whether it is valid. Justify your decision.
(a) 5 points If I am wealthy, then I am happy. I am happy, therefore, I am wealthy.
Solution: The simple propositions are as follows.
p : I am wealthy q : I am happy The argument is

The conclusion p cannot be inferred from its premises. Therefore, argument is invalid(the argument is saying that if p =⇒ q then q =⇒ p which is not true.)
(b) 5 points If Ahmed drives his car, he is at least 18 years old. Ahmed does not drive a car. Therefore, Ahmed is not yet 18 years old.
Solution: The simple propositions are as follows.
p : Ahmed drives his car q : Ahmed is at least 18 years old
The argument is

The conclusion ¬q cannot be inferred from the premises. Therefore, the argument is invald (The argument is saying that if p =⇒ q then ¬p =⇒ ¬q which is not true.)
(c) 5 points If I study, then I will not fail CS 113. If I do not play cards too often, then I will study. I failed CS 113. Therefore, I played cards too often.
Solution: The simple propositions are as follows.
p : I study q : I failed CS 113 r : I play cards too often
The argument is

The conclusion r can be inferred from its premises. Therefore, the argument is valid
(The argument is saying that q =⇒ r and r =⇒ q which is true.)
1. There is a hint at Learn Courtyard or at the Gym.
4. If there are people in Learn Courtyard, then there is no hint at Learn Courtyard.
5. If there is a hint at Learn Courtyard, then the manual is at Zen Garden.
6. If there is hint at the Gym, then the manual is at Earth Courtyard.
You notice that there are people in Learn Courtyard. Where is the manual?
Identify the relevant simple propositions to model the above in propositional logic. Represent the above situation using propositional logic and describe the steps needed to infer the location of the manual.
Solution: The simple propositions are as follows:
e : There are people in Learn Courtyard f : The manual is at Zen Garden g : The manual is at Earth Courtyard h : The manual is at Fire Courtyard
The above situation in propositional logic can be represented as:
1 : a ∨ b
2 : (c ∨ d) =⇒ a
3 : ¬c =⇒ b
4 : e =⇒ ¬a
5 : a =⇒ f 6 : b =⇒ g
7 : d =⇒ h
The manual is at Earth Courtyard.
7. 5 points A TV channel is reporting a terrorist attack on a shopping mega-mall. The megamall website claims that the mall closes only in case of an attack. It is known that a sale is on whenever the mega-mall is open, and that many people come when there is a sale. A crime expert explained that in case of an attack, neighbors end up hearing firing sounds and calls are made to the local police. Phone logs indicate no recent calls to the police.
(a) 5 points We are not sure about the TV report, but we trust all the other sources. Is the mega-mall open?
Solution: The propositions are as follows:
a : The mall is open b : There is a terrorist attack c : A sale is on d : Many people come to the mall e : neighbours here firing sounds f : calls are made to the local police
From the propositions above, the situations can be represented in propositinoal logic as:
1 : b =⇒ ¬ a
2 : a =⇒ c
3 : c =⇒ d 4 : b =⇒ e
5 : e =⇒ f
From the given information, it is true that no phone calls were made to the police, thus:
¬ f
¬ f =⇒ ¬ e (By Contraposition)
¬ e (Modus Ponens)
b =⇒ e
¬ e =⇒ ¬ b (By Contraposition)
¬ b (Moden Ponens)
b =⇒ ¬ a
a =⇒ ¬ b (By Contraposition) a (Modus Ponens)
Since a is true, thus we can conclude that the mega-mall must be open
(b) 5 points Is the TV report true?
Solution: The propositions are as follows:
a : The mall is open b : There is a terrorist attack g : The TV Report is true
From the propositions, the situation can be represented in propositional logic as:
1 : b =⇒ ¬ a
2 : g =⇒ b
It was established in the first part that the mega-mall is open, thus: b =⇒ ¬ a
a =⇒ ¬ b (By Contraposition)
¬ b (Modus Ponens)
g =⇒ b
¬ b =⇒ ¬ g (By Contraposition)
¬ g (Modus Ponens)
Since the mall is open, there is no terrorist attack on the mega-mall, so it can be concluded that the TV report is not True
Predicate Logic
8. (a) 5 points There is a third quantifier often used in predicate logic called the Uniqueness
Quantifier, ∃!x P(x) which is read as, “P(x) is true for one and only one x in the domain”, or “there is a unique x such that P(x)”. Give an example of a propositional function P(x) and a corresponding domain, such that ∃!x P(x) is a true proposition.
Solution: Domain: x,y ∈Z
∀y ∃!x (yx = y) (the statement is only true for one value of x which is 1)
(b) 5 points The uniqueness quantifier can be expressed using the other two quantifiers but is still used on its own as it shortens the logical terms. In particular,
∃!x P(x) ≡∃x (P(x) ∧∀y (P(y) → y = x)) (1)
Solution: There exists an x suuch that for P(x), and for any y, if P(y) is true, then y must be equal to x. Thus stating the uniqueness of x that there can only be one x foor which y = x and the statement is true.
(c) 5 points Express ¬∃!xP (x) in a similar way as (1). Provide an expression in formal notation as well as in English. Also, give an example of a true proposition ¬∃!x P(x) by slightly changing the one you gave in part (a).
Solution: ¬∃!x P(x) ≡¬(∃x (P(x) ∧∀y (P(y) =⇒ y = x)))
≡∀x (¬P(x)∨∃y (P(y)∧¬(y = x))) (Negation of ∃, negation of ∀, DeMorgan’s Law, and negation of implication)
The above statement can be explained as:
“ For all x, there does not exist any x or some y exists such that P(y) is true and y is not equal to x, so there are either none, or more than one values of x for which the statement can be true”
Domain x,y ∈Z
∀y ¬∃!x (yx ̸= y) (there can be multiple values of x for which yx is not equal to y)
9. For each of the statements given below, perform the following.
1. Express the statement in formal notation using quantifiers.
2. Express the negation of the statement in formal notation such that no negation is left tothe quantifier.
3. Express the negated statement above as a statement in English.
(a) 5 points No one can have Pakistani and Indian citizenship.
Solution: Let P(x) be “x can have Pakistani citizenship”
Let I(x) be “x can have Indian citizenship”
The domain of x is all people
1 – Statement: ∀x (¬(P(x) ∧ I(x)))
2 – Negation: ¬(∀x (¬(P(x) ∧ I(x))))
∃x (¬¬(P(x) ∧ I(x))) (Double Negation)
∃x (P(x) ∧ I(x))
3 – Negated Statement: There exists someone who has both Pakistani and Indian
citizenship
(b) 5 points If everyone does their homework and goes to the recitations, no one will be badly prepared for the exams.
Solution: Let H(x) be “x does his homework”
Let R(x) be “x goes to the recitations”
Let E(x) be “x is not badly prepared for the exams”
The domain of x is all students
1 – Statement: ∀x (H(x) ∧ R(x)) =⇒ ∀x ¬E(x)
2 – Negation: ¬(∀x (H(x) ∧ R(x)) =⇒ ∀x¬E(x))
∃x (¬H(x) ∨¬R(x)) ∧¬∃x(E(x))
3 – Negated Statement: There exists someone who has not done their homework or they have not attended the recitations and they are badly prepared for exams
(c) 5 points No student has solved at least one exercise in every section of the book.
Solution: Let S(s, e) be “student ‘s’ solved exercise ‘e’ ”
Let E(e, c) be “exercise ‘e’ of section ‘c’ of the book”
The domain of s is all students
The domain of e is all exerises of a section
The domain of c is all sections of the book
1 – Statement: ¬∃s ∃e ∀c (S(s,e) ∧ E(e,c))
2 – Negation: ∃s ∃e ∀c (S(s,e) ∧ E(e,c)) (By Double Negation)
3 – Negated Statement: There exists some student who has solved at least one exercise in every section of the book.
(d) 5 points No one has climbed every mountain in Pakistan.
Solution: Let P(p, m) be “ person ‘p’ has climbed mountain ‘m’ of Pakistan ” The domain of p is all people
The domain of m is all mountains
1 – Statement: ¬∃p ∀m (P(p,m))
2 – Negation: ∃p ∀m (P(p,m))
3 – Negated Statement: There exists someone who has climbed every mountain in Pakistan
10. Translate the specifications below into English using the given propositional functions.F(p) : The printer p is out of service
B(p) : Printer p is busy
L(j) : Print job j is lost
Q(j) : Print job j is queued
(a) 5 points ∃p (F(p) ∧ B(p)) →∃j L(j)
Solution: If there is a printer that is out of service and is busy, then there exists a print job that is lost.
(b) 5 points (∀p B(p) ∧∀j Q(j)) →∃j L(j)
Solution: If all printers are busy and all jobs are queued, then there exists some job that is lost.
11. Express each of the system specifications below using suitable predicates, quantifiers, and logicalconnectives.
(a) 5 points At least one mail message can be saved if there is a disk with more than 10KB of free space.
Solution: Let P(d, memory) be “disk ‘d’ with greater than ‘memory’ KB of free space
”
Let S(m) be “mail message ‘m’ that can be saved ”
The domain of m is all mail messages
The domain of d is all disks
Logical Statement: ∃d P(d,10) =⇒ ∃m S(m)
(b) 5 points The system mailbox can be accessed by everyone in the group if the file system is locked.
Solution:
Let F(s, p) be “system ‘s’ that can be accessed by person ‘p’ ”
Let L(s) be “system ‘s’ is locked ”
The domain of s is all systems
The domain of p is all people in the group
Logical Statement: ∃s L(s) =⇒ ∃s ∀p F(s,p)
12. Consider the propositions below for which the domain of all variables is Z. For each proposition,
1. Express the proposition in English,
2. State its truth value and provide an explanation if it is true or a counterexample if it isfalse, and
3. Specify a domain for which the proposition has the other truth value.
(a) 5 points ∀x∀y (x2 = y2 → x = y)
Solution:
1 – English: For all values of x and y in integers, if x2 = y2, then x = y
2 – Truth Value: Truth value is false as if x2 = 1 and y2 = 1, then x can be 1 and y can be -1 and vice verse. Hence the conclusion is false even if the premise is true.
3 – Other Truth Value: Truth value will be True for the domain Z+
(b) 5 points ∀x∃y (y2 = x)
Solution:
1 – English: For all integers x, there exists some integer y such that y2 = x
2 – Truth Value: Truth value is false as if x = 2, then for y2 to be 2, y exists outside the domain of integers. Thus the condition is only valid for perfect squares.
3 – Other Truth Value: Truth value will be true for the domain R+
(c) 5 points ∃x∀y (x ≤ y2)
Solution:
1 – English: For all integers y, there exists some integer x such that x ≤ y2
2 – Truth Value: Truth value is true as y2 will always result a positive inte-
ger while x can be some number less than that including negative integers, thus it is true.
3 – Other Truth Value: There does not exist any such domain for which truth value will always be false.
(d) 5 points ∀x∀y ∃z (x − z = y)
Solution:
1 – English: For all integers x and y, there exists some integer z such that z subtracted from x results in an integer y
2 – Truth Value: Truth value is true as for an integer x, there must be some integer z such that z subtracted from x will result in an integer y
3 – Other Truth Value: Truth value is false for domain Z+