Exam 1: The Foundations: Logic and Proofs

Match the English statement with all its equivalent symbolic statements in this list: 1. $\exists x \forall y T ( x , y )$$\quad$$\quad$$\quad$ 2. $\exists y \forall x T ( x , y )$$\quad$$\quad$$\quad$ 3. $\forall x \exists y T ( x , y )$ 4. $\neg \exists x \exists y T ( x , y )$$\quad$$\quad$ 5. $\exists x \forall y \neg T ( x , y )$$\quad$$\quad$$\quad$ 6. $\forall y \exists x T ( x , y )$ 7. $\exists y \forall x \neg T ( x , y )$$\quad$$\quad$ 8. $\neg \forall x \exists y T ( x , y )$$\quad$$\quad$$\quad$ 9. $\neg \exists y \forall x T ( x , y )$ 10. $\neg \forall x \exists y \neg T ( x , y )$$\quad$ 11. $\neg \forall x \neg \forall y \neg T ( x , y )$$\quad$ 12. $\forall x \exists y \neg T ( x , y )$ -Some courses are being taken by no students.

assume that the universe for x is all people and the universe for y is the set of all movies. Write the statement in good English, using the predicates $S ( x , y ) : x \text { saw } y \quad L ( x , y ) : x \text { liked } y \text {. }$ Do not use variables in your answer. - $\exists y \neg S \text { (Margaret, } y \text { ) }$

Match the statement in symbols with one of the English statements in this list: 1. Some freshmen are math majors. 2. Every math major is a freshman. 3. No math major is a freshman. - $\forall x ( F ( x ) \rightarrow \neg M ( x ) )$

Explain why the negation of "Al and Bill are absent" is not "Al and Bill are present".

Find the output of the combinatorial circuits in 54-55.

P(x, y) means "x and y are real numbers such that $x + 2 y = 5 "$ Determine whether the statement is true. - $\exists x \forall y P ( x , y )$ In 73-75 P(m, n) means $“ m \leq n "$ where the universe of discourse for m and n is the set of nonnegative integers. What is the truth value of the statement?

Determine whether this proposition is a tautology: $( ( p \rightarrow q ) \wedge \neg p ) \rightarrow \neg q$

Give a proof by contradiction of the following: "If n is an odd integer, then n2 is odd".

P(m, n) means $“ m \leq n "$ where the universe of discourse for m and n is the set of nonnegative integers. What is the truth value of the statement? - $\exists n \forall m P ( m , n )$

suppose the variable x represents students and y represents courses, and: U(y): y is an upper-level course M(y): y is a math course F(x): x is a freshman B(x): x is a full-time student T(x, y): student x is taking course y. Write the statement using these predicates and any needed quantifiers. -All students are freshmen.

Prove or disprove: For all real numbers x and $y , \lfloor x - y \rfloor = \lfloor x \rfloor - \lfloor y \rfloor \text {. }$

write the negation of the statement in good English. Don't write "It is not true that . . . ." -Roses are red and violets are blue.

write the negation of the statement in good English. Don't write "It is not true that . . . ." -Some skiers do not speak Swedish.

Match the English statement with all its equivalent symbolic statements in this list: 1. $\exists x \forall y T ( x , y )$$\quad$$\quad$$\quad$ 2. $\exists y \forall x T ( x , y )$$\quad$$\quad$$\quad$ 3. $\forall x \exists y T ( x , y )$ 4. $\neg \exists x \exists y T ( x , y )$$\quad$$\quad$ 5. $\exists x \forall y \neg T ( x , y )$$\quad$$\quad$$\quad$ 6. $\forall y \exists x T ( x , y )$ 7. $\exists y \forall x \neg T ( x , y )$$\quad$$\quad$ 8. $\neg \forall x \exists y T ( x , y )$$\quad$$\quad$$\quad$ 9. $\neg \exists y \forall x T ( x , y )$ 10. $\neg \forall x \exists y \neg T ( x , y )$$\quad$ 11. $\neg \forall x \neg \forall y \neg T ( x , y )$$\quad$ 12. $\forall x \exists y \neg T ( x , y )$ -Every course is being taken by at least one student.

Suppose you wish to prove a theorem of the form "if p then q". (a) If you give a direct proof, what do you assume and what do you prove? (b) If you give a proof by contraposition, what do you assume and what do you prove? (c) If you give a proof by contradiction, what do you assume and what do you prove?

It is Thursday and it is cold.

suppose the variable x represents students and the variable y represents courses, and $A ( y ) : y \text { is an advanced course } \quad S ( x ) : x \text { is a sophomore } \quad F ( x ) : x \text { is a freshman } \quad T ( x , y ) : x \text { is taking } y \text {. }$ Write the statement using these predicates and any needed quantifiers. -No freshman is a sophomore.

suppose the variables x and y represent real numbers, and L(x,y):x

Show that the hypotheses "I left my notes in the library or I finished the rough draft of the paper" and "I did not leave my notes in the library or I revised the bibliography" imply that "I finished the rough draft of the paper or I revised the bibliography".