How do I convince students to use Boolean algebra?

Question

I have taught Boolean algebra in an upper-level discrete math course for CS majors. I showed them how, using just the axioms (distributive property, etc.), you can derive other properties (such as De Morgan's Law). Then I assigned them to try it, and most of them happily (or grumpily) worked through the algebra. But one student proved the statement exhaustively using a truth table, instead of using algebra. That is not what I had wanted him to do, but I was at a loss on how to justify it to him. Since Boolean variables can only have 2 different values, proving a Boolean algebra equality can always be done exhaustively. Or am I wrong?

Answer 1

Back to the question :

Since Boolean variables can only have 2 different values, proving a Boolean algebra equality can always be done exhaustively. Or am I wrong ?

Yes. you_are_right or not(you are right) = true. That's basic binary logic.

Lame joke aside,

• Boolean algebras are (usually defined as) complemented distributive lattices.
• the two-element algebra (true, false, and, or, not, whatever) is one of them
• it has an interesting property:

identities that hold in the specific two-element algebra are exactly the same as the identities that hold for ALL boolean algebras. No more, no less.

So proving equalities with truth tables is a perfectly correct method, although a somehow boring activity.

The point is you want to teach them something else: using identities to prove other identities, or more generally turn terms into equivalent ones using algebraic manipulation of expressions.

The truth-tables method has an obvious adavantage for students: they don't have to think, just compute. When you use algebra, you have to chose a target (the kind of expression you want to get) and find how you can get there step by step. It is sometimes tricky, like introducing instances of X or not(X) in a conjunction. It requires imagination, and taking decisions with try-and-error tentatives. Most students hate this.

---

See remark on https://en.wikipedia.org/wiki/Boolean_algebra_(structure)#Examples

The two-element Boolean algebra is also important in the general theory of Boolean algebras, because an equation involving several variables is generally true in all Boolean algebras if and only if it is true in the two-element Boolean algebra (which can be checked by a trivial brute force algorithm for small numbers of variables). This can for example be used to show that the following laws (Consensus theorems) are generally valid in all Boolean algebras

(a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c)
(a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) ≡ (a ∧ b) ∨ (¬a ∧ c)

Answer 2

Well, for one, computing a truth table doesn't scale: generating one takes exponential time, with respect to the number of variables you're using.

You can perhaps "subtly" drive this idea home by asking your students to manipulate some proposition that contains 7 or 8 variables (which would require creating a truth table with 128 or 256 rows). That would require an exhausting amount of work -- the benefits of using algebra should hopefully be more obvious, then.

To make the problem more tractable for the people who are using algebra, you could perhaps engineer the original statement so some of the variables end up "vanishing" (e.g. they simplify into something like p || !p).

I think it would also be worth explaining why it's useful to be able to systematically simplify or manipulate boolean expressions in the first place -- for example, you could explain that when you're designing circuits, you have a vested interest in minimizing the number of gates used to keep costs down (as well as potentially minimizing the number of unique gates used).

And finally, another idea is to just simply tell your students why you're asking them to learn this material in the first place. For example, you could say that you're trying to prepare them to write proofs later on in the course (assuming that's what you're doing). After all, a large part of writing proofs is about correctly manipulating and applying definitions, and that's exactly what you're asking the students to do now.

Generally, I think sharing your gameplan is a good way of getting students on-board (albeit sometimes reluctantly).

Answer 3

I am mostly with @Buffy, A student should be praised for finding their own way of solving a problem. However I also think it is often good to have more than one way of doing things.

Therefore:

If the exam insists that they do it a certain way, then explain this to your student. Also explain that having more than one way of doing things is better.

Instead of getting them to prove A = B e.g. $\overline{a+b} = \overline{a}\cdot \overline{b}$ that is (depending on how you like to write it) $\lnot(a \lor b) = \lnot{a} \land \lnot{b}$ This can be proved exhaustively with truth tables, as your student proved.

But instead try some other questions such as

Rewrite the following using only and and not, $\overline{a+b}$

Add more complex examples, ones they have not done already.

Answer 4

I've never encountered this particular problem (possibly because I mention that truth tables are great, but we need both sets of skills?) Looking through the examples that I teach, though, a few of them pretty easily motivate boolean algebra:

1. Prove that nand is boolean complete by mapping each logical symbol back to nand (or other symbols that you have already proven). This example forces you to only use the terms that you have already proven, so it is structured rather like @ctrl-alt-delor's suggestion.

2. Bring expressions to Conjunctive Normal Form (which you can use to trivially prove that any boolean expression, no matter how complex, can be solved in $O(1)$), but limit the number of disjunctive clauses that you are allowed to have in the final answer. The truth-table method of creating CNFs does not come with any such guarantees!

3. For that matter, the truth-table method of generating a CNF requires a whole host of DeMorgansing in order to get it done.

CNFs are really a good tool to force kids into boolean algebra. I understand that they are rather computer-sciencey for a course in mathematics, but since you are asking the question here (and not, say, at matheducators), perhaps they will suit your needs.

Answer 5

Well, you won't do it by simply insisting. In fact, if your student has an alternate way to demonstrate the truth of the statement, he/she should be praised, not censured, even implicitly. Your students aren't like you. They don't think like you for the most part. It is useful, of course, to show them how you do think, but still, they are unique individuals.

However, if you want to convince them to use Boolean, you could give them an assignment to actually compute boolean functions. Or, more interesting, you could create (or find) some active learning games that are both fun and rewarding. CSUnplugged may have such thing already. A search of their site will turn up a few things on Binary Numbers that might be adapted, and a few links on teaching Boolean Algebra.

Discussing simple circuits (gates) might also give some an incentive to do more. Discussions of why nand and nor are preferred over and and or are instructive.

Answer 6

You haven't given them any practical applications for it, so the merit of doing so is lost on them. Why should anyone care about things like De Morgan's Law, etc, if they can just use a truth table to hammer out the answer?

Boolean expressions can be reduced to a minimalist SOP (Sum of Products) or POS expression, which is the whole point of what you are teaching. In turn these expressions can be used to describe a logic circuit using AND, OR, NOT, NAND, NOR and XOR gates. A Boolean algebra expression allows a person to define not only what gates to use but also how to wire them. For example, when you apply De Morgan's, how would the circuit change for the resulting SOP?

K Maps (Karnaugh maps) can be used to find the smallest SOP, which describes the smallest possible circuit to get the logical output required. Finite state machines (FSMs) use groups of SOPs that allow you to get a logic circuit to do what you want it to do - traffic lights are a typical example used, where you apply multiple inputs and get multiple outputs.

Math needs to get used in order for people to want to use it.