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