Self-Assessment Quiz: Partial Orders, Lattices, and Boolean Algebra

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Question 1

A partial order is a relation that is:

A) reflexive, symmetric, and transitive B) reflexive, antisymmetric, and transitive C) symmetric, antisymmetric, and transitive D) irreflexive, antisymmetric, and transitive

Question 2

Which single property does an equivalence relation have that a partial order replaces?

A) reflexivity (replaced by irreflexivity) B) transitivity (replaced by antisymmetry) C) symmetry (replaced by antisymmetry) D) antisymmetry (replaced by symmetry)

Question 3

The relation $\mid$ (divides) is a partial order on:

A) $\mathbb{Z}$ B) $\mathbb{Z}^{+}$ C) $\mathbb{Q}$ D) any set of integers

Question 4

In a Hasse diagram, we draw an edge from $a$ up to $b$ exactly when:

A) $a \preceq b$ B) $b$ covers $a$ (i.e. $a \prec b$ with nothing strictly between) C) $a$ and $b$ are incomparable D) $a \prec b$, for every such pair

Question 5 (True/False, justify)

True or false: In the divisors-of-12 poset $(\{1,2,3,4,6,12\}, \mid)$, there is an edge drawn from 1 to 12 in the Hasse diagram. Justify in one sentence.

Question 6

"Maximal" and "greatest" differ because:

A) they are synonyms; the distinction is purely historical B) "maximal" means nothing is above it; "greatest" means it is above everything C) "greatest" means nothing is above it; "maximal" means it is above everything D) a poset can have many greatest elements but only one maximal element

Question 7

A total order (linear order) is a partial order in which:

A) every element has a cover B) there is a greatest and a least element C) every two elements are comparable D) every two elements are incomparable

Question 8

In a poset, an antichain is a subset in which:

A) every two elements are comparable B) every two distinct elements are incomparable C) there is a unique minimal element D) the order is total

Question 9

In the divisors-of-12 poset, which set is a chain of length 4?

A) $\{2, 3, 4, 6\}$ B) $\{1, 2, 4, 12\}$ C) $\{4, 6\}$ D) $\{1, 2, 3\}$

Question 10

A topological sort of a finite poset is:

A) a way to make every pair of elements incomparable B) a total order consistent with $\preceq$ (a linear extension) C) the list of all maximal elements D) the transitive closure of the order

Question 11

The proof that every finite poset has a topological sort rests on the fact that every finite nonempty poset has:

A) a greatest element B) a unique chain C) a minimal element D) an antichain of size 2

Question 12 (True/False, justify)

True or false: A topological sort of a poset is always unique. Justify in one sentence.

Question 13

A finite poset corresponds to a directed acyclic graph (DAG). Topological sort fails (no valid order exists) exactly when:

A) the poset has more than one minimal element B) the poset is not a lattice C) the graph contains a cycle (a circular dependency) D) the graph is disconnected

Question 14

The join $a \vee b$ in a poset is the:

A) greatest lower bound of $a$ and $b$ B) least upper bound of $a$ and $b$ C) any common upper bound D) the larger of $a$ and $b$ only when they are comparable

Question 15

In $(\mathcal{P}(S), \subseteq)$, the join and meet operations are, respectively:

A) intersection and union B) union and intersection C) difference and complement D) $\max$ and $\min$

Question 16

In $(\mathbb{Z}^{+}, \mid)$, the join $a \vee b$ and meet $a \wedge b$ are:

A) $\max(a,b)$ and $\min(a,b)$ B) $a+b$ and $a-b$ C) $\operatorname{lcm}(a,b)$ and $\gcd(a,b)$ D) $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$

Question 17

A poset is a lattice when:

A) it has a greatest and least element B) every pair of elements has both a join and a meet C) it is totally ordered D) it is the power set of some set

Question 18 (True/False, justify)

True or false: The "X" poset on $\{a,b,c,d\}$ with $a \prec c$, $a \prec d$, $b \prec c$, $b \prec d$ is a lattice. Justify in one sentence.

Question 19

Which single law distinguishes a Boolean algebra from an arbitrary (bounded, complemented) lattice?

A) commutativity B) associativity C) the distributive law D) idempotence

Question 20

In the two-element Boolean algebra $\{0,1\}$, the AND gate computes which operation, and which lattice operation is it?

A) $a \vee b$, the join B) $a \wedge b$, the meet C) $\overline{a}$, the complement D) $a \oplus b$, the symmetric difference

Question 21 (Short answer)

State the principle of duality for Boolean algebra: what transformation produces the dual of a law, and what does it guarantee?

Question 22 (Short answer)

In one sentence, explain why a join, when it exists, is unique — and name the property responsible.

Question 23 (Short answer)

A half adder produces a sum bit and a carry bit from inputs $a, b$. Give the Boolean expression for each, and state which is just the meet $a \wedge b$.

Question 24

By De Morgan's law, $\overline{a \vee b}$ equals:

A) $\overline{a} \vee \overline{b}$ B) $\overline{a} \wedge \overline{b}$ C) $a \wedge b$ D) $\overline{a \wedge b}$

Question 25 (Short answer)

The absorption law says $a \vee (a \wedge b) = a$. Translate this into a statement about a logic circuit: what can a chip designer delete, and what is the guarantee?

Answer Key

Topics to review by question