Homework Week 4

Problem 31

Express the negations of each statement so that all negation symbols immediately precede predicates.

1. \(\forall x\exists y\forall z\,T(x,y,z)\)
   
2. \(\forall x\exists y\,P(x,y) \lor \forall x\exists y\,Q(x,y)\)
   
3. \(\forall x\exists y(P(x,y) \land \exists z\,R(x,y,z))\)
   
4. \(\forall x\exists y(P(x,y) \to Q(x,y))\)

Problem 33

Rewrite each statement so that negations appear only within predicates.

1. \(\neg\forall x\forall y\,P(x,y)\)
   
2. \(\neg\forall y\exists x\,P(x,y)\)
   
3. \(\neg\forall y\forall x(P(x,y) \lor Q(x,y))\)
   
4. \(\neg(\exists x\exists y\neg P(x,y) \land \forall x\forall y\,Q(x,y))\)
   
5. \(\neg\forall x(\exists y\forall z\,P(x,y,z) \land \exists z\forall y\,P(x,y,z))\)

Problem 37

Express each statement using quantifiers. Then form the negation so that no negation is to the left of a quantifier. Then express the negation in simple English.

1. Every student in this class has taken exactly two mathematics classes at this school.
   
2. Someone has visited every country in the world except Libya.
   
3. No one has climbed every mountain in the Himalayas.
   
4. Every movie actor has either been in a movie with Kevin Bacon or has been in a movie with someone who has been in a movie with Kevin Bacon.

Problem 41

Use quantifiers to express the associative law for multiplication of real numbers.

Problem 45

Determine the truth value of \(\forall x\exists y(xy=1)\) if the domain is:

1. the nonzero real numbers
   
2. the nonzero integers
   
3. the positive real numbers

Problem 3

What rule of inference is used in each argument?

1. Alice is a mathematics major. Therefore, Alice is either a mathematics major or a computer science major.
   
2. Jerry is a mathematics major and a computer science major. Therefore, Jerry is a mathematics major.
   
3. If it is rainy, then the pool will be closed. It is rainy. Therefore, the pool is closed.
   
4. If it snows today, the university will close. The university is not closed today. Therefore, it did not snow today.
   
5. If I go swimming, then I will stay in the sun too long. If I stay in the sun too long, then I will sunburn. Therefore, if I go swimming, then I will sunburn.

Problem 5

Exact text not pasted in chat. Listed in the official Week 4 assignment for Section 1.6.

Reading

Read Sections 1.6.7 and 1.6.8.

Problem 17

What is wrong with this argument?

Let \(H(x)\) be “\(x\) is happy.” Given the premise \(\exists x H(x)\), we conclude that \(H(\text{Lola})\). Therefore, Lola is happy.

Problem 23

Identify the error or errors in the argument that supposedly shows that if \(\exists x P(x) \land \exists x Q(x)\) is true, then \(\exists x(P(x)\land Q(x))\) is true.

1. \(\exists xP(x) \lor \exists xQ(x)\) Premise
   
2. \(\exists xP(x)\) Simplification from (1)
   
3. \(P(c)\) Existential instantiation from (2)
   
4. \(\exists xQ(x)\) Simplification from (1)
   
5. \(Q(c)\) Existential instantiation from (4)
   
6. \(P(c)\land Q(c)\) Conjunction from (3) and (5)
   
7. \(\exists x(P(x)\land Q(x))\) Existential generalization

Direct Proof Practice

1. Use a direct proof to show that the sum of two odd integers is even.
   
2. Exact text not pasted in chat.
   
3. Show that the square of an even number is an even number using a direct proof.
   
4. Show that the additive inverse, or negative, of an even number is an even number using a direct proof.
   
5. Exact text not pasted in chat.
   
6. Exact text not pasted in chat.
   
7. Use a direct proof to show that every odd integer is the difference of two squares. Hint: Find the difference of the squares of \(k+1\) and \(k\).

More Proof Practice

16. Prove that if \(x\), \(y\), and \(z\) are integers and \(x+y+z\) is odd, then at least one of \(x\), \(y\), and \(z\) is odd.
    
17. Use a proof by contraposition to show that if \(x+y\ge 2\), where \(x\) and \(y\) are real numbers, then \(x\ge 1\) or \(y\ge 1\).
    
18. Prove that if \(m\) and \(n\) are integers and \(mn\) is even, then \(m\) is even or \(n\) is even.
    
19. Show that if \(n\) is an integer and \(n^3+5\) is odd, then \(n\) is even using: (a) a proof by contraposition, (b) a proof by contradiction.
    
20. Prove that if \(n\) is an integer and \(3n+2\) is even, then \(n\) is even using: (a) a proof by contraposition.