Chapter 1

Determine all the partial orders and their Hasse diagrams on the set \(L=\) \(\\{a, b, c\\} .\) Which of them are chains?

Prove the generalized distributive inequality for lattices: $$ y \wedge\left(\bigvee_{i=1}^{n} x_{i}\right) \geq \bigvee_{i=1}^{n}\left(y \wedge x_{1}\right) $$

Prove that in a finite Boolean algebra every ideal is a principal ideal.

Is \(x_{1} x_{2} x_{3}+x_{1} x_{2}^{\prime} x_{3}+x_{1}^{\prime} x_{2} x_{3}+x_{1}^{\prime} x_{2}^{\prime} x_{3}^{\prime}+x_{1}^{\prime} x_{3}\) irredundant?

Give an example of a poset which has exactly one maximal element but does not have a greatest element.

Let \(L\) be a distributive lattice with 0 and 1. Prove: If \(a\) has a complement \(a^{\prime}\), then $$ a \vee\left(a^{\prime} \wedge b\right)=a \vee b . $$

How many Boolean algebras are there with four elements \(0,1, a\), and \(b ?\)

Let \(B\) be a Boolean algebra. Prove: \(F\) is a filter in \(B\) if and only if \(F^{\prime}:=\) \(\left.\left|x^{\prime}\right| x \in F\right\\}\) is an ideal of \(B\).

Find all prime implicants of \(x y^{\prime} z+x^{\prime} y z^{\prime}+x y z^{\prime}+x y z\) and form the corresponding prime implicant table.

Let \((\mathbb{R}, \leq)\) be the poset of all real numbers and let \(A=\left[x \in \mathbb{R} \mid x^{3}<3\right\\} .\) Is there an upper bound (or lower bound) or a supremum (or infimum) of \(A ?\)

Show that the direct product of Boolean algebras is again a Boolean algebra.

Find all ideals and filters of the Boolean algebra \(\mathcal{P}(\\{1,2,3\\})\). Which of the filters are ultrafilters? Are they fixed?

Find three prime implicants of \(x y+x y^{\prime} z+x^{\prime} y^{\prime} z\).

Show that the set \(N\), ordered by divisibility, is a distributive lattice. Is it complemented? Consider the same questions for \(\mathbb{N}_{0}\).

Prove: A nonempty subset \(I\) of a Boolean algebra \(B\) is an ideal if and only if $$ i \in I, j \in I \Longleftrightarrow i+j \in I $$

Use the Quine-McCluskey method to find the minimal form of \(w x^{\prime} y^{\prime} z+\) \(w^{\prime} x y^{\prime} z^{\prime}+w x^{\prime} y^{\prime} z^{\prime}+w^{\prime} x y z+w^{\prime} x^{\prime} y^{\prime} z^{\prime}+w x y z+w x^{\prime} y z+w^{\prime} x y z^{\prime}+w^{\prime} x^{\prime} y z^{\prime}\)

Is \(F:=|A \subseteq \mathbb{N}| A\) finite \(\\}\) a sublattice of \(\mathcal{P}(\mathrm{N}) ?\) is \(F\) bounded? Is \(\mathcal{P}(\mathbb{N})\) bounded?

Let \(S\) be an arbitrary set and \(D\) a distributive lattice. Show that the set of all functions from \(S\) to \(D\) is a distributive lattice, where \(f \leq g\) means \(f(x) \leq g(x)\) for all \(x\).

Demonstrate in detail how an interval \([a, b]\) in a Boolean algebra \(B\) can be made into a Boolean algebra.

Are \(x_{1}\left(x_{2}+x_{3}\right)^{\prime}+x_{1}^{\prime}+x_{3}^{\prime}\) and \(\left(x_{1} x_{3}\right)^{\prime}\) equivalent?

Let \(S\) be a subset of a Boolean algebra \(B\). Prove: (i) The intersection \(J\) of all ideals \(I\) containing \(S\) is an ideal containing \(S\). (ii) \(J\) in (i) consists of all elements of the form $$ b_{1} s_{1}+\cdots+b_{n} s_{n}, \quad n \geq 1 $$ where \(s_{1}, \ldots, s_{n} \in S\), and \(b_{1}, \ldots, b_{n}\) are arbitrary elements of \(B\). (iii) \(J\) in (i) consists of the set \(A\) of all \(a\) such that $$ a \leq s_{1}+\cdots+s_{n}, \quad n \geq 1 $$ where \(s_{1}, \ldots, s_{n}\) are arbitrary elements of \(S\). (iv) \(J\) in (i) is a proper ideal of \(B\) if and only if $$ s_{1}+\cdots+s_{n} \neq 1 $$ for all \(s_{1}, \ldots, s_{n} \in S\)

Determine the prime implicants of \(f=w^{\prime} x^{\prime} y^{\prime} z^{\prime}+w^{\prime} x^{\prime} y z^{\prime}+w^{\prime} x y^{\prime} z+w^{\prime} x y z^{\prime}+\) \(w^{\prime} x y z+w x^{\prime} y^{\prime} z^{\prime}+w x^{\prime} y z+w x y^{\prime} z+w x y z+w x y z^{\prime}\) by using Quine's proce- dure. Complete the minimizing process of \(f\) by using the Quine-McCluskey method.

Prove that any finite lattice is bounded. Find a lattice without a zero and a unit element.

Show that \((B, g c d, 1 c m)\) is a Boolean algebra if \(B\) is the set of all positive divisors of 110 .

Simplify the following Boolean polynomials: (i) \(x y+x y^{\prime}+x^{\prime} y\) (ii) \(x y^{\prime}+x(y z)^{\prime}+z\).

Show that all ultrafilters in a finite Boolean algebra are fixed.

Find the disjunctive normal form of \(f\) and simplify it: $$ f=x^{\prime} y+x^{\prime} y^{\prime} z+x y^{\prime} z^{\prime}+x y^{\prime} z $$

More generally, prove that in a lattice \((L, \leq)\) every finite nonempty subset \(S\) has a least upper bound and a greatest lower bound.

Show that sublattices, homomorphic images, and direct products of distributive lattices are again distributive.

Show that \((\\{1,2,3,6,9,18\\}\), gcd, \(1 \mathrm{~cm}\) ) does not form a Boolean algebra for the set of positive divisors of 18 .

Let \(f: \mathbb{B}^{3} \rightarrow \mathbb{B}\) have the value 1 precisely at the arguments \((0,0,0),(0,1,0)\), \((0,1,1),(1,0,0) .\) Find a Boolean polynomial \(p\) with \(\bar{p}=f\) and try to simplify \(p\).

By use of Zorn's Lemma, prove that each proper filter in a Boolean algebra \(B\) is contained in an ultrafilter.

Use a Karnaugh diagram to simplify: (a) \(x_{1} x_{2} x_{3}^{\prime}+x_{1}^{\prime} x_{2} x_{3}^{\prime}+\left(x_{1}+x_{2}^{\prime} x_{3}^{\prime}\right)^{\prime}\left(x_{1}+x_{2}+x_{3}\right)^{\prime}+x_{3}\left(x_{1}^{\prime}+x_{2}\right)\) (b) \(x_{1} x_{2} x_{3}+x_{2} x_{3} x_{4}+x_{1}^{\prime} x_{2} x_{4}+x_{1}^{\prime} x_{2} x_{3} x_{4}^{\prime}+x_{1}^{\prime} x_{2}^{\prime} x_{4}^{\prime}\)

Let \(\mathbb{C}\) be the set of complex numbers \(z=x+i y\) where \(x\) and \(y\) are in \(R\). Define a partial order \(\subseteq\) on \(\mathrm{C}\) as in Equation \(1.2 \mathrm{by}: x_{1}+\mathrm{r}_{1} \subseteq x_{2}+\mathrm{iy}_{2}\) if and only if \(x_{1} \leq x_{2}\) and \(y_{1} \leq y_{2}\). Is this a linear order? Is there a minimal or a maximal element in \((\mathbb{C}, \subseteq) ?\) How does \(\subseteq\) compare with the lexicographic order \(\leq\) defined by \(x_{1}+u y_{1} \leq x_{2}+i y_{2}\) if and only if \(x_{1}

Prove that the lattice of all positive divisors of \(n \in \mathbb{N}\) is a Boolean algebra with respect to \(1 \mathrm{~cm}\) and gcd if and only if the prime factor decomposition of \(n\) does not contain any squares.

Find the disjunctive normal form of: (i) \(x_{1}\left(x_{2}+x_{3}\right)^{\prime}+\left(x_{1} x_{2}+x_{3}^{\prime}\right) x_{1} ;\) (ii) \(\left(\left(x_{2}+x_{1} x_{3}\right)\left(x_{1}+x_{3}\right) x_{2}\right)^{\prime}\).

Find the minimal forms for \(x_{3}\left(x_{2}+x_{4}\right)+x_{2} x_{4}^{\prime}+x_{2}^{\prime} x_{3}^{\prime} x_{4}\) using the Karnaugh diagrams.

An isomorphism of posets is a bijective order-homomorphism, whose inverse is also an order-homomorphism. Prove: If \(f\) is an isomorphism of a poset \(L\) onto a poset \(M\), and if \(L\) is a lattice, then \(M\) is also a lattice, and \(f\) is an isomorphism of the lattices.

Let \(B=\\{X \subseteq \mathbb{N} \mid X\) is finite or its complement in \(\mathbb{N}\) is finite\\}. Show that \(B\) is a Boolean subalgebra of \(P(\mathbb{N})\) which cannot be Boolean isomorphic to some \(\mathcal{P}(M)\).

Find the conjunctive normal form of \(\left(x_{1}+x_{2}+x_{3}\right)\left(x_{1} x_{2}+x_{1}^{\prime} x_{3}\right)^{\prime} .\)

Show that the equation \(a+x=1\) in a Boolean algebra \(B\) has the general solution \(x=a^{\prime}+u\), where \(u\) is an arbitrary element in \(B\).

Let ( \(C[a, b]\), max, min) be the lattice of continuous real-valued functions on a closed interval \([a, b]\) and let \(D[a, b]\) be the set of all differentiable functions on \([a, b]\). Show by example that \(D[a, b]\) is not a sublattice of \(C[a, b]\).

Let \(L\) be the lattice \(\left(\mathrm{N}_{0}, \mathrm{gcd}, \mathrm{lcm}\right) .\) Determine the atoms in \(L .\) Which elements are join- irreducible?

Consider the set \(\mathcal{M}\) of \(n \times n\) matrices \(\mathbf{X}=\left(x_{0}\right)\) whose entries \(x_{y}\) belong to a Boolean algebra \(B=\left(B, \wedge, v, 0,1,^{\prime}\right)\). Define two operations on \(\mathcal{M}\) : $$ \mathbf{X} \vee \mathbf{Y}:=\left(x_{\eta} \vee y_{y}\right), \quad \mathbf{X} \wedge \mathbf{Y}:=\left(x_{i j} \wedge y_{0}\right) $$ Show that \(\mathcal{M}\) is a Boolean algebra. Furthermore, let $$ \mathbf{I}=\left(\begin{array}{cccc} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{array}\right) $$ and consider the subset \(\mathcal{N}\) of \(\mathcal{M}\) consisting of all \(\mathbf{X} \in \mathcal{M}\) with the property \(\mathbf{X} \geq \mathbf{1}\). (Here \(\mathbf{X} \geq \mathbf{Y} \Longleftrightarrow x_{v} \geq y_{v}\) for all \(i, j\).) Show that \(\mathcal{N}\) is a sublattice of \(\mathcal{M}\).

Let \(f\) be a monomorphism from the lattice \(L\) into the lattice \(M\). Show that \(L\) is isomorphic to a sublattice of \(\underline{M}\).

Show by example that relative complements are not always unique.

If \(L\) and \(M\) are isomorphic lattices and \(L\) is distributive (complemented, sectionally complemented), show that this applies to \(M\) as well.

Is every ideal (filter) of \(B\) a sublattice of \(B ?\) Is it a Boolean subalgebra?

Prove: \(\ln\) any lattice \(L\), we have $$ ((x \wedge y) \vee(x \wedge z)) \wedge((x \wedge y) \vee(y \wedge z))=x \wedge y \quad \text { for all } x, y, z \in L $$

Let \(C_{1}\) and \(C_{2}\) be the finite chains \([0,1,2\\}\) and \([0,1\\}\), respectively. Draw the Hasse diagram of the product lattice \(C_{1} \times C_{2} \times C_{2}\).