LOGIC AND PROOFS: SOLUTION OF ROSEN'S DISCRETE MATHEMATICS

SECTION:1.1

1. Which of these sentences are propositions? What are the truth values of those that are propositions?

a) Boston is the capital of Massachusetts.

b) Miami is the capital of Florida.

c) 2+3=5.

d) 5+7=10.

e) x +2=11.

f) Answer this question

Ans: The propositions are - a) , b) ,c) , d)

a) T

b) F

c) T

d) F

2. Which of these are propositions? What are the truth values of those that are propositions?

a) Do not pass go. NO

b) What time is it? NO

c) There are no black ﬂies in Maine. YES =T

d) 4+x =5. NO

e) The moon is made of green cheese. YES =F

f) 2n ≥100. NO

3. What is the negation of each of these propositions?

a) Mei has an MP3 player.

Mei doesn't have an MP3 player.

b) There is no pollution in New Jersey.

There is pollution in New Jersey.

c) 2+1=3.

2+1 !=3.

d) The summer in Maine is hot and sunny.

The summer in Maine is not hot or it is not sunny.

4. What is the negation of each of these propositions?

a) Jennifer and Teja are friends.

Jennifer and Teja are not friends.

b) There are 13 items in a baker’s dozen.

There is not 13 items in a baker's dozen.

c) Abby sent more than 100 text messages every day.

Abby didn't send more than 100 text messages every day.

d) 121 is a perfect square

121 is not a perfect square.

5. What is the negation of each of these propositions?

a) Steve has more than 100 GB free disk space on his laptop.

Steve doesn't have more than 100 GB free disk space on his laptop.

b) Zach blocks e-mails and texts from Jennifer.

Zack doesn't block emails from Jennifer, or he doesn't block texts from Jennifer.

c) 7·11·13=999.

7.11.13!=999

d) Diane rode her bicycle 100 miles on Sunday.

Diane didn't ride her bicycle 100 miles on Sunday.

6. Suppose that Smartphone A has 256 MB RAM and 32GB ROM, and the resolution of its camera is 8 MP; Smartphone B has 288 MB RAM and 64 GB ROM, and the resolution of its camera is 4 MP; and Smartphone C has 128 MB RAM and 32 GB ROM, and the resolution of its camera is 5 MP. Determine the truth value of each of these propositions.

a) Smartphone B has the most RAM of these three smartphones.

TRUE

b) Smartphone C has more ROM or a higher resolution camera than Smartphone B.

TRUE

c) Smartphone B has more RAM, more ROM, and a higher resolution camera than Smartphone A.

FALSE

d) If Smartphone B has more RAM and more ROM than Smartphone C, then it also has a higher resolution camera.

FALSE

e) Smartphone A has more RAM than Smartphone B if and only if Smartphone B has more RAM than Smartphone A.

FALSE

7. Suppose that during the most recent ﬁscal year, the annual revenue of Acme Computer was 138 billion dollars and its net proﬁt was 8 billion dollars, the annual revenue of Nadir Software was 87 billion dollars and its net proﬁt was 5 billion dollars, and the annual revenue of Quixote Media was 111 billion dollars and its net proﬁt was 13 billion dollars. Determine the truth value of each of these propositions for the most recent ﬁscal year.

a) Quixote Media had the largest annual revenue.

FALSE

b) Nadir Software had the lowest net proﬁt and Acme Computer had the largest annual revenue.

TRUE

c) Acme Computer had the largest net proﬁt or Quixote Media had the largest net proﬁt.

TRUE

d) If Quixote Media had the smallest net proﬁt, then Acme Computer had the largest annual revenue.

TRUE

e) Nadir Software had the smallest net proﬁt if and only if Acme Computer had the largest annual revenue.

TRUE

9. Let p and q be the propositions “Swimming at the New Jersey shore is allowed” and “Sharks have been spotted near the shore,” respectively. Express each of these compound propositions as an English sentence.

a) ¬q

Shark have not been spotted near the shore.

b) p∧q

Swimming at the New Jersey shore is allowed and Sharks have been spotted near the shore.

c) ¬p∨q

Swimming at the New Jersey shore is not allowed or Sharks have been spotted near the shore.

d) p →¬ q

If Swimming at the New Jersey shore is allowed , then Sharks have not been spotted near the shore.

e) ¬q → p

If sharks have not been spotted near the shore, then swimming at the New Jersey is allowed.

f) ¬p →¬ q

If Swimming at the New Jersey shore is not allowed , then Sharks have not been spotted near the shore.

g) p ↔¬ q

Swimming at the New Jersey shore is allowed if and only if Sharks have not been spotted near the shore.

h) ¬p∧(p∨¬q)

Swimming at the New Jersey shore is not allowed, and either swimming at the New Jersey shore is allowed or sharks have not been spotted near the shore.

SECTION: 1.2

In Exercises 1–6, translate the given statement into propositional logic using the propositions provided.

1. You cannot edit a protected Wikipedia entry unless you are an administrator. Express your answer in terms of

e: “You can edit a protected Wikipedia entry” and

a: “You are an administrator.”

e → a

2. You can see the movie only if you are over 18 years old or you have the permission of a parent. Express your answer in terms of

m:“You can see the movie,”

e:“Youare over 18 years old,” and

p: “You have the permission of a parent.”

( p ∨ e) → m

3. You can graduate only if you have completed the requirements of your major and you do not owe money to the university and you do not have an overdue library book. Express your answer in terms of

g: “You can graduate,”

m: “You owe money to the university,”

r:“You have completed the requirements of your major,” and

b:“You have an overdue library book.”

g → (r ∧ ( ¬m ) ∧ ( ¬b ) )

4. To use the wireless network in the airport you must pay the daily fee unless you are a subscriber to the service. Express your answer in terms of

w:“You can use the wireless network in the airport,”

d: “You pay the daily fee,” and

s: “You are a subscriber to the service.”

ans: w → ( d ∨ s )

5. You are eligible to be President of the U.S.A. only if you are at least 35 years old, were born in the U.S.A, or at the time of your birth both of your parents were citizens, and you have lived at least 14 years in the country. Express your answer in terms of

e: “You are eligible to be President of the U.S.A.,”

a: “You are at least 35 years old,”

b: “You were born in the U.S.A,”

p: “At the time of your birth, both of your parents where citizens,”

and r: “You have lived at least 14 years in the U.S.A.”

ans : e →( a∧ (b ∨ p ) ∧ r)

6. You can upgrade your operating system only if you have a 32-bit processor running at 1 GHz or faster, at least 1 GB RAM, and 16 GB free hard disk space, or a 64 bit processor running at 2 GHz or faster, at least 2 GB RAM, and at least 32 GB free hard disk space. Express you answer in terms of

u: “You can upgrade your operating system,”

b32: “You have a 32-bit processor,”

b64:“You have a 64-bit processor,”

g1: “Your processor runs at 1 GHz or faster,”

g2:“Your processor run sat 2GHz or faster,”

r1: “Your processor has at least 1 GB RAM,”

r2: “Your processor has at least 2GB RAM,”

h16:“Youhave at least 16 GB free hard disk space,”

and h32: “You have at least 32 GB free hard disk space.”

ans: u →( ( b32 ∧ g1 ∧ r1 ∧ h16) ∨ ( b64 ∧ g2 ∧ r2 ∧ h32) )

7. Express these system speciﬁcations using the propositions

p “The message is scanned for viruses”

and q “The message was sent from an unknown system” together with logical connectives (including negations).

a) “The message is scanned for viruses whenever the message was sent from an unknown system.”

ans: q → p

b) “The message was sent from an unknown system but it was not scanned for viruses.”

ans: q ∧ ~p

c) “It is necessary to scan the message for viruses whenever it was sent from an unknown system.”

ans: q→p

d) “When a message is not sent from an unknown system it is not scanned for viruses.”

ans: ~q → ~p

8. Express these system speciﬁcations using the propositions

p “The user enters a valid password,”

q “Access is granted,” and

r “The user has paid the subscription fee”

and logical connectives (including negations).

a) “The user has paid the subscription fee, but does not enter a valid password.”

ans : r ∧ ~p

b) “Access is granted whenever the user has paid the subscription fee and enters a valid password.”

ans: p → q

c) “Access is denied if the user has not paid the subscription fee.”

ans: ~r → ~q

d) “If the user has not entered a valid password but has paid the subscription fee, then access is granted.”

ans: ( ~p ∧ r) → q

9. Are these system speciﬁcations consistent? “The system is in multi user state if and only if it is operating normally. If the system is operating normally, the kernel is functioning. The kernel is not functioning or the system is in interrupt mode. If the system is not in multi user state, then it is in interrupt mode. The system is not in interrupt mode.”

ans: p: “The system is in multi user state "

q: " It is operating normally"

r: " the kernel is functioning."

s: " the system is in interrupt mode"

p ↔ q

q → r

~r ∨ s

~p → s

Not consistent

10. Are these system speciﬁcations consistent? “Whenever the system software is being upgraded, users cannot access the ﬁle system. If users can access the ﬁle system, then they can save new ﬁles. If users cannot save new ﬁles, then the system software is not being upgraded.”

ans: Not consistent.

11. Are these system speciﬁcations consistent? “The router can send packets to the edge system only if it supports the new address space. For the router to support the new address space it is necessary that the latest software release be installed. The router can send packets to the edge system if the latest software release is installed, The router does not support the new address space.”

ans: Consistent.

12. Are these system speciﬁcations consistent? “If the ﬁle system is not locked, then new messages will be queued. If the ﬁle system is not locked, then the system is functioning normally, and conversely. If new messages are not queued, then they will be sent to the message buffer. If the ﬁle system is not locked, then new messages will be sent to the message buffer. New messages will not be sent to the message buffer.”

ans: Not consistent.

13. What Boolean search would you use to look for Web pages about beaches in New Jersey? What if you wanted to ﬁnd Web pages about beaches on the isle of Jersey (in the English Channel)?

ans:

NEW AND JERSEY AND BEACHES

( JERSEY AND BEACHES) NOT NEW

14. What Boolean search would you use to look for Web pages about hiking in West Virginia ?What if you wanted to ﬁnd Webpages about hiking in Virginia, but not in West Virginia?

Ans: HIKING AND WEST AND VIRGINIA

( HIKING AND VIRGINIA) NOT WEST

15. Each inhabitant of a remote village always tells the truth or always lies. A villager will give only a “Yes” or a “No” response to a question a tourist asks. Suppose you are a tourist visiting this area and come to a fork in the road. One branch leads to the ruins you want to visit; the other branch leads deep into the jungle. A villager is standing at the fork in the road. What one question can you ask the villager to determine which branch to take?

Ans:

“If I were to ask you whether the right branch leads to the ruins, would you answer yes?”

16. An explorer is captured by a group of cannibals. There are two types of cannibals—those who always tell the truth and those who always lie. The cannibals will barbecue the explorer unless he can determine whether a particular cannibal always lies or always tells the truth. He is allowed to ask the cannibal exactly one question.

a) Explain why the question “Are you a liar?” does not work.

b) Find a question that the explorer can use to determine whether the cannibal always lies or always tells the truth.

17. When three professors are seated in a restaurant, the hostess asks them: “Does everyone want coffee?” The ﬁrst professor says: “I do not know.” The second professor then says: “I do not know.” Finally, the third professor says: “No, not everyone wants coffee.” The hostess comes back and gives coffee to the professors who want it. How did she ﬁgure out who wanted coffee?

Ans: The first professor wants coffee. if he doesn't want. he must have said "NO". Similarly the second professor only knows that the first professor wants coffee, but doesn't know about third one and as he doesn't say "NO" so he wants coffee. But the third one says "NO" after knowing that first and second professor wants coffee. So, the third professor doesn't want coffee.

18. When planning a party you want to know whom to invite. Among the people you would like to invite are three touchy friends. You know that if Jasmine attends, she will become unhappy if Samir is there, Samir will attend only if Kanti will be there, and Kanti will not attend unless Jasmine also does. Which combinations of these three friends can you invite so as not to make someone unhappy?

Ans: p: Jasmine attends.

q: Samir attends

r: kanti attends

p → ~q

q → r

~p → ~q

Kanti and Jasmine.

40. Find the output of each of these combinatorial circuits

a) ~p ∨ ~q

b) ~ ( p ∨ ( ~p ∧ q ) )

41. Find the output of each of these combinatorial circuits

a) ~( p ∧ ( q ∨ ~r))

b) ( ~p ∧ ~q ) ∨ ( p ∧ r)

SECTION: 1.3

7. Use De Morgan’s laws to ﬁnd the negation of each of the following statements.

a) Jan is rich and happy.

Ans: Jan is not rich or Jan is not happy.

b) Carlos will bicycle or run tomorrow.

Ans: Carlos will not bicycle and will not run tomorrow.

c) Mei walks or takes the bus to class.

Ans: Mei doesn't walk and doesn't take the bus to class.

d) Ibrahim is smart and hard working.

Ans: Ibrahim is not smart or he is not hard working.

8. Use De Morgan’s laws to ﬁnd the negation of each of the following statements.

a) Kwame will take a job in industry or go to graduate school.

Ans: Kwame will not take a job in industry and he will not go to graduate school.

b) Yoshiko knows Java and calculus.

Ans: Yoshiko doesn't know Java or he doesn't know calculus.

c) James is young and strong.

Ans: James is not young or he is not strong.

d) Rita will move to Oregon or Washington.

Ans: Rita will not move to Oregon and she will not move to Washington.

11. Show that each conditional statement in Exercise 9 is a tautology without using truth tables.

a) (p∧q)→ p

=~(p ∧ q) ∨ p

= (~p ∨ ~q) ∨ p (de morgan's law)

= (~p ∨ p) ∨ ~q

= T ∨ ~q

b) p → (p∨q)

=~p∨ (p∨q)

=(~p∨p)∨q

=T∨q

c) ¬p → (p → q)

=~(~p) ∨ (~p∨q)

=p∨(~p∨q)

=(p∨~p)∨q

=T∨q

d) (p∧q)→ (p → q)

=~(p∧q)∨ (~p∨q)

=(~p∨~q)∨(~p∨q)

=(~p∨~p)∨(~q∨q)

=~p∨T

e) ¬(p → q)→ p

=~(¬(p → q))∨p

=(~p∨q)∨p

=(~p∨p)∨q

=T∨q

f) ¬(p → q)→¬ q

=~(¬(p → q))∨~q

=(~p∨q)∨~q

=~p∨(q∨~q)

=~p∨T

12. Show that each conditional statement in Exercise 10 is a tautology without using truth tables.

a) [¬p∧(p∨q)]→q

=~[¬p∧(p∨q)] V q

=[~(~p) V ~(p∨q)]Vq

=[p∨(~p∧ ~q)] Vq

=[(p ∨ ~p) ∧ (pV~q)] Vq

=[ T ∧ (pV~q)] Vq

=(p∨~q)∨q

=p∨(~q∨q)

=p∨T

b) [(p → q)∧(q → r)]→(p → r)

c) [p∧(p → q)]→q

=[p∧(~p∨q)]→q

=[ (p∧~p) ∨ (p∧q)]→q

=[ F ∨ (p∧q)]→q

=(p∧q)→q

=~(p∧q)∨q

=(~p∨~q)∨q

=~p∨(~q∨q)

=~p∨T

d) [(p∨q)∧(p → r)∧(q → r)]→r

SECTION:1.4

1. Let P(x)denote the statement “x ≤4.” What are these truth values?

a) P(0)

b) P(4)

c) P(6)

2. Let P(x) be the statement “the word x contains the letter a.” What are these truth values?

a) P(orange) T

b) P(lemon) F

c) P(true) F

d) P(false) T

3. Let Q(x,y) denote the statement “x is the capital of y.” What are these truth values?

a) Q(Denver, Colorado) T

b) Q(Detroit, Michigan) F

c) Q(Massachusetts, Boston) F

d) Q(NewYork, NewYork) F

4. State the value of x after the statement if P(x) then x :=1 is executed, where P(x)is the statement “x>1,” if the value of x when this statement is reached is a) x =0. b) x =1. c) x =2.

Ans: c

5. Let P(x) be the statement “x spends more than ﬁve hours every week day in class,” where the domain for x consists of all students. Express each of these quantiﬁcations in English.

a) ∃xP(x)

=> There exists a student who spends more than ﬁve hours every week day in class

b) ∀xP(x)

=> All students spends more than ﬁve hours every week day in class

c) ∃x¬P(x)

=> There exist a student who doesn't spend more than ﬁve hours every week day in class

d) ∀x¬P(x)

=> No student spends more than ﬁve hours every week day in class.

6. Let N(x)be the statement “x has visited North Dakota,” where the domain consists of the students in your school. Express each of these quantiﬁcations in English.

a) ∃xN(x)

=> There is a student who has visited North DAkota.

b) ∀xN(x)

=> Every student has visited North Dakota.

c) ¬∃xN(x)

=> No student has visited North Dakota.

d) ∃x¬N(x)

=> There is a student who has not visited North Dakota.

e) ¬∀xN(x)

=>There is a student who has not visited North Dakota.

f) ∀x¬N(x)

=> No student has visited North Dakota.

7. Translate these statements into English, where C(x) is “x is a comedian” and F(x)is “x is funny” and the domain consists of all people.

a) ∀x(C(x)→ F(x))

=> Every comedian is funny

b) ∀x(C(x)∧F(x))

=> Every person is a funny comedian.

c) ∃x(C(x)→ F(x))

=>There exists a person such that if she or he is a comedian, then she or he is funny

d) ∃x(C(x)∧F(x))

=>) Some comedians are funny.

8. Translate these 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))

=> Every rabbit hops.

b) ∀x(R(x)∧H(x))

=> Every animal is a rabbit and hops.

c) ∃x(R(x)→ H(x))

=>Some rabbits hop.

d) ∃x(R(x)∧H(x))

=> Some animals are rabbit and hops.

9. Let P(x)be the statement “x can speak Russian” and let Q(x) be the statement “x knows the computer language C++.”Express each of these sentences in terms of P(x) , Q(x), quantiﬁers, and logical connectives. The domain for quantiﬁers consists of all students at your school.

a) There is a student at your school who can speak Russian and who knows C++.

=>∃x(P(x)∧Q(x))

b) There is a student at your school who can speak Russian but who doesn’t know C++.

=>)∃x(P(x)∧¬Q(x))

c) Every student at your school either can speak Russian or knows C++.

=>∀x(P(x)∨Q(x))

d) No student at your school can speak Russian or knows C++.

=>∀x¬(P(x)∨Q(x))

Exercises 38–42 deal with the translation between system speciﬁcation and logical expressions involving quantiﬁers.

38. Translate these system speciﬁcations into English where the predicate S(x,y) is “x is in state y” and where the domain for x and y consists of all systems and all possible states, respectively.

a) ∃xS(x, open)

=> Some systems are open.

b) ∀x(S(x, malfunctioning) ∨ S(x, diagnostic))

=>All systems are either malfunctioning or diagnostic.

c) ∃xS(x, open) ∨ ∃xS(x, diagnostic)

=> Some systems are open or some are diagonstic.

d) ∃x¬S(x, available)

=> All systems are not available

e) ∀x¬S(x, working)

=> All systems are not working.

39. Translate these speciﬁcations into English where F(p)is “Printer p is out of service,” B(p) is “Printer p is busy,” L(j) is “Print job j is lost,” and Q(j) is “Print job j is queued.”

a) ∃p(F(p)∧B(p))→∃jL(j)

=>If there is a printer that is both out of service and busy, then some job has been lost.

b) ∀pB(p) →∃jQ(j)

=> If every printer is busy, then there is a job in the queue.

c) ∃j(Q(j)∧L(j)) →∃pF(p)

=>If there is a job that is both queued and lost, then some printer is out of service.

d) (∀pB(p)∧∀jQ(j)) →∃jL(j)

=>) If every printer is busy and every job is queued, then some job is lost.

40. Express each of these system speciﬁcations using predicates, quantiﬁers, and logical connectives.

a) When there is less than 30 megabytes free on the hard disk, a warning message is sent to all users.

=> ∀x(P(x) →Q(x))

b) No directories in the ﬁle system can be opened and no ﬁles can be closed when system errors have been detected.

=>∀x(P(x) →(¬Q(x)∧ R(x))

c) The ﬁle system cannot be backed up if there is a user currently logged on.

=> ∀x(P(x) →~Q(x))

d) Video on demand can be delivered when there are at least 8 megabytes of memory available and the connection speed is at least 56 kilobits per second.

=>∀x(P(x)∧ Q(x)) →R(x))

41. Express each of these system speciﬁcations using predicates, quantiﬁers, and logical connectives.

a) At least one mail message, among the nonempty set of messages, can be saved if there is a disk with more than 10 kilobytes of free space.

=> (∃x F(x, 10)) →∃x S(x), where F(x, y) is “Disk x has more than y kilobytes of free space,” and S(x) is “Mail message x can be saved”

b) Whenever there is an active alert, all queued messages are transmitted.

=> (∃x A(x)) →∀x(Q(x) → T (x)), where A(x) is “Alert x is active,” Q(x) is “Message x is queued,” and T (x)is “Message x is transmitted”

c) The diagnostic monitor tracks the status of all systems except the main console.

=>∀x((x = main console) → T (x)) , where T (x)is “The diagnostic monitor tracks the status of system x”

d) Each participant on the conference call whom the host of the call did not put on a special list was billed.

=>∀x(¬L(x) → B(x)), where L(x) is “The host of the conference call put participant x on a special list” and B(x)is “Participant x was billed”

Exercises 59–62 are based on questions found in the book Symbolic Logic by Lewis Carroll.

59. Let P(x) , Q(x), and R(x) be the statements “x is a professor,” “x is ignorant,” and “x is vain,” respectively. Express each of these statements using quantiﬁers; logical connectives; and P(x) , Q(x), and R(x), where the domain consists of all people.

a) No professors are ignorant.

=>)∀x(P(x) →¬ Q(x))

b) All ignorant people are vain.

=>∀x(Q(x) → R(x))

c) No professors are vain.

=>∀x(P(x) →¬R(x))

d) Does (c) follow from (a) and (b)?

=>NO

60. Let P(x) , Q(x), and R(x)be the statements “x is a clear explanation,” “x is satisfactory,” and “x is an excuse,” respectively. Suppose that the domain for x consists of all English text. Express each of these statements using quantiﬁers, logical connectives, and P(x) ,Q(x),and R(x).

a) All clear explanations are satisfactory.

=>∀x (P(x)→Q(x))

b) Some excuses are unsatisfactory.

=>∃x(R(x)→¬Q(x))

c) Some excuses are not clear explanations.

=>∃x(R(x)→¬P(x))

∗d) Does (c) follow from (a) and (b)?

=>YES.

61. Let P(x) , Q(x), R(x), and S(x) be the statements “x is a baby,” “x is logical,” “x is able to manage a crocodile,” and “x is despised,” respectively. Suppose that the domain consists of all people. Express each of these statements using quantiﬁers; logical connectives; and P(x) , Q(x), R(x), and S(x).

a) Babies are illogical.

=>∀x (P(x)→~Q(x))

b) Nobody is despised who can manage a crocodile.

=>)∀x(R(x) →¬S(x))

c) Illogical persons are despised.

=>)∀x(¬Q(x) →S(x))

d) Babies cannot manage crocodiles.

=>)∀x(P (x) →¬R(x))

∗e) Does (d) follow from (a), (b), and (c)? If not, is there a correct conclusion?

=> YES

SECTION:1.5

1. Translate these statements into English, where the domain for each variable consists of all real numbers.