Homework Week 3

Problem 65

Determine whether each of these compound propositions is satisfiable.

1. \((p \lor \neg q) \land (\neg p \lor q) \land (\neg p \lor \neg q)\)

2. \((p \to q) \land (p \to \neg q) \land (\neg p \to q) \land (\neg p \to \neg q)\)

3. \((p \leftrightarrow q) \land (\neg p \leftrightarrow q)\)

Problem 1

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

1. \(P(0)\)
   
2. \(P(4)\)
   
3. \(P(6)\)

Problem 5

Let \(P(x)\) be the statement “\(x\) spends more than five hours every weekday in class,” where the domain for \(x\) consists of all students. Express each of these quantifications in English.

1. \(\exists x P(x)\)
   
2. \(\forall x P(x)\)
   
3. \(\exists x \neg P(x)\)
   
4. \(\forall x \neg P(x)\)
   
5. \(\neg\exists x P(x)\)
   
6. \(\neg\forall x P(x)\)

Problem 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)\), quantifiers, and logical connectives. The domain for quantifiers consists of all students at your school.

1. There is a student at your school who can speak Russian and who knows C++.
   
2. There is a student at your school who can speak Russian but who doesn’t know C++.
   
3. Every student at your school either can speak Russian or knows C++.
   
4. No student at your school can speak Russian or knows C++.

Problem 11

Let \(P(x)\) be the statement “\(x=x^2\).” If the domain consists of the integers, what are these truth values?

1. \(P(0)\)
   
2. \(P(1)\)
   
3. \(P(2)\)
   
4. \(P(-1)\)
   
5. \(\exists x P(x)\)
   
6. \(\forall x P(x)\)

Problem 15

Determine the truth value of each of these statements if the domain for all variables consists of all integers.

1. \(\forall n(n^2 \ge 0)\)
   
2. \(\exists n(n^2 = 2)\)
   
3. \(\forall n(n^2 \ge n)\)
   
4. \(\exists n(n^2 < 0)\)

Problems 19, 21, 25

Exact text not pasted in chat. Listed in the official Week 3 assignment for Section 1.4.

Problem 33

Express each of these statements using quantifiers. Then form the negation of the statement, so that no negation is to the left of a quantifier. Next, express the negation in simple English. Do not simply use the phrase “It is not the case that.”

1. Some old dogs can learn new tricks.
   
2. No rabbit knows calculus.
   
3. Every bird can fly.
   
4. There is no dog that can talk.
   
5. There is no one in this class who knows French and Russian.

Problems 35, 37

Exact text not pasted in chat. Listed in the official Week 3 assignment for Section 1.4.

Problem 39

Find a counterexample, if possible, to these universally quantified statements, where the domain for all variables consists of all integers.

1. \(\forall x\forall y(x^2 = y^2 \to x = y)\)
   
2. \(\forall x\exists y(y^2 = x)\)
   
3. \(\forall x\forall y(xy \ge x)\)

Problems 45, 47, 51, 53

Exact text not pasted in chat. Listed in the official Week 3 assignment for Section 1.4.

Problem 1

Exact text not pasted in chat. Listed in the official Week 3 assignment for Section 1.5.

Problem 3

Let \(Q(x,y)\) be the statement “\(x\) has sent an email message to \(y\),” where the domain for both \(x\) and \(y\) consists of all students in your class. Express each of these quantifications in English.

1. \(\exists x\exists y Q(x,y)\)
   
2. \(\exists x\forall y Q(x,y)\)
   
3. \(\forall x\exists y Q(x,y)\)
   
4. \(\exists y\forall x Q(x,y)\)
   
5. \(\forall y\exists x Q(x,y)\)
   
6. \(\forall x\forall y Q(x,y)\)

Problems 9, 25, 27, 29, 39

Exact text not pasted in chat. Listed in the official Week 3 assignment for Section 1.5.

Consider the predicate \(P(x,y,z)\), with domain being all integers. For each statement below, determine whether it is true or false. The actual predicate definition was not pasted in the chat.

1. \(\forall x\forall y\forall z\,P(x,y,z)\)
   
2. \(\forall x\forall y\exists z\,P(x,y,z)\)
   
3. \(\forall x\exists y\forall z\,P(x,y,z)\)
   
4. \(\forall x\exists y\exists z\,P(x,y,z)\)
   
5. \(\exists x\forall y\forall z\,P(x,y,z)\)
   
6. \(\exists x\forall y\exists z\,P(x,y,z)\)
   
7. \(\exists x\exists y\forall z\,P(x,y,z)\)
   
8. \(\exists x\exists y\exists z\,P(x,y,z)\)