maths.free › Abstract Algebra › 19. Lattices and Boolean Algebras › Lattices and Boolean Algebras: exercises

Lattices and Boolean Algebras: exercises

Lattices and Boolean Algebras: exercises — from Judson, Abstract Algebra: Theory and Applications.

Practice (23)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Draw the lattice diagram for the power set of \(X = \{ a, b, c, d \}\) with the set inclusion relation, \(\subset\).

  2. Draw the diagram for the set of positive integers that are divisors of \(30\). Is this poset a Boolean algebra?

    Odhalte odpověď

    Hint:

  3. Draw a diagram of the lattice of subgroups of \({\mathbb Z}_{12}\).

  4. Let \(B\) be the set of positive integers that are divisors of \(210\). Define an order on \(B\) by \(a \preceq b\) if \(a \mid b\). Prove that \(B\) is a Boolean algebra. Find a set \(X\) such that \(B\) is isomorphic to \({\mathcal P}(X)\).

    Odhalte odpověď

    Hint:

    What are the atoms of \(B\)?

  5. Prove or disprove: \({\mathbb Z}\) is a poset under the relation \(a \preceq b\) if \(a \mid b\).

    Odhalte odpověď

    Hint:

    False.

  6. Draw the switching circuit for each of the following Boolean expressions.

    1. \((a \vee b \vee a') \wedge a\)

    2. \((a \vee b)' \wedge (a \vee b)\)

    3. \(a \vee (a \wedge b)\)

    4. \((c \vee a \vee b) \wedge c' \wedge (a \vee b)'\)

    Odhalte odpověď

    Hint:

    (a) \((a \vee b \vee a') \wedge a\)

    (c) \(a \vee (a \wedge b)\)

  7. Draw a circuit that will be closed exactly when only one of three switches \(a\), \(b\), and \(c\) are closed.

  8. Prove or disprove that the two circuits shown are equivalent.

    Odhalte odpověď

    Hint:

    Not equivalent.

  9. Let \(X\) be a finite set containing \(n\) elements. Prove that \(|{\cal P}(X)| = 2^n\). Conclude that the order of any finite Boolean algebra must be \(2^n\) for some \(n \in {\mathbb N}\).

  10. For each of the following circuits, write a Boolean expression. If the circuit can be replaced by one with fewer switches, give the Boolean expression and draw a diagram for the new circuit.

    Odhalte odpověď

    Hint:

    (a) \(a' \wedge [(a \wedge b') \vee b] = a \wedge (a \vee b)\).

  11. Prove or disprove: The set of all nonzero integers is a lattice, where \(a \preceq b\) is defined by \(a \mid b\).

  12. Let \(L\) be a nonempty set with two binary operations \(\vee\) and \(\wedge\) satisfying the commutative, associative, idempotent, and absorption laws. We can define a partial order on \(L\), as in , by \(a \preceq b\) if \(a \vee b = b\). Prove that the greatest lower bound of \(a\) and \(b\) is \(a \wedge b\).

  13. Let \(G\) be a group and \(X\) be the set of subgroups of \(G\) ordered by set-theoretic inclusion. If \(H\) and \(K\) are subgroups of \(G\), show that the least upper bound of \(H\) and \(K\) is the subgroup generated by \(H \cup K\).

  14. Let \(R\) be a ring and suppose that \(X\) is the set of ideals of \(R\). Show that \(X\) is a poset ordered by set-theoretic inclusion, \(\subset\). Define the meet of two ideals \(I\) and \(J\) in \(X\) by \(I \cap J\) and the join of \(I\) and \(J\) by \(I + J\). Prove that the set of ideals of \(R\) is a lattice under these operations.

    Odhalte odpověď

    Hint:

    Let \(I, J\) be ideals in \(R\). We need to show that \(I + J = \{ r + s : r \in I \text{ and } s \in J \}\) is the smallest ideal in \(R\) containing both \(I\) and \(J\). If \(r_1, r_2 \in I\) and \(s_1, s_2 \in J\), then \((r_1 + s_1) + (r_2 + s_2) = (r_1 + r_2) +(s_1 + s_2)\) is in \(I + J\). For \(a \in R\), \(a(r_1 + s_1) = ar_1 + as_1 \in I + J\); hence, \(I + J\) is an ideal in \(R\).

  15. Let \(B\) be a Boolean algebra. Prove each of the following identities.

    1. \(a \vee I = I\) and \(a \wedge O = O\) for all \(a \in B\).

    2. If \(a \vee b = I\) and \(a \wedge b = O\), then \(b = a'\).

    3. \((a')'=a\) for all \(a \in B\).

    4. \(I' = O\) and \(O' = I\).

    5. \((a \vee b)' = a' \wedge b'\) and \((a \wedge b)' = a' \vee b'\) (De Morgan's laws).

  16. By drawing the appropriate diagrams, complete the proof of to show that the switching functions form a Boolean algebra.

  17. Let \(B\) be a Boolean algebra. Define binary operations \(+\) and \(\cdot\) on \(B\) by \[\begin{aligned}a + b & = (a \wedge b') \vee (a' \wedge b) \\ a \cdot b & = a \wedge b\end{aligned}\]. Prove that \(B\) is a commutative ring under these operations satisfying \(a^2 = a\) for all \(a \in B\).

  18. Let \(X\) be a poset such that for every \(a\) and \(b\) in \(X\), either \(a \preceq b\) or \(b \preceq a\). Then \(X\) is said to be a totally ordered set.

    1. Is \(a \mid b\) a total order on \({\mathbb N}\)?

    2. Prove that \({\mathbb N}\), \({\mathbb Z}\), \({\mathbb Q}\), and \({\mathbb R}\) are totally ordered sets under the usual ordering \(\leq\).

    Odhalte odpověď

    Hint:

    (a) No.

  19. Let \(X\) and \(Y\) be posets. A map \(\phi : X \rightarrow Y\) is order-preserving if \(a \preceq b\) implies that \(\phi(a) \preceq \phi(b)\). Let \(L\) and \(M\) be lattices. A map \(\psi: L \rightarrow M\) is a lattice homomorphism if \(\psi( a \vee b ) = \psi(a) \vee \psi(b)\) and \(\psi( a \wedge b ) = \psi(a) \wedge \psi(b)\). Show that every lattice homomorphism is order-preserving, but that it is not the case that every order-preserving homomorphism is a lattice homomorphism.

  20. Let \(B\) be a Boolean algebra. Prove that \(a = b\) if and only if \((a \wedge b') \vee ( a' \wedge b) = O\) for \(a, b \in B\).

    Odhalte odpověď

    Hint:

    \(( \Rightarrow)\). \(a = b \Rightarrow (a \wedge b') \vee (a' \wedge b) = (a \wedge a') \vee (a' \wedge a) = O \vee O = O\). \(( \Leftarrow)\). \(( a \wedge b') \vee (a' \wedge b) = O \Rightarrow a \vee b = (a \vee a) \vee b = a \vee (a \vee b) = a \vee [I \wedge (a \vee b)] = a \vee [(a \vee a') \wedge (a \vee b)] = [a \vee (a \wedge b')] \vee [a \vee (a' \wedge b)] = a \vee [(a \wedge b') \vee (a' \wedge b)] = a \vee 0 = a\). A symmetric argument shows that \(a \vee b = b\).

  21. Let \(B\) be a Boolean algebra. Prove that \(a = O\) if and only if \((a \wedge b') \vee ( a' \wedge b) = b\) for all \(b \in B\).

  22. Let \(L\) and \(M\) be lattices. Define an order relation on \(L \times M\) by \(( a, b) \preceq (c, d)\) if \(a \preceq c\) and \(b \preceq d\). Show that \(L \times M\) is a lattice under this partial order.

  23. A Boolean or switching function on \(n\) variables is a map \(f : \{O, I\}^n \rightarrow \{ 0, I\}\). A Boolean polynomial is a special type of Boolean function: it is any type of Boolean expression formed from a finite combination of variables \(x_1, \ldots, x_n\) together with \(O\) and \(I\), using the operations \(\vee\), \(\wedge\), and \('\). The values of the functions are defined in . Write a program to evaluate Boolean polynomials.

    \(x\)\(y\)\(x'\)\(x \vee y\)\(x \wedge y\)
    \(0\)\(0\)\(1\)\(0\)\(0\)
    \(0\)\(1\)\(1\)\(1\)\(0\)
    \(1\)\(0\)\(0\)\(1\)\(0\)
    \(1\)\(1\)\(0\)\(1\)\(1\)

Symbols used here

a \mid b,\ \gcd(a,b)
divides, greatest common divisor
b is a multiple of a; the largest number dividing both.
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow
not, and, or, implies, iff
Logical connectives.
\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}
number sets
Naturals, integers, rationals, reals, complex numbers.
\blacksquare\ \text{or}\ \square
end of proof (halmos)
Marks the point where the statement has been established.
a \equiv b \pmod n
congruent modulo n
n divides a − b; a and b have the same remainder.
(G, \cdot),\ e,\ g^{-1}
group, identity, inverse
A set with an operation; the do-nothing element; the element that undoes g.
G \cong H,\ G / N
isomorphic, quotient group
Same structure; the group of cosets of a normal subgroup N.
\mathbb{Z}/n\mathbb{Z},\ \mathbb{Z}_n
integers modulo n
The remainders 0…n−1 with clock arithmetic.
\operatorname{Hom}(A, B),\ f \circ g
arrows from A to B, composition
The set of morphisms; do g then f.

Questions people ask

What is a group, in plain words?

A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group — that is where the idea came from.

What is the difference between a ring and a field?

A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.

Zkuste si vlastní.

Parts of this page are adapted from Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Condensed and re-explained here; errors are ours.

Více v Abstract Algebra

GroupsSubgroups, cosets and Lagrange's theoremCyclic groups and permutation groupsHomomorphisms, normal subgroups and quotient groupsRings and fieldsGalois theory: why the quintic has no formula