Chapter 13

Write the following Boolean expression in the notation of logic design. $$ \left(x_{1} \wedge \overline{x_{2}}\right) \vee\left(x_{1} \wedge x_{2}\right) \vee\left(\overline{x_{1}} \wedge x_{2}\right) $$

Consider the Boolean expression \(f\left(x_{1}, x_{2}, x_{3}\right)=\left(\overline{x_{3}} \wedge x_{2}\right) \vee\left(\overline{x_{1}} \wedge x_{3}\right) \vee\) \(\left(x_{2} \wedge x_{3}\right)\) on \(\left[B_{2}^{3} ; V, \wedge,-\right]\) (a) Simplify this expression using basic Boolean algebra laws. (b) Write this expression in minterm normal form. (c) Write out the table for the given function defined by \(f\) and compare it to the tables of the functions in parts a and \(\mathrm{b}\). (d) How many possible different functions in three variables on \(\left[B_{2} ; V_{1} \wedge_{1}-\right]\) are there?

Let \(\left[B ; V_{1} \wedge_{+}-\right]\) be a Boolean algebra of order \(4,\) and let \(f\) be a Boolean function of two variables on \(B\). (a) How many elements are there in the domain of \(\mathrm{f?}\) (b) How many different Boolean functions are there of two, variables? Three variables? (c) Determine the minterm normal form of \(f\left(x_{1}, x_{2}\right)=x_{1} \vee x_{2}\). (d) If \(B=\\{0, a, b, 1\\},\) define a function from \(B^{2}\) into \(B\) that is not a Boolean function.

(a) State the commutative laws, associative laws, idempotent laws, and absorption laws for lattices. (b) Prove laws you stated.

Give an example of a Boolean algebra of order 16 whose elements are certain subsets of the set {1,2,3,4,5,6,7}

Let \(A=\\{a, b\\}\) and \(B=\mathcal{P}(A)\). (a) Prove that \(\left[B ; \cup, \cap,^{c}\right]\) is a Boolean algebra. (b) Write out the operation tables for the Boolean algebra.

Corollary 13.4.7 implies that there do not exist Boolean algebras of orders \(3,5,6,7,9,\) etc. (orders different from \(\left.2^{n}\right)\). Without this corollary, directly show that we cannot have a Boolean algebra of order 3 . Hint. Assume that \([B ; \vee, \wedge,-]\) is a Boolean algebra of order 3 where \(B=\\{0, x, 1\\}\) and show that this cannot happen by investigating the possibilities for its operation tables.

It can be shown that the following statement, \(S,\) holds for any Boolean algebra \([B ; \vee, \wedge,-]:(a \wedge b)=a\) if and only if \(a \leq b\) (a) Write the dual, \(S^{*}\), of the statement \(S\). (b) Write the statement \(S\) and its dual, \(S^{*}\), in the language of sets. (c) Are the statements in part b true for all sets? (d) Write the statement \(S\) and its dual, \(S^{*}\), in the language of logic. (e) Are the statements in part d true for all propositions?

(a) There are many different, yet isomorphic, Boolean algebras with two elements. Describe one such Boolean algebra that is derived from a power set, \(\mathcal{P}(A),\) under \(\subseteq .\) Describe a second that is described from \(D_{n},\) for some \(n \in P,\) under "divides." (b) Since the elements of a two-element Boolean algebra must be the greatest and least elements, 1 and \(0,\) the tables for the operations on \\{0,1\\} are determined by the Boolean algebra laws. Write out the operation tables for \([\\{0,1\\} ; \vee, \wedge,-]\)

Consider the Boolean function \(f\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=x_{1}+\left(x_{2} \cdot\left(\overline{x_{1}}+x_{4}\right)+x_{3} \cdot\left(\overline{x_{2}}+\overline{x_{4}}\right)\right)\). (a) Simplify \(f\) algebraically. (b) Draw the gate diagram based on the simplified version of \(f\).

We naturally order the numbers in \(A_{m}=\\{1,2, \ldots, m\\}\) with "less than or equal to," which is a partial ordering. We define an ordering, \(\preceq\) on the elements of \(A_{m} \times A_{n}\) by $$ (a, b) \preceq\left(a^{\prime}, b^{\prime}\right) \Leftrightarrow a \leq a^{\prime} \text { and } b \leq b^{\prime} $$ (a) Prove that \(\preceq\) is a partial ordering on \(A_{m} \times A_{n}\). (b) Draw the ordering diagrams for \(\preceq\) on \(A_{2} \times A_{2}, A_{2} \times A_{3},\) and \(A_{3} \times A_{3}\). (c) In general, how does one determine the least upper bound and greatest lower bound of two elements of \(A_{m} \times A_{n},(a, b)\) and \(\left(a^{\prime}, b^{\prime}\right) ?\) (d) Are there least and/or greatest elements in \(A_{m} \times A_{n} ?\)

State the dual of: (a) \(a \vee(b \wedge a)=a\). (b) \(a \vee(\overline{(\bar{b} \vee a) \wedge b})=1\). (c) \((\overline{a \wedge \bar{b}}) \wedge b=a \vee b\).

Let \([L ; \vee, \wedge]\) be a lattice based on a partial ordering \(\preceq\). Prove that if \(a, b, c \in L\) (a) \(a \preceq a \vee b\). (b) \(a \wedge b \preceq a\). (c) \(b \preceq a\) and \(c \preceq a \Rightarrow b \vee c \preceq a\).

Find a Boolean algebra with a countably infinite number of elements.

Draw a logic circuit using only AND, OR and NOT gates that realizes an XOR gate.

Formulate a definition for isomorphic Boolean algebras.

Draw a logic circuit using only AND, OR and NOT gates that realizes the Boolean function on three variables that returns 1 if the majority of inputs are 1 and 0 otherwise.

Prove if two finite sets \(A_{1}\) and \(A_{2}\) both have \(n\) elements then \(\left[\mathcal{P}\left(A_{1}\right) ; \cup, \cap, c\right]\) is isomorphic to \(\left[\mathcal{P}\left(A_{2}\right) ; \cup, \cap,^{c}\right]\)

Prove an element of a Boolean algebra is an atom if and only if it covers the zero element.