Answers.Body: <p>Back to the question : </p>
  
  <blockquote>
    <p>Since Boolean variables can only have 2 different values, proving a Boolean algebra equality can always be done exhaustively. Or am I wrong ?</p>
  </blockquote>
  
  <p>Yes. <code>you_are_right or not(you are right) = true</code>. That's basic binary logic.</p>
  
  <p>Lame joke aside, </p>
  
  <ul>
  <li>Boolean algebras are (usually defined as) <em>complemented distributive lattices</em>.</li>
  <li>the two-element algebra (true, false, and, or, not, whatever) is one of them</li>
  <li>it has an interesting property:</li>
  </ul>
  
  <blockquote>
    <p>identities that hold in the specific two-element algebra  are <em>exactly
    the same</em> as the identities that hold for ALL boolean algebras. No
    more, no less.</p>
  </blockquote>
  
  <p>So proving equalities with truth tables is a perfectly correct method, although a somehow boring activity.</p>
  
  <p>The point is <strong>you want to teach them something else</strong>: using identities to prove other identities, or more generally turn terms into equivalent ones using algebraic manipulation of expressions.</p>
  
  <p>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 <code>X or not(X)</code> in a conjunction. It requires imagination, and taking decisions with try-and-error tentatives. <strong>Most students hate this</strong>.</p>
  
  <hr>
  
  <p>See remark on <a href="https://en.wikipedia.org/wiki/Boolean_algebra_(structure)#Examples" rel="nofollow noreferrer" title="this Wikipedia page">https://en.wikipedia.org/wiki/Boolean_algebra_(structure)#Examples</a></p>
  
  <blockquote>
    <p>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 </p>
  
  <pre><code>(a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c)
  (a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) ≡ (a ∧ b) ∨ (¬a ∧ c)
  </code></pre>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-01T11:18:28.187Z
Answers.Text: I might make more explicit the relationship to other, perhaps more familiar algebras. It may not be motivational enough, but will probably sparkle curiosity.
Answers.UserDisplayName: wvxvw
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-01T16:54:05.380Z
Answers.Text: 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`.
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-01T09:04:49.730Z
Answers.LastActivityDate: 2017-10-01T09:12:15.757Z
Answers.LastEditDate: 2017-10-01T09:12:15.757Z
Answers.UserDisplayName: Michel Billaud
Answers.Body: <p>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.</p>
  
  <p>Therefore:</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>But instead try some other questions such as </p>
  
  <blockquote>
    <p>Rewrite the following using only <code>and</code> and <code>not</code>, $\overline{a+b}$</p>
  </blockquote>
  
  <p>Add more complex examples, ones they have not done already.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-28T19:58:26.483Z
Answers.Text: 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.
Answers.UserDisplayName: James Vanderhyde
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T07:44:07.967Z
Answers.Text: 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.
Answers.UserDisplayName: ctrl-alt-delor
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T09:30:20.837Z
Answers.Text: @ctrl-alt-delor: Truth tables are worse than $O(n^2)$, they're $O(2^n)$, which grows a lot faster!
Answers.UserDisplayName: psmears
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T11:27:33.823Z
Answers.Text: @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.
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T12:46:52.930Z
Answers.Text: @MichelBillaud: Are you sure you're replying to my comment? None of what you say contradicts what I said :)
Answers.UserDisplayName: psmears
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T15:53:58.063Z
Answers.Text: @psmears I didn't expect the Argument Clinic sketch. My point is : the theoretical complexity is a barrier when values of n are "sufficiently big".
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-30T15:10:04.647Z
Answers.Text: @MichelBillaud no, psmears is just pointing out a mistake
Answers.UserDisplayName: somebody
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-30T16:17:58.937Z
Answers.Text: @somebody You are right, psmears is right, and  I should have started by "anyway, whatever the theoretical complexity, it can be handled (by student written programs) in such practical cases with only a few (<= 10 or 20) variables".  3 methods : truth tables by hand, algebraic transformations, case exhaustion by program.
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-30T17:00:51.337Z
Answers.Text: I am not making any sense of the last few comments, so can not tell if you have made any sense of mine. What I am saying is that if you get students to do the type of question in my answer, then the complexity of `repeat until I get it correct: guess an answer, draw up truth table, compare`, should be enough to discourage this approach. This is $O(2^n)$ for the truth table × $O(?)$ for the guesses, which is quite a lot.
Answers.UserDisplayName: ctrl-alt-delor
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-01T08:20:52.743Z
Answers.Text: @ctrl-alt-delor Doing truth tables by hand is quick for <= 4 variables, but fastidious enough so students will soon discover the interest of algebraic manipulation of expressions by themselves. 
  To answer the OP question : yes, identities valid in all Boolean algebras (true/false, sets, bitvectors, whatever) can always be proved by truth tables on the "basic" true/false algebra.
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-28T16:55:44.803Z
Answers.LastActivityDate: 2017-09-28T16:55:44.803Z
Answers.UserDisplayName: ctrl-alt-delor
Answers.Body: <p>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.</p>
  
  <p>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.</p>
  
  <p>To make the problem more tractable for the people who <em>are</em> using algebra, you could perhaps engineer the original statement so some of the variables end up "vanishing" (e.g. they simplify into something like <code>p || !p</code>).</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 <em>unique</em> gates used).</p>
  
  <p>And finally, another idea is to just simply tell your students <em>why</em> 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.</p>
  
  <p>Generally, I think sharing your gameplan is a good way of getting students on-board (albeit sometimes reluctantly).</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-28T20:11:11.103Z
Answers.Text: You're right; I need to consider what my learning goals actually are. I think I have two reasons for teaching this practice: (1) manipulating logical expressions is a common activity in computer programming, and (2) practice with algebra of any kind helps with the mental skill of mathematical abstraction.
Answers.UserDisplayName: James Vanderhyde
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T02:30:41.203Z
Answers.Text: 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.
Answers.UserDisplayName: Nelson
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T03:01:44.550Z
Answers.Text: @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.
Answers.UserDisplayName: Michael0x2a
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T03:05:20.037Z
Answers.Text: @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.
Answers.UserDisplayName: Michael0x2a
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T11:22:50.893Z
Answers.Text: @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.
Answers.UserDisplayName: David Mulder
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T11:41:39.553Z
Answers.Text: In a programming-teaching context, you have to convince students that boolean expressions ARE expressions, not things that only appear as condition parts of if, for, while etc. As expressions, computations can be done on them, and some computations can be simplified/clarified either by case analysis (truth tables) or routine transformations (algebraic laws). Unfortunately, De Morgan laws don't really work in this context, as evaluation is often left-to-right with some reason `( i==n || t[i] == x)`... so **multivalued logic should be used instead** (sorry for the math teacher :-))
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T15:37:05.773Z
Answers.Text: @DavidMulder -- sure, I can concede that some devs might legitimately have never heard of De Morgan's law. But I still stand by the rest of my assertion -- are you really claiming that your co-workers are completely incapable of understanding things like why `(a && b) && c == a && (b && c)` and `(a || !a) == true` are true? I find that extremely hard to believe.
Answers.UserDisplayName: Michael0x2a
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T15:42:16.577Z
Answers.Text: @MichelBillaud -- I suppose. That said, OP said in their question that this was for an upper division class about specifically discrete math, so I'm making the assumption that the students are already familiar and comfortable with programming.
Answers.UserDisplayName: Michael0x2a
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T15:56:55.740Z
Answers.Text: @Michael0x2a It's one thing to logically understand such a thing, another entirely to understand one specific abstracted model from which such logic can be derived. Let me put it this way, a decade and a half ago in my early teens I started programming seriously and I am sure I could've reasoned those two things within seconds... yet if I would've opened the Wikipedia page about Morgan's law I would've gotten stuck in literally the first sentence. Personally I never took a computer science education (very intentionally) (cont.)
Answers.UserDisplayName: David Mulder
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T15:58:34.747Z
Answers.Text: and the only reason why I have any knowledge about the computer scientific model is because I am naturally curious, not because I need it professionally. So yeah, boolean algebra is not something I would recommend anybody to use in a professional setting (unless you're doing some very specific type of tasks which are comparatively rare in the real world).
Answers.UserDisplayName: David Mulder
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T16:52:26.630Z
Answers.Text: @DavidMulder -- I'm not sure if I agree with your conclusion. There aren't that many boolean algebra laws, and most of them are common sense (for example, things like `a && b == b && a`). As a result, I think it's very reasonable to expect devs to be able to follow most boolean algebra proofs, even if they've never been formally taught the material -- after all, all you do is just apply these (mostly) common-sense laws one after the other. That is, I claim all you need to follow a boolean algebra proof is the ability to "logically understand" something, as you put it.
Answers.UserDisplayName: Michael0x2a
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T16:54:00.487Z
Answers.Text: @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.
Answers.UserDisplayName: Michael0x2a
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-30T01:56:28.657Z
Answers.Text: @Michael0x2a I'd be concerned about the opposite.  While I agree that I'd expect a developer to be able to understand that `(a && b) == !(!a || b)`, the real question would be, if someone made a mistake with said logic, would the developers be able to catch it in a code review?  That's a much harder question.  (And a funnier one too.  You'll know it when you get it!  It was actually quite unintentional)
Answers.UserDisplayName: Cort Ammon
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-30T03:18:23.263Z
Answers.Text: @CortAmmon -- well, that's what things like unit tests, code coverage analysis, mutation tests, fuzz tests, and the like are for, right? To catch accidental errors like that one. But yes, typos can be hard to catch in general. I'm not sure what that fact has to do with boolean algebra in particular? (I also note that correctly applying boolean algebra is likely to *reduce* bugs -- after all, if you simplify an expression, it'll be easier for somebody else to reason about and verify.)
Answers.UserDisplayName: Michael0x2a
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-30T05:24:06.210Z
Answers.Text: @Michael0x2a To catch an error like that, a developer not only needs to understand that laws like DeMorgan's work, but to be able to apply them subconsciously and see that a piece of code just doesn't smell right.
Answers.UserDisplayName: Cort Ammon
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-30T05:34:25.820Z
Answers.Text: The thing is, I'll rather put a truth table in a requirements document than expect a client to understand boolean algebra.  I can walk through the truth table, automate the unit tests, and tell them, right then and there, whether my code meets the requirements.
Answers.UserDisplayName: Nelson
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-03T11:48:54.903Z
Answers.Text: @Michael0x2a Actually, laws of Boolean algebras are actually *broken* for conditions in C-like languages.  Think about  `p != nullptr  &&  *p = x`
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-28T16:39:08.133Z
Answers.LastActivityDate: 2017-09-29T00:08:55.493Z
Answers.LastEditDate: 2017-09-29T00:08:55.493Z
Answers.UserDisplayName: Michael0x2a
Answers.Body: <p>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:</p>
  
  <ol>
  <li><p>Prove that <code>nand</code> is boolean complete by mapping each logical symbol back to <code>nand</code> (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.</p></li>
  <li><p>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!</p></li>
  <li><p>For that matter, the truth-table method of generating a CNF requires a whole host of DeMorgansing in order to get it done.</p></li>
  </ol>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-28T19:56:02.230Z
Answers.Text: These actually are CS majors; this is a discrete math course for CS majors. I edited my question for clarity.
Answers.UserDisplayName: James Vanderhyde
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-28T18:45:05.010Z
Answers.LastActivityDate: 2017-09-28T18:53:26.023Z
Answers.LastEditDate: 2017-09-28T18:53:26.023Z
Answers.UserDisplayName: Ben I.
Answers.Body: <p>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?</p>
  
  <p>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?</p>
  
  <p>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.</p>
  
  <p>Math needs to get used in order for people to want to use it.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-29T01:06:24.563Z
Answers.Text: Hey MuffinMan! Welcome to [cseducators.se]!
Answers.UserDisplayName: thesecretmaster
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-28T20:42:46.870Z
Answers.LastActivityDate: 2017-09-28T20:42:46.870Z
Answers.UserDisplayName: MuffinMan
Answers.Body: <p>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 <em>do</em> think, but still, they are unique individuals. </p>
  
  <p>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. <a href="http://csunplugged.org" rel="nofollow noreferrer">CSUnplugged</a> 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. </p>
  
  <p>Discussing simple circuits (gates) might also give some an incentive to do more. Discussions of why <em>nand</em> and <em>nor</em> are preferred over <em>and</em> and <em>or</em> are instructive. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-28T20:27:28.843Z
Answers.Text: "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].
Answers.UserDisplayName: alephzero
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-28T16:02:40.603Z
Answers.LastActivityDate: 2017-09-28T16:02:40.603Z
Answers.UserDisplayName: Buffy
Body: <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-09-28T18:57:02.720Z
Comments.Text: This is your second great question here on cseducators.  Feel free to come by [The Classroom](https://chat.stackexchange.com/rooms/59174/the-classroom) and say hi!
Comments.UserDisplayName: Ben I.
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-09-30T05:20:54.367Z
Comments.Text: 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.
Comments.UserDisplayName: Daniel Wagner
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-10-14T19:56:54.147Z
Comments.Text: Your final question is intriguing. Booleans have some deep properties. See, for example: [http://en.wikipedia.org/wiki/Cook–Levin_theorem](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.
Comments.UserDisplayName: Buffy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-29T23:39:53.887Z
Comments.Text: Ask them for a legend for their graphic--how to determine what proposition the table states.
Comments.UserDisplayName: philipxy
Tags: <boolean-algebra>
Title: How do I convince students to use Boolean algebra?
ThreadText: # How do I convince students to use Boolean algebra?
  
  (Asked by: username_0 on 2017-09-28)
  
  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?
  
  **Tags:** boolean-algebra
  
  > **Comments:**
  > **username_1**: This is your second great question here on cseducators.  Feel free to come by [The Classroom](https://chat.stackexchange.com/rooms/59174/the-classroom) and say hi!  
  > **username_2**: 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.  
  > **username_3**: Your final question is intriguing. Booleans have some deep properties. See, for example: [http://en.wikipedia.org/wiki/Cook–Levin_theorem](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.  
  > **username_4**: Ask them for a legend for their graphic--how to determine what proposition the table states.  
  
  ---
  
  ## 6 answers
  
  ### Answer by username_5 on 2017-10-01. Score: 2 | Accepted answer
  
  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](https://en.wikipedia.org/wiki/Boolean_algebra_(structure)#Examples "this Wikipedia page")
  
  > 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)
  >
  > ```
  
  > **Comments:**
  > **username_6**: I might make more explicit the relationship to other, perhaps more familiar algebras. It may not be motivational enough, but will probably sparkle curiosity.  
  > **username_5**: 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`.  
  
  ---
  
  ### Answer by username_10 on 2017-09-28. Score: 39
  
  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).
  
  > **Comments:**
  > **username_0**: You're right; I need to consider what my learning goals actually are. I think I have two reasons for teaching this practice: (1) manipulating logical expressions is a common activity in computer programming, and (2) practice with algebra of any kind helps with the mental skill of mathematical abstraction.  
  > **username_11**: 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.  
  > **username_10**: @username_11 -- 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.  
  > **username_10**: @username_11 -- 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.  
  > **username_12**: @username_10 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.  
  > **username_5**: In a programming-teaching context, you have to convince students that boolean expressions ARE expressions, not things that only appear as condition parts of if, for, while etc. As expressions, computations can be done on them, and some computations can be simplified/clarified either by case analysis (truth tables) or routine transformations (algebraic laws). Unfortunately, De Morgan laws don't really work in this context, as evaluation is often left-to-right with some reason `( i==n || t[i] == x)`... so **multivalued logic should be used instead** (sorry for the math teacher :-))  
  > **username_10**: @username_12 -- sure, I can concede that some devs might legitimately have never heard of De Morgan's law. But I still stand by the rest of my assertion -- are you really claiming that your co-workers are completely incapable of understanding things like why `(a && b) && c == a && (b && c)` and `(a || !a) == true` are true? I find that extremely hard to believe.  
  > **username_10**: @username_5 -- I suppose. That said, OP said in their question that this was for an upper division class about specifically discrete math, so I'm making the assumption that the students are already familiar and comfortable with programming.  
  > **username_12**: @username_10 It's one thing to logically understand such a thing, another entirely to understand one specific abstracted model from which such logic can be derived. Let me put it this way, a decade and a half ago in my early teens I started programming seriously and I am sure I could've reasoned those two things within seconds... yet if I would've opened the Wikipedia page about Morgan's law I would've gotten stuck in literally the first sentence. Personally I never took a computer science education (very intentionally) (cont.)  
  > **username_12**: and the only reason why I have any knowledge about the computer scientific model is because I am naturally curious, not because I need it professionally. So yeah, boolean algebra is not something I would recommend anybody to use in a professional setting (unless you're doing some very specific type of tasks which are comparatively rare in the real world).  
  > **username_10**: @username_12 -- I'm not sure if I agree with your conclusion. There aren't that many boolean algebra laws, and most of them are common sense (for example, things like `a && b == b && a`). As a result, I think it's very reasonable to expect devs to be able to follow most boolean algebra proofs, even if they've never been formally taught the material -- after all, all you do is just apply these (mostly) common-sense laws one after the other. That is, I claim all you need to follow a boolean algebra proof is the ability to "logically understand" something, as you put it.  
  > **username_10**: @username_12 -- 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.  
  > **username_13**: @username_10 I'd be concerned about the opposite.  While I agree that I'd expect a developer to be able to understand that `(a && b) == !(!a || b)`, the real question would be, if someone made a mistake with said logic, would the developers be able to catch it in a code review?  That's a much harder question.  (And a funnier one too.  You'll know it when you get it!  It was actually quite unintentional)  
  > **username_10**: @username_13 -- well, that's what things like unit tests, code coverage analysis, mutation tests, fuzz tests, and the like are for, right? To catch accidental errors like that one. But yes, typos can be hard to catch in general. I'm not sure what that fact has to do with boolean algebra in particular? (I also note that correctly applying boolean algebra is likely to *reduce* bugs -- after all, if you simplify an expression, it'll be easier for username_9 else to reason about and verify.)  
  > **username_13**: @username_10 To catch an error like that, a developer not only needs to understand that laws like DeMorgan's work, but to be able to apply them subconsciously and see that a piece of code just doesn't smell right.  
  > **username_11**: The thing is, I'll rather put a truth table in a requirements document than expect a client to understand boolean algebra.  I can walk through the truth table, automate the unit tests, and tell them, right then and there, whether my code meets the requirements.  
  > **username_5**: @username_10 Actually, laws of Boolean algebras are actually *broken* for conditions in C-like languages.  Think about  `p != nullptr  &&  *p = x`  
  
  ---
  
  ### Answer by username_7 on 2017-09-28. Score: 9
  
  I am mostly with @username_3, 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.
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_7**: 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.  
  > **username_8**: @username_7: Truth tables are worse than $O(n^2)$, they're $O(2^n)$, which grows a lot faster!  
  > **username_5**: @username_8 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.  
  > **username_8**: @username_5: Are you sure you're replying to my comment? None of what you say contradicts what I said :)  
  > **username_5**: @username_8 I didn't expect the Argument Clinic sketch. My point is : the theoretical complexity is a barrier when values of n are "sufficiently big".  
  > **username_9**: @username_5 no, username_8 is just pointing out a mistake  
  > **username_5**: @username_9 You are right, username_8 is right, and  I should have started by "anyway, whatever the theoretical complexity, it can be handled (by student written programs) in such practical cases with only a few (<= 10 or 20) variables".  3 methods : truth tables by hand, algebraic transformations, case exhaustion by program.  
  > **username_7**: I am not making any sense of the last few comments, so can not tell if you have made any sense of mine. What I am saying is that if you get students to do the type of question in my answer, then the complexity of `repeat until I get it correct: guess an answer, draw up truth table, compare`, should be enough to discourage this approach. This is $O(2^n)$ for the truth table × $O(?)$ for the guesses, which is quite a lot.  
  > **username_5**: @username_7 Doing truth tables by hand is quick for <= 4 variables, but fastidious enough so students will soon discover the interest of algebraic manipulation of expressions by themselves.  To answer the OP question : yes, identities valid in all Boolean algebras (true/false, sets, bitvectors, whatever) can always be proved by truth tables on the "basic" true/false algebra.  
  
  ---
  
  ### Answer by username_1 on 2017-09-28. Score: 5
  
  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 @username_7'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.
  
  > **Comments:**
  > **username_0**: These actually are CS majors; this is a discrete math course for CS majors. I edited my question for clarity.  
  
  ---
  
  ### Answer by username_14 on 2017-09-28. Score: 4
  
  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.
  
  > **Comments:**
  > **username_15**: Hey username_14! Welcome to [cseducators.se]!  
  
  ---
  
  ### Answer by username_3 on 2017-09-28. Score: 4
  
  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](http://csunplugged.org) 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.
  
  > **Comments:**
  > **username_16**: "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].  
  
  ---
  
  