### A Boole’s Errand

Did you know this is the last day of CS Education Week? The creators of this event are highly engaged in bringing Computer Science to more high schools — in many states, CS is not given full consideration in the curriculum and this is shocking to me given that children are using computers not much later than they can read and write. But, let me leave you with a link to a very detailed report if you want to know more, and instead ask you some puzzles.

In Boolean algebra (named after George Boole) you manipulate the symbols T (for true) and F (for false). This is useful to help analyze, understand, and simplify the flow of logic in computer programs and electronic circuits. The **NOT** function swaps T to F and vice-versa, for example **NOT**(F) = T and **NOT**(T) = F. One way to combine two values is with the **OR** function: if you give it two of the same input it gives you the same one back, but if you give it a mix of T’s and F’s it gives you back T. For example **OR**(T, F) = T and **OR**(F, F) = F. **AND** does the same thing, but it gives you back F if the inputs are a mix of T and F.

A couple of miraculous things happen from these definitions. One is DeMorgan‘s Law, which says that

**NOT**(**AND**(*x*,*y*)) =**OR**(**NOT**(*x*),**NOT**(*y*)), no matter what the values of*x*and*y*are;- similarly
**NOT**(**OR**(*x*,*y*)) =**AND**(**NOT**(*x*),**NOT**(*y*)).

In a sense, this law says that **NOT** turns **AND** in to **OR** and vice-versa.

Another one is that we get a distributive law

**AND**(*x*,**OR**(*y*,*z*)) =**OR**(**AND**(*x*,*y*),**AND**(*x*,*z*)), no matter what the values of*x, y,*and*z*are;- similarly
**OR**(*x*,**AND**(*y*,*z*)) =**AND**(**OR**(*x*,*y*),**OR**(*x*,*z*)).

So this is like arithmetic where *x**(*y*+*z*) = *x*y + x*z* but continuing the analogy, somehow for Boolean algebra we also have *x+y*z = (x+y)*(x+z)*, which is not like arithmetic.

Finally, there is a function **XOR** (exclusive or) which is a cousin of **OR**. Note that in English sometimes we use “or” to mean the “**OR**” function described above: “you’re not allowed to drive if you have no license **OR** you’re drunk” (or both). But in English sometimes “or” means “either but not both,” like “this combo comes with a salad or fries” — in this case you can’t get both. This is **XOR** in Boolean logic: it has the same behaviour as **OR** except that **XOR**(T, T)=F instead of how **OR**(T, T) = T. It turns out that there are a couple of ways to build **XOR**,

**AND**(**OR**(*x*,*y*),**OR**(**NOT**(*x*),**NOT**(*y*))) is one definition of**XOR**(*x*,*y*)**OR**(**AND**(*x*,**NOT**(*y*)),**AND**(**NOT**(*x*),*y*)) is another equivalent definition of**XOR**(*x*,*y*).

I’d call this equivalence another law.

Here are some questions:

**Troolean logic**. Let’s say we extend Boolean logic to have a third value ? meaning “I don’t know.” So we should define**NOT**(?)=?, as well as**OR**(F, ?) = ? and**OR**(T, ?) = T since in the first case we can’t tell what the result of OR should be, but in the second it should definitely return T. Show that we can define**AND**and**XOR**on all pairs of inputs involving T, F, and ? so that all of the laws above hold.**Quadroolean logic**. Instead, we could extend Boolean logic to have 4 values: F, T, VF and VT, where VF is “very false” and VT is “very true.” Thus**NOT**(VF)=VT and**NOT**(VT)=VF makes a sensical definition, as well as**OR**(VF,*x*) =*x*for all*x*and**OR**(VT,*x*) = VT for all*x*. Show that we can define**AND**and**XOR**on all pairs of inputs involving T, F, VT and VF so that all of the laws above hold.**n-****oolean logic**. Show that for any integer*n*> 1, we can come up with a set of exactly*n*symbols including T and F, and definitions of**NOT**,**AND**,**OR**and**XOR**for them so that all of the laws above hold, plus a few others:**NOT**(**NOT**(*x*)) =*x*; the commutative property**AND**(*x*,*y*)=**AND**(*y*,*x*) and similarly for**OR**; the associative property**AND**(*x*,**AND**(*y*,*z*)) =**AND**(**AND**(*x*,*y*),*z*) and similarly for**OR**; the idempotent laws**OR**(*x*,*x*) =**AND**(*x*,*x*) =*x*.- Are there multiple truly different
*n*-oolean logics? - Does the XOR equivalence law follow automatically from all of the other laws? (This one I don’t know the answer to.)

Filed under: computer science, puzzlers, toc | 4 Comments

Hi Dave, my lawyers will be in touch 🙂 Andrew

http://polylogblog.wordpress.com/2012/03/29/a-booles-errand/

Glad it’s not George’s lawyers from beyond the grave…

You’ve given high school students a rigorous justification for answering ‘?’ on their exams. They’ll eat this up…

FWIW: I think that there is an answer to 5 which involves all binomial(4, 2) down-and-left closed subsets of the 2×2 grid.