# Solution to HW 2 – Discrete Mathematics 1 [Short Semester 2015]

The problems are taken from Discrete Mathematics and Its Applications – Kenneth H. Rossen, 7th edition.

Section 1.4.

Problem 5. [carries 15 marks]

a. “There exists a student who spends more than five hours every weekday in class.”, “Some students spend more than five hours every weekday in class.” (note that in English, “some students” does not require more than one student to exist).

b. “Every student spends more than five hours every weekday in class.”

c. “There is a student who does not spend more than five hours every weekday in class.”

d. “Every student does not spend more than five hours every weekday in class.”

Problem 8. [carries 15 marks]

a. All rabbits hop.

b. Every animal is a rabbit and hops.

c. There exists an animal such that it hops if it’s a rabbit.

d. There exists an animal that is a rabbit and hops.

Problem 17. [carries 15 marks]

a. $P(0) \vee P(1) \vee P(2) \vee P(3) \vee P(4)$

b. $P(0) \wedge P(1) \wedge P(2) \wedge P(3) \wedge P(4)$

c. $\neg P(0) \wedge \neg P(1) \wedge \neg P(2) \wedge \neg P(3) \wedge \neg P(4)$

d. $\neg P(0) \vee \neg P(1) \vee \neg P(2) \vee \neg P(3) \vee \neg P(4)$.

Problem 20. [carries 5 marks]

$P(-5) \wedge P(-3) \wedge P(-1) \wedge P(3) \wedge P(5)$

Problem 33. [carries 20 marks]

a. Define a predicate $T(x)$: $x$ can learn new things with $x$ having a set of all old dogs as the domain.

The sentence is $\exists x T(x)$.

The negation is $\forall x \neg T(x)$.

In English, the negation is “All old dogs cannot learn new things.”

b. Define a predicate $C(x)$: $x$ knows calculus with set of all rabbit as the domain of $x$.

The sentence is $\forall x \neg C(x)$.

The negation is $\exists x C(x)$.

In English, the negation is “There is a rabbit that knows calculus.”

c. Define a predicate $F(x):$ $x$ can fly with the domain set of bids.

The sentence is $\forall x F(x)$.

The negation is $\exists x \neg F(x)$.

In English, the negation is “Some birds cannot fly”, “There is a bird that cannot fly.”

Problem 40. [carries 15 marks]

a. Define some predicates $P(x)$: there is less than $x$ megabytes on hard disk and $M(x)$: user $x$ is sent a warning message. Here the domain of $x$ in predicate $P$ is a real number and the domain of $x$ in predicate $M$ is set of all users. The sentence is $P(30) \rightarrow \forall x Q(x)$.

b. Define some predicates $A(x):$ directory $x$ cannot be accessed and $O(x):$ file $x$ cannot be opened where $A$ has domain the set of all directories and $O$ has domain the set of all files, and also let $p$ be a proposition that system errors have been detected. The sentence is $p \rightarrow (\forall x A(x) \wedge \forall x O(x))$.

Section 1.5.

Problem 9. [carries 20 marks]

a. $\forall x L(x,\text{Jerry})$.

b. $\forall x \exists y L(x,y)$.

c. $\exists x \forall y L(y,x)$.