📄 chap05.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 5: SETS, ETC.</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap06.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap04.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="0729_0001">CHAPTER 5: SETS, ETC.<a name="0729_0001"></h1><P>
In earlier chapters, we touched on the elements of discrete mathematics. This chapter reviews more completely the notations, definitions, and elementary properties of sets, relations, functions, graphs, and trees. Readers already well versed in this material need only skim this chapter.<P>
<h1><a name="072b_1217">5.1 Sets<a name="072b_1217"></h1><P>
<a name="072b_11e3"><a name="072b_11e4"><a name="072b_11e5"><a name="072b_11e6"><a name="072b_11e7"><a name="072b_11e8">A <I><B>set</I></B> is a collection of distinguishable objects, called its <I><B>members</I></B> or <I><B>elements.</I></B> If an object <I>x</I> is a member of a set <I>S</I>, we write <I>x</I> <img src="../images/memof12.gif"> <I>S</I> (read "<I>x</I> is a member of <I>S</I>" or, more briefly, "<I>x</I> is in <I>S</I>"). If <I>x</I> is not a member of <I>S</I>, we write <I>x</I> <img src="../images/notmem.gif"> <I>S</I>. We can describe a set by explicitly listing its members as a list inside braces. For example, we can define a set <I>S</I> to contain precisely the numbers 1, 2, and 3 by writing <I>S</I> = {1, 2, 3}. Since 2 is a member of the set <I>S</I>, we can write 2 <img src="../images/memof12.gif"> <I>S</I>, and since 4 is not a member, we have 4 <img src="../images/notmem.gif"> <I>S</I>. A set cannot contain the same object more than once, and its elements are not ordered. Two sets <I>A</I> and <I>B</I> are <I><B>equal</I></B>, written <I>A</I> = <I>B</I>, if they contain the same elements. For example, {1, 2, 3, 1} = {1, 2, 3} = {3, 2, 1}.<P>
We adopt special notations for frequently encountered sets.<P>
<a name="072b_11e9"><FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT> <img src="77_a.gif"> denotes the <I><B>empty set</I></B>, that is, the set containing no members.<P>
<a name="072b_11ea"><a name="072b_11eb"><FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT> <B>Z</B> denotes the set of <I><B>integers</I></B>, that is, the set {. . . , 2, -1, 0, 1, 2, . . .}.<P>
<a name="072b_11ec"><a name="072b_11ed"><FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT> <B>R</B> denotes the set of <I><B>real numbers</I></B>.<P>
<a name="072b_11ee"><a name="072b_11ef"><FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT> <B>N</B> denotes the set of <I><B>natural numbers</I></B>, that is, the set {0, 1, 2, . . .}.<SUP>1</sup><P>
<SUP>1</SUP>Some authors start the natural numbers with 1 instead of 0. The modern trend seems to be to start with 0.<P>
<a name="072b_11f0"><a name="072b_11f1">If all the elements of a set <I>A</I> are contained in a set <I>B</I>, that is, if <I>x</I> <img src="../images/memof12.gif"> <I>A </I>implies <I>x</I> <img src="../images/memof12.gif"> <I>B</I>, then we write <I>A </I><img src="../images/rgtubar.gif"> <I>B</I> and say that <I>A</I> is a <I><B>subset</I></B> of <I>B</I>. A set <I>A</I> is a <I><B>proper subset</I></B> of <I>B</I>, written <I>A</I> <img src="../images/rightu.gif"> <I>B</I>, if <I>A</I> <img src="../images/rgtubar.gif"> <I>B</I> but <I>A</I> <img src="../images/noteq.gif"> <I>B.</I> (Some authors use the symbol "<img src="../images/rightu.gif"> to denote the ordinary subset relation, rather than the proper-subset relation.) For any set <I>A</I>, we have <I>A</I> <img src="../images/rgtubar.gif"> <I>A</I>. For two sets <I>A</I> and <I>B</I>, we have <I>A</I> = <I>B</I> if and only if <I>A</I> <img src="../images/rgtubar.gif"> <I>B</I> and <I>B</I> <img src="../images/rgtubar.gif"> <I>A</I>. For any three sets <I>A</I>, <I>B</I>, and <I>C</I>, if <I>A</I> <img src="../images/rgtubar.gif"> <I>B</I> and <I>B</I> <img src="../images/rgtubar.gif"> <I>C</I>, then <I>A</I> <img src="../images/rgtubar.gif"> <I>C</I>. For any set <I>A</I>, we have <img src="78_a.gif"> <img src="../images/rgtubar.gif"> <I>A</I>.<P>
<a name="072b_11f2">We sometimes define sets in terms of other sets. Given a set <I>A</I>, we can define a set <I>B</I> <img src="../images/rgtubar.gif"> <I>A</I> by stating a property that distinguishes the elements of <I>B</I>. For example, we can define the set of even integers by {<I>x</I> : <I>x</I> <img src="../images/memof12.gif"> <B>Z</B> and <I>x</I>/2 is an integer}. The colon in this notation is read "such that." (Some authors use a vertical bar in place of the colon.)<P>
Given two sets <I>A</I> and <I>B</I>, we can also define new sets by applying <I><B>set operations</I></B><I>:</I><P>
<a name="072b_11f3"><a name="072b_11f4"><FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT> The <I><B>intersection</I></B> of sets <I>A</I> and <I>B</I> is the set<P>
<pre><I>A</I> <img src="../images/dome.gif"> <I>B</I> = {<I>x</I> : <I>x</I> <img src="../images/memof12.gif"> <I>A</I> and <I>x</I> <img src="../images/memof12.gif"> <I>B</I>} .</sub></sup></pre><P>
<a name="072b_11f5"><a name="072b_11f6"><FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT> The <I><B>union</I></B> of sets <I>A</I> and <I>B</I> is the set<P>
<pre><I>A</I> <img src="../images/wideu.gif"> <I>B</I> = {<I>x</I> : <I>x</I> <img src="../images/memof12.gif"> <I>A</I> and <I>x</I> <img src="../images/memof12.gif"> <I>B</I>} .</sub></sup></pre><P>
<a name="072b_11f7"><a name="072b_11f8"><FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT> The <I><B>difference</I></B> between two sets <I>A</I> and <I>B</I> is the set<P>
<pre><I>A</I> - <I>B</I> = {<I>x</I> : <I>x</I> <img src="../images/memof12.gif"> <I>A</I> and <I>x</I> <img src="../images/notmem.gif"> <I>B</I>} .</sub></sup></pre><P>
Set operations obey the following laws.<P>
<a name="072b_11f9"><B>Empty set laws:</B><P>
<img src="78_b.gif"><P>
<a name="072b_11fa"><B>Idempotency laws:</B><P>
<pre><I>A</I> <img src="../images/dome.gif"> <I>A</I> = <I>A</I>,</sub></sup></pre><P>
<pre><I>A</I> <img src="../images/wideu.gif"> <I>A</I> = <I>A</I>.</sub></sup></pre><P>
<a name="072b_11fb"><B>Commutative laws:</B><P>
<pre><I>A</I> <img src="../images/dome.gif"> B = <I>B</I> <img src="../images/dome.gif"> <I>A</I>,</sub></sup></pre><P>
<pre><I>A</I> <img src="../images/wideu.gif"> B = <I>B</I> <img src="../images/wideu.gif"> <I>A.</I></sub></sup></pre><P>
<a name="072b_11fc"><B>Associative laws:</B><P>
<pre><I>A</I> <img src="../images/dome.gif"> (<I>B</I> <img src="../images/dome.gif"> <I>C</I>) = (<I>A</I> <img src="../images/dome.gif"> <I>B</I>) <img src="../images/dome.gif"> <I>C,</I></sub></sup></pre><P>
<pre><I>A</I> <img src="../images/wideu.gif"> (<I>B</I> <img src="../images/wideu.gif"> <I>C</I>) = (<I>A</I> <img src="../images/wideu.gif"> <I>B</I>) <img src="../images/wideu.gif"> <I>C.</I></sub></sup></pre><P>
<a name="072b_11fd"><B>Distributive laws:</B><P>
<pre><I>A</I> <img src="../images/dome.gif"> (<I>B</I> <img src="../images/wideu.gif"> <I>C</I>) = (<I>A</I> <img src="../images/dome.gif"> <I>B</I>) <img src="../images/wideu.gif"> (<I>A</I> <img src="../images/dome.gif"> <I>C</I>),</sub></sup></pre><P>
<pre><I>A</I> <img src="../images/wideu.gif"> (<I>B</I> <img src="../images/dome.gif"> <I>C</I>) = (<I>A</I> <img src="../images/wideu.gif"> <I>B</I>) <img src="../images/dome.gif"> (<I>A</I> <img src="../images/wideu.gif"> <I>C</I>).</sub></sup></pre><P>
<h4><a name="072b_1218">(5.1)<a name="072b_1218"></sub></sup></h4><P>
<a name="072b_11fe"><B>Absorption laws:</B><P>
<pre><I>A</I> <img src="../images/dome.gif"> (<I>A</I> <img src="../images/wideu.gif"> <I>B</I>) = <I>A</I>,</sub></sup></pre><P>
<pre><I>A</I> <img src="../images/wideu.gif"> (<I>A</I> <img src="../images/dome.gif"> <I>B</I>) = <I>A.</I></sub></sup></pre><P>
<a name="072b_11ff"><B>DeMorgan's laws:</B><P>
<pre><I>A</I> - (<I>B</I> <img src="../images/dome.gif"> <I>C</I>) = (<I>A</I> - <I>B)</I> <img src="../images/wideu.gif"> (<I>A</I> - <I>C</I>),</sub></sup></pre><P>
<pre><I>A</I> - (<I>B</I> <img src="../images/wideu.gif"> <I>C</I>) = (<I>A</I> - <I>B)</I> <img src="../images/dome.gif"> (<I>A</I> - <I>C</I>).</sub></sup></pre><P>
<h4><a name="072b_1219">(5.2)<a name="072b_1219"></sub></sup></h4><P>
<img src="79_a.gif"><P>
<h4><a name="072b_121a">Figure 5.1 A Venn diagram illustrating the first of DeMorgan's laws (5.2). Each of the sets A, B, and C is represented as a circle in the plane.<a name="072b_121a"></sub></sup></h4><P>
<a name="072b_1200">The first of DeMorgan's laws is illustrated in Figure 5.1, using a <I><B>Venn diagram</I></B>, a graphical picture in which sets are represented as regions of the plane.<P>
<a name="072b_1201"><a name="072b_1202">Often, all the sets under consideration are subsets of some larger set <I>U </I>called the <I><B>universe</I>.</B> For example, if we are considering various sets made up only of integers, the set <B>Z</B> of integers is an appropriate universe. Given a universe <I>U</I>, we define the <I><B>complement</I></B> of a set <I>A</I> as <img src="79_b.gif">. For any set <I>A</I> <img src="../images/rgtubar.gif"> <I>U</I>, we have the following laws:<P>
<img src="79_c.gif"><P>
DeMorgan's laws (5.2) can be rewritten with complements. For any two sets <I>A, B</I> <img src="../images/rgtubar.gif"> <I>U</I>, we have<P>
<img src="79_d.gif"><P>
<a name="072b_1203"><a name="072b_1204">Two sets <I>A</I> and <I>B</I> are <I><B>disjoint</I></B> if they have no elements in common, that is, if <img src="79_e.gif">. A collection <I>S</I> = {<I>S<SUB>i</I></SUB>} of nonempty sets forms a <I><B>partition </I></B>of a set <I>S</I> if<P>
<a name="072b_1205"><FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT> the sets are <I><B>pairwise disjoint</I></B>, that is, <I>S<SUB>i</I></SUB>, <I>S<SUB>j</I></SUB> <img src="../images/memof12.gif"> <I><FONT FACE="Courier New" SIZE=2>S</I></FONT> and <I>i</I> <img src="../images/noteq.gif"> <I>j</I> imply <img src="79_f.gif">, and<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -