CSE 21
Math for Algorithms


Week 2 Tip

De Morgan's Laws for Counting

Be comfortable converting from ANDs (set intersections ∩) to ORs (set unions ∪) and vice-versa. Recall De Morgan's laws! This conversion can occasionally come in handy for counting problems. For example, if it seems difficult to count

  1. |set A ∩ set B|
  2. |set which meets condition A AND condition B|

via some application of the product rule, try counting

  1. |¬(¬set A ∪ ¬set B)|
  2. |¬(set which doesn't meet condition A OR doesn't meet condition B)|

via some application of the sum rule (inclusion-exclusion in the general case). Note: ¬ (NOT) denotes the complement of a set and |x| denotes the size of a set.

Example

As a more concrete example, take a look at problem 1g on Group HW1. It asks for

the number of passwords with >= 1 lowercase letter AND >= 1 uppercase letter AND >= 1 numeral

which is hard to count directly. Instead, you should have counted

(the total number of passwords) - (the number of passwords with 0 lowercase letters OR 0 uppercase letters OR 0 numerals)

which is a much easier prospect (hint: i-e!). Using the following definitions:

L: "has >= 1 lowercase letter"
U: "has >= 1 uppercase letter"
N: "has >= 1 numeral"

you'll see that we can restate the conversion as

|set with L AND U AND N|
= |¬(set with (NOT L) OR (NOT U) OR (NOT N))|
= |universe| - |set with (NOT L) OR (NOT U) OR (NOT N)|

noting in the final step that the size of the complement of a set is merely the size of the universe minus the size of the set. (Likewise, the size of a set is equal to the size of the universe minus the size of the complement of the set.)

Bottom Line

Remember, we probably don't intend to make you write and count a billion sub-cases. If you find yourself doing this, consider trying to convert the problem to something more tractable, e.g. using De Morgan's laws.

back