chap05.htm

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

for all <I>a </I><img src="../images/memof12.gif"><I> A</I>. For example, &quot;=&quot; and &quot;<img src="../images/lteq12.gif">&quot; are reflexive relations on <B>N</B>, but &quot;&lt;&quot; is not. The relation <I>R</I> is <I><B>symmetric</I></B> if<P>
<pre><I>a</I> <I>R</I> <I>b</I> implies <I>b</I> <I>R</I> <I>a</I></sub></sup></pre><P>
for all <I>a</I>, <I>b</I> <img src="../images/memof12.gif"> <I>A</I>. For example, &quot;=&quot; is symmetric, but &quot;&lt;&quot; and &quot;<img src="../images/lteq12.gif">&quot; are not. The relation <I>R</I> is <I><B>transitive</I></B> if<P>
<pre><I>a</I> <I>R</I> <I>b</I> and <I>b</I> <I>R</I> <I>c</I> imply <I>a R</I> <I>c</I></sub></sup></pre><P>
for all <I>a,b,c</I> <img src="../images/memof12.gif"> <I>A</I>. For example, the relations &quot;&lt;,&quot; &quot;<img src="../images/lteq12.gif">,&quot; and &quot;=&quot; are transitive, but the relation <I>R</I> = {(<I>a, b</I>): <I>a, b</I> <img src="../images/memof12.gif"> <B>N</B> and <I>a</I> = <I>b</I> - 1 } is not, since 3 <I>R</I> 4 and 4 <I>R</I> 5 do not imply 3 <I>R</I> 5.<P>
<a name="072d_121d"><a name="072d_121e"><a name="072d_121f">A relation that is reflexive, symmetric, and transitive is an <I><B>equivalence relation</I>.</B> For example, &quot;=&quot; is an equivalence relation on the natural numbers, but &quot;&lt;&quot; is not. If <I>R</I> is an equivalence relation on a set <I>A</I>, then for <I>a</I> <img src="../images/memof12.gif"><I>A</I>, the <I><B>equivalence class</I></B> of <I>a</I> is the set [<I>a</I>] = {<I>b</I> <img src="../images/memof12.gif"> <I>A</I>: <I>a</I> <I>R</I> <I>b</I>}, that is, the set of all elements equivalent to <I>A</I>. For example, if we define <I>R</I> = {(<I>a, b</I>): <I>a, b</I> <img src="../images/memof12.gif"> <B>N</B> and <I>a</I> + <I>b</I> is an even number}, then <I>R</I> is an equivalence relation, since <I>a</I> + <I>a</I> is even (reflexive), <I>a </I>+ <I>b</I> is even implies <I>b</I> + <I>a </I>is even (symmetric), and <I>a</I> + <I>b</I> is even and <I>b </I>+ <I>c </I>is even imply <I>a</I> + <I>c</I> is even (transitive). The equivalence class of 4 is [4] = {0, 2, 4, 6, . . .}, and the equivalence class of 3 is [3] = {1, 3, 5, 7, . . .}. A basic theorem of equivalence classes is the following.<P>
<a name="072d_122a">Theorem 5.1<a name="072d_122a"><P>
<a name="072d_1220">The equivalence classes of any equivalence relation <I>R</I> on a set <I>A</I> form a partition of <I>A</I>, and any partition of <I>A</I> determines an equivalence relation on <I>A</I> for which the sets in the partition are the equivalence classes.<P>
<I><B>Proof     </I></B>For the first part of the proof, we must show that the equivalence classes of <I>R</I> are nonempty, pairwise-disjoint sets whose union is <I>A</I>. Because <I>R</I> is reflexive, <I>a</I> <img src="../images/memof12.gif"> [<I>a</I>], and so the equivalence classes are nonempty; moreover, since every element <I>a</I> <img src="../images/memof12.gif"> <I>A</I> belongs to the equivalence class [<I>a</I>], the union of the equivalence classes is <I>A</I>. It remains to show that the equivalence classes are pairwise disjoint, that is, if two equivalence classes [<I>a</I>] and [<I>b</I>] have an element <I>c</I> in common, then they are in fact the same set. Now a <I>R</I> <I>c</I> and <I>b</I> <I>R</I> c, which by symmetry and transitivity imply <I>a</I> <I>R</I> <I>b</I>. Thus, for any arbitrary element <I>x</I> <img src="../images/memof12.gif"> [<I>a</I>], we have <I>x</I> <I>R</I> a implies <I>x</I> <I>R</I> <I>b</I>, and thus [<I>a</I>] <img src="../images/rgtubar.gif"> [<I>b</I>]. Similarly, [<I>b</I>] <img src="../images/rgtubar.gif"> [<I>a</I>], and thus [<I>a</I>] = [<I>b</I>].<P>
For the second part of the proof, let <I>A</I> = {<I>A<SUB>i</I></SUB>} be a partition of <I>A</I>, and define <I>R</I> = {(<I>a,b</I>): there exists <I>i</I> such that <I>a</I> <img src="../images/memof12.gif"> <I>A<SUB>i</I></SUB> and <I>b</I> <img src="../images/memof12.gif"> <I>A<SUB>i</I></SUB>}. We claim that <I>R</I> is an equivalence relation on <I>A</I>. Reflexivity holds, since <I>a </I><img src="../images/memof12.gif"> <I>A<SUB>i</I></SUB> implies <I>a</I> <I>R</I> <I>a</I>. Symmetry holds, because if <I>a</I> <I>R</I> <I>b</I>, then <I>a</I> and <I>b</I> are in the same set <I>A<SUB>i</I></SUB>, and hence <I>b</I> <I>R</I> <I>a</I>. If <I>a</I> <I>R</I> <I>b </I>and <I>b</I> <I>R</I> <I>c</I>, then all three elements are in the same set, and thus <I>a</I> <I>R</I> <I>c</I> and transitivity holds. To see that the sets in the partition are the equivalence classes of <I>R</I>, observe that if <I>a</I> <img src="../images/memof12.gif"> <I>A<SUB>i</I></SUB>, then <I>x</I> <img src="../images/memof12.gif"> [<I>a</I>] implies <I>x</I> <img src="../images/memof12.gif"> <I>A<SUB>i</I></SUB>, and <I>x</I> <img src="../images/memof12.gif"> <I>A<SUB>i</I></SUB> implies <I>x</I> <img src="../images/memof12.gif"> [<I>a</I>].      <P>
<a name="072d_1221">A binary relation <I>R</I> on a set <I>A</I> is <I><B>antisymmetric</I></B> if<P>
<pre><I>a</I> <I>R</I> <I>b</I> and <I>b</I> <I>R</I> <I>a</I> imply <I>a</I> = <I>b</I> .</sub></sup></pre><P>
<a name="072d_1222"><a name="072d_1223"><a name="072d_1224">For example, the &quot;<img src="../images/lteq12.gif">&quot; relation on the natural numbers is antisymmetric, since <I>a</I> <img src="../images/lteq12.gif"> <I>b</I> and <I>b</I> <img src="../images/lteq12.gif"> <I>a</I> imply <I>a</I> = <I>b</I>. A relation that is reflexive, antisymmetric, and transitive is a <I><B>partial order</I></B>, and we call a set on which a partial order is defined a <I><B>partially ordered set</I></B>. For example, the relation &quot;is a descendant of&quot; is a partial order on the set of all people (if we view individuals as being their own descendants).<P>
In a partially ordered set <I>A</I>, there may be no single &quot;maximum&quot; element <I>x</I> such that <I>y</I> <I>R</I> <I>x</I> for all <I>y</I> <img src="../images/memof12.gif"> <I>A</I>. Instead, there may several <I><B>maximal</I></B> elements <I>x</I> such that for no <I>y</I> <img src="../images/memof12.gif"> <I>A</I> is it the case that <I>x</I> <I>R</I> y. For example, in a collection of different-sized boxes there may be several maximal boxes that don't fit inside of any other box, yet no single &quot;maximum&quot; box into which any other box will fit.<P>
<a name="072d_1225"><a name="072d_1226"><a name="072d_1227"><a name="072d_1228">A partial order <I>R</I> on a set <I>A</I> is a <I><B>total</I></B> or <I><B>linear order</I></B><I> </I>if for all <I>a, b</I> <img src="../images/memof12.gif"> <I>A</I>, we have <I>a</I> <I>R</I> <I>b</I> or <I>b</I> <I>R a</I>, that is, if every pairing of elements of <I>A</I> can be related by <I>R</I>. For example, the relation &quot;<img src="../images/lteq12.gif">&quot; is a total order on the natural numbers, but the &quot;is a descendant of&quot; relation is not a total order on the set of all people, since there are individuals neither of whom is descended from the other.<P>





<h2><a name="072e_122c">Exercises<a name="072e_122c"></h2><P>
<a name="072e_122d">5.2-1<a name="072e_122d"><P>
Prove that the subset relation <FONT FACE="CG Times (W1)" SIZE=2>"<img src="../images/rgtubar.gif"></FONT><FONT FACE="CG Times (W1)" SIZE=2></FONT> on all subsets of <B>Z </B>is a partial order but not a total order.<P>
<a name="072e_122e">5.2-2<a name="072e_122e"><P>
<a name="072e_1229"><a name="072e_122a"><a name="072e_122b">Show that for any positive integer <I>n</I>, the relation <FONT FACE="CG Times (W1)" SIZE=2>"</FONT>equivalent modulo <I>n</I>" is an equivalence relation on the integers. (We say that <I>a</I> <img src="../images/equiv10.gif"> <I>b </I>(mod <I>n</I>) if there exists an integer <I>q</I> such that <I>a</I> - <I>b</I> =<I>qn</I>.) Into what equivalence classes does this relation partition the integers?<P>
<a name="072e_122f">5.2-3<a name="072e_122f"><P>
Give examples of relations that are<P>
<I><B>a</I>.</B>      reflexive and symmetric but not transitive,<P>
<I><B>b.</I></B>     reflexive and transitive but not symmetric,<P>
<I><B>c.     </I></B>symmetric and transitive but not reflexive.<P>
<a name="072e_1230">5.2-4<a name="072e_1230"><P>
Let <I>S</I> be a finite set, and let <I>R</I> be an equivalence relation on <I>S</I> <img src="../images/mult.gif"> <I>S</I>. Show that if in addition <I>R</I> is antisymmetric, then the equivalence classes of <I>S</I> with respect to <I>R</I> are singletons.<P>
<a name="072e_1231">5.2-5<a name="072e_1231"><P>
Professor Narcissus claims that if a relation <I>R</I> is symmetric and transitive, then it is also reflexive. He offers the following proof. By symmetry, <I>a</I> <I>R</I> <I>b</I> implies <I>b</I> <I>R</I> <I>a</I>. Transitivity, therefore, implies <I>a</I> <I>R</I> <I>a</I>. Is the professor correct?<P>
<P>


<P>







<h1><a name="072f_1241">5.3 Functions<a name="072f_1241"></h1><P>
<a name="072f_122c"><a name="072f_122d"><a name="072f_122e">Given two sets <I>A</I> and <I>B</I>, a <I><B>function</I></B> <I>f</I> is a binary relation on <I>A </I><img src="../images/mult.gif"> <I>B</I> such that for all <I>a</I> <img src="../images/memof12.gif"> <I>A</I>, there exists precisely one <I>b </I><img src="../images/memof12.gif"> <I>B</I> such that (<I>a,b</I>) <img src="../images/memof12.gif"> <img src="../images/scrptf12.gif">. The set <I>A</I> is called the <I><B>domain</I> </B>of <I>f</I>, and the set <I>B</I> is called the <I><B>codomain </I></B>of <I>f</I>. We sometimes write <I>f</I>: <I>A</I> <img src="../images/arrow12.gif"> <I>B</I>; and if (<I>a, b</I>) <img src="../images/memof12.gif"> <I>f</I>, we write <I>b</I> = <I>f</I> (<I>a</I>), since <I>b</I> is uniquely determined by the choice of <I>a</I>.<P>
Intuitively, the function <I>f</I> assigns an element of <I>B</I> to each element of <I>A</I>. No element of <I>A</I> is assigned two different elements of <I>B</I>, but the same element of <I>B</I> can be assigned to two different elements of <I>A</I>. For example, the binary relation<P>
<pre><I>f</I> = {(<I>a,b</I>) : <I>a</I> <img src="../images/memof12.gif"> <B>N</B> and <I>b</I> = <I>a</I> mod 2 }</sub></sup></pre><P>
is a function <I>f </I>: <B>N</B> <img src="../images/arrow12.gif"> {0,1}, since for each natural number <I>a</I>, there is exactly one value <I>b</I> in {0, 1} such that <I>b</I> = <I>a</I> mod 2. For this example 0 = <I>f </I>(0), 1 = <I>f</I> (1), 0 = <I>f </I>(2), etc. In contrast, the binary relation<P>
<pre><I>g</I> = {(<I>a</I>,<I>b</I>) : <I>a</I> <img src="../images/memof12.gif"> <B>N</B> and <I>a</I> + <I>b</I> is even}</sub></sup></pre><P>
is not a function, since (1, 3) and (1, 5) are both in <I>g</I>, and thus for the choice <I>a</I> = 1, there is not precisely one <I>b</I> such that (<I>a, b</I>) <img src="../images/memof12.gif"> <I>g</I>.<P>
<a name="072f_122f"><a name="072f_1230"><a name="072f_1231">Given a function <I>f </I>: <I>A</I> <img src="../images/arrow12.gif"> <I>B</I>, if <I>b</I> = <I>f</I> (<I>a</I>), we say that <I>a</I> is the <I><B>argument </I></B>of <I>f</I> and that <I>b</I> is the <I><B>value</I></B> of <I>f</I> at <I>a</I>. We can define a function by stating its value for every element of its domain. For example, we might define <I>f </I>(<I>n</I>) = 2<I>n</I> for <I>n</I> <img src="../images/memof12.gif"> <B>N</B>, which means <I>f </I>= {(<I>n</I>,2<I>n</I>): <I>n</I> <img src="../images/memof12.gif"> <B>N</B>}. Two functions <I>f </I>and <I>g</I> are <I><B>equal</I></B> if they have the same domain and codomain and if, for all <I>a</I> in the domain, <I>f </I>(<I>a</I>) = <I>g</I>(<I>a</I>).<P>
<a name="072f_1232"><a name="072f_1233"><a name="072f_1234"><a name="072f_1235"><a name="072f_1236">A <I><B>finite sequence </I></B>of length <I>n</I> is a function<I> f </I>whose domain is the set {0, 1, . . . , <I>n</I> - 1}. We often denote a finite sequence by listing its values: <img src="../images/lftwdchv.gif"><I>f </I>(0), <I>f </I>(1), . . . , <I>f</I> (<I>n</I> - 1)<img src="../images/wdrtchv.gif">. An <I><B>infinite sequence</I></B> is a function whose domain is the set <B>N</B> of natural numbers. For example, the Fibonacci sequence, defined by (2.13), is the infinite sequence <FONT FACE="Times New Roman" SIZE=3><img src="../images/lftwdchv.gif"></FONT>0, 1, 1, 2, 3, 5, 8, 13, 21, . . .<img src="../images/wdrtchv.gif">.<P>
When the domain of a function <I>f </I>is a Cartesian product, we often omit the extra parentheses surrounding the argument of <I>f</I>. For example, if <I>f </I>: <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"><I> </I><img src="../images/mult.gif"> <I>A<SUB>n</I></SUB> <img src="../images/arrow12.gif"> <I>B</I>, we would write <I>b</I> = <I>f </I>(<I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I></SUB>) instead of <I>b</I> = <I>f </I>((<I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I></SUB>)). We also call each <I>a<SUB>i</I></SUB>, an <I><B>argument</I></B> to the function <I>f </I>, though technically the (single) argument to <I>f </I>is the <I>n-</I>tuple (<I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . ,<I>a</I><SUB>n</SUB>).<P>
<a name="072f_1237">If <I>f </I>: <I>A</I> <img src="../images/arrow12.gif"> <I>B</I> is a function and <I>b</I> = <I>f </I>(<I>a</I>), then we sometimes say that <I>b </I>is the <I><B>image</I></B> of <I>a</I> under <I>f </I>. The image of a set <I>A</I>'<img src="../images/rgtubar.gif"> <I>A</I> under <I>f </I>is defined by<P>
<pre><I>f</I>(<I>A</I>' = {<I>b</I> <img src="../images/memof12.gif"> <I>B : b</I> = <I>f</I>(<I>a</I>) for some <I>a</I> <img src="../images/memof12.gif"> <I>A</I>'} .</sub></sup></pre><P>
<a name="072f_1238">The <I><B>range</I></B> of <I>f</I> is the image of its domain, that is, <I>f </I>(<I>A</I>). For example, the range of the function <I>f </I>: <B>N</B> <img src="../images/arrow12.gif"> <B>N</B> defined by <I>f </I>(<I>n</I>) = 2<I>n</I> is <I>f </I>(<B>N</B>)<I> = </I>{<I>m </I>: <I>m </I>= 2<I>n</I> for some <I>n</I> <img src="../images/memof12.gif"> <B>N</B>}.<P>
<a name="072f_1239"><a name="072f_123a">A function is a <I><B>surjection</I></B> if its range is its codomain. For example, the function <I>f</I>(<I>n</I>) = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> is a surjective function from <B>N</B> to <B>N</B>, since every element in <B>N</B> appears as the value of <I>f </I>for some argument. In contrast, the function <I>f</I>(<I>n</I>) = 2<I>n</I> is not a surjective function from <B>N</B> to <B>N</B>, since no argument to <I>f </I>can produce 3 as a value. The function <I>f </I>(<I>n</I>) = 2<I>n</I> is, however, a surjective function from the natural numbers to the even numbers. A surjection <I>f </I>: <I>A</I> <img src="../images/arrow12.gif"> <I>B</I> is sometimes described as mapping <I>A</I> <I><B>onto</I></B><I> B</I>. When we say that <I>f </I>is onto, we mean that it is surjective.<P>
<a name="072f_123b"><a name="072f_123c">A function <I>f </I>: <I>A</I> <img src="../images/arrow12.gif"> <I>B</I> is an<I> <B>injection</I></B> if distinct arguments to &acirc; produce<B> </B>distinct values, that is, if <I>a</I> <img src="../images/noteq.gif"> <I>a</I>' implies <I>&acirc;</I>(<I>a</I>)<I> = &acirc;</I>(<I>a</I>'). For example, the function <I>f </I>(<I>n</I>) = 2<I>n</I> is an injective function from <B>N</B> to <B>N</B>, since each even number <I>b</I> is the image under <I>&acirc;</I> of at most one element of the domain, namely <I>b</I>/2. The function <I>f </I>(<I>n</I>) = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> is not injective, since the value 1 is produced by two arguments: 2 and 3. An injection is sometimes called a <I><B>one-to-one</I></B> function.<P>
<a name="072f_123d">A function <I>f </I>: <I>A</I> <img src="../images/arrow12.gif"> <I>B</I> is a <I><B>bijection</I></B> if it is injective and surjective. For example, the function <I>f </I>(<I>n</I>) = (-1)<I><SUP>n</I></SUP> <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrur14.gif"></FONT> is a bijection from <B>N</B> to <B>Z</B>:<P>
<pre>0 <img src="../images/leftu.gif"> <img src="../images/arrow12.gif">  0 ,</sub></sup></pre><P>
<pre>1  <img src="../images/arrow12.gif">  -1 ,</sub></sup></pre><P>
<pre>2  <img src="../images/arrow12.gif">  1 ,</sub></sup></pre><P>
<pre>3  <img src="../images/arrow12.gif">  -2 ,</sub></sup></pre><P>