Ruby’s String#delete and Boolean Algebra

How can learning about the String#delete method in Ruby help us understand Boolean Algebra?

It starts with a misuse of gsub

I cannot tell you how many times have I written code like

'abc-de'.gsub('-','')

when I could have just written

'abc-de'.delete('-')

facepalm

Fortunately, Stack Overflow was there to educate me. Not only is delete more semantic and concise than gsub for removing a single character, it gets even better with more complex deletions.

Delete with Multiple Characters

Imagine that you are working with a long string, maybe one containing the alphabet.

alphabet = 'abcdefghijklmnopqrstuvwxyz'

If you wanted to remove all of the vowels, starting with what we’ve seen from delete so far, you could do something atrocious like:

alphabet.delete('a').delete('e').delete('i').delete('o').delete('u')
# => 'bcdfghjklmnpqrstvwxyz'

Fortunately, the developers of Ruby provide a much simpler approach for this use case. Instead of chaining all these method calls together, you can pass all of the characters at once, and delete will remove any matches.

alphabet.delete('aeiou')
# => 'bcdfghjklmnpqrstvwxyz'

When executing alphabet.delete('aeiou'), we are not deleting the string 'aeiou' from alphabet; that string does not exist as a substring of alphabet. Instead, we are deleting any element from the set of letters {a,e,i,o,u}.

Consequently, if you did want to delete a substring from alphabet, e.g. ‘lmnop’, I would recommend using slice!.

Delete with Multiple Parameters

A feature that makes delete even cooler is how it handles multiple parameters. Working with the same alphabet string, imagine you now want to remove all of the letters that satisfy both of the following criteria:

1. Is a vowel
2. Is in the first quartile of the alphabet (i.e. a-g)

delete is perfect for this! While delete treats a single argument string as a set of characters, when supplied with multiple argument strings, delete will remove the intersection of those sets.

Remember an intersection (∩) is like AND, whereas a union (⋃) is like OR; more on this later

First, let’s take a look at delete handling each of our criteria independently.

vowels = 'aeiou'
first_quartile = 'abcdefg'
alphabet.delete(vowels)
# => 'bcdfghjklmnpqrstvwxyz'
alphabet.delete(first_quartile)
# => 'hijklmnopqrstuvwxyz'

Now let’s see what happens when we supply both strings as arguments to delete.

alphabet.delete(vowels, first_quartile)
# => 'bcdfghijklmnopqrstuvwxyz'

The only letters deleted from alphabet were ‘a’ and ‘e’, because they were the only letters that appeared in all of the strings passed as parameters. That is equivalent to the intersection of the sets of characters represented by our two argument strings.

{a,e,i,o,u} ∩ {a,b,c,d,e,f,g} = {a,e}

Interestingly, the result of using delete with both arguments is the same as the union of the results of using delete with each of the arguments independently, once sorted.

{b,c,d,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z} = {b,c,d,f,g,h,j,k,l,m,n,p,q,r,s,t,v,w,x,y,z} ⋃ {h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}

Expressed another way, deleting the intersection of vowels and first_quartile is equal to the union of deleting vowels and deleting first_quartile.

# Call split so we can use Array's intersection (&) and union (|) operators
intersection = alphabet.delete(
  (
    vowels.split('') & 
    first_quartile.split('')
  ).join
)
# => "bcdfghijklmnopqrstuvwxyz"
union = (
  alphabet.delete(vowels).split('') |     
  alphabet.delete(first_quartile).split('')
).sort.join
# => "bcdfghijklmnopqrstuvwxyz"
intersection == union
# => true

.sort is necessary since union concatenates the two arrays

I think that code got really confusing really fast. But if we replace alphabet.delete with !, and remove the array methods for simplicity, we are left with:

!(vowels && first_quartile) == !vowels || !first_quartile

Simplified to the general case, that would look like

!(A && B) == !A || !B

That’s pretty neat! And it makes a lot of sense if we think about it from a Boolean Algebra perspective.

For more about delete, check out the documentation.

Boolean Algebra

If you’ve been writing code for any time at all, you are probably familiar with the boolean — a data type that can have either a true or false value (sometimes represented as 1 or 0, respectively). Boolean Algebra, then, is the branch of algebra dealing with booleans. It is fundamental to understanding the construction of logical conditions. The properties of Boolean Algebra — its operations, identities, and laws — are often reminiscent of those in arithmetic.

Boolean Algebra is the branch of algebra in which the values of the variables are the truth values ‘true’ and ‘false’, usually denoted 1 and 0 respectively

We are going to talk about a few boolean operations, focusing on the operators AND, OR, and NOT. Here is a glossary of symbols, each of which you might encounter depending on the source. The “Style” is not actual nomenclature, but rather my way of referring to the area of study where you are most likely to encounter each group of symbols.

+-------+-----+-----+-----+
| Style | AND | OR  | NOT |
+-------+-----+-----+-----+
| Set   | A∩B | A⋃B |  Ā  | 
| Code  | A&B | A|B | !A  |
| Math  | A·B | A+B | ~A  |
| Logic | A∧B | A∨B | ¬A  |
|       |     |     |  A' |
+-------+-----+-----+-----+

Note: In code the logical AND (&) and OR (|) operators are often doubled (&&, ||) to differentiate from bitwise operators.

These three primary operations are analogous to Intersection (AND), Union (OR), and Complement (NOT).

Let’s see an example. If I say “my car is red (R) and fast (F)”, is that true? We can determine the veracity of the statement as a whole with a truth table, a table that lists all possible values for the inputs (R, F) and the resulting output (R & F).

+-------++-------+
| R | F || R & F |
+---+---++-------+
| 0 | 0 ||   0   | // not red, not fast -> not red and fast
| 0 | 1 ||   0   | // not red, fast -> not red and fast
| 1 | 0 ||   0   | // red, not fast -> not red and fast
| 1 | 1 ||   1   | // red, fast -> red and fast
+---+---++-------+

My car is only “red and fast” if it is both red and fast. So far, this just sounds like common sense. But something else to notice is that, if you look at my car and see it is blue, you know my car is not “red and fast” without even seeing how fast it is. In coding, this is called “short-circuiting,” meaning that if any part of an AND condition is false, the entire condition is false and the rest of the condition does not need to be evaluated.

+-------++-------+
| R | F || R & F |
+---+---++-------+
| 0 | x ||   0   | // not red, unknown fast -> not red and fast
| x | 0 ||   0   | // unknown red, not fast -> not red and fast
| 1 | 1 ||   1   | // red, fast -> red and fast
+---+---++-------+

On the other hand, what if I said “my car is red or fast.”

+-------++-------+
| R | F || R | F |
+---+---++-------+
| 0 | 0 ||   0   | // not red, not fast -> not red or fast
| 0 | 1 ||   1   | // not red, fast -> red or fast
| 1 | 0 ||   1   | // red, not fast -> red or fast
| 1 | 1 ||   1   | // red, fast -> red or fast
+---+---++-------+

Now, as long as my car is red, it is “red or fast,” regardless of the speed. Again, we can short-circuit the evaluation of this statement, because if any part of an OR condition is true, the entire condition is true and the rest of the condition does not need to be evaluated.

+-------++-------+
| R | F || R | F |
+---+---++-------+
| 0 | 0 ||   0   | // not red, not fast -> not red or fast
| x | 1 ||   1   | // unknown red, fast -> red or fast
| 1 | x ||   1   | // red, unknown fast -> red or fast
+---+---++-------+

More formally, these properties are codified in the Identity and Annihilator Laws.

Identity for ∧: 𝓍 ∧ 1 = 𝓍
Identity for ∨: 𝓍 ∨ 0 = 𝓍
Annihilator for ∧: 𝓍 ∧ 0 = 0
Annihilator for ∨: 𝓍 ∨ 1 = 1

Knowing the four Identity and Annihilator laws will get you through most of the logic you’ll ever need for coding. However, with Ruby, which provides convenient logical complements such as if and unless, select and reject, or any? and none?, I think it helps to understand my favorite pair of laws of Boolean Algebra: De Morgan’s Laws.

De Morgan’s Laws

De Morgan’s Laws are “a pair of transformation rules…[that] allow the expression of conjunctions and disjunctions purely in terms of each other via negation,” as follows.

Negation of a disjunction: ¬(A ∨ B) = (¬A) ∧ (¬B)
Negation of a conjunction: ¬(A ∧ B) = (¬A) ∨ (¬B)

Here it is again “in English”:

the complement of the union of two sets is the same as the intersection of their complements; and the complement of the intersection of two sets is the same as the union of their complements.

To translate into Ruby:

• When you read ‘complement’ think ! (NOT)
• When you read ‘union’ think || (OR)
• When you read ‘intersection’ think && (AND)

Which gives us:

!(A || B) == !A && !B
!(A && B) == !A || !B

Just like we saw above!

Deleting Without Delete

To see De Morgan’s Laws in action, we can try a homegrown implementation of delete using the Enumerable methods select and reject.

alphabet.split('').select {|c| !vowels.include?(c) || !first_quartile.include?(c) }.join
# retain the letters that are either NOT in vowels OR NOT in first_quartile
alphabet.split('').reject {|c| vowels.include?(c) && first_quartile.include?(c)}.join
# discard the letters that are in BOTH vowels AND first_quartile

Since the String class does not include the Enumerable module, we first use split to convert the alphabet to an array of characters; join is used to reassemble the remaining characters back into a string.

With select, we want to keep any letter that is either NOT in vowels or NOT in first_quartile; whereas with reject, we want to discard any letter that IS in both of the strings. Because select and reject are complements of each other, their conditions should be logical inverses of each other as well. This can easily be demonstrated with a trivial exercise.

arr = [1,2,3,4,5]
arr.reject {|a| a.odd?} == arr.select {|a| !a.odd?}
# => true

Going back to our alphabet example, we should be able to demonstrate

# !(reject_condition) == select_condition
!(vowels.include?(c) && first_quartile.include?(c)) == !vowels.include?(c) || !first_quartile.include?(c)

If we replace vowels.include?(c) with A and first_quartile.include?(c) with B, we get

!(A && B) == !A || !B

Et voila! Is this starting to look familiar yet?

Keeping De Morgan’s Laws in mind allows you to switch freely between select and reject, or other logical complements. You may find this helps you convert your logical expressions into something more intuitive. Is it easier for you to wrap your head around one code snippet over the other? (For me, reject makes a lot more sense in this case.)

More Truth Tables and Karnaugh Maps

As with the “fast and red car” example, we can use a truth table for our alphabet expression. In this case, to be consistent with what we’ll see later, we are using slightly different notation; !A || !B becomes A' + B' and !(A && B) becomes '(A·B) or simply '(AB).

+-------++---------+-------+----+
| A | B || A' + B' | '(AB) | AB |
+---+---++---------+-------+----+
| 0 | 0 ||    1    |   1   | 0  |
| 0 | 1 ||    1    |   1   | 0  |
| 1 | 0 ||    1    |   1   | 0  |
| 1 | 1 ||    0    |   0   | 1  |
+---+---++---------+-------+----+

The truth table confirms what we already demonstrated with boolean algebra — that the expressions A' + B' and '(AB) are equivalent, and both are the inverse of AB.

Finally, we can use a tool called a Karnaugh Map, or K-map, to approach this problem from a slightly different angle. A K-map is useful for mapping a set of requirements to the desired logical outcomes, to derive a logical expression satisfying the requirements. Furthermore, if you already have a logical expression, K-maps can sometimes help you find a simpler expression that yields the same results. It is akin to a truth table, but laid out in a sort of grid.

+---------------+
|       |   A   |
+       +---+---+
|       | 0 | 1 | <- Input values for A
+---------------+
| B | 0 |   |   | <- Results (to be determined)
|   | 1 |   |   | 
+---+---+---+---+
      ^
Input values for B

So once again, let’s say that we want to keep the letters in the string alphabet that are either not in vowels (A) or not in first_quartile (B). The K-map is filled out by evaluating our various inputs and filling in the corresponding outputs.

• If A is false (0) and B is false (0), the letter is not in vowels and not in first_quartile, and therefore should be kept in our string (1).

+---------------+
|       |   A   |
+       +---+---+
|       | 0 | 1 | <- Input values for A
+---------------+
| B | 0 | 1 |   | <- Results
|   | 1 |   |   | 
+---+---+---+---+
      ^
Input values for B

• If A is true (1) and B is false (0), the letter is in vowels but not in first_quartile, and should be kept in our string (1).

+---------------+
|       |   A   |
+       +---+---+
|       | 0 | 1 | <- Input values for A
+---------------+
| B | 0 | 1 | 1 | <- Results
|   | 1 |   |   | 
+---+---+---+---+
      ^
Input values for B

• If A is false (0) and B is true (1), the letter is not in vowels but is in first_quartile, and should be kept in our string (1).

+---------------+
|       |   A   |
+       +---+---+
|       | 0 | 1 | <- Input values for A
+---------------+
| B | 0 | 1 | 1 | <- Results
|   | 1 | 1 |   | 
+---+---+---+---+
      ^
Input values for B

• Finally, if A is true (1) and B is true (1), the letter is in vowels and is also in first_quartile, and thus should not be kept in our string (0).

+---------------+
|       |   A   |
+       +---+---+
|       | 0 | 1 | <- Input values for A
+---------------+
| B | 0 | 1 | 1 | <- Results
|   | 1 | 1 | 0 | 
+---+---+---+---+
      ^
Input values for B

Now that the K-map has been filled out, the goal is to find the minimum number of maximum (largest) groupings that cover all true outcomes, as illustrated below (sometimes this is much simpler than others).

a Karnaugh Map for A’ + B’

The groupings represent logical expressions.

• The red rectangle in the image above corresponds to A = 0, or A’
• The blue rectangle in the image corresponds to B = 0, or B’.
• Even though both rectangles cover the condition A=0, B=0, this duplication is preferable as it yields a simpler logical expression.

To combine both predicates, we use a union, yielding A’ + B’ (hence K=A'+B' in the image); the complement is also listed, K’=AB. Once again, this is consistent with what we saw before!

!A || !B == !(A && B)

Boolean algebra is just one of the many topics engineers at Def Method chat about in our free time. If you’re facing a technical challenge, we’d love to work with you. And we’re hiring!