Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $?

EDIT:

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.

share|improve this question
    
What's $p'$? It appears to be missing from the definitions. –  Matt N. Dec 17 '12 at 19:54
    
@MattN. It's the complement. I thought "the complement law" implies that. –  Metta World Peace Dec 17 '12 at 19:55
    
@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? –  Asaf Karagila Dec 17 '12 at 19:57
    
Depends on your definition of basic. Probably a little bit. I can't really quantify it. –  Asaf Karagila Dec 17 '12 at 19:59
    
Another question, do you have DeMorgan laws? $(p\land q)'=p'\lor q'$? –  Asaf Karagila Dec 17 '12 at 20:00

1 Answer 1

up vote 2 down vote accepted

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$

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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