CSI131 - Discrete Structures I WEEK 4 Tutorial 3
Attempt All questions
Duration: 2 hours
Predicate Calculus
1. Study the Prolog facts below and answer questions that follow.
• instructor(chan,math273)
• instructor(patel,ee222)
• instructor(grossman,cs301)
• enrolled(kevin,math273)
• enrolled(juan,ee222)
• enrolled(juan,cs301)
• enrolled(kiko,math273)
• enrolled(kiko,cs301)
• teaches(p,s) :- instructor(P,C), enrolled(S,C)
What would Prolog return given these queries:
(a) ?instructor(chan,math273)
(b) ?instructor(patel,cs301)
(c) ?enrolled(X,cs301)
(d) ?enrolled(kiko,Y)
(e) ?teaches(grossman,Y)
2. Let P (x) be the statement: ”the word x contains the letter a”. What are the truth
values of?
(a) P (Orange)
(b) P (Lemon)
3. Translate the following statements into English, where R(x) is ”x is a rabbit”, and
H(x) is ”x hops”, and the domain consists of all animals.
(a) ∀x(R(x) → H(x))
(b) ∀x(R(x) ∧ H(x))
1
4. Let C(x) be the statement ”x has a cat”, Let D(x) be the statement ”x has a dog” and
Let F (x) be the statement ”x has a ferret”. Express each of these statements in terms
of C(x), D(x), F (x), quantifiers, and logical connectives. Let the domain consists of all
students in your class.
(a) some student in your class has a cat and a ferret, but not a dog.
(b) No student in your class has a cat, dog and ferret.
5. Let P (x) be the statement “x = x2 ”. If the domain consists of integers, what are the
truth values of:
(a) ∃xP (x)
(b) ∀xP (x)
6. Determine the truth value of each of these statements if the domain for all variables
consists of all integers.
(a) ∀n(n2 ≥ n)
(b) ∃n(n2 < 0)
7. Suppose that the domain of the propositional function P (x) consists of the integers
1, 2, 3, 4 and 5. Express these statements without using quantifiers, instead using only
negations, disjunctions and conjunctions.
(a) ∀xP (x)
(b) ¬∃xP (x)
(c) ∀x((x 6= 3) → P (x)) ∨ ∃x¬P (x)
8. Translate in two ways each of these statements into logical expressions using predicates,
quantifiers and logical connectives. First let the domain consists of the students in your
class and second, let it consist of all people.
(a) All students in your class can solve quadratic equations.
(b) Somebody in your class has seen a foreign movie.
9. Translate each of these statements into logical expressions using predicates, quantifiers
and logical connectives.
(a) All tools are in correct place and are in excellent condition.
(b) One of your tools is not in in the correct place, but it is in excellent condition.
10. Show that the following conditional statement is a tautology without using truth
tables.[p ∧ (p → q)] → q
2
11. Without the use of truth tables, determine whether (¬p∧(p → q)) → ¬q is a tautology.
show all your work.
12. Show that each of the compound propositions below are logically equivalent. To do
this, either show that both sides are true, or that both sides are false for exactly the
same combinations of truth values of the propositional variables in these expressions
(whichever is easier.)
(a) Show that: p ↔ q ≡ (p ∨ q) ∨ (¬p ∧ ¬q)
(b) show that: p → q ≡ ¬q → ¬p
(c) show that: ¬(p ⊕ q) ≡ p ↔ q
(d) Show that (p → q) ∨ (p → r) ≡ p → (q ∨ r)
13. Show that: (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r) is a tautology
14. Show that (p ∧ q) → r and (p → r) ∧ (q → r) are not logically equivalent.
0.1 Logical Equivalences
3
Equivalence name
p∧T ≡p
p∨F ≡p Identity Laws
p∨T ≡T
p∧F ≡F Domination Laws
p∧p≡p
p∨p≡p Idempotent Laws
¬(¬p) ≡ p double negation Law
p∧q ≡q∧p
p∨q ≡q∨p commutative laws
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q De Morgan’s laws
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Associative Laws
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) Distributive Laws
p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p Absorption Laws
p ∨ ¬p ≡ T
p ∧ ¬p ≡ F negation Laws
p → q ≡ ¬p ∨ q
p → q ≡ ¬q → ¬p
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
(p → r) ∧ (q → r) ≡ (p ∨ q) → r
(p → q) ∨ (p → r) ≡ p → (q ∨ r)
(p → r) ∨ (q → r) ≡ (p ∧ q) → r
p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
¬(p ↔ q) ≡ p ↔ ¬q