Discrete Computational Structures Homework Assignment #2

CS 230 : Discrete Computational Structures

Homework Assignment #2

Suggested Reading: Rosen Sections 1.4 - 1.6; LLM Chapter 3
For the problems below, explain your answers and show your reasoning.
1. [4 Pts] Prove, by counterexample, that the propositions ∀x(P(x) → Q(x)) and
∀xP(x) → ∀xQ(x) are not logically equivalent. Hint: Let your domain be the set
of integers. Define P(x) to be ‘x is odd’ and Q(x) to be ‘x is even’.
2. [8 Pts] For the following problems, let S(x), F(x) and A(x, y) be the statements “x is
a student”, “x is a faculty member” and “x has asked y a question”. Let the domain
be all people at ISU. Translate into English or logic, as appropriate.
(a) ∃x∃y∀z(S(x) ∧ S(y) ∧ (x 6= y) ∧ (F(z) → (A(x, z) ↔ A(y, z))))
(b) There are at least two faculty members who have not asked questions to any
students.
3. [4 Pts] State whether the following arguments are correct. Explain your answer briefly.
(a) All freshmen take online classes. Jim is not a freshman. Therefore, Jim does not
take online classes.
(b) Mary likes all her computer science classes. Mary likes ‘Discrete Math’. Therefore,
‘Discrete Math’ is a computer science class.
4. [8 Pts] Define predicates and prove the following using the appropriate rules of inference:
(a) [4 Pts] Jim, a student in class, owns a personal computer. Everyone who owns
a personal computer types up their homework. Therefore, someone in class types
up their homework.
(b) [4 Pts] There are college towns in the midwest. All college towns are fun places
to live. There is a town in the midwest that is a fun to live in.
5. [14 Pts] Consider the following argument:
All bears are good swimmers. If you can catch fish, you will not go hungry. If you can’t
catch fish, you are not a good swimmer. Therefore, no bears go hungry.
(a) [4 Pts] Define the predicates B(x), S(x), H(x) and F(x) to describe the sentences
above using predicate logic. Then, prove the argument using the rules of inference
you have learned.
(b) [3 Pts] Prove the universal transitivity rule, which states:
if ∀x(P(x) → Q(x)) and ∀x(Q(x) → R(x)), then ∀x(P(x) → R(x)).
(c) [3 Pts] Prove the universal contrapositive rule, which states:
if ∀x(P(x) → Q(x)) then ∀x(¬Q(x) → ¬P(x)).
(d) [4 Pts] Now, prove the previous argument using the universal transitivity rule
and the universal contrapositive rule. Is your proof shorter? Notice that you
no longer have to use instantiation and generalization rules.
6. [12 Pts] Given the universe of all non-negative integers, we have the two predicates
A(k, m, n) : (k = m + n) and M(k, m, n) : (k = mn). For example A(4, 3, 1) is true
while A(5, 2, 2) is false. We can use A and M to define other predicates. For example,
Zero(n) : A(n, n, n). Note that n = 0 is the only integer such that n = n + n. We can
now use Zero to define Greater(m, n) : ∃k(¬Zero(k)∧A(m, n, k)). Define the following
predicates. You can use the predicates defined earlier in subsequent definitions.
(a) [4 Pts] Equal(m, n)
(b) [4 Pts] One(n)
(c) [4 Pts] Two(n)
(d) Extra Credit [4 Pts] P rime(p)
For more practice, work on the problems from Rosen Sections 1.4 - 1.6 and LLM Chapter 3.