Boolean Logic

One of the first topics I wanted to discuss was boolean arithmetic. You will probably find out that there's quite a few things to say, even if it comes down to only two values: "true" or "false". Most of you are already familiar with boolean functions and how to combine operands to form any expression, so this topic will be a bit shorter than the rest.

For the purpose of this post, I will denote by "~A", the opposite of the boolean expression A ("not" A). It is a bit easier to see than what I suspect most of you are used to: "!A" (the C-style boolean negation).

First, a few rules I wanted to write down:

• ~(~A) = A (double negation cancels itself out)
• A OR true = true
• A OR false = A
• A AND true = A
• A AND false = false
• A AND ~A = false
• A OR ~A = true
• ~(A AND B) = ~A OR ~B (De Morgan's laws)
• ~(A OR B) = ~A AND ~B 

Of course, these are not the only relations out there. But they are probably the most used. Next, I will give you a few tables. I've seen this happen on more than one occasion, so pay attention, because it might come in handy sooner than you think. Suppose you have two boolean expressions (A and B) and you have to call one piece of code if a certain combination of values applies and another piece when it doesn't (the classic "if-then-else" block). More specifically, in some languages it might look like this:

if ( A ??? B ) {

   // code 1

} else {

  // code 2

}

You might think that the operand you place in that ??? is always simple if you know what the code should do. It is (or it should be a lot easier to see by the time you finish reading this post). Some cases might seem more complicated than others.

It's pretty common to stumble on a situation when you don't know what to put as that operator (this is why I'm writing this). What I usually do is to try to put in a table (see below) when I should go into code block 1 and spot the necessary operator. In the following, I will try to show you how to recognize each boolean operation, depending on the layout of that table.

Case 1: all the same value

(a)  A   ~A   B  1 1  ~B  1 1

(b)  A   ~A   B  0 0  ~B  0 0

In this case, you obviously never enter one of the "then" or "else" branches. The condition is "if (true)", respectively "if (false)". You might as well ignore writing the "if" statement completely and just write the "then" block for subcase (a), respectively the "else" block for subcase (b).

For the following cases, I will not put the zero (false) values in the table, so the true values are easier to see.

Case 2: two 'true' values on the same line/column

(a)  A   ~A   B  1 1  ~B

(b)  A   ~A   B   ~B  1 1

(c)  A   ~A   B  1  ~B  1

(d)  A   ~A   B  1  ~B  1

In the first two tables, you can see that the value of the condition A doesn't affect the outcome of the evaluation (for A and ~A, the columns are identical). Therefore, it's only logical that the entire condition you place on the "if" statement depends only on the condition that influences the lines and ignores the boolean values on the columns. Similarly, on the last two cases, the condition will depend only on the column, ignoring the rows. The conditions for each table are as follows:

1. if (B)
2. if (~B)
3. if (A)
4. if (~A)

Case 3: only one 'true' value

(a)  A   ~A   B  1  ~B

(b)  A   ~A   B   ~B  1

(c)  A   ~A   B  1  ~B

(d)  A   ~A   B   ~B  1

Probably the most common of all situations revolving around two boolean variables. You only enter the "true" block if both variables are exactly the values you want. The easiest way to explain it is: "enter only if ((A has the value I want) AND (B has the value I want))". Visually, just put the AND between the values corresponding to the row and column that intersect at that "true" value. The conditions for each table are as follows:

1. if (A AND B)
2. if (A AND ~B)
3. if (~A AND B)
4. if (~A AND ~B)

Case 4: three 'true' values (only one out of four excluded)

(a)  A   ~A   B  1 1  ~B  1

(b)  A   ~A   B  1  ~B  1 1

(c)  A   ~A   B  1 1  ~B  1

(d)  A   ~A   B  1  ~B  1 1

If the AND operator is the most common boolean operator, this one definitely is a close second. You enter the "true" block if either one of the variables has the value you want. So, if you try to put it into words, it would go like "enter if at least one of them has the value I want". Visually, just put the OR between the values corresponding to the row and column that don't intersect at that "false" value (or, how I sometimes think it: OR the column and row that intersect in the cell that sits diagonally opposite of the "false" value). The conditions for each table are as follows:

1. if (A OR B)
2. if (A OR ~B)
3. if (~A OR B)
4. if (~A OR ~B)

As an exercise, try to verify the De Morgan laws using the tables in cases 3 and 4 (AND and OR tables). If you apply the NOT (~) operator to an entire table, all the values in it change.

Case 5: only two 'true' values, on opposite corners

(a)  A   ~A   B  1  ~B  1

(b)  A   ~A   B  1  ~B  1

If I said that the AND and OR cases are in the middle of a close fight for first place, this one comes in last. Maybe because it's so rarely encountered, but most people don't handle it efficiently. I've seen this over and over again, and although it is in fact correct, it can be done in a shorter version. For sub-case (a), one of the most common conditions is "if ((A AND B) OR (~A AND ~B))". Again, this is correct and for most people, it is the most logical way to write it. Ok, by now, most of you are probably thinking: "hey, there was that other operator I only heard about, but never used... XOR (exclusive OR)". In many languages, for those who are unfamiliar with it, it is represented either as "XOR" or "^". Indeed, this operator should definitely get a little more credit.

As a side story that happened in highscool, when I learned about the boolean operators in Pascal; my teacher was intentionally going to overlook it because he considered nobody uses it. When I tried to correct him and said that there is another operator for boolean variables, he was a bit upset (probably because it was the third time that class when I interrupted him, but that's not relevant here) and he gave me a special assignment to find at least three useful applications for the XOR operator. I could probably do an entire post only on this subject, but maybe later.

Back to the topic at hand, the English translation of the condition would be something like: "if only one of the conditions apply (but not both)". In order to apply the operator properly, just put XOR between a row containing one of the 'true' values and the column containing the other 'true' value. Or similarly, XOR a row and a column that have a 'false' at their intersection. The conditions for the two tables pictured above are:

1. if (A XOR B)     or    if (~A XOR ~B)
2. if (A XOR ~B)    or    if (~A XOR B)

A few properties of the XOR operator (some of them can be verified with the above tables, others may be easier to check after we discuss an alternative operator for XOR expressions):

• ~(A XOR B) = ~A XOR B = A XOR ~B (negating a XOR expression is equivalent to negating one of the operands)
• ~A XOR ~B = A XOR B (if you negate both operands, is the same as leaving them intact - use this to simplify your expressions)
• A XOR A = false
• A XOR ~A = true
• A XOR true = ~A
• A XOR false = A

One more thing to add regarding this case. Sometimes, there is another way to write this conditions without using the XOR operator. However, they apply only if your language has exactly one value for 'true' and one value for 'false' (or if you always use only one of the possible values for 'true' and only one of the possible values for 'false'). A few examples might clarify this: Java, C#, Pascal have only one value for 'true'/'false'.
On the other side, in C/C++, NULL == 0 == false and anything else can be evaluated as 'true' if placed as a condition ("int x = 7; if (x) {...}"). Similarly, in Javascript, "if (!some_var)" can mean either of:
- "if (some_var == false)"
- "if (some_var != undefined)"
- "if (some_var != null)"
So, as I said before, you can write a condition like "A XOR B" in another way if you use a language that has only one 'true' and only one 'false' value (or you are 100% sure you are using one value every time - for example, you write your boolean functions in C with return type int, and always return zero or one, never any other values). There's no need to keep you in suspense, so: "A XOR B" if and only if "A != B" (or "A <> B" if you prefer). Similarly, "A XOR ~B" is the same as "A == B".

Conclusion: like I said in the beginning of this post, there's quite a lot to talk about even if it comes down to something simple as 1 and 0 (I guess the length of this post stands as proof). Also, if you were a bit confused by the previous post (that long "introduction" in which I tried to explain what this blog is going to be about), well... stuff like this. Small tricks I've picked up over the years, stuff that make me the programmer I am today. For some, it may all be obvious and they are not going to bother reading it. Even so, reading this might help you remember stuff you have long forgotten.

PS: I know I said this post is going to be shorter than the rest... I was actually referring to the useful information in it, not the actual length (I got sidetracked along the line and it came out a lot longer than I anticipated).