[PDF] Section 14, selected answers Math 114 Discrete Mathematics

7004_6Sec14.pdf

Section 1.4, selected answers

Math 114 Discrete Mathematics

D Joyce, Spring 2018

4.P(x;y) is \xhas taken classy." Express the following

in English. There are minor variants that you can give for each of these. Let's writePxyrather thanP(x;y) whenever we can to reduce parentheses. a.9x9y Pxy. Someone has taken some class. b.9x8y Pxy. Someone has taken every class. c.8x9y Pxy. Everyone has taken at least one class. Or \taken a class" or \taken some class." d.9y8xPxy. There's a class that everyone has taken. e.8y9xPxy. Every class has at least one student. f.8x8y Pxy. Everyone has taken every class.

6.LetC(x;y) mean that a studentxis enrolled in a classy.

Express the following in English. Of course, there are many variant sentences you can give. These are just samples. a.C(Randy Goldberg;CS 252). Randy Goldberg is en- rolled in CS 252. b.9xC(x;Math 695). Someone is taking Math 695. c.9y C(Carol Sitea;y). Carol Sitea is enrolled in some class. d.9xC(x;Math 222)^C(x;Math 252). Somebody is taking both Math 222 and Math 252. e.9x9y8z((x6=y)^(Cxz!Cyz). There are two students such that the every class that the rst student is taking is also taken by the second student. More brie y, but a little less clearly, you could say: somebody is enrolled in every class someone else is taking. f.9x9y8z((x6=y)^(Cxz$Cyz). Somebody is taking the exact same classes that somebody else is taking.

12.LetI(x) be \xhas an internet connection" and let

C(x;y) be \xandyhave chatted over the internet." Assume the universe of discourse consists of all students in your class.

Express the following using quantiers.

An alternative way of writing predicates is to drop the parentheses, that is, writeIxinstead ofI(x), andCxyin- stead ofC(x;y). Some of these statements have so many parentheses that it makes sense to drop these extra paren- theses, especially when the arguments are variables. a.Jerry does not have an Internet connection.:I(Jerry). b.Rachel has not chatted over the internet with Chelsea. :C(Rachel,Chelsea). c.Jan and Sharon have never chatted over the internet. :C(Jan,Sharon). d.No one in the class has chatted with Bob. :9xC(x;Bob). Alternatively,8x:C(x;Bob). e.Sanjay has chatted with everyone except Joseph.

8y(y6= Joseph!C(Sanjay;y)). Alternatively,8y(y=

Joseph_C(Sanjay;y)).

f.Someone in your class does not have an internet con- nection.9x:Ix.g.Not everyone in your class has an internet connection. :8xIx. This is logically equivalent to the previous state- ment. h.Exactly one student in your class has an internet connection.9x(Ix^ 8y(Iy!y=x)). Alternatively,

9x(Ix^ 8y(y6=x! :Iy)). Using the uniqueness quan-

tier, you could write this as9!xIx. i.Everyone except one student in your class has an inter- net connection. It appears this means exactly one student does not have a connection. That would be9!x:Ixwhen expressed with the uniqueness quantier, but without the uniquenss quantier it could be9x(:Ix^8y(Iy!y=x)). j.Everyone in your class with an internet connection has chatted over the internet with at least one other student in your class.8x(Ix! 9y(Cxy^x6=y)). If you assume no- body can chat with him or herself, a reasonable assumption, then you can drop thex6=yat the end. k.Someone in your class has an internet connection but has not chatted with anyone else in your class.9x(Ix^

8y:Cxy). Alternatively,9x(Ix^ :9y Cxy).

l.There are two students in your class who have not chat- ted with each other over the internet.9x9y(x6=y^:Cxy).

Sometimes this would be abbreviated9x9y6=x;:Cxy.

m.There is a student in your class who has chatted with everyone in your class over the internet.9x8y Cxy. It's reasonable to assume that the statement had an implicit \else" in it: ... with everyone else ..., in which case you need

9x8y(x6=y!Cxy).

n.There are at least two students in your class who have not chatted with the same person in your class.9x9y(x6= y^ 9z(:Cxz^ :Cyz). Probably, the intent of the sentence is thatzis a third person, so a better translation would be

9x9y(x6=y^ 9z(x6=z^y6=z^ :Cxz^ :Cyz).

o.There are two students in the class who between them have chatted with everyone else in the class.9x9y(x6= y^ 8z(Cxz_Cyz)).

20.Express these statements using predicates, quantiers,

logical connectives, and mathematical operators where the universe of discourse is the set of all integers. a.The product of two negative integers is positive.

One logical expression that does the job is

8x;8y;(x <0^y <0!xy >0):

But we usually combine the conditionx <0 with the quan- tier to make a shorter expression:

8x <0;8y <0; xy >0:

b.The average of two positive integers is positive.

8x >0;8y >0;x+y2

>0: 1 c.The dierence of two negative integers is not necessarily negative. You could say it is not the case that the dierence is always negative as follows :8x <0;8y <0; xy <0; or you could say that there are negative numbers whose dierence is not negative:

9x <0;9y <0; xy6<0:

The two statements are logically equivalent. Note that you could writerather than6<. d.The absolute value of the sum of two integers does not exceed the sum of the absolute values of these integers.

8x;8y;jx+yj  jxj+jyj:

This inequality is sometimes called thetriangle inequality.

28.Determine the truth value . The universe of discourse

is the set of real numbers. Think of these as questions. a.8x9y(x2=y). For eachxis there aysuch that x

2=y? Yes,x2.

b.8x9y(x=y2). Is every numberxthe square of some numbery? No, not the negative ones; negative numbers don't have square roots. c.9x8y(xy= 0). Is there some number whose product with any other number is 0? Yes there is, namely 0. d.9x9y(x+y6=y+x). Can you nd two numbers whose sum depends on the order you add them? No. Addition is commutative. e.8x6=09y(xy= 1). This is an abbreviation for8x(x6=

0! 9y(xy= 1). For any nonzero real numberxcan you

solvexy= 1 fory? Yes,y= 1=x. f.9x8y6=0(xy= 1). Compare this with part d above. Is there some number whose product with any other number is 1? No. g.8x9y(x+y= 1). Can you solvex+y= 1 foryin terms ofx? Yes,y= 1x. h.9x9y(x+ 2y= 2^2x+ 4y= 5). Can you solve the pair of simultaneous equationsx+ 2y= 2 and 2x+ 4y= 5 forxandy? No, there are no solutions. If you double the rst you get 2x+ 4y= 4, but the second says 2x+ 4y= 5.

Since 46= 5, there are no solutions.

i.8x9y(x+y= 2^2xy= 1). For anyxcan you nd aythat satises bothx+y= 2 and 2xy= 1? According to the rst equation,y= 2x, but according to the second equation,y= 2x1. Since 2xdoes not equal 2x1 for allx, both equations can't be satised for allx. j.8x8y9z z=x+y2  . Yes. Given any two numbersx andy, you can indeed average them.32.Express the negations of each of these statements so that all negation symbols immediately precede predicates.

As you pass the:past a quantier, exchange8and9,

and as you pass it past either^or_, exchange them. a.8z9y9x:T(x;y;z) b.8x8y:P(x;y)_ 9x9y:Q(x;y) c.8x8y(Q(x;y)Q(y;x)), or8x8y(:Q(x;y)$

Q(y;x)), or8x8y(Q(x;y)$ :Q(y;x)).

d.9y8x8z(:T(x;y;z)^ :Q(x;y))

46.Determine the truth value of the statement

9x8y(xy2)

if the universe of discourse for the variables consists of a.the positive real numbers. How about this? Just letx be 0. The squarey2of any real numberyis greater than or equal to 0. Wait a minute. We're not allowed to letxbe 0 sincexhas to be positive. Then it's false. No matter what positive numberxis, there are squaresy2that are smaller thanx. b.the integers. Yep,x= 0 is an integer that works. c.the nonzero real numbers. We're not allowed to letx be 0. But we can takexto be negative, sayx=1. Then every squarey2is greater thanx.

Math 114 Home Page athttp://math.clarku.edu/

~ djoyce/ma114/ 2