Learning to Program – A Beginners Guide – Part Eleven – More With Functions and Logic in F#: Minimizing Boolean Expressions
We left off with a couple of exercises last time.
Exercise 1: Remember the exercises in our first introduction to algorithms? Can you implement functions in F# for the sum of an arithmetic series and the sum of a geometric series?
Remember that this is the formula for an arithmetic series:
where \(d\ \) is the difference between each term, \(m\ \) is the index of the first term in the progression that we want to include in the sum, and \(n\ \) is the index of the last term we want to include; \(a\_m\ \) is the value of the first term, and \(a\_n\ \) is the value of the last term.
So, for the progression 1, 3, 5, 7, 9, 11
\(d\ \) is 2
\(m\ \) is 1 (from the 1st term)
\(n\ \) is 6 (to the 6th term)
\(a\_m\ \) is 1
\(a\_n\ \) Is 11
We could define this function in F# as follows:
let arithmeticseries m n am an = (((n - m) + 1) * (am + an)) / 2
We've defined it with 4 parameters - a record, and bound it to an identifier called arithmeticseries (although, of course, we could have picked any name we liked).
What do you think F# will respond for this definition?
val arithmeticseries : m:int -> n:int -> am:int -> an:int -> int
So, this is a function that takes an integer, and returns a function that takes an integer and returns a function that takes and integer and returns a function that takes an integer and returns an integer! A bit of a mouthful, but the same pattern as our "two parameter" function, and no more difficult to deal with!
Let's try out our function on our example progression (whose sum is, incidentally 1+3+5+7+9+11=36)
arithmeticseries 1 6 1 11
val it : int = 36
Looks good! Let's move on to the second part of this exercise, the geometric progression.
Remember that a geometric progression is one in which each term is a constant multiple of the previous term: \(a\ \) , \(ar\ \) , \(ar^2\ \) , \(ar^3\ \) ... \(ar^n\ \)
For example \(3, 6, 12, 24, 48\ \) is a geometric sequence where \(a=3, r=2\ \) and its sum is 93.
The formula for the sum of a geometric progression where a is the value of the first term in the sequence, and r is the constant multiplier is:
In the hints for this exercise, we mentioned a function called pown which raises one value to the power of another. Let's use that that to translate that formula into the definition of a function for a geometric series.
let geometricseries m n a r = (a * (1 - pown r ((n - m) + 1))) / (1 - r)
F# responds
val geometricseries : m:int -> n:int -> a:int -> r:int -> int
Now we can test it out.
geometricseries 1 5 3 2
val it : int = 93
Did you get that? If so, that's definitely a moment of triumph. You've translated a fairly complex mathematical formula into a neat little function in F#. If not, go back and see how the F# function definition maps on to the mathematical expression. Don't forget that the pown function is applied to the parameter(s) immediately to its right. Once you've worked it out, take a few seconds to bask in the moment triumph, then move on!
Exercise 2: Another derived Boolean operator is called the** equivalence **operator. It is true if the two operands are equal, otherwise it is false. First, draw out the truth table for the equivalence operator. Then, work out a compact Boolean expression for it. Finally, implement the equivalence operator as an F# operator.
Here's the truth table for the equivalence operator (for which we use the symbol \(\\equiv\ \) )
\(x\ \)
\(y\ \)
\(x \\equiv y\ \)
true
true
true
false
true
false
true
false
false
false
false
true
Compare this with the truth table for XOR
\(x\ \)
\(y\ \)
\(x \\oplus y\ \)
true
true
false
false
true
true
true
false
true
false
false
false
Can you see that \(x \\equiv y = \\lnot(x \\oplus y)\ \) ?
This gives us a big hint as to how we could implement it - by applying the not operator to our Boolean expression for XOR.
\(x \\equiv y = \\lnot((x \\lor y) \\land \\lnot(x \\land y))\ \)
We could write that in F# as:
let (|==|) x y = not ((x || y) && not (x && y))
F# responds as you might expect for a standard "two parameter" function:
val ( |==| ) : x:bool -> y:bool -> bool
(You might have picked a different identifier for your operator, of course - the choice is yours.)
Let's test that out by reproducing the truth table.
true |==| true
val it : bool = true
true |==| false
val it : bool = false
false |==| true
val it : bool = false
false |==| false
val it : bool = true
So far so good! It works, but it is a little more unwieldy than the XOR definition - we've added an extra term. Given that they are so similar, should it not be possible to express equivalence just as succinctly as we did XOR? The answer is yes, but to do that, we need to learn some more of the rules of Boolean algebra.
Laws of algebra
In regular maths, you're probably so familiar with the rules of algebra, that you don't even think about them as being laws at all, just "the way things are". But there's nothing magic about them - they're just rules people have made up to try to create a consistent system of mathematics. Brace yourself. There's a lot of detail coming up, so take it slowly and experiment with the rules as we come across them.
Two of the most familiar are called associativity and commutativity. Don't be put off by the names if you haven't heard them before - you'll recognize them when you see them. Here's an example of the law of associativity for addition.
\(x+(y+z) = (x+y)+z\ \)
You're probably thinking "well, obviously!". We saw a similar example when we were talking about operator precedence. If so, good - this should be obvious!
Spot test: give an example of the law of associativity for multiplication.
Answer:
\(x \\times (y \\times z) = (x \\times y) \\times z\ \)
Now, commutativity. This is the idea that the ordering of the operands doesn't matter. Here's an example for addition.
\(x + y = y + x\ \)
Spot test: give an example of the law of commutativity for multiplication.
Answer:
\(x \\times y = y \\times x\ \)
Again, you're probably thinking that this is painfully obvious stuff.
OK - so let's look at something a bit more complicated. What about distributivity? This is the idea that multiplication "distributes" over addition - like this:
\(x \\times (y+z) = (x \\times y) + (x \\times z)\ \)
Spot test: Does addition distribute over multiplication?
Answer: No, it doesn't
\(x + (y \\times z) \\not= (x + y) \\times (x + z)\ \)
Another law is called identity. This is the notion that there is some operation that results in the original operand.
Here's the identity law for addition.
\(x + 0 = x\ \)
Spot test: what is the identity law for multiplication?
Answer:
\(x \\times 1 = x\ \)
One last common law is the annihilator for multiplication. If you multiply anything by zero, you get zero.
\(x \\times 0 = 0\ \)
Notice how this "annihilates" the term \(x\ \) from the result.
We use these rules all the time to help us manipulate algebraic expressions. Remember when we were trying to derive a formula for an arithmetic progression? Amongst other things, we specifically used the fact that we could write the whole expression forwards or backwards, and that this would be equivalent - this relied on commutativity.
In our previous section on Boolean logic, we noted that the Boolean operator \(\\land\ \) is broadly equivalent (in regular algebra) to multiplication, and the operator \(\\lor\ \) is equivalent to addition. This similarity holds true for all of these laws, for which there are equivalents in Boolean algebra.
Spot test: can you write out the laws of associativity, commutativity, distributivity, identity and annihilation for the Boolean operators \(\\land\ \) and \(\\lor\ \) ?
Answer:
Associativity
\(x \\land (y \\land z) = (x \\land y) \\land z\ \)
\(x \\lor (y \\lor z) = (x \\lor y) \\lor z\ \)
Commutativity
\(x \\land y = y \\land x\ \)
\(x \\lor y = y \\lor x\ \)
Distributivity
\(x \\land (y \\lor z) = (x \\land y) \\lor (x \\land z)\ \)
Identity
\(x \\land 1 = x\ \)
\(x \\lor 0 = x\ \)
Annihilation
\(x \\land 0 = 0\ \)
Did you get that lot? Take a moment of triumph! If not, go back and look at the laws for regular algebra, and the equivalence of AND and multiplication, OR and addition, and see if you can work them out.
With practice, these laws of Boolean algebra will become just as 'obvious' as their equivalents in regular algebra. As usual, the laws aren't complicated, but the symbols take some getting used to.
Of course, Boolean algebra is not exactly equivalent to the algebra you already know. It adds a few laws of its own.
First, there's idempotence. This is the idea that if the inputs to the operator are the same, then the output is the same as the input.
\(x \\land x = x\ \)
\(x \\lor x = x\ \)
This is very different from the equivalent expressions in regular algebra, where
\(x \\times x = x^2\ \)
\(x + x = 2x\ \)
(So multiplication and division are not idempotent!)
Another law is called absorption. Let's have a look at the expressions, and you'll see why it got that name.
\(x \\land (x \\lor y) = x\ \)
\(x \\lor (x \\land y) = x\ \)
It is as if the AND operator "absorbs" the OR expression that follows (and vice-versa).
There's also a wrinkle with distribution. A minute ago, we saw how in regular arithmetic, multiplication distributed over addition
\(x \\times (y + z) = (x \\times y) + (x \\times z)\ \)
And in Boolean algebra, the equivalent AND distributes over OR
\(x \\land (y \\lor z) = (x \\land y) \\lor (x \\land z)\ \)
And while addition doesn't distribute over multiplication...
\(x + (y \\times z) \\not= (x + y) \\times (x + z)\ \)
In Boolean algebra, OR does distribute over AND
\(x \\lor (y \\land z) = (x \\lor y) \\land (x \\lor z)\ \)
Another place in which Boolean algebra is more symmetrical than the algebra we know and love is annihilation. There is also an annihilator for OR, as well as the one for AND.
\(x \\land 0 = 0\ \)
\(x \\lor 1 = 1\ \)
Still with me? We're nearly done; there's one more set of laws to look at. We've covered AND and OR, addition and multiplication, but we've not yet had anything to say about negation.
As usual, the laws of multiplying and adding with negation in regular algebra are so familiar they seem to be stating the obvious.
\((-x) \\times (-y) = xy\ \)
\((-x) + (-y) = -(x + y)\ \)
\(-(-x) = x\ \)
The first is the familiar "two negatives make a positive" rule for multiplication, the third is "double negation". The second tells us that adding together two negated values is equivalent to adding together the two values and negating the result.
But in Boolean logic, the basic rules are a bit different, and called complementation.
\(x \\land \\lnot x = 0\ \)
\(x \\lor \\lnot x = 1\ \)
\(\\lnot(\\lnot x ) = x\ \)
We can also write down a couple of rules derived from these laws of complementation called de Morgan's laws. These are really interesting because they allow us to express the AND operator purely in terms of the OR operator and negation; and vice-versa.
\((\\lnot x ) \\land (\\lnot y ) = \\lnot(x \\lor y)\ \)
\((\\lnot x ) \\lor (\\lnot y ) = \\lnot(x \\land y)\ \)
Now - let's go back to where we started and look at our expression for the equivalence operator.
\(x \\equiv y = \\lnot((x \\lor y) \\land \\lnot(x \\land y))\ \)
If we say
\((x \\lor y) = a\ \)
and
\(\\lnot(x \\land y) = b\ \)
Then we could rewrite this as
\(x \\equiv y = \\lnot(a \\land b)\ \)
But looking at de Morgan's laws above, we can see that this is equivalent to
\(x \\equiv y = (\\lnot a) \\lor (\\lnot b)\ \)
Now
\(\\lnot a = \\lnot(x \\lor y)\ \)
and
\(\\lnot b = \\lnot(\\lnot(x \\land y))\ \)
We know the rule for double negation - it is one of our complementation rules above. So it follows that
\(\\lnot b = x \\land y\ \)
We can substitute this back into our equation
\(x \\equiv y = \\lnot (x \\lor y) \\lor (x \\land y)\ \)
Remember our original expression for XOR?
\(x \\oplus y = (x \\lor y) \\land \\lnot(x \\land y) \ \)
We can use the law of commutativity to swap our expression for equivalence into the same form:
\(x \\equiv y = (x \\land y) \\lor \\lnot(x \\lor y)\ \)
This is clearly simpler than the original form, and we say that we have minimized the expression.
When you get used the laws, you could have done this in one quick step; you'd remember de Morgan's laws, negate the two terms either side of the central AND operator, and flip the operator from AND to OR. This is probably the most common day-to-day Boolean minimization you'll carry out on real-world expressions.
Let's check that it is still correct by implementing it in F#.
Spot test: Can you implement this new form for the equivalence operator in F#?
Answer:
let (|==|) x y = (x && y) || not (x || y)
F# responds with
val ( |==| ) : x:bool -> y:bool -> bool
So the form of our operator is, of course, still correct. Let's check that it does what we expect!
true |==| true
val it : bool = true
true |==| false
val it : bool = false
false |==| true
val it : bool = false
false |==| false
val it : bool = true
Systematic approaches to minimization
There are various systematic approaches to minimization - from the repeated application of these laws of algebra, to something called a Karnaugh Map.
One simple way to minimize a function is to apply the law of complementation. Specifically, you look to rearrange any Boolean expression to generate terms that look like this:
\(x \\lor \\lnot x = 1\ \)
Those terms can then be immediately eliminated.
For example, consider this slightly brain-bending expression:
\((x \\land y \\land \\lnot z) \\lor (\\lnot x \\land y \\land \\lnot z)\ \)
We can rearrange this to something much simpler
\(y \\land \\lnot z\ \)
No - really; we can! First let's say
\(a = y \\land \\lnot z\ \)
We can then rewrite the first expression as
\((x \\land a) \\lor (\\lnot x \\land a)\ \)
Applying our law of commutativity on each term, this is the same as
\((a \\land x) \\lor (a \\land \\lnot x )\ \)
We recognize this as an example where our distribution law \(x \\land (y \\lor z) = (x \\land y) \\lor (x \\land z)\ \) applies, so that becomes
\(a \\land (x \\lor \\lnot x )\ \)
And since
\(x \\lor \\lnot x = 1\ \)
This becomes
\(a \\land 1\ \)
Substituting the value of a back in, we get
\((y \\land \\lnot z) \\land 1 \ \)
Which is just
\(y \\land \\lnot z\ \)
We went from the brain bending \((x \\land y \\land \\lnot z) \\lor (\\lnot x \\land y \\land \\lnot z)\ \) to the simple \(y \\land \\lnot z\ \) in a few sort-of-easy steps.
Let's check that they're actually the same, using F# to build the two truth tables. First for the complex expression.
Spot test: create an F# function to implement \((x \\land y \\land \\lnot z) \\lor (\\lnot x \\land y \\land \\lnot z)\ \) , and then build the truth table for the expression.
Answer:
let expression1 x y z = (x && y && not z) || (not x && y && not z)
x
y
z
1
1
1
0
1
1
0
1
1
0
1
0
1
0
0
0
0
1
1
0
0
1
0
1
0
0
1
0
0
0
0
0
Notice how the results in the truth table don't depend on the value of x at all - this is a good sign that we can eliminate x entirely.
Let's try our second expression
Spot test: create an F# function to implement \(y \\land \\lnot z\ \) , and then build the truth table for the expression.
Answer:
let expression2 y z = y && not z
y
z
1
1
0
1
0
1
0
1
0
0
0
0
Success!
Why minimize a Boolean expression?
This is an excellent question. You'll often hear arguments that it is "more efficient" to minimize the expression - but for anything but the most extraordinary expressions (or implementation in discrete electronic components) this is a bit of a side issue.
The usual reason to minimize is to make it more comprehensible. Human brains are not great at double negatives and extremely long chains of reasoning, so a compact expression is generally more understandable.
However, this can also be a good reason not to minimize. If you have well-defined clauses (wrapped in parentheses and indented neatly) that mean something obvious individually, then it may be better to leave them un-minimized.
In the case of the equivalence operator, you might make the argument that the expanded version made it clear that it was the complement of the XOR operator - but I think that argument is a little weak. The minimized version is simple to read, and the two expressions are recognizably similar. When you get used to Boolean algebra, you will also recognize that they have the form of complementary expressions: they are otherwise identical, but all the ANDs and ORs are swapped around.
In the second example, the benefits of minimization were clear - we eliminated one entire variable, and made the expression much simpler to read.
So, the general rule for minimization is to make it as compact and understandable as possible.
OK, that was a lot of information. There's no substitute for some practice with this stuff. For most developers, the rules of logic eventually become second nature, just like the ones for regular algebra. (So much so, that they often forget that they've learned them!)
With that in mind, here are a couple of exercises. The answers are at the bottom of the page.
Exercise 1: Minimize the following Boolean expressions
\((x \\lor \\lnot y) \\land (z \\land \\lnot y)\ \)
\(\\lnot ((x \\lor y) \\land (z \\lor \\lnot y))\ \)
\((x \\land \\lnot y) \\lor \\lnot ((x \\lor y) \\land (z \\lor \\lnot y))\ \)
Exercise 2: Implement F# functions for the expressions above (both minimized and as originally stated), and verify their truth tables.
Answers to exercises
Exercise 1
\(\\lnot y \\land z\ \)
\((\\lnot x \\land \\lnot y) \\lor (y \\land \\lnot z)\ \) , or alternatively, \((\\lnot x \\lor y) \\land (\\lnot y \\lor \\lnot z)\ \)
\(\\lnot y \\lor \\lnot z\ \)
Exercise 2
a1) let exa1 x y z = (x || not y) && (z && not y)
a2) let exa2 y z = not y && z
b1) let exb1 x y z = not ((x || y) && (z || not y))
b2) let exb2 x y z = (not x && not y) || (y && not z) or (not x || y) && (not y || not z)
c1) let exc1 x y z = (x && not y) || not ((x || y) && (z || not y))
c2) let exc2 y z = (not y) || (not z)
