# CSE 21Math 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