Let S = {0, 1}, and define operations + and on S by the following tables: + 0 1 0 0 1 1

In 1–3 assume that B is a Boolean algebra with operations + and \(\cdot\). Give the reasons needed to fill in the blanks in the proofs, but do not use any parts of Theorem 6.4.1 unless they have already been proved. You may use any part of the definition of a Boolean algebra and the results of previous exercises, however. For all a in B, \(a \cdot a=a\). Proof: Let a be any element of B. Then \(a=a \cdot 1\) (a) = \(a \cdot(a+\bar{a})\) (b) = \((a \cdot a)+(a \cdot \bar{a})\) (c) = \((a \cdot a)+0\) (d) = \(a \cdot a\) (e). Text Transcription: cdot a cdot a=a a=a cdot 1 a cdot(a+ bar a) (a cdot a)+(a cdot bar a) (a cdot a)+0 a cdot a

In 1–3 assume that B is a Boolean algebra with operations + and \(\cdot\). Give the reasons needed to fill in the blanks in the proofs, but do not use any parts of Theorem 6.4.1 unless they have already been proved. You may use any part of the definition of a Boolean algebra and the results of previous exercises, however. For all a in B, a + 1 = 1. Proof: Let a be any element of B. Then \(a+1=a+(a+\bar{a})\) (a) = \((a+a)+\bar{a}\) (b) = \(a+\bar{a}\) by Example 6.4.2 = 1 (c). Text Transcription: cdot a+1=a+(a+bar a) (a+a)+bar a a+bar a

In 1–3 assume that B is a Boolean algebra with operations + and \(\cdot\). Give the reasons needed to fill in the blanks in the proofs, but do not use any parts of Theorem 6.4.1 unless they have already been proved. You may use any part of the definition of a Boolean algebra and the results of previous exercises, however. For all a and b in B, \((a+b) \cdot a=a\). Proof: Let a and b be any elements of B. Then \((a+b) \cdot a=a \cdot(a+b)\) (a) = \(a \cdot a+a \cdot b\) (b) = \(a+a \cdot b\) (c) = \(a \cdot 1+a \cdot b\) (d) = \(a \cdot(1+b)\) (e) = \(a \cdot(b+1)\) (f) = \(a \cdot 1\) by exercise 2 = a (g). Text Transcription: cdot (a+b) cdot a=a (a+b) cdot a=a cdot(a+b) a cdot a+a cdot b a+a cdot b a cdot 1+a cdot b a cdot(1+b) a cdot(b+1) a cdot 1

In 4–10 assume that B is a Boolean algebra with operations + and \(\cdot\). Prove each statement without using any parts of Theorem 6.4.1 unless they have already been proved. You may use any part of the definition of a Boolean algebra and the results of previous exercises, however. For all a in B, \(a \cdot 0 = 0\). Text Transcription: cdot a cdot 0 = 0

In 4–10 assume that B is a Boolean algebra with operations + and \(\cdot\). Prove each statement without using any parts of Theorem 6.4.1 unless they have already been proved. You may use any part of the definition of a Boolean algebra and the results of previous exercises, however. For all a and b in B, \((a \cdot b) + a = a\). Text Transcription: cdot (a cdot b) + a = a

In 4–10 assume that B is a Boolean algebra with operations + and \(\cdot\). Prove each statement without using any parts of Theorem 6.4.1 unless they have already been proved. You may use any part of the definition of a Boolean algebra and the results of previous exercises, however. a. \(\overline{0}=1\). b. \(\overline{1}=0\) Text Transcription: cdot overline 0=1 overline 1=0

In 4–10 assume that B is a Boolean algebra with operations + and \(\cdot\). Prove each statement without using any parts of Theorem 6.4.1 unless they have already been proved. You may use any part of the definition of a Boolean algebra and the results of previous exercises, however. a. There is only one element of B that is an identity for +. b. There is only one element of B that is an identity for \(\cdot\). Text Transcription: cdot cdot

In 4–10 assume that B is a Boolean algebra with operations + and \(\cdot\). Prove each statement without using any parts of Theorem 6.4.1 unless they have already been proved. You may use any part of the definition of a Boolean algebra and the results of previous exercises, however. For all a and b in B, \(\overline{a \cdot b}=\bar{a}+\bar{b}\). (Hint: Prove that \((a \cdot b)+(\bar{a}+\bar{b})=1\) and that \((a \cdot b) \cdot(\bar{a}+\bar{b})=0\), and use the fact that \(a \cdot b\) has a unique complement.) Text Transcription: cdot overline a cdot b =bar a +bar b (a cdot b)+(bar a+bar b)=1 (a cdot b) cdot(bar a+bar b)=0 a cdot b

In 4–10 assume that B is a Boolean algebra with operations + and \(\cdot\). Prove each statement without using any parts of Theorem 6.4.1 unless they have already been proved. You may use any part of the definition of a Boolean algebra and the results of previous exercises, however. For all a and b in B, \(\overline{a+b}=\bar{a} \cdot \bar{b}\). Text transcription: cdot overline a+b=bar a cdot bar b

In 4–10 assume that B is a Boolean algebra with operations + and \(\cdot\). Prove each statement without using any parts of Theorem 6.4.1 unless they have already been proved. You may use any part of the definition of a Boolean algebra and the results of previous exercises, however. For all x, y, and z in B, if x + y = x + z and \(x \cdot y=x \cdot z\), then y = z. Text Transcription: cdot x cdot y=x cdot z

Let S = {0, 1}, and define operations + and \(\cdot\) on S by the following tables: a. Show that the elements of S satisfy the following properties: (i) the commutative law for + (ii) the commutative law for \(\cdot\) (iii) the associative law for + (iv) the associative law for \(\cdot\) (v) the distributive law for + over \(cdot\) (vi) the distributive law for \(\cdot\) over + b. Show that 0 is an identity element for + and that 1 is an identity element for \(\cdot\). c. Define \(\overline{0}=1\) and \(\overline{1}=0\). Show that for all a in S, a + a = 1 and a ·a = 0. It follows from parts (a)–(c) that S is a Boolean algebra with the operations + and \(\cdot\). Text Transcription: cdot cdot cdot cdot cdot cdot overline 0=1 overline 1=0 cdot

Prove that the associative laws for a Boolean algebra can be omitted from the definition. That is, prove that the associative laws can be derived from the other laws in the definition

In 13–18 determine whether each sentence is a statement. Explain your answers. This sentence is false.

In 13–18 determine whether each sentence is a statement. Explain your answers. If 1 + 1 = 3, then 1 = 0.

In 13–18 determine whether each sentence is a statement. Explain your answers.

In 13–18 determine whether each sentence is a statement. Explain your answers. All positive integers with negative squares are prime.

In 13–18 determine whether each sentence is a statement. Explain your answers. This sentence is false or 1 + 1 = 3.

In 13–18 determine whether each sentence is a statement. Explain your answers. This sentence is false and 1 + 1 = 2.

a. Assuming that the following sentence is a statement, prove that 1 + 1 = 3: If this sentence is true, then 1 + 1 = 3. b. What can you deduce from part (a) about the status of “This sentence is true”? Why? (This example is known as Löb’s paradox.)

The following two sentences were devised by the logician Saul Kripke. While not intrinsically paradoxical, they could be paradoxical under certain circumstances. Describe such circumstances. (i) Most of Nixon’s assertions about Watergate are false. (ii) Everything Jones says about Watergate is true. (Hint: Suppose Nixon says (ii) and the only utterance Jones makes about Watergate is (i).)

Can there exist a computer program that has as output a list of all the computer programs that do not list themselves in their output? Explain your answer.

Can there exist a book that refers to all those books and only those books that do not refer to themselves? Explain your answer

Some English adjectives are descriptive of themselves (for instance, the word polysyllabic is polysyllabic) whereas others are not (for instance, the word monosyllabic is not monosyllabic). The word heterological refers to an adjective that does not describe itself. Is heterological heterological? Explain your answer.

As strange as it may seem, it is possible to give a preciselooking verbal definition of an integer that, in fact, is not a definition at all. The following was devised by an English librarian, G. G. Berry, and reported by Bertrand Russell. Explain how it leads to a contradiction. Let n be the smallest integer not describable in fewer than 12 English words. (Note that the total number of strings consisting of 11 or fewer English words is finite.)

Is there an algorithm which, for a fixed quantity a and any input algorithm X and data set D, can determine whether X prints a when run with data set D? Explain. (This problem is called the printing problem.)

Use a technique similar to that used to derive Russell’s paradox to prove that for any set A, \(\mathscr{P}(A) \nsubseteq A\). Text Transcription: mathscr P(A) nsubseteq A