Key Concepts in Computer Science -Assignment 3

1. [2 marks] Show that (¬q  (p  q))  ¬p is a tautology using truth table.
We showed that all of the rows are True. Therefore, the statement is a tautology.

3. [3 marks] Give a proof that ¬p  ¬q and q  p are logically equivalent.
Note: You can also start from the left side and modify it until it looks like the right side. Or you can start from the right side and modify it until it looks like the left side.
We start from left side: ¬p  ¬q  p  ¬q [we use p  q  ¬p  q]
Then, we go to the right side: q  p  ¬q  p  p  ¬q [we use p  q  ¬p  q and p  q  q  p]
We showed that both sides are equivalent to p  ¬q. Therefore, both sides are equivalent.
4. [5 marks] Give a proof that (p  q)  (p  r)  p  (q  r)
Note: You can also start from the left side and modify it until it looks like the right side. Or you can start from the right side and modify it until it looks like the left side.
We start from left side: (p  q)  (p  r)  (¬p  q)  (¬p  r) [we use p  q  ¬p  q for each statement in parenthesis]
Then, we go to the right side: p  (q  r)  ¬p  (q  r)  (¬p  q)  (¬p  r) [we use p  q  ¬p  q and De Morgan’s law]
We showed that both sides are equivalent to (¬p  q)  (¬p  r). Therefore, both sides are equivalent.
5. [5 marks] Determine using truth tables whether the condition of the if statement is true for any value of x and y:
[Hint: For a given value of x, x > 5 is a proposition. Let it be p. Similarly, let q be the proposition y < 7 for a given value of y. Remark: if the value of x is not given, x > 5 is not a proposition!]
if ((x > 5 or not y < 7) and (not x > 5 or y < 7) and (not x > 5 or not y < 7)) then print “true” p: x > 5
q: x < 7 Therefore, we can rewrite the if statement as follows: if ((p  ¬q)  (¬p  q)  (¬p  ¬q)) then print “true” In other words, we want to see whether (p  ¬q)  (¬p  q)  (¬p  ¬q) is satisfiable or not. A statement is satisfiable if at least on row in its associated truth table is True.

 Because the last row is True, we can say the statement is satisfiable.
 Therefore, if we set both p and q to false, the if statement becomes True.
 For example, we can set x to 3 (which makes p false) and y to 9 (which makes q false) to make the if statement true.
6. [3 marks] Suppose that the domain of the propositional function P(x) is {4, -3, 1, -5}.
Express these statements without using quantifiers, instead using only negations, disjunctions, and conjunctions.
a)  x P(x)  P(4)  P(-3)  P(1)  P(-5)
b)  x P(x)  P(4)  P(-3)  P(1)  P(-5)
7. [5 marks] If U consists of 5, 6, and 7, and P(x) is the statement “2x + 1 ≥ 15”, then:
a) x P(x) is true or false?
b) ¬x P(x) is true or false?
Justify your answer.
First, we simplify the statement: 2x + 1 ≥ 15 ⟹ 2x ≥ 14 ⟹ x ≥ 7
x P(x) is True because we can find at least one x that satisfies P(x). For example, P(7) is true.
¬x P(x) is equivalent to x ¬P(x) using De Morgen’s law. x ¬P(x) is True because we can find at least one x that DOES NOT satisfy P(x). For example, P(5) is not true (P(5) is false).