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:

public void DoNightThings()
{
    if (_itsLate)
        GoToBed();
}

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:

public void DoNightThings()
{
    if (_itsLate && (_itsLate || _iAmTired))
        GoToBed();
}

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:

public void DoNightThings()
{
    if (_itsLate)
        GoToBed();
}

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.

By

Old Programmer’s Guide to Practical Maths

I’m writing this post to introduce another series of posts I intend to embark upon, to coexist alongside my “abstractions,” “design patterns,” and “home automation” posts. I’m going to post these under the category “Practical Math” and think of the series as being called “Practical Math for Programmers,” the title of this post notwithstanding. (Speaking of which, bonus Renaissance-Man points to the first commenter who knows what inspired the title.)

Does Math Matter?

This is a discussion that I’ve heard a lot over the years as a programmer, and it seems to be a slightly more muted and cordial debate than the typically contentious “computer science degree vs certifications” or “schooling versus self-taught” ones. Generally the accepted answer is the “architect answer” of “it depends.” I’ll see/hear consensuses such as, “well, you need it if you’re going to be doing really low level stuff or processing lots of data or designing compilers or something, but if you’re just writing basic line of business apps or if you’re more of a designer then you don’t need math.” I often like the architect answer because trending toward nuance and avoiding absolutes gives you the most chance of recovering from bad assumptions, but I’m going to go out on a limb here with more of a hard-line stance. I think that programmers do need and use math and that it doesn’t “depend” at all. It’s just that some are more trained in and aware of their usage of it while others do it by intuition, rote, or dependence on others.

One thing that I think clouds the issue is what is meant by “math.” Many think back to derivatives or perhaps back further to trigonometry and algebra and realize that they don’t frequently hit the math libraries for things like cosine or solve for x. Sure, there are some basic arithmetic operations when laying out a page–addition, subtraction, etc., but that’s it. There’s a broad tendency to dismiss the basic arithmetic as too trivial for discussion and declare math unnecessary in these cases.

But I think that this analysis tends to overlook two math concerns: missed opportunities to leverage math and lack of understanding that it’s even being used. For the first one, consider a scenario of laying out a form with simple arithmetic. Say there are three buttons that need to be evenly spaced on a form, and the form should have a fixed width, but you have some control over that. The visual, “non-math” way to do this might be to assign the buttons random horizontal locations and then move them around by trial and error. Time could be saved, however, with a simple algebraic solution of determining a ratio of padding to button, determining a form width, and solving for x–no trial and error and exactly right the first time.

The second concern is a bit more subtle. Perhaps each of the aforementioned buttons have handlers and those handlers have some logic. If button 2 is clicked after button 1, and button 3 is red or else button 2 is blue, disable button 1. Is there any math there, or just a series of weird procedures? The answer is “both,” but you’re probably not thinking of or looking for the math. You’re intuitively constructing logic chains in your head and trying to figure out where the nested parentheses are going to go in your if statement. If you’re intuitively constructing scenarios and you think you’re not doing any math, it’s because you’ve never been exposed to truth tables or Boolean algebra.

It Definitely Matters

Boolean logic lies at the core of most things that any programmer does, and it isn’t alone. Arithmetic is obviously indispensable, if reasonably taken for granted, but at the core or arithmetic lies the cousin of Boolean algebra, which is algebra over real numbers. Pulling back from the more “fluid” concerns about real numbers with which we’re used to dealing, there is also a whole world of discrete/finite math that involves distinct values and forms the basis for concepts like sets, graphs, and basic data structures which are in turn assembled into algorithms and design patterns. From that emerges everything from the exotic, like cryptography, to the mundane, such as preconditions and functions. If you’re a programmer and haven’t had exposure to these things, you’re living in The Matrix, blissfully unaware that you could take a red pill and start to see everything you’re doing as a weird, dripping series of green symbols and digits on black background.

Because I think that math matters a lot and because it’s fairly heavily in my background, I’m going to embark upon this series of posts. I’d like to cover things such as DeMorgan’s Laws/Boolean Inference, O-notation, formal methods, combinatorics, probability/game theory, etc. But if you find your eyes glazing over just reading that list, don’t worry–it won’t be a bumpy ride. And I’ll be in it with you, since my days of heavy exposure to theoretical math are, along with college and grad school, surprisingly far away in my rearview mirror. I’ll have some rust to shake off myself. These are going to be very elementary explanations of these concepts, along with practical concerns of why you as a programmer should care. I’ll also provide links to more information and formal reading along with perhaps examples of where you’re already using this and maybe not even realizing it. I’m going to keep these posts mainly language agnostic, and I might switch it up among C#, Java, and C++, depending on what I’m covering.

Stay tuned if this kind of thing interests you.