Boolean Algebra and DeMorgan’s Laws

Boolean Algebra is a branch of mathematics devoted to the study of Boolean values and operators. Boolean Algebra consists of these fundamental operands and operators:

• operands (values): true, false
• operators: and (&&), or (||), not (!)

Note: Java has other Boolean operators, such as ^ (XOR - “exclusive or”) and equivalence. This curriculum does not cover these other operators because they are not part of the AP subset.

There are many identities that have been developed to use with compound Boolean expressions. Two of the more useful identities are DeMorgan's Laws, which are used to negate compound Boolean expressions.

• DeMorgan’s Laws:

  • !(A || B) -> ! A && ! B

  • !(A && B) -> ! A || ! B

• The symbols A and B represent the Boolean values, true or false.

Here is the truth table that proves the first DeMorgan’s Law.

Notice that columns with the titles ! (A || B) and ! A && ! B result in the same answers.

Following is the truth table that proves the second DeMorgan's Law.

Notice that columns with the titles ! (A && B) and ! A || ! B result in the same answers.

Here is a good way to think about both of DeMorgan’s Laws. Notice that it is similar to the distributive postulate in mathematics. The not operator is distributed through both terms inside of the parentheses, except that the operator switches from and to or, or vice versa.

!(A && B) -> ! A || ! B
!(A || B) -> ! A && ! B