Chapter 2

In Exercises \(34-37, n\) denotes a positive integer less than \(10 .\) Rewrite each set using the listing method. \(\\{n | n \text { is divisible by } 2 \text { or } 3\\}\)

According to a survey among 160 college students, 95 students take a course in English, 72 take a course in French, 67 take a course in German, 35 take a course in English and in French, 37 take a course in French and in German, 40 take a course in German and in English, and 25 take a course in all three languages. Find the number of students in the survey who take a course in: Neither English, French, nor German.

Mark each as true or false, where \(A, B,\) and \(C\) are arbitrary sets and \(U\) the universal set. $$A \subseteq A \cap B$$

\(n\) denotes a positive integer less than \(10 .\) Rewrite each set using the listing method. \(\\{n | n \text { is divisible by } 2 \text { or } 3\\}\)

Find the family of subsets of each set that do not contain consecutive integers. $$\\{1,2\\}$$

A recent survey by the MAD corporation indicates that of the 700 families interviewed, 220 own a television set but no stereo, 200 own a stereo but no camera, 170 own a camera but no television set, 80 own a television set and a stereo but no camera, 80 own a stereo and a camera but no television set, 70 own a camera and a television set but no stereo, and 50 do not have any of these. Find the number of families with: Exactly one of the items.

Mark each as true or false, where \(A, B,\) and \(C\) are arbitrary sets and \(U\) the universal set. $$B \cap(A-B)=\varnothing$$

Find the family of subsets of each set that do not contain consecutive integers. $$\\{1,2,3\\}$$

A recent survey by the MAD corporation indicates that of the 700 families interviewed, 220 own a television set but no stereo, 200 own a stereo but no camera, 170 own a camera but no television set, 80 own a television set and a stereo but no camera, 80 own a stereo and a camera but no television set, 70 own a camera and a television set but no stereo, and 50 do not have any of these. Find the number of families with: Exactly two of the items.

Let \(a_{n}\) denote the number of subsets of the set \(S=\\{1,2, \ldots, n\\}\) that do not contain consecutive integers, where \(n \geq 1 .\) Find \(a_{3}\) and \(a_{4}\).

A recent survey by the MAD corporation indicates that of the 700 families interviewed, 220 own a television set but no stereo, 200 own a stereo but no camera, 170 own a camera but no television set, 80 own a television set and a stereo but no camera, 80 own a stereo and a camera but no television set, 70 own a camera and a television set but no stereo, and 50 do not have any of these. Find the number of families with: At least one of the items.

In Exercises \(41-46,\) a language \(L\) over \(\Sigma=\\{a, b\\}\) is given. Find five words in each language. \(L=\left|x \in \Sigma^{*}\right| x\) begins with and ends in \(b .1\)

A recent survey by the MAD corporation indicates that of the 700 families interviewed, 220 own a television set but no stereo, 200 own a stereo but no camera, 170 own a camera but no television set, 80 own a television set and a stereo but no camera, 80 own a stereo and a camera but no television set, 70 own a camera and a television set but no stereo, and 50 do not have any of these. Find the number of families with: All of the items.

a language \(L\) over \(\Sigma=\\{a, b\\}\) is given. Find five words in each language. \(L=\left\\{x \in \Sigma^{*} | x \text { begins with and ends in } b .\right\\}\)

In Exercises \(41-46,\) a language \(L\) over \(\Sigma=\\{a, b\\}\) is given. Find five words in each language. \(L=\left\\{x \in \Sigma^{*} | x \text { contains exactly one } b .1\right.\)

a language \(L\) over \(\Sigma=\\{a, b\\}\) is given. Find five words in each language. \(L=\left\\{x \in \Sigma^{*} | x \text { contains exactly one } b .\right\\}\)

In Exercises \(41-46,\) a language \(L\) over \(\Sigma=\\{a, b\\}\) is given. Find five words in each language. \(L=\left|x \in \Sigma^{*}\right| x\) contains an even number of \(a^{\prime} 8.1\)

Determine if each is a partition of the set \(\\{a, \ldots, z, 0, \ldots, 9\\}.\) $$\\{\\{a, \ldots, z\\},\\{0, \ldots, 9\\}, \emptyset\\}$$

a language \(L\) over \(\Sigma=\\{a, b\\}\) is given. Find five words in each language. \(L=\left\\{x \in \Sigma^{*} | x \text { contains an even number of } a \text { 's. }\right\\}\)

In Exercises \(41-46,\) a language \(L\) over \(\Sigma=\\{a, b\\}\) is given. Find five words in each language. \(L=\left\\{x \in \Sigma^{*} | x \text { contains an even number of } a^{\prime} \text { s followed by an odd }\right.\) number of \(b^{\prime} s . \\}\)

Determine if each is a partition of the set \(\\{a, \ldots, z, 0, \ldots, 9\\}.\) $$\\{\\{a, \ldots, 1\\},\\{n, \ldots, t\\},\\{u, \ldots, z\\},\\{0, \ldots, 9\\}\\}$$

Determine if each is a partition of the set \(\\{a, \ldots, z, 0, \ldots, 9\\}.\) $$\\{\\{a, \ldots, u\\},\\{v, \ldots, z\\},\\{0,3\\},\\{1,2,4, \ldots, 9\\}$$

Prove each, where \(A, B,\) and \(C\) are any sets. $$\left(A^{\prime}\right)^{\prime}=A$$

Prove each, where \(A, B,\) and \(C\) are any sets. $$A \cup(A \cap B)=A$$

Let \(A, B,\) and \(C\) be subsets of a finite set \(U .\) Derive a formula for each. \(\left|A^{\prime} \cap B^{\prime}\right|\)

Prove each, where \(A, B,\) and \(C\) are any sets. $$A \cap(A \cup B)=A$$

Let \(A, B,\) and \(C\) be subsets of a finite set \(U .\) Derive a formula for each. \(\left|A^{\prime} \cap B^{\prime} \cap C^{\prime}\right|\)

Arrange the binary words of the given length in increasing order of magnitude. Length two.

Arrange the binary words of the given length in increasing order of magnitude. Length three.

State the inclusion-exclusion principle for four finite sets \(A_{t}, 1 \leq\) \(i \leq 4 .\) (The formula contains 15 terms.)

A ternary word is a word over the alphabet \(\\{0,1,2\\} .\) Arrange the ternary words of the given length in increasing order of magnitude. Length one.

State the inclusion-exclusion principle for \(n\) finite sets \(A_{i}, 1 \leq i \leq n\).

The empty set is a subset of every set. (Hint: Consider the implication \(x \in \emptyset \rightarrow x \in A .\) )

Prove each, where \(A, B,\) and \(C\) are any sets. $$A \oplus B=B \oplus A$$

Prove each, where \(A, B,\) and \(C\) are any sets. $$A-B=A \cap B^{\prime}$$

The empty set is unique. (Hint: Assume there are two empty sets, \(\emptyset_{1}\) and \(\emptyset_{2}\). Then use Exercise 53.)

Prove each, where \(A, B,\) and \(C\) are any sets. $$(A \cup B \cup C)^{\prime}=A^{\prime} \cap B^{\prime} \cap C^{\prime}$$

Let \(A, B,\) and \(C\) be arbitrary sets such that \(A \subseteq B\) and \(B \subseteq C .\) Then \(A \subseteq C\) (transitive property)

If \(\Sigma\) is a nonempty alphabet, then \(\Sigma^{*}\) is infinite. (Hint: Assume \(\Sigma^{*}\) is finite. since \(\Sigma \neq \emptyset,\) it contains an element \(a\) Let \(x \in \Sigma^{*}\) with largest length. Now consider \(x a .\) )

Prove each, where \(A, B,\) and \(C\) are any sets. $$(A \cap B \cap C)^{\prime}=A^{\prime} \cup B^{\prime} \cup C^{\prime}$$

Simplify each set expression. $$A \cap(A-B)$$

Simplify each set expression. $$\left(A-A^{\prime}\right) \cup(B-A)$$

Simplify each set expression. $$\left(A-B^{\prime}\right)-\left(B-A^{\prime}\right)$$

Simplify each set expression. $$(A \cup B) \cup\left(A \cap B^{\prime}\right)^{\prime}$$

Simplify each set expression. $$(A \cup B)-(A \cap B)^{\prime}$$

Simplify each set expression. $$(A \cup B)^{\prime} \cap\left(A \cap B^{\prime}\right)$$

Simplify each set expression. $$ (A \cap B)^{\prime} \cup\left(A \cup B^{\prime}\right) $$

Simplify each set expression. $$\left(A \cup B^{\prime}\right)^{\prime} \cap\left(A^{\prime} \cap B\right)$$

Simplify each set expression. $$ \left(A \cup B^{\prime}\right)^{\prime} \cap\left(A^{\prime} \cap B\right) $$

Simplify each set expression. $$(A \cap B)^{\prime} \cup\left(A \cup B^{\prime}\right)$$