CISC 102 Lecture Notes - Lecture 7: Red Guitars, Complex Instruction Set Computing

• School: Queen's University
• Department: Computing
• Course: CISC 102
• Professor: D. Rappaport

Document Summary

Ginger owns a music store where all instruments are either red or a guitar (if not red). There are 15 red instruments and 18 guitars. A venn diagram can be used to model ginger"s inventory. From the diagram, it is clear that we need to know how many of ginger"s guitars are red in order to determine the total num of instruments. Let r denote the set of red instruments and g the set of guitars. |r| = 15, |g| = 18, |r g| = 8. |r g| = |r| + |g| - |r g| = 15 + 18 - 8 = 25. The principle of inclusion and exclusion can be stated as: Theorem: suppose a and b are finite sets. |a b| = |a| + |b| - |a b| The above generalizes the principle to a formula useful for determining the cardinality (or num of elements) of the union of three sets.