chap05.htm

美国麻省理工的算法导论,英文版,看后程序员宏观的能力培养有好处

<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT>     their union is <I>S</I>, that is,<P>
<img src="79_g.gif"><P>
In other words, <I>S</I> forms a partition of <I>S</I> if each element of <I>S</I> appears in exactly one <I>S<SUB>i</I></SUB> <img src="../images/memof12.gif"> <I>S</I>.<P>
<a name="072b_1206"><a name="072b_1207"><a name="072b_1208"><a name="072b_1209"><a name="072b_120a"><a name="072b_120b"><a name="072b_120c">The number of elements in a set is called the <I><B>cardinality</I></B> (<I>or <B>size</I></B>) of the set, denoted |<I>S|</I>. Two sets have the same cardinality if their elements can be put into a one-to-one correspondence. The cardinality of the empty set is <img src="79_h.gif">. If the cardinality of a set is a natural number, we say the set is <I><B>finite</I></B>; otherwise, it is <I><B>infinite</I></B>. An infinite set that can be put into a one-to-one correspondence with the natural numbers <B>N</B> is <I><B>countably infinite</I></B>; otherwise, it is <I><B>uncountable</I></B>. The integers <B>Z</B> are countable, but the reals <B>R</B> are uncountable.<P>
For any two finite sets <I>A</I> and <I>B</I>, we have the identity<P>
<pre><I>|A</I> <img src="../images/wideu.gif"> <I>B| = |</I>A| + |<I>B| - |</I>A<I> <img src="../images/dome.gif"> </I>B| <I>,</I></sub></sup></pre><P>
<h4><a name="072b_121b">(5.3)<a name="072b_121b"></sub></sup></h4><P>
from which we can conclude that<P>
<pre><I>|A</I> <img src="../images/wideu.gif"> <I>B| <img src="../images/lteq12.gif"> |</I>A| + |<I>B| </I>.</sub></sup></pre><P>
If <I>A</I> and <I>B</I> are disjoint, then |<I>A</I> <FONT FACE="Times New Roman" SIZE=3><img src="../images/dome.gif"></FONT> <I>B| = 0 and thus |</I>A<I> <FONT FACE="Times New Roman" SIZE=3><img src="../images/wideu.gif"></FONT> </I>B| = |<I>A| + |</I>B|. If <I>A </I><img src="../images/rgtubar.gif"> <I>B</I>, then |<I>A| <img src="../images/lteq12.gif"> |</I>B|.<P>
<a name="072b_120d"><a name="072b_120e"><a name="072b_120f">A finite set of <I>n</I> elements is sometimes called an <I><B>n-set</I></B>. A 1-set is called a <I><B>singleton</I></B>. A subset of <I>k</I> elements of a set is sometimes called a <I><B>k-subset</I></B>.<P>
<a name="072b_1210">The set of all subsets of a set <I>S</I>, including the empty set and the set <I>S </I>itself, is denoted 2<I><SUP>S</I></SUP> and is called the <I><B>power set</I></B> of <I>S</I>. For example, <img src="80_a.gif">. The power set of a finite set <I>S</I> has cardinality 2<SUP>|<I></SUP>S|.</I><P>
<a name="072b_1211">We sometimes care about setlike structures in which the elements are ordered. An <I><B>ordered pair</I></B> of two elements <I>a</I> and <I>b</I> is denoted (<I>a, b</I>) and can be defined formally as the set (<I>a, b</I>) = {<I>a</I>, {<I>a, b</I>}}. Thus, the ordered pair (<I>a, b</I>) is <I>not</I> the same as the ordered pair (<I>b, a</I>).<P>
<a name="072b_1212"><a name="072b_1213"><a name="072b_1214">The <I><B>Cartesian product</I> </B>of two sets <I>A</I> and <I>B</I>, denoted <I>A</I> <img src="../images/mult.gif"> <I>B</I>, is the set of all ordered pairs such that the first element of the pair is an element of <I>A </I>and the second is an element of <I>B</I>. More formally,<P>
<pre><I>A</I> <img src="../images/mult.gif"> <I>B</I> = {(<I>a,b</I>) : <I>a</I> <img src="../images/memof12.gif"> <I>A</I> and <I>b</I> <img src="../images/memof12.gif"> <I>B</I>}.</sub></sup></pre><P>
For example, {<I>a, b</I>} <img src="../images/mult.gif"> {<I>a, b, c</I>} = {(<I>a, a</I>), (<I>a, b</I>), (<I>a, c</I>), (<I>b, a</I>), (<I>b, b</I>), (<I>b, c</I>)}. When <I>A</I> and <I>B</I> are finite sets, the cardinality of their Cartesian product is<P>
<pre><I>|A</I> <img src="../images/mult.gif"> <I>B| = |</I>A| <I><img src="../images/dot10.gif"> |</I>B| .</sub></sup></pre><P>
<h4><a name="072b_121c">(5.4)<a name="072b_121c"></sub></sup></h4><P>
<a name="072b_1215"><a name="072b_1216">The Cartesian product of <I>n</I> sets <I>A</I><SUB>l</SUB>, <I>A</I><SUB>2</SUB>,. . . , <I>A<SUB>n</I></SUB> is the set of <I><B>n-tuples</I></B><P>
<pre><I>A</I><SUB>1</SUB> <img src="../images/mult.gif"> <I>A</I><SUB>2</SUB> <img src="../images/mult.gif"> <img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif"> <img src="../images/mult.gif"> <I>A<SUB>n</I></SUB> = {(<I>a</I><SUB>1</SUB>,<I>a</I><SUB>2</SUB>,...,<I>a<SUB>n</I></SUB>):<I>a<SUB>i </I></SUB><img src="../images/memof12.gif"> <I>A<SUB>i</I></SUB>,<I>i</I> = 1, 2,...,<I>n</I>} ,</sub></sup></pre><P>
whose cardinality is<P>
<pre><I>|A</I><SUB>1</SUB> <img src="../images/mult.gif"> <I>A</I><SUB>2</SUB> <img src="../images/mult.gif"> <img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif"> <img src="../images/mult.gif"> <I>A<SUB>n</I></SUB>| = |<I>A</I><SUB>1</SUB>| <img src="../images/dot10.gif"> |<I>A</I><SUB>2</SUB>| <img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif"> |<I>A<SUB>n</I></SUB>|</sub></sup></pre><P>
if all sets are finite. We denote an <I>n-</I>fold Cartesian product over a single set <I>A</I> by the set<P>
<pre><I>A<SUP>n</I></SUP> = <I>A</I> <img src="../images/mult.gif"> <I>A</I> <img src="../images/mult.gif"> <img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif"> <img src="../images/mult.gif"> <I>A </I>,</sub></sup></pre><P>
whose cardinality is |<I>A<SUP>n</I></SUP>| = |<I>A|</I><SUP>n<I></SUP></I> if <I>A</I> is finite. An <I>n-</I>tuple can also be viewed as a finite sequence of length <I>n</I> (see page 84).<P>





<h2><a name="072c_1218">Exercises<a name="072c_1218"></h2><P>
<a name="072c_1219">5.1-1<a name="072c_1219"><P>
Draw Venn diagrams that illustrate the first of the distributive laws (5.1).<P>
<a name="072c_121a">5.1-2<a name="072c_121a"><P>
Prove the generalization of DeMorgan's laws to any finite collection of sets:<P>
<img src="81_a.gif"><P>
<a name="072c_121b">5.1-3<a name="072c_121b"><P>
<a name="072c_1217">Prove the generalization of equation (5.3), which is called the<I><B> principle of inclusion and exclusion:</B></I><P>
<pre><I>|A</I><SUB>1 </SUB><img src="../images/wideu.gif"><I> A</I><SUB>2 </SUB><img src="../images/wideu.gif"><I> </I><img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif"> <img src="../images/wideu.gif"><I> A<SUB>n</I></SUB>|<I><SUB> =</I></sub></sup></pre><P>
<pre><I>|A</I><SUB>1</SUB>| + |<I>A</I><SUB>2</SUB>| + <img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif"> + |<I>A<SUB>n</SUB>|</I></sub></sup></pre><P>
<pre>-|<I>A</I><SUB>1</SUB> <img src="../images/dome.gif"> <I>A</I><SUB>2</SUB>| - |<I>A</I><SUB>1 </SUB><img src="../images/dome.gif"> <I>A</I><SUB>3</SUB>| - <img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif">     (all pairs)</sub></sup></pre><P>
<pre>+|<I>A</I><SUB>1</SUB> <img src="../images/dome.gif"> <I>A</I><SUB>2</SUB> <img src="../images/dome.gif"> <I>A</I><SUB>3</SUB><img src="../images/sglvrt.gif"> + <img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif">            (all triples)</sub></sup></pre><P>
<img src="81_b.gif"><P>
<pre>+(-1)<I><SUP>n</I>-1 </SUP>|<I>A</I><SUB>1</SUB> <img src="../images/dome.gif"> <I>A</I><SUB>2</SUB> <img src="../images/dome.gif"> <img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif"> <img src="../images/dome.gif"> <I>A<SUB>n</I></SUB>|<I> .</I></sub></sup></pre><P>
<a name="072c_121c">5.1-4<a name="072c_121c"><P>
Show that the set of odd natural numbers is countable.<P>
<a name="072c_121d">5.1-5<a name="072c_121d"><P>
Show that for any finite set <I>S</I>, the power set 2<I><SUP>S </I></SUP>has 2<SUP>|<I></SUP>S</I>| elements (that is, there are 2<SUP>|<I></SUP>S</I>| distinct subsets of <I>S</I>).<P>
<a name="072c_121e">5.1-6<a name="072c_121e"><P>
Give an inductive definition for an <I>n-</I>tuple by extending the set-theoretic definition for an ordered pair.<P>
<P>


<P>







<h1><a name="072d_1229">5.2 Relations<a name="072d_1229"></h1><P>
<a name="072d_1218"><a name="072d_1219">A<I><B> binary relation</I></B> <I>R</I> on two sets <I>A</I> and <I>B</I> is a subset of the Cartesian product <I>A</I> <img src="../images/mult.gif"> <I>B</I>. If (<I>a, b</I>) <img src="../images/memof12.gif"> <I>R</I>, we sometimes write <I>a</I> <I>R</I> <I>b</I>. When we say that <I>R</I> is a binary relation on a set <I>A</I>, we mean that <I>R</I> is a subset of <I>A</I> <img src="../images/mult.gif"> <I>A</I>. For example, the "less than" relation on the natural numbers is the set {(<I>a,b</I>): <I>a,b</I> <img src="../images/memof12.gif"> <B>N</B> and <I>a </I>&lt; <I>b</I>}. An <I>n</I>-ary relation on sets <I>A</I><SUB>1</SUB>, <I>A</I><SUB>2</SUB>, . . . , <I>A<SUB>n</I></SUB> is a subset of <I>A</I><SUB>1</SUB><I> </I><img src="../images/mult.gif"><I> A<SUB>2</SUB> </I> <img src="../images/mult.gif">  <img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif"> <img src="../images/mult.gif"> <I> A<SUB>n</SUB>.</I><P>
<a name="072d_121a"><a name="072d_121b"><a name="072d_121c">A binary relation <I>R</I> <img src="../images/rgtubar.gif"> A<I> <img src="../images/mult.gif"> </I>A <I>is<B> </B></I><B>reflexive<I> </B>if</I><P>
<pre><I>a</I> <I>R</I> <I>a</I></sub></sup></pre><P>