teaching machines

Power Set of Venn Diagrams

In our introductory programming class, I try to reframe abstract logic into concrete spatial thinking. One way I do this is through the game Trux Falsy. Another way is through Venn diagrams. I want students to see how the AND operator creates an intersection, how the OR operator creates a union, and how DeMorgan’s Law flips an expression.

To support a visualization exercise in lecture today, I wrote this short Twoville program that generates all possible Venn diagrams for a 2-term boolean expression:

There are four regions in a two-term Venn diagram: the aMinusB region, the bMinusA region, the both region, and the neither region. In the code above, the venn function accepts a bit for each of these four regions. Each is colored according to its bit. With 4 regions, each either selected or unselected, we have $2^4 = 16$ possible diagrams.

When I first coded it up, I manually called the venn function with all possible bit configurations for these four regions:

// the parameters: aMinusB, bMinusA, both, neither, column, row

venn(0, 0, 0, 0, 0, 0)
venn(1, 0, 0, 0, 1, 0)
venn(0, 1, 0, 0, 2, 0)
venn(1, 1, 0, 0, 3, 0)

venn(0, 0, 1, 0, 0, 1)
venn(1, 0, 1, 0, 1, 1)
venn(0, 1, 1, 0, 2, 1)
venn(1, 1, 1, 0, 3, 1)

venn(0, 0, 0, 1, 0, 2)
venn(1, 0, 0, 1, 1, 2)
venn(0, 1, 0, 1, 2, 2)
venn(1, 1, 0, 1, 3, 2)

venn(0, 0, 1, 1, 0, 3)
venn(1, 0, 1, 1, 1, 3)
venn(0, 1, 1, 1, 2, 3)
venn(1, 1, 1, 1, 3, 3)

During a refactoring, I decided to simplify this code by iterating through [0, 15] and extracting out the individual bits from the iterator. Twoville doesn’t yet support the shifting and masking operators, which are the usual means of extracting bits, and I was just about to add them. But then I thought, “Why not add the subscript operator to integers?” bitfield[0] would yield bit 0, bitfield[1] would yield bit 1, and so on.

Four lines of code later, I was able to condense my calls down to this:

for i to 16
  venn(i[0], i[1], i[2], i[3], i % 4, i / 4)

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *