Boolean Arithmetic

General

This article assumes you have already read  Computation Rules and Comparisons and that you understand the basics of logical operators and comparisons. It also assumes you have read  Creating Temporary Variables and understand how temporary variables work. This article will cover how to use the basic tools given by the logical operators to create complex and extremely useful comparisons.

Basic Boolean Arithmetic

Boolean arithmetic allows us to combine a series of inputs to get a series of outputs. In Boolean arithmetic, all of the inputs are true or false, and all of the outputs are true or false. In this article, true will be represented as T and false will be represented as F.

For brevity the syntax “∨” means or, “∧” means and, and “¬” means not. Inputs will be represented with capital letters as well, most often A and B. Below is a Boolean statement:

A ∧ B ∧ C

This statement can be read as “A and B and C,” and the Lisp equivalent is (and A B C). AND operations are commutative with other AND operations, and OR operations are commutative with other OR operations. However, AND and OR operations are not commutative with each other. For example:

A ∧ B ∧ C = B ∧ C ∧ A

A ∨ B ∨ C = C ∨ B ∨ A

A ∧ B ∨ C ≠ B ∨ C ∧ A

Because of this, parentheses are used to distinguish which sections are being ANDed and which sections are being ORed.

(A ∨ B ) ∧ C

NOT operations stay with the input that they are inverting.

A ∨ B ∨ ¬C = ¬C ∨ B ∨ A

ANDs, ORs, and NOTs can be distributed inside of parentheses; however, when distributing NOTs, it also affects the logical operation (see De Morgan’s Law below).

(A ∨ B) ∧ C = (A ∧ C) ∨ (B ∧ C)

De Morgan’s Law

De Morgan’s Law is the name of a very important law in Boolean arithmetic. This law states how inversion applies to logical operations. For example, lets say we have ¬(A ∧ B) and we want to know what it’s equal to. De Morgan’s law states that when inverting a logical operation, it becomes the opposite operation (for example, when inverting an AND it becomes an OR, and vice versa). For example:

¬(A ∧ B) = ¬A ∨ ¬B

¬(A ∨ B) = ¬A ∧ ¬B

Double Negation

When something is NOTed twice (negated twice), the NOTs cancel out. So ¬¬B = B and ¬¬(A ∨ B) = (A ∨ B).

Truth Tables

Truth tables are a great way to visualize the inputs and outputs of a Boolean expression. Basically, you list all of the possible inputs and then you list the corresponding outputs for the given inputs. For example, below is the truth table for A ∧ B.

A

B

A ∧ B

F

F

F

F

T

F

T

F

F

T

T

T

Putting It All Together

Now lets say we want to know when A is true or B is true, but not when both A and B are true. This is called an exclusive-or or an XOR for short. The first step is to draw the truth table for this so we can see our inputs and outputs.

A

B

A ∨ B

F

F

F

F

T

T

T

F

T

T

T

F

Now we know what we want to see happen. Let’s now write the exact conditions when we get T in the output. We get it when A ∧ ¬B or when ¬A ∧ B. If we do full binary arithmetic we get:

(A ∧ ¬B) ∨ (¬A ∧ B)

Now to use this, we need to convert it to Lisp. We use the same conversion procedure we do for mathematical equations, as outlined below.

  1. ((A ∧ (¬B)) ∨ ((¬A) ∧ B))
  2. (∨ (∧ A (¬B)) (∧ (¬A) B))
  3. (or (and A (not B)) (and (not A) B))

Our final result is (or (and A (not B)) (and (not A) B)).

Combining it All with Comparisons

Now we will replace the arbitrary inputs A and B from the above example with actual inputs. Let’s say we want A to be true when 3 is less than 5 and B to be true when 9 is less than 7. We could replace (< 3 5) everywhere that we find an A and (< 9 7) everywhere that we find a B, but that takes a lot of work and it’s hard to read. Instead, we’re going to create a variable called A that’s equal to (< 3 5) and a variable called B that’s equal to (< 9 7). Using the information from  Creating Temporary Variables we get the following Lisp:

(let[A (< 3 5) B (< 9 7)] (or (and A (not B)) (and (not A) B)))

Note that if you invert an expression with a comparison, it inverts the comparison as well. For example, the inverse of less-than (<) is greater than or equal to (>=) and the inverse of greater than (>) is less than or equal to (<=). This can be thought of as including all of the numbers not included in the original comparison. (For example, if we have x < 5 and we invert it, we want all x’s that are not less than 5, which includes 5, 6, 7, and so on to infinity, so we would have x ≥ 5.)

Below is a list of all of the comparison operators and their opposites.

=

not=

not =

=

<

>

>

<

If you wish to learn more about Boolean arithmetic, go to  https://en.wikipedia.org/wiki/Boolean_algebra.


How did we do?


Powered by HelpDocs (opens in a new tab)