Skip to main content
Engineering LibreTexts

2.2.A Basics of Boolean Algebra

  • Page ID
    9841
  • Many of the rules of Boolean algebra are fairly obvious, if you think a bit about what they mean. Even those that are not obvious can be verified easily by using a truth table. Figure 2.2 lists the most important of these laws. You will notice that all these laws, except the first, come in pairs: Each law in the pair can be obtained from the other by interchanging ∧ with ∨ and T with F. This cuts down on the number of facts you have to remember.

    Just as an example, let’s verify the first rule in the table, the Law of Double Negation. This law is just the old, basic grammar rule that two negatives make a positive. Although the way this rule applies to English is questionable, if you look at how it is used—no matter what the grammarian says, “I can’t get no satisfaction” doesn’t really mean “I can get satisfaction”—the validity of the rule in logic can be verified just by computing the two possible cases: when is true and when is false. When is true, then by the definition of the ¬ operator, ¬is false. But then, again by the definition of ¬, the value of ¬(¬p) is true, which is the same as the value of p. Similarly, in the case where is false, ¬(¬p) is also false. Organized into a truth table, this argument takes the rather simple form

    屏幕快照 2019-06-24 13.45.36.png

    The fact that the first and last columns are identical shows the logical equivalence of and ¬(¬p). The point here is not just that ¬(¬p) ≡ p, but also that this logical equivalence is valid because it can be verified computationally based just on the relevant definitions. Its validity does not follow from the fact that “it’s obvious” or “it’s a well- known rule of grammar”.

    Students often ask “Why do I have to prove something when it’s obvious?” The point is that logic—and mathematics more generally—is its own little world with its own set of rules. Although this world is related somehow to the real world, when you say that something is obvious (in the real world), you aren’t playing by the rules of the world of logic. The real magic of mathematics is that by playing by its rules, you can come up with things that are decidedly not obvious, but that still say something about the real world— often, something interesting and important.

    Each of the rules in Figure 2.2 can be verified in the same way, by making a truth table to check all the possible cases. In one of the pencasts of this course we further discuss how to check the equivalence of two propositions using truth tables.