The laws of Boolean algebras are given.

  • The identity laws (13): $p \land 1 = p$, $p \lor 0= p$,
  • the complement laws (14): $p \land p' = 0 $, $p \lor p' =1$,
  • the commutative laws (18): $p \land q = q \land p$, $p \lor q = q \lor p$,
  • and the distributive laws (20): $p \land (q \lor r)=(p \land q) \lor (p \land r)$, $p \lor (q \land r)=(p \lor q) \land(p \lor r)$

How to derive (15):$(p')' = p $?


This is a problem on Page 12,in Introduction to Boolean Algebras,Steven Givant,Paul Halmos(2000):

(Harder.) Show that the identities in (13), (14), (18), and (20) together form a set of axioms for the theory of Boolean algebras. In other words, show that they imply the identities in (11), (12), (15), (16), (17), and (19).

(13), (14), (18), and (20) corresponds to the given 4 laws.(15) corresponds to the question.

This set of axioms is wastefully large, more than strong enough for the purpose. The problem of selecting small subsets of this set of conditions that are strong enough to imply them all is one of dull axiomatics. For the sake of the record: one solution of the problem, essentially due to Huntington [28], is given by the identity laws (13), the complement laws (14), the commutative laws (18), and the distributive laws (20). To prove that these four pairs imply all the other conditions, and, in particular, to prove that they imply the De Morgan laws (17) and the associative laws (19), involves some non-trivial trickery.

Apologize for my laziness not to cite the original problem.

  • $\begingroup$ What's $p'$? It appears to be missing from the definitions. $\endgroup$ – Rudy the Reindeer Dec 17 '12 at 19:54
  • $\begingroup$ @MattN. It's the complement. I thought "the complement law" implies that. $\endgroup$ – Metta World Peace Dec 17 '12 at 19:55
  • $\begingroup$ @Metta: Are you given a list of rules, like $p\land p=p$ or $p=q$ if and only if $p\land q=p\lor q$ and stuff like that? $\endgroup$ – Asaf Karagila Dec 17 '12 at 19:57
  • $\begingroup$ Depends on your definition of basic. Probably a little bit. I can't really quantify it. $\endgroup$ – Asaf Karagila Dec 17 '12 at 19:59
  • $\begingroup$ Another question, do you have DeMorgan laws? $(p\land q)'=p'\lor q'$? $\endgroup$ – Asaf Karagila Dec 17 '12 at 20:00

For those who don't have the OP's cited source available, a Boolean algebra is initially defined to be a non-empty set $B$, on which two binary operations--called $\wedge$ and $\vee$--and a unary operation--called $'$--are all defined, where $B$ has two distinct elements $0,1$ (possibly among other elements), such that the following axioms are all satisfied:

$$0'=1\text{ and }1'=0,\tag{11}$$ $$\forall p\in B[p\wedge 0=0\text{ and }p\vee 1=1],\tag{12}$$ $$\forall p\in B[p\wedge 1=p\text{ and }p\vee 0=p],\tag{13}$$ $$\forall p\in B[p\wedge p'=0\text{ and }p\vee p'=1],\tag{14}$$ $$\forall p\in B\left[(p')'=p\right],\tag{15}$$ $$\forall p\in B[p\wedge p=p\text{ and }p\vee p=p],\tag{16}$$ $$\forall p,q\in B\left[(p\wedge q)'=p'\vee q'\text{ and }(p\vee q)'=p'\wedge q'\right],\tag{17}$$ $$\forall p,q\in B[p\wedge q=q\wedge p\text{ and }p\vee q=q\vee p],\tag{18}$$ $$\forall p,q,r\in B\bigl[(p\wedge q)\wedge r=p\wedge(q\wedge r)\text{ and }(p\vee q)\vee r=p\vee(q\vee r)\bigr],\tag{19}$$ $$\forall p,q,r\in B\bigl[p\wedge (q\vee r)=(p\wedge q)\vee(p\wedge r)\text{ and }p\vee (q\wedge r)=(p\vee q)\wedge(p\vee r)\bigr].\tag{20}$$

It is then claimed that $(13)$, $(14)$, $(18)$, and $(20)$ (and the assumptions about $B$) entail all the other axioms. Just for fun, I'm going to prove that we can make even fewer assumptions and still get all the desired properties.

Definition: We will say a Boolean algebra is a non-empty set $B$, on which two binary operations--called $\wedge$ and $\vee$--are defined, where $B$ has at least two distinct elements, such that the following axioms are all satisfied:

$$\exists u,z\in B\forall p\in B\bigl[[p\wedge u=p\text{ and }p\vee z=p]\text{ and }\exists q\in B[p\wedge q=z\text{ and }p\vee q=u]\bigr],\tag{i}$$ $$\forall p,q\in B[p\wedge q=q\wedge p\text{ and }p\vee q=q\vee p],\tag{ii}$$ $$\forall p,q,r\in B\bigl[p\wedge (q\vee r)=(p\wedge q)\vee(p\wedge r)\text{ and }p\vee (q\wedge r)=(p\vee q)\wedge(p\vee r)\bigr].\tag{iii}$$

Observe that the latter two axioms are simply $(18)$ and $(20)$, while the former is entailed by $(13)$ and $(14)$ together with the extra assumptions about $B$ (such as $0,1\in B$, and the existence of the unary operation $'$ on $B$).

Proposition A: The $u$ and $z$ from (i) are unique, and so is the $q$.

Proof: Suppose $u,v\in B$ are such that for all $p\in B$, $p\wedge u=p$ and $p\wedge v=p$. In particular, then, it follows from $(18)$ that $$v=v\wedge u=u\wedge v=u,$$ so uniqueness holds. We may similarly prove the uniqueness of $z$. Hereinafter, we refer to $z$ and $u$ as $0$ and $1$, respectively. Then $(13)$ holds, and by (i), we have $$\forall p\in B\exists q\in B[p\wedge q=0\text{ and }p\vee q=1],$$ a weakening of $(14)$. Once we've demonstrated that such a $q$ is uniquely determined by $p$, then we will be able to explicitly define the unary operation $'$ on $B$ so that $(14)$ is satisfied completely.

Take any $p\in B$, and suppose that $q,r\in B$ are such that $p\wedge q=0=p\wedge r$ and $p\vee q=1=p\vee r$. Then by $(13)$, $(18)$ and $(20)$, we see that $$\begin{align}q &= q\wedge 1\\ &= q\wedge(p\vee r)\\ &= (q\wedge p)\vee(q\wedge r)\\ &= (r\wedge q)\vee(p\wedge q)\\ &= (r\wedge q)\vee 0\\ &= (r\wedge q)\vee(p\wedge r)\\ &= (r\wedge p)\vee(r\wedge q)\\ &= r\wedge(p\vee q)\\ &= r\wedge 1\\ &=r,\end{align}$$ as desired.

Hereinafter, given $p\in B$, we will define $p'$ to be the unique $q\in B$ such that $p\wedge q=0$ and $p\vee q=1$. $\Box$

Lemma 1: $(11)$, $(12)$, and $(16)$ hold.

Proof: By $(14)$, we have $0'=0'\vee 0=1$. Other part of $(11)$ similar.

By $(13)$, $(18)$, and $(20)$, we have $$p\vee 1=(p\vee 1)\wedge 1=(p\vee 1)\wedge(p\vee p')=p\vee(1\wedge p')=p\vee(p'\wedge 1)=p\vee p'=1.$$ Other part of $(12)$ similar.

By $(13)$, $(14)$, and $(20)$, we have$$p\wedge p=(p\wedge p)\vee 0=(p\wedge p)\vee(p\wedge p')=p\wedge(p\vee p')=p\wedge 1=p.$$ Other part of $(16)$ similar. $\Box$

Lemma 2: $p\wedge(p\vee q)=p$ and $p\vee(p\wedge q)=p$.

Proof: By $(12)$, $(13)$, $(18)$, and $(20)$, we have $$p\wedge(p\vee q)=(p\vee 0\wedge(p\vee q)=p\vee(0\wedge q)=p\vee(q\wedge 0)=p\vee 0=p.$$ Other part similar. $\Box$

Lemma 3: $p\vee q=q$ if and only if $p\wedge q=p$.

Proof: If $p\vee q=q$, then by Lemma 2, $p=p\wedge(p\vee q)=p\wedge q$. Other direction similar. $\Box$

Proposition B: $(19)$ holds.

Proof: Let $x=p\vee(q\vee r)$ and $y=(p\vee q)\vee r$.

By Lemma 2--$p\wedge(p\vee q)=p$ portion--it follows that $p\wedge x=p$. By $(20)$ and by Lemma 2, we also have $$\begin{align}p\wedge y &= p\wedge\bigl((p\vee q)\vee r\bigr)\\ &= \bigl(p\wedge(p\vee q)\bigr)\vee(p\wedge r)\\ &= p\vee(p\wedge r)\\ &= p,\end{align}$$ so $p\vee x=p\vee y$.

Now, by $(13)$, $(14)$, $(18)$, and $(20)$, we have $$\begin{align}p'\wedge x &= p'\wedge\bigl(p\vee (q\vee r)\bigr)\\ &= (p'\wedge p)\vee\bigl(p'\wedge(q\vee r)\bigr)\\ &= \bigl(p'\wedge(q\vee r)\bigr)\vee(p\wedge p')\\ &= \bigl(p'\wedge(q\vee r)\bigr)\vee 0\\ &= p'\wedge(q\vee r),\end{align}$$ and also $$\begin{align}p'\wedge y &= p'\wedge\bigl((p\vee q)\vee r\bigr)\\ &= \bigl(p'\wedge(p\vee q)\bigr)\vee(p'\wedge r)\\ &= \bigl((p'\wedge p)\vee(p'\wedge q)\bigr)\vee(p'\wedge r)\\ &= \bigl((p'\wedge q)\vee(p\wedge p')\bigr)\vee(p'\wedge r)\\ &= \bigl((p'\wedge q)\vee 0\bigr)\vee(p'\wedge r)\\ &= \bigl(p'\wedge q)\vee(p'\wedge r)\\ &= p'\wedge(q\vee r),\end{align}$$ so $p'\wedge x=p'\wedge y$.

Finally, by $(13)$, $(14)$, $(18)$, $(20)$, and the identities derived above, we have $$\begin{align}p\vee(q\vee r) &= x\\ &= x\wedge 1\\ &= x\wedge(p\vee p')\\ &= (x\wedge p)\vee(x\wedge p')\\ &= (p\wedge x)\vee(p'\wedge x)\\ &= (p\wedge y)\vee(p'\wedge y)\\ &= (y\wedge p)\vee(y\wedge p')\\ &= y\wedge(p\vee p')\\ &= y\wedge 1\\ &= y\\ &= (p\vee q)\vee r,\end{align}$$ as desired. Other part of $(19)$ similar. $\Box$

Lemma 4: Define a relation $\leq$ on $B$ by $p\leq q$ iff $p\vee q=q$ iff $p\wedge q=p$. Then $\leq$ partially orders $B.$ Moreover, by $(12)$ $0,1$ are respectively the least and greatest elements of $B$ under the partial ordering by $\leq$, so since $B$ has at least $2$ elements by definition, then we have that $0\neq 1$.

Proof: Reflexivity holds by $(16)$, and antisymmetry holds by $(18)$. If $p\leq q$ and $q\leq r$, then by $(19)$ we have $$p\vee r=p\vee(q\vee r)=(p\vee q)\vee r=q\vee r=r,$$ so $p\leq r$, and so transitivity holds. Thus, $\leq$ partially orders $B$. $\Box$

Lemma 5: If $r\leq p,q$, then $r\leq p\wedge q$, and if $r\geq p,q$, then $r\geq p\vee q$. Also, by Lemma 2, $p\wedge q\leq p\leq p\vee q$ for all $p,q$. Thus, $p\wedge q$ and $p\vee q$ are (respectively) the greatest lower bound and least upper bound of $p,q$ in $B$ under the partial order $\leq$.

Proof: Suppose $r\leq p,q$, so $r\vee p=p$ and $r\vee q=q$, so $$r\vee(p\wedge q)=(r\vee p)\wedge(r\vee q)=p\wedge q,$$ and so $r\leq p\wedge q$. Other part similar. $\Box$

Lemma 6: If $p\leq q$, then $p\vee r\leq q\vee r$ and $p\wedge r\leq q\wedge r$ for all $r$.

Proof: If $p\leq q$, then $p\vee q=q$, so $$(p\wedge r)\vee(q\wedge r)=(p\vee q)\wedge r=q\wedge r,$$ and so $p\wedge r\leq q\wedge r$. Other part similar. $\Box$

Lemma 7: $p\vee q=1$ if and only if $p\geq q'$. $p\wedge q=0$ if and only if $p\leq q'$.

Proof: If $p\geq q'$, then by Lemma 6, we have $$1\geq p\vee q\geq q'\vee q=1,$$ so $p\vee q=1$ by antisymmetry. On the other hand, if $p\vee q=1$, then $$p\vee q'=1\wedge(p\vee q')=(p\vee q)\wedge(p\vee q')=p\vee(q\wedge q')=p\vee 0=p,$$ so $p\geq q'$. Other part similar. $\Box$

Proposition C: $(15)$ and $(17)$ hold.

Proof: Since $p\vee p'=1$, then by Lemma 7, we have $p\geq (p')'$. On the other hand, $p\wedge p'=0$, then $p\leq (p')'$. By antisymmetry, we have $p=(p')'$.

By $(12)$, $(14)$, $(16)$, $(18)$, $(19)$, and $(20)$, we have $$\begin{align}(p'\wedge q')\vee(p\vee q) &= (p\vee q)\vee(p'\wedge q')\\ &= \bigl((p\vee q)\vee p'\bigr)\wedge\bigl((p\vee q)\vee q'\bigr)\\ &= \bigl((q\vee p)\vee p'\bigr)\wedge\bigl((p\vee q)\vee q'\bigr)\\ &= \bigl(q\vee (p\vee p')\bigr)\wedge\bigl(p\vee (q\vee q')\bigr)\\ &= \bigl(q\vee 1\bigr)\wedge\bigl(p\vee 1\bigr)\\ &= 1\wedge 1\\ &= 1,\end{align}$$ so $p'\wedge q'\geq (p\vee q)'$ by Lemma 7, but on the other hand, $$\begin{align}(p'\wedge q')\wedge(p\vee q) &= \bigl((p'\wedge q')\wedge p\bigr)\vee\bigl((p'\wedge q')\wedge q\bigr)\\ &= \bigl((q'\wedge p')\wedge p\bigr)\vee\bigl((p'\wedge q')\wedge q\bigr)\\ &= \bigl(q'\wedge (p'\wedge p)\bigr)\vee\bigl(p'\wedge (q'\wedge q)\bigr)\\ &= \bigl(q'\wedge (p\wedge p')\bigr)\vee\bigl(p'\wedge (q\wedge q')\bigr)\\ &= \bigl(q'\wedge 0\bigr)\vee\bigl(p'\wedge 0\bigr)\\ &= 0\wedge 0\\ &= 0,\end{align}$$ so $p'\wedge q'\leq (p\vee q)'$ by Lemma 7, and so $p'\wedge q'=(p\vee q)'$ by antisymmetry.

Other part of $(17)$ similar. $\Box$

| cite | improve this answer | |
  • $\begingroup$ Thank you for your great answer. I've never expected it to be such a detailed and insightful one. $\endgroup$ – Metta World Peace Dec 18 '12 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.