33
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ This is your second great question here on cseducators. Feel free to come by The Classroom and say hi! $\endgroup$ – Ben I. Sep 28 '17 at 18:57
  • 1
    $\begingroup$ There's lots of boolean algebras that aren't just on the set {True, False}. e.g. take a big square-free number; then its divisors form a boolean algebra where conjunction is lcm and disjunction is gcd. The "truth table" approach can easily be made unapproachably tedious (or even infinite!) with a careful choice of boolean algebra. $\endgroup$ – Daniel Wagner Sep 30 '17 at 5:20
  • $\begingroup$ Your final question is intriguing. Booleans have some deep properties. See, for example: http://en.wikipedia.org/wiki/Cook–Levin_theorem. I doubt you were trying to get to situations where that would apply, but it is worth a look. $\endgroup$ – Buffy Oct 14 '17 at 19:56
2
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ I might make more explicit the relationship to other, perhaps more familiar algebras. It may not be motivational enough, but will probably sparkle curiosity. $\endgroup$ – wvxvw Oct 1 '17 at 11:18
  • 1
    $\begingroup$ Another method to prove identities, between truth tables and algebraic manipulation : 1. select the most frequent variable v 2. replace it by 0, apply simplifications, prove (recursively) whats left. 3. do the same with v=1. Applying at to the first consensus law : with a=0 (0 ∨ b) ∧ (¬0 ∨ c) ∧ (b ∨ c) ≡ (0 ∨ b) ∧ (¬0 ∨ c), iff b ∧ (b ∨ c) ≡ b and on the other side, if a=1 (1 ∨ b) ∧ (¬1 ∨ c) ∧ (b ∨ c) ≡ (1 ∨ b) ∧ (¬0 ∨ c) iff c ∧ (b ∨ c) ≡ c. To prove b ∧ (b ∨ c) ≡ b, b=0 leads to 0≡0, and b=1 to 1≡1. $\endgroup$ – Michel Billaud Oct 1 '17 at 16:54
38
$\begingroup$

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).

$\endgroup$
  • 3
    $\begingroup$ Yet in the workplace, if you presented boolean algebra math to "prove" something, most people will not understand it. I don't care if the truth table has 1000 rows; everyone can understand that! And if you have a problem that has EIGHT variables, then it's time to break the problem down to smaller bits... god be damned if I were to look at an SQL statement with 8 joins, or an if statement with 8 conditions. $\endgroup$ – Nelson Sep 29 '17 at 2:30
  • 6
    $\begingroup$ @Nelson -- I disagree with the claim that most people in a workplace don't understand basic boolean algebra laws. If a dev doesn't understand things like De Morgan's law or laws like (a && b) && c == a && (b && c) or (a || !a) == true, then they're grossly incompetent and should never have been hired, full stop. I'm also not sure why you have "prove" in scare quotes. Applying boolean algebra laws is a perfectly valid proof strategy, as is generating a truth table. $\endgroup$ – Michael0x2a Sep 29 '17 at 3:01
  • 6
    $\begingroup$ @Nelson -- Also, regarding truth tables not scaling if you have many variables: are you familiar with the SAT problem as well as SAT solvers, SMT solvers, and the like...? They're pretty useful and come up in several subfields of CS/software engineering -- it turns out the SAT problem is NP-complete, and SAT solvers can do a pretty good job of efficiently finding solutions in most (though not all) cases. When you're taking your domain-specific NP problem and converting them into propositions to feed to your SAT/SMT solver, it's not uncommon to generate thousands or millions of variables. $\endgroup$ – Michael0x2a Sep 29 '17 at 3:05
  • 3
    $\begingroup$ @Michael0x2a A lot of my completely competent colleagues of mine throughout the years would have had no ideas about De Morgan's law... and yet they were able to program things of amazing complexity. That's the thing, sure, a law like that can save you a couple of seconds or give marginally clearer code, but in the end 99.99% of real world programming has nothing to do with that. So calling those types of programmers incompetent and not worth hiring is beyond naive and rude, showing a complete lack of understanding of the real world. $\endgroup$ – David Mulder Sep 29 '17 at 11:22
  • 4
    $\begingroup$ @DavidMulder -- Regarding De Morgan's law -- sure, if a beginner starts with Wikipedia, they'd be lost, but Wikipedia is pretty obtuse in general. De Morgan's law is usually presented within most intro classes as just two factoids: !(a && b) == (!a || !b) and !(a || b) == (!a && !b) (and the instructor then spends some class time working through truth tables to convince students why this is the case). So sure, I can agree that not everybody might have run into this factoid, but I don't think it's some hugely complicated thing a beginner will have trouble understanding. $\endgroup$ – Michael0x2a Sep 29 '17 at 16:54
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think I get what you're saying. A student would have to use the algebra rules to try to find an equivalent expression. A particularly stubborn student might still use two truth tables to prove that the rewrite is equivalent to the original. $\endgroup$ – James Vanderhyde Sep 28 '17 at 19:58
  • $\begingroup$ Yes you could use a truth table to check the answer is correct. Therefore you could find the answer by brute force guessing and checking. If they are that stubborn, then you need a question that has too many possible answers, and a large truth table, they are both correlated so $O(n^2)$. You should find (as long as you have done nothing to annoy the student, to make them stubborn), that they are not stubborn, they are just pragmatic. Truth tables are easier, and sufficient, oh now they are not, I now see why boolean algebra may be of use. $\endgroup$ – ctrl-alt-delor Sep 29 '17 at 7:44
  • 1
    $\begingroup$ @ctrl-alt-delor: Truth tables are worse than $O(n^2)$, they're $O(2^n)$, which grows a lot faster! $\endgroup$ – psmears Sep 29 '17 at 9:30
  • $\begingroup$ @psmears Anyway, we won't use them with functions with more than 10 arguments, so it is reasonable to use them to compare (by computer) if 2 combinatorial circuits have the same behaviour, and who where the differences are. Just print the (first) lines, where they differ. $\endgroup$ – Michel Billaud Sep 29 '17 at 11:27
  • $\begingroup$ @MichelBillaud: Are you sure you're replying to my comment? None of what you say contradicts what I said :) $\endgroup$ – psmears Sep 29 '17 at 12:46
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ These actually are CS majors; this is a discrete math course for CS majors. I edited my question for clarity. $\endgroup$ – James Vanderhyde Sep 28 '17 at 19:56
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Discussing simple circuits (gates) might also give some an incentive to do more" ... but don't teach them about Karnaugh maps, or you have given them another reason not to mess about with Boolean algebra! [/devil]. $\endgroup$ – alephzero Sep 28 '17 at 20:27
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.