Unit Review for boolean algebra

Question

Background:

This is the first unit in junior year for a course in theoretical computer science. Prior to this, the students have already had AP CS A and a mish-mash of other topics. They have, by this point, studied:

1. Python (as their introduction to programming)
2. Java for AP CS A (loops, arrays, object design, recursion, polymorphism)
3. 6502 Assembly (for stack operation, including recursion again)
4. C (largely for pointers)
5. Additional things in Java (e.g. trees, linked lists, tries, Hashmaps, generics) and some algorithms (such as BFS, DFS, Huffman Encoding, Conway's Game of Life, Prim's, etc)

This course, then, is a year of theoretical computer science. The first unit is background mathematics that they will need during the rest of the course, and it focuses on boolean algebra and sets. The requested Unit Review here is for my boolean algebra opening.

The general goals are to help the students gain serious familiarity with algebraic manipulations and with the symbols themselves. After these lessons, we will move onto Conjunctive and Disjunctive Normal Forms, fairly substantial algebraic manipulations involving 5-10 steps, and then into logic gates for a gentle introduction to computer circuitry, so it is important that they come out prepared for that.

Word of warning: The unit below has some serious weaknesses, as you will see. Please be gentle! This year will be my second time giving these lessons, and while I have made a series of improvements from what I did this last September, there is still a long way to go. There is a lot of lecture, and I would really like to make it more engaging when I do it again27.

The Curriculum

Lesson one:

We begin our foray into boolean algebra by converting our Java boolean symbols to formal math symbology: && to $\land$, || to $\lor$, and ! to $\lnot$. We then discuss how != is essentially $\oplus$, and begin our discussion of $\Longleftrightarrow$ as being a near approximation of == (with a promise that we will come back to this again, because we are not done with it yet).

We then introduce tautologies (such as $B \lor \lnot B$), and go over their truth tables. I finally provide them with an extremely short homework worksheet where they have to circle the boolean statements that are tautologies. (It also provides practice with all of the symbols we have discussed)

Lesson two:

We review lesson 1, and then introduce the concept of contradictions as the opposite of tautologies, go over their truth tables, and look at the obvious contradiction $B \land \lnot B$.

I ask them to create two tautologies with a partner, the more creative the better, walk around, and ask for a number of students to write interesting ones on the board.

We move on to $A \Rightarrow B$, discuss its meaning and truth table, and then ask what in Java is similar? I first propose:

 if (A)
     B = true;

We talk about this for awhile, and talk about why, though it may seem like a reasonable choice at first, it is not really the same idea. We then spend some time on the hardest idea of implies: what we mean when we say that $False \Rightarrow True$ is $True$.

At this point, I take a break to introduce the way I approach proofs in this class. Over the course of the year, certain very important proofs must be reproduced by a student chosen at random during the following period. This forces the students not to ignore these proofs, and helps them to internalize both the mathematical symbols that I need them to gain fluency with, and some very clever proof techniques.

I spend a substantial chunk of time then doing a formal proof that $False \Rightarrow True \equiv True$. I finish the class with a second, informal, and intuitive proof of the same (which they will not need to reproduce.)

Lesson 3:

We review from the prior day, and a student is called up to reproduce the proof.

We then spend about 15 minutes going over necessary and sufficient in depth, and re-examine both $\Longleftrightarrow$ and $\Rightarrow$ through this new lense. During this process, I introduce $\Longleftrightarrow$ more properly as $(A \Rightarrow B) \land (A \Leftarrow B)$ and as iff, and we talk about the similarities that $\Longleftrightarrow$ shares with $\equiv$.

I go over DeMorgan's Laws, and briefly cover 5 more symbols: ∀, ∃, |, ∈, and ∴.

At this point, I give them English statements to translate to mathematical statements, and mathematical statements to translate to English statements, one at a time. We use the following format: I provide an exercise, they work on it with a buddy or on their own while I bounce around the room offering help, and then I go over how we do it. The final exercise is to translate Goldbach's Conjecture (which I do not identify to them until after the translation work is done) from boolean symbology into English:

$\forall n|n \gt 2 \wedge (\frac{n}{2}) \in \mathbb{N}$,

$\exists (m,ℓ)\,\,|\,\, m \in P \wedge ℓ \in P \wedge m+ℓ=n$

As they leave, I give them a homework assignment with practice problems in very simple 1- or 2-step boolean algebraic reductions (including applying DeMorgan's Law), translating statements from English back and forth into symbols, creating truth tables from algebraic statements, and creating algebraic statements from truth tables.

The Request

This is my opener for the year, and it is so. very. dry. There is also very little activity! I am already aware that I've got a real snoozer here.

This material must to come first in the year for large-scale organizational reasons, but I would really like ideas to make it more engaging. I am also particularly seeking out ideas for active learning and ways to utilize pair partners to improve both engagement and mastery.

Answer 1

I don't know if I have a solid answer to the main thrust of your question, but I do have some one-off suggestions that may or may not be helpful.

First, something you could try integrating into your lessons is some kind of meta-narrative about why proofs are useful in the first place. This seems to be a very common concern from students in the discrete maths course that I help teach (especially since they've been mostly programming up to that point) -- this post made earlier might be applicable (though idk if I fully agree with all of the answers).

The second thing you could try doing is squashing your first and second lessons into one. If your students are already familiar with that many programming languages, I think they'll also be pretty familiar with boolean symbols, and won't find truth tables terribly hard (or interesting).

It might then be more fruitful to cover tautologies, contradictions, and contingencies around the same time -- might as well cover all of the related definitions at once.

I think focusing on implications for some time would be useful, though. That seems to be a very challenging concepts for students to fully grasp -- see How to teach logical implication for more details. Making students do challenging exercises that the Wason selection task to see if they really grok implication may also help.

You mentioned you briefly cover first-order logic (symbols like ∀, ∃, |, ∈, and ∴). I think those merit more time -- those also seem to be challenging concepts for students to grasp (in particular, what they mean, how variable scoping works, how to correctly use rules like ∀-introduction, ∀-elimination, and the like). One good challenge question for your students is to ask them whether or not $\forall x \, \exists \, y P(x, y)$ and $\exists y \, \forall x \, P(x, y)$ have same or differing truth values.

I'd also save teaching what ∈ for when you formally introduce sets.

Finally, one way to perhaps make your lessons more exciting is to introduce homework/introduce problems that involve solving logic puzzles, particularly ones that are challenging to reason through normally. Have your students start by converting the constraints into logical propositions then have them simplify them until they're able to find an answer. This lets them practice their English to logic skills and their logic manipulation skills in a hopefully more fun setting.

If you want, you can even take this one step further and turn it into a programming assignment by asking them to generate constraints they then feed into a SAT solver like z3. (For example, take sudoku -- you can make each cell a variable, define 9 predicates that encode whether or not a cell contains a number or not, then define a whole bunch of implications encoding relationships between relevant pairs of cells). This lets them see more concretely how propositional logic is relevant to computer science, and also lets them play around with a cool piece of tech.

Answer 2

I've found a lot of success giving real world (often times very silly) examples of boolean algebra to give them a more intuitive understanding in addition to the pure algebraic laws. An example would be "If it rains tomorrow, I will bring an umbrella so I will stay dry".

This is a simple A -> B:

If it rains tomorrow then I will bring an umbrella, I will stay dry (T -> T = T)

If it rains tomorrow then I will not bring an umbrella, I will not stay dry (T -> F = F)

If it does not rain tomorrow then I will bring an umbrella, I will stay dry (F -> T = T)

If it does not rain tomorrow then I will not bring an umbrella, I will stay dry (F -> F = T)

Using DeMorgan's we know A -> B = !A V B. We can say A = it will rain tomorrow, B = bringing an umbrella and whether you stay dry or not is the equivalent of the resulting truth table value.

You can incorporate students in coming up with these silly examples, and having them figure out how the narrative would look like to reflect the truth table values. In addition, pairs can come up with scenarios and test each other's knowledge. (This was during 2nd year University too! So it's never too old to get silly)

Lastly as a remark, I did not see you mention some Laws of Boolean Algebra such as Associative, Commutative, Idempotent, Identity, and Distributive. I think it's worth while to introduce these laws during lesson 1 or 2 because solving boolean algebra down the road is built off of these fundamentals.

Answer 3

A couple of ideas:

1st day

Start by getting everybody up and moving. Have people form sets - say, a set of colors, with everybody wearing a different color, or a set of ages - but remind them that they can't have two people representing the same color in the set. Perform different operations with the human sets - intersections, unions, etc. After a couple of exercises like this, show them the formal notation for sets and match it to what exactly they were doing (i.e., when you created a new set of only the people that were in both sets, you were performing an operation called an intersection, which you can notate as $A\cap B$, etc).

Hopefully you can get far enough into set theory such that you can reach DeMorgan's Law. Another good thing to introduce would be proofs - you could, for example, do the proof of DeMorgan's Law, or a simpler topic in set theory. As you continue with set theory and set theory notation, let them experiment with Python's set type - maybe your exercises could have them solve simple set problems on paper and with Python, and also a little work with proofs.

2nd day

This day is talking about truth tables, logic gates, and boolean symbols. A couple of ideas for making this part less dry:

• Include some information about George Boole and why his work was such a success - I particularly like Martin Gardner's Logic Machines and Diagrams; it provides some entertaining history.
• Put logic gates (and all the notation that goes with them) in the context of the rest of the computer - I enjoy Crash Course's Computer Science series of videos; the relevant one can be found here.

After the history and the introduction of logic gates, perhaps let them mess around with logic gates trying to create their own "circuits" that do something. (If you wish, let them test it out with some transistors, batteries, LEDs, or whatever.) Obviously, this is hard, so as they start complaining about difficulty, introduce the notation as an easier way to keep track of it. For example, let them sketch out truth tables for different gates, (perhaps testing them). At this stage you can also show them how the symbols they are using connect to the notation in Java/Python. The exercises probably should get them fairly familiar with the notation and truth tables.

3rd day

This is where everything gets put together. The first part of the class could be devoted to putting English language and notation together, starting with an introduction of the notation, and then an activity with partners contributing phrases to each other to translate, or picking a phrase from a movie for the class to translate (easier phrases preferred, obviously). Cover tautologies and contradictions, and advance through to translating Goldbach's conjecture.

The second part of class would then be devoted to the one thing left in your plan of the first three days - the formal proof that $False\Rightarrow True\equiv True$. Since you've already done a formal proof, ask for suggestions, let students complete simple half-finished statements in the proof, and so on. The exercises would basically be the same as your original third-day exercises, along with some tautology practice, perhaps.