Chapter 2

A restaurant displays the sign "Good food is not cheap." and a competing restaurant displays the sign "Cheap food is not good." Are the two restaurants saying the same thing?

1\. Let \(X\) be the set of all students at a university. Let \(A\) be the set of students who are firstyear students, \(B\) the set of students who are second- year students, \(C\) the set of students who are in a discrete mathematics course, \(D\) the set of students who are international relations majors, \(E\) the set of students who went to a concert on Monday night, and \(F\) the set of students who studied until 2 AM on Tuesday. Express in set theoretic notation the following sets of students: (a) All second-year students in the discrete mathematics course. Sample Solution. \(\mid x \in X: x \in B\) and \(x \in C\\} .\) (b) All first-year students who studied until 2 AM on Tuesday. (c) All students who are international relations majors and went to the concert on Monday night. (d) All students who studied until 2 AM on Tuesday, are second-year students, and are not international relations majors. (e) All first- and second-year students who did not go to the concert on Monday night but are intemational relations majors. (f) All students who are first-year international relations majors or who studied until 2 AM on Tuesday. (g) All students who are first-or second-year students who went to a concert on Monday night. (h) All first-year students who are intemational relations majors or went to a concert on Monday night.

Find formulas in DNF equivalent to each of the following formulas: (a) \(\neg(p \wedge T)\) (b) \(((p \rightarrow q) \rightarrow r) \rightarrow F\) (c) \(((p \rightarrow q) \rightarrow r) \rightarrow T\) (d) \((p \leftrightarrow q) \leftrightarrow r\) (e) \(\neg(p \leftrightarrow q) \leftrightarrow r\) (f) \(((p \vee q) \rightarrow r) \wedge(r \rightarrow \neg(p \vee q))\) (g) \((\neg r) \rightarrow(((p \vee q) \rightarrow r) \rightarrow \neg q)\)

The country of Ost is inhabited only by people who either always tell the truth or always tell lies and who will respond to questions only with a "yes" or a "no." A tourist comes to a fork in a road, where one branch leads to the capital and the other does not. There is no sign indicating which fork to take, but Mr. Zed, who is a resident of Ost, comes along. What single question should the tourist ask Mr. Zed to determine which fork in the road to take?

Find at least two different ways to fill in the ellipses in the set descriptions given. For example, \(\\{2,4, \ldots, 12\\}\) could be written either \(\mid 2 n: 1 \leq n \leq 6\) and \(n \in \mathbb{N})\) or \(\mid n+1: n \in\\{1,3,5,7,11\\}\\}\) (a) \([1,3, \ldots, 31)\) (b) \(\\{1,2, \ldots, 26 \mid\) (c) \(\\{2,5, \ldots, 32\\}\)

Which of the following DNF formulas are satisfiable? If the formula is satisfiable, give an interpretation that satisfies it. If it is not satisfiable, explain why not. (a) \((a \wedge b \wedge c) \vee(c \wedge \neg c \wedge b)\) (b) \((a \wedge b \wedge c \wedge d \wedge \neg b) \vee(c \wedge d \wedge \neg c \wedge e \wedge f)\) (c) \((a \wedge b \wedge c) \vee(\neg a \wedge \neg b \wedge \neg c)\)

Write three descriptions of the elements of the set 12,5,8,11,14\(\\}\)

Find the expression tree for the formula $$ ((p \rightarrow \neg q) \vee q) \rightarrow q $$ Evaluate the expression tree if proposition \(p\) is \(F\) and proposition \(q\) is \(T\).

Find formulas in DNF equivalent to each of the following formulas, and find at least two interpretations that make each formula satisfiable: (a) \(((p \rightarrow q) \rightarrow r) \rightarrow F\) (b) \(\neg(p \leftrightarrow q) \leftrightarrow r\) (c) \((\neg r) \rightarrow(((p \vee q) \rightarrow r) \rightarrow \neg q)\)

For the following predicates with universal set \(\mathbb{R}\), state the meaning of the predicate in a sentence. If it is false, give an example to show why. (Example: \(\forall x(\exists y(xz \wedge z>y))))\) (h) \(\forall x(\forall y(\forall z)(x>y \wedge y>z) \rightarrow x>z))\) )