Looking for a Computer Science Worksheet Templates? Download it for free!

COT3100 – Discrete Structures and Applications- HomeWork 2 Solution 1

Problem 1 [Section 1.5 Exercise 14 (f)(g)) (5 points)]

Use quantifiers and predicates with more than one variable to express these statements.

f) Some students in this class grew up in the same town as exactly one other student in this class.

g) Every student in this class has chatted with at least one other student in at least one chat group.

Solution

The answers to this exercise are not unique; there are many ways of expressing the same propositions

symbolically. Our domain of discourse for persons here consists of people in this class. We need to make

up a predicate in each case.

f) LetG(x,y) mean that persons xand y grew up in the same town. Then our statement is ∃x∃y(x,=

y∧G(x,y)∧∀z(G(x,z)→(x=y∨x=z))).

g)LetC(x,y,z) mean that persons x and y have chatted with each other in chat group z. Then our

statement is ∀x∃y∃z(x,=y∧C(x,y,z)).

Problem 2 [Section 1.5 Exercise 28 (f)(h)(i)(j) (10 points)]

Determine the truth value of each of these statements if the domain of each variable consists of

all real numbers.

f) ∃x∀y(y != 0 → xy = 1)

h) ∃x∃y(x + 2y = 2 ∧ 2x + 4y = 5)

i) ∀x∃y(x + y = 2 ∧ 2x − y = 1)

j) ∀x∀y∃z(z = (x + y)/2)

Solution

f) false(the reciprocal of y depends on y—there is not one x that works for all y)

h) false (this system of equations is inconsistent)

i) false (this system has only one solution; if x=0, for example, then no y satisfies y=2∧−y=1)

j) true (let z=(x+y)/2)

Problem 3 [Section 1.5 Exercise 30 (c)(d) (5 points)]

Rewrite each of these statements so that negations appear only within predicates (that is, so

that no negation is outside a quantifier or an expression involving logical connectives).

c) ¬∃y(Q(y) ∧ ∀x¬R(x,y))

d) ¬∃y(∃xR(x,y) ∨ ∀xS(x,y))

Solution

We need to use the transformations shown in Table2of Section1.4, replacing ¬∀by∃¬, and replacing ¬∃

By ∀¬. In other words, we push all the negation symbols inside the quantifiers, changing the sense of the

quantifiers as we do so, because of the equivalences in Table2of Section1.4.Inaddition,we need to use

De Morgan’s laws (Section1.3)to change the negation of a conjunction to the disjunction of the

negations and to change the negation of a disjunction to the conjunction of the negations. We also use

the fact that ¬¬p≡p.

c)∀y(¬Q(y)∨∃xR(x,y))

d)∀y(∀x¬R(x,y)∧∃x¬S(x,y))

Problem 4 [Section 1.6 Exercise 12 (10 points)]

Show that the argument form with premises (p ∧ t) → (r ∨ s), q → (u ∧ t), u → p, and ¬s

and conclusion q → r is valid by first using Exercise 11 of Section 1.6 and then using the rules of

inference from Table 1 of Section 1.6.

Exercise 11 (You can directly use the conclusion without proving it): Show that the argument

form with premises p

,p2,,...,pn and conclusion q → r is valid if the argument form with premises

p1,p2,...,pn,q and conclusion r is valid.

Cot3100 - Discrete Structures And Applications - Homework 2 Solution - University Of Florida

Related Articles

Related forms

Related Categories