DaedTech

Stories about Software

By

Practical Math for Programmers: Truth Tables and Boolean Basics

The “Why This Should Matter to You” Story

Let’s say you’re responsible for maintaining a piece of code for the business that figures out recommendations for what to do at night. At the moment, it’s pretty simple:

Let’s say a project manager comes along and says to you, “what does the program currently recommend at night” and you say “well, if it’s late, the method recommends that you go to bed.” The project manager then says “okay, that’s great, but you should recommend that the user goes to bed in that case and also the case where either it’s late or you’re tired.” You dutifully make that happen:

You run the application, try out a few scenarios and see that it seems to make sense: you always wind up in bed when it’s late and generally wind up in bed when you’re tired, so you deliver it. You figure this makes sense since you’re usually tired when it’s late. Satisfied, you deliver the code and reason that it’s almost certainly fine and, if not, the architect will let you know in the next few days when she reviews the code.

A few days later, walking through the hallway, you see the architect coming and offer her a friendly wave. She frowns at you, opens her mouth for a second, then closes it, shakes her head, and walks by with a quick “hi”. A bit nonplussed, you return to your desk wondering what the issue was. She is quite busy so it’s no surprise she might not have time to talk right this second, so you decide to investigate further. Seeing nothing in your inbox from the architect, you decide to check through the code you’ve recently touched and you see this:

She’s put your code back to the way it was. Your sense of unease growing a bit, you walk over to her desk and ask why she reverted code that you added as per a new requirement. She testily tells you that she doesn’t have time for “Programming 101” right now and says she’ll go over some basic stuff with you next week.

What happened, and what should you do?

Math Background

Given that the architect’s displeasure revolves around the inclusion (and later omission) of an if condition, it’s a safe bet that we’re going to be covering Boolean logic in today’s post. Most people think of conditional control flow operators that you see in programs such as if, else, and switch/case in anecdotal and somewhat intuitive terms. Statements like “if my favorite sports team loses today, I will be sad” are the cornerstone of deductive reasoning, a mental exercise that is nearly universal to human communication and certainly not limited to programmers. And if you come to programming from a largely self-taught background with limited exposure to mathematics, this is probably the extent of your experience with conditional operations. You’re likely to reason about conditional operations the same way you reason about conversational ones.

This conversational reasoning works pretty well on simple code scenarios in code with situations like “if x then y else z” but it starts to get a little more interesting when there are compound conditions strung together with AND and OR. When this comes up, programmers and people in general without a mathematical background are likely to start struggling with keeping it straight. For example, consider this sentence: “If my dog is sleeping and my car is unlocked or if my car is locked but the keys are on the coffee table and I’m near the coffee table or else if someone can give me a ride, I’m going to go to the store.” Ready to start coding that up? Will you feel good about getting that right with an intuitive approach?

If the answer to that is “no”, then you’ve come to the right place. The math involved in Boolean operations will help you make sense of strings of conditions that are arbitrarily complex. First, let’s define some terms:

(Truth) Value:                             True (T) or False (F) in the Boolean world.
Variable:                                       A proxy that represents an unknown truth value (often A, B, C, etc)
(Basic) Operation:                      Algorithm applied to one or more values/variables to yield an output value/variable (e.g. “And”, “Or”, “Not”).
Expression:                                  Any grouping of operations, values and variable with a resultant truth value (e.g. “A”, “True”, “A AND True”, “A OR NOT(B)”).
Conjunction:                               Formal term for “AND” and represented in a variety of ways: (A AND B), (A^B), (AB)
Disjunction:                                Formal term for “OR” and represented in a variety of ways: (A OR B), (AvB), (A+B)
Negation (or Complement):    Formal term for “NOT” and represented in a variety of ways: (NOT(A)), (~A), (!A)
Truth Table:                               An enumeration of all possible expression inputs and their resultant truth output.

Notice that in this description of the basic operations, I do not use their common programming language equivalents such as “&&” and “||” (bang (!) operator being an exception). This is intentional. For one thing, these operators in their programming language contexts often have meaning beyond Boolean algebra (such as bitwise operations, which I will cover in a future post) which would distract from this post and for another thing, it is important to keep in mind that we’re operating outside of a programming contexts. Here, our expressions are propositions rather than representative of some kind of state of a program.

The truth table definition is a bit ambiguous, so let’s do some examples of what that looks like. In this case, a picture is worth a thousand words. Here is a truth table for the variable A:

On the left is the input, which is simply the variable A, and on the right is the value of that expression with the left hand truth value used for A. It’s easier to get the idea with another example or two. Here’s negation:

If we substitute T for A, the value of ~A is F, and vice-versa if we use the value F for A. Here’s an example with two variables:

As you can see, this is pretty simple stuff. You simply take all possible combination of variables, plug them in, and evaluate the results to see what the value of the expression is in each case. Let’s try this with the condition that so annoyed the architect:

Looking at this table, do you notice anything interesting? The expression is true in the first two cases and false in the second two. Just like the “A” variable. In fact, it’s identical to the A variable. The B variable doesn’t matter at all!

How It Helps You

Truth tables are not rocket science. In fact, they’re one of the easiest mathematical concepts you’re likely to encounter since they are simply brute force documentation of an expression. But they will help you see patterns. You’ll see patterns directly in the manner we laid out here, but as you get familiar with truth table patterns, you’ll start to apply them within larger conditionals as well and even to recognize intuitively and automatically situations that can be simplified. Or, if you don’t recognize them immediately, you might at least suspect simplifications are possible and write out a truth table to confirm or refute your hypothesis.

This has a powerful impact on your code. Instead of large and laborious conditionals strung together, you will gravitate toward the simplest possible representations. Not only does this keep the code clean and readable, but it also helps with your clarity of thought from a requirements and reasoning perspective. Consider our example situation. Isn’t it nice to be able to say to the PM, “hey, we should talk about what you want here because the requirement you added actually has no effect as you’ve stated it.” Without a knowledge of Boolean basics, you’d have a hard time recognizing this yourself, much less explaining it to someone else.

And finally, this understanding gains you respect from your fellow programmers. If you write big, unwieldy conditional statements, often containing redundancies or tautologies (statements that always evaluate to true, such as “A OR NOT(A)”), other people will come to view you as sloppy or poorly informed as far as programming goes. The example with the architect isn’t far-fetched at all. It pays to have a basic understanding of Boolean logic and some of its rules for the sake of being taken seriously.

You don’t need to be an expert in the various transforms and axioms in Boolean algebra (which I will cover next time) to get this right. A truth table may seem cumbersome and it may feel sort of plodding and non-elegant, but it’s a surefire way to get things right, look for patterns, and feel more comfortable in the conditionals you’re writing. Practice them and know them and you won’t be sorry.

Further Reading

  1. There are some other operators (NAND, XOR, XNOR, NOR) that can be composed from AND, OR, and NOT, which you can read about here.
  2. NAND (and NOR) has the interesting property of being functionally complete in terms of logic (meaning all other operators can be derived from it). You can read about that here, though it’s framed in terms of circuits rather than pure math.
  3. This is a cool site that will generate actual truth tables for you if you punch in an expression.
  4. Here is a very rigorous, but math jargon-heavy reading about Boolean algebra, how it is constructed from axioms, and how it relates to other mathematical systems. Warning — this is not a light read.
  5. On the flip side of jargon-heavy is this practical, conversational series of examples of truth tables and the reasoning behind them.
  Subscribe  
newest oldest most voted
Notify of
Andy Lamb
Guest
Andy Lamb

I find binary decision trees a good way to reason about complex boolean logic. I’ve even written a Visual Studio extension that will generate BDTs from .NET lambda expressions used heavily in Linq. If you’re interested, search for ‘Expression Debug Visualizer’ in the Visual Studio Gallery.

Erik Dietrich
Guest

That’s a pretty powerful tool! (Here’s the link, for anyone else reading: https://visualstudiogallery.msdn.microsoft.com/5bd20501-57d9-4fa3-b655-b5934ea9c3e6 )

trackback

[…] of all, you may want to go back and brush up on some previous posts in this […]