{"id":815,"date":"2012-06-29T13:39:07","date_gmt":"2012-06-29T05:39:07","guid":{"rendered":"http:\/\/www.dogeye.net\/?p=815"},"modified":"2012-06-29T13:39:07","modified_gmt":"2012-06-29T05:39:07","slug":"%e4%b8%ad%e5%b1%b1%e5%a4%a7%e5%ad%a6%e7%a6%bb%e6%95%a3%e6%95%b0%e5%ad%a6%e8%80%83%e8%af%95%e8%af%95%e9%a2%98","status":"publish","type":"post","link":"https:\/\/ykyi.net\/?p=815","title":{"rendered":"\u4e2d\u5c71\u5927\u5b66\u79bb\u6563\u6570\u5b66\u8003\u8bd5\u8bd5\u9898"},"content":{"rendered":"<h3><strong>\u300a\u79bb\u6563\u6570\u5b66\u300b\u671f\u672b\u8bd5\u9898(A\u5377)<\/strong><\/h3>\n<p><a href=\"http:\/\/ykyi.net\">ykyi.net<\/a><\/p>\n<p>(\u8003\u8bd5\u5f62\u5f0f:\u95ed\u5377&nbsp;&nbsp;\u8003\u8bd5\u65f6\u95f4:2\u5c0f\u65f6)<\/p>\n<p>\u300a\u4e2d\u5c71\u5927\u5b66\u6388\u4e88\u5b66\u58eb\u5b66\u4f4d\u5de5\u4f5c\u7ec6\u5219\u300b\u7b2c\u516d\u6761<\/p>\n<p>\u8003\u8bd5\u4f5c\u5f0a\u4e0d\u6388\u4e88\u5b66\u58eb\u5b66\u4f4d<\/p>\n<p>\u65b9\u5411\uff1a&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\u59d3\u540d\uff1a&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\u5b66\u53f7\uff1a&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<\/p>\n<p>\u51fa\u5377\uff1a &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;\u590d\u6838\uff1a&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<\/p>\n<p style=\"margin-left:13.2500pt;\">1.&nbsp;(10&nbsp;points)&nbsp;&nbsp;A,&nbsp;B&nbsp;and&nbsp;C&nbsp;are&nbsp;sets,&nbsp;prove&nbsp;or&nbsp;disprove&nbsp;the&nbsp;following&nbsp;statements.<\/p>\n<p style=\"margin-left:10.5000pt;\">(1).&nbsp;if&nbsp;A&nbsp;&ndash;&nbsp;B&nbsp;=&nbsp;A&nbsp;&ndash;&nbsp;C,&nbsp;then&nbsp;B&nbsp;=&nbsp;C<\/p>\n<p style=\"margin-left:10.5000pt;\">(2).&nbsp;if&nbsp;A&nbsp;&acute;&nbsp;B&nbsp;=&nbsp;A&nbsp;&acute;&nbsp;C,&nbsp;A&nbsp;&sup1;&nbsp;&AElig;,&nbsp;then&nbsp;B&nbsp;=&nbsp;C<\/p>\n<p style=\"margin-left:13.2500pt;\">2.&nbsp;(10&nbsp;points)&nbsp;&nbsp;Write&nbsp;each&nbsp;of&nbsp;the&nbsp;following&nbsp;statements&nbsp;in&nbsp;terms&nbsp;of&nbsp;propositional&nbsp;variables,&nbsp;predicates,&nbsp;quantifiers&nbsp;and&nbsp;logical&nbsp;connectives.&nbsp;You&nbsp;can&nbsp;choose&nbsp;any&nbsp;propositional&nbsp;variables&nbsp;and&nbsp;predicates&nbsp;freely.<\/p>\n<p style=\"margin-left:10.5000pt;\">(1).&nbsp;If&nbsp;I&nbsp;like&nbsp;the&nbsp;course&nbsp;or&nbsp;the&nbsp;teacher,&nbsp;I&nbsp;will&nbsp;attend&nbsp;the&nbsp;class. (statement&nbsp;and&nbsp;its&nbsp;negation)<\/p>\n<p style=\"margin-left:10.5000pt;\">(2).&nbsp;For&nbsp;all&nbsp;students&nbsp;of&nbsp;our&nbsp;school,&nbsp;someone&nbsp;studies&nbsp;hard&nbsp;and&nbsp;has&nbsp;good&nbsp;score,&nbsp;someone&nbsp;studies&nbsp;hard&nbsp;and&nbsp;does&nbsp;not&nbsp;have&nbsp;good&nbsp;score.<\/p>\n<p style=\"margin-left:10.5000pt;\">Note:&nbsp;The&nbsp;first&nbsp;question&nbsp;is&nbsp;expressed&nbsp;in&nbsp;propositional&nbsp;logic,&nbsp;the&nbsp;second&nbsp;is&nbsp;expressed&nbsp;in&nbsp;predicate&nbsp;logic.<\/p>\n<p style=\"margin-left:13.2500pt;\">3.&nbsp;(15&nbsp;points)&nbsp;Let&nbsp;A={a,b,c,d,e},&nbsp;a&nbsp;relation&nbsp;R&nbsp;on&nbsp;A&nbsp;is&nbsp;{(a,b),&nbsp;(b,b),&nbsp;(b,c),&nbsp;(b,d),&nbsp;(c,d),&nbsp;(d,d),&nbsp;(d,e),&nbsp;(e,d)}.<\/p>\n<p style=\"margin-left:10.5000pt;\">(1)&nbsp;Give&nbsp;the&nbsp;digraph&nbsp;and&nbsp;matrix&nbsp;of&nbsp;relation&nbsp;R;<\/p>\n<p style=\"margin-left:10.5000pt;\">(2)&nbsp;Compute&nbsp;R2,&nbsp;reflexive&nbsp;closure&nbsp;r(R)&nbsp;and&nbsp;symmetric&nbsp;closure&nbsp;s(R).<\/p>\n<p style=\"margin-left:13.2500pt;\">4.&nbsp;(15&nbsp;points)&nbsp;Let&nbsp;S&Icirc;Z+&nbsp;and&nbsp;A=S&times;S.&nbsp;Define&nbsp;the&nbsp;following&nbsp;relation&nbsp;R&nbsp;on&nbsp;A:<\/p>\n<p style=\"margin-left:13.2000pt;\">(a,b)&nbsp;R&nbsp;(a&prime;,b&prime;)&nbsp;if&nbsp;and&nbsp;only&nbsp;if&nbsp;ab&prime;=a&prime;b<\/p>\n<p style=\"margin-left:10.5000pt;\">(1)&nbsp;Show&nbsp;that&nbsp;R&nbsp;is&nbsp;an&nbsp;equivalent&nbsp;relation;<\/p>\n<p style=\"margin-left:10.5000pt;\">(2)&nbsp;Let&nbsp;S={1,2,3,4,5,6,7,8,9},&nbsp;compute&nbsp;the&nbsp;equivalent&nbsp;class&nbsp;[(2,4)].<\/p>\n<p>5.&nbsp;(10&nbsp;points)&nbsp;Let&nbsp;function&nbsp;f(x,&nbsp;y)=(&nbsp;x+3y,&nbsp;2x+y),&nbsp;(x,&nbsp;y)&Icirc;R&times;R,&nbsp;prove&nbsp;that&nbsp;f&nbsp;is&nbsp;bijection.<\/p>\n<p>6.&nbsp;(15&nbsp;points)&nbsp;Let&nbsp;A={2,&nbsp;4,&nbsp;5,&nbsp;6,&nbsp;8,&nbsp;10,&nbsp;12,&nbsp;20,&nbsp;120},&nbsp;R&nbsp;is&nbsp;the&nbsp;relation&nbsp;of&nbsp;divisibility&nbsp;on&nbsp;A.<\/p>\n<p style=\"margin-left:10.5000pt;\">(1)&nbsp;Draw&nbsp;the&nbsp;Hasse&nbsp;diagram&nbsp;of&nbsp;the&nbsp;poset&nbsp;&lt;A,&nbsp;R&gt;;<\/p>\n<p style=\"margin-left:10.5000pt;\">(2)&nbsp;Find&nbsp;all&nbsp;the&nbsp;minimal&nbsp;elements,&nbsp;the&nbsp;maximal&nbsp;elements,&nbsp;the&nbsp;least&nbsp;element&nbsp;and&nbsp;the&nbsp;greatest&nbsp;element&nbsp;of&nbsp;the&nbsp;poset&nbsp;&lt;A,&nbsp;R&gt;&nbsp;if&nbsp;they&nbsp;exist;<\/p>\n<p style=\"margin-left:10.5000pt;\">(3)&nbsp;Let&nbsp;B&nbsp;=&nbsp;{2,&nbsp;4,&nbsp;6},&nbsp;find&nbsp;the&nbsp;upper&nbsp;bound,&nbsp;the&nbsp;lower&nbsp;bound,&nbsp;the&nbsp;least&nbsp;upper&nbsp;bound&nbsp;and&nbsp;the&nbsp;greatest&nbsp;lower&nbsp;bound&nbsp;of&nbsp;B&nbsp;if&nbsp;they&nbsp;exist.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"margin-left:13.2500pt;\">7.&nbsp;(15&nbsp;points)&nbsp;Use&nbsp;the&nbsp;labeling&nbsp;algorithm&nbsp;(Ford-Fulkerson&rsquo;s)&nbsp;to&nbsp;find&nbsp;a&nbsp;maximum&nbsp;flow&nbsp;for&nbsp;the&nbsp;following&nbsp;transport&nbsp;network&nbsp;in&nbsp;Fig.&nbsp;1.&nbsp;Use&nbsp;of&nbsp;figures&nbsp;is&nbsp;required&nbsp;to&nbsp;show&nbsp;the&nbsp;variety&nbsp;of&nbsp;flows&nbsp;during&nbsp;the&nbsp;procedure.<\/p>\n<p>&nbsp;<\/p>\n<p><img decoding=\"async\" alt=\"labeling algorithm (Ford-Fulkerson\u2019s) to find a maximum flow for the following transport network\" src=\"\/imgs\/discrete_math\/Ford-Fulkerson.jpg\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"margin-left:13.2500pt;\">8.&nbsp;(10&nbsp;points)&nbsp;Use&nbsp;Kruskal&rsquo;s&nbsp;algorithm&nbsp;to&nbsp;find&nbsp;a&nbsp;minimal&nbsp;spanning&nbsp;tree&nbsp;of&nbsp;graph&nbsp;in&nbsp;Fig.&nbsp;2.&nbsp;The&nbsp;sequence&nbsp;of&nbsp;edges-selecting&nbsp;is&nbsp;ordered&nbsp;to&nbsp;be&nbsp;shown&nbsp;up.<\/p>\n<p><img decoding=\"async\" alt=\"Use Kruskal\u2019s algorithm to find a minimal spanning tree of graph.\" src=\"\/imgs\/discrete_math\/Kruskal.jpg\" \/><\/p>\n<p><a href=\"http:\/\/ykyi.net\">ykyi.net<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u300a\u79bb\u6563\u6570\u5b66\u300b\u671f\u672b\u8bd5\u9898(A\u5377) ykyi.net (\u8003\u8bd5\u5f62\u5f0f:\u95ed\u5377&nbsp;&nbsp;\u8003\u8bd5\u65f6\u95f4:2\u5c0f\u65f6) \u300a\u4e2d\u5c71\u5927\u5b66\u6388\u4e88\u5b66\u58eb\u5b66\u4f4d\u5de5\u4f5c\u7ec6\u5219\u300b\u7b2c\u516d\u6761 \u8003\u8bd5\u4f5c\u5f0a\u4e0d\u6388\u4e88\u5b66\u58eb\u5b66\u4f4d \u65b9\u5411\uff1a&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\u59d3\u540d\uff1a&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\u5b66\u53f7\uff1a&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; \u51fa\u5377\uff1a &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;\u590d\u6838\uff1a&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1.&nbsp;(10&nbsp;points)&nbsp;&nbsp;A,&nbsp;B&nbsp;and&nbsp;C&nbsp;are&nbsp;sets,&nbsp;prove&nbsp;or&nbsp;disprove&nbsp;the&nbsp;following&nbsp;statements. (1).&nbsp;if&nbsp;A&nbsp;&ndash;&nbsp;B&nbsp;=&nbsp;A&nbsp;&ndash;&nbsp;C,&nbsp;then&nbsp;B&nbsp;=&nbsp;C (2).&nbsp;if&nbsp;A&nbsp;&acute;&nbsp;B&nbsp;=&nbsp;A&nbsp;&acute;&nbsp;C,&nbsp;A&nbsp;&sup1;&nbsp;&AElig;,&nbsp;then&nbsp;B&nbsp;=&nbsp;C 2.&nbsp;(10&nbsp;points)&nbsp;&nbsp;Write&nbsp;each&nbsp;of&nbsp;the&nbsp;following&nbsp;statements&nbsp;in&nbsp;terms&nbsp;of&nbsp;propositional&nbsp;variables,&nbsp;predicates,&nbsp;quantifiers&nbsp;and&nbsp;logical&nbsp;connectives.&nbsp;You&nbsp;can&nbsp;choose&nbsp;any&nbsp;propositional&nbsp;variables&nbsp;and&nbsp;predicates&nbsp;freely. (1).&nbsp;If&nbsp;I&nbsp;like&nbsp;the&nbsp;course&nbsp;or&nbsp;the&nbsp;teacher,&nbsp;I&nbsp;will&nbsp;attend&nbsp;the&nbsp;class. (statement&nbsp;and&nbsp;its&nbsp;negation) (2).&nbsp;For&nbsp;all&nbsp;students&nbsp;of&nbsp;our&nbsp;school,&nbsp;someone&nbsp;studies&nbsp;hard&nbsp;and&nbsp;has&nbsp;good&nbsp;score,&nbsp;someone&nbsp;studies&nbsp;hard&nbsp;and&nbsp;does&nbsp;not&nbsp;have&nbsp;good&nbsp;score. Note:&nbsp;The&nbsp;first&nbsp;question&nbsp;is&nbsp;expressed&nbsp;in&nbsp;propositional&nbsp;logic,&nbsp;the&nbsp;second&nbsp;is&nbsp;expressed&nbsp;in&nbsp;predicate&nbsp;logic. 3.&nbsp;(15&nbsp;points)&nbsp;Let&nbsp;A={a,b,c,d,e},&nbsp;a&nbsp;relation&nbsp;R&nbsp;on&nbsp;A&nbsp;is&nbsp;{(a,b),&nbsp;(b,b),&nbsp;(b,c),&nbsp;(b,d),&nbsp;(c,d),&nbsp;(d,d),&nbsp;(d,e),&nbsp;(e,d)}. (1)&nbsp;Give&nbsp;the&nbsp;digraph&nbsp;and&nbsp;matrix&nbsp;of&nbsp;relation&nbsp;R; (2)&nbsp;Compute&nbsp;R2,&nbsp;reflexive&nbsp;closure&nbsp;r(R)&nbsp;and&nbsp;symmetric&nbsp;closure&nbsp;s(R). 4.&nbsp;(15&nbsp;points)&nbsp;Let&nbsp;S&Icirc;Z+&nbsp;and&nbsp;A=S&times;S.&nbsp;Define&nbsp;the&nbsp;following&nbsp;relation&nbsp;R&nbsp;on&nbsp;A: (a,b)&nbsp;R&nbsp;(a&prime;,b&prime;)&nbsp;if&nbsp;and&nbsp;only&nbsp;if&nbsp;ab&prime;=a&prime;b (1)&nbsp;Show&nbsp;that&nbsp;R&nbsp;is&nbsp;an&nbsp;equivalent&nbsp;relation; (2)&nbsp;Let&nbsp;S={1,2,3,4,5,6,7,8,9},&nbsp;compute&nbsp;the&nbsp;equivalent&nbsp;class&nbsp;[(2,4)]. 5.&nbsp;(10&nbsp;points)&nbsp;Let&nbsp;function&nbsp;f(x,&nbsp;y)=(&nbsp;x+3y,&nbsp;2x+y),&nbsp;(x,&nbsp;y)&Icirc;R&times;R,&nbsp;prove&nbsp;that&nbsp;f&nbsp;is&nbsp;bijection. 6.&nbsp;(15&nbsp;points)&nbsp;Let&nbsp;A={2,&nbsp;4,&nbsp;5,&nbsp;6,&nbsp;8,&nbsp;10,&nbsp;12,&nbsp;20,&nbsp;120},&nbsp;R&nbsp;is&nbsp;the&nbsp;relation&nbsp;of&nbsp;divisibility&nbsp;on&nbsp;A. (1)&nbsp;Draw&nbsp;the&nbsp;Hasse&nbsp;diagram&nbsp;of&nbsp;the&nbsp;poset&nbsp;&lt;A,&nbsp;R&gt;; (2)&nbsp;Find&nbsp;all&nbsp;the&nbsp;minimal&nbsp;elements,&nbsp;the&nbsp;maximal&nbsp;elements,&nbsp;the&nbsp;least&nbsp;element&nbsp;and&nbsp;the&nbsp;greatest&nbsp;element&nbsp;of&nbsp;the&nbsp;poset&nbsp;&lt;A,&nbsp;R&gt;&nbsp;if&nbsp;they&nbsp;exist; (3)&nbsp;Let&nbsp;B&nbsp;=&nbsp;{2,&nbsp;4,&nbsp;6},&nbsp;find&nbsp;the&nbsp;upper&nbsp;bound,&nbsp;the&nbsp;lower&nbsp;bound,&nbsp;the&nbsp;least&nbsp;upper&nbsp;bound&nbsp;and&nbsp;the&nbsp;greatest&nbsp;lower&nbsp;bound&nbsp;of&nbsp;B&nbsp;if&nbsp;they&nbsp;exist. &nbsp; 7.&nbsp;(15&nbsp;points)&nbsp;Use&nbsp;the&nbsp;labeling&nbsp;algorithm&nbsp;(Ford-Fulkerson&rsquo;s)&nbsp;to&nbsp;find&nbsp;a&nbsp;maximum&nbsp;flow&nbsp;for&nbsp;the&nbsp;following&nbsp;transport&nbsp;network&nbsp;in&nbsp;Fig.&nbsp;1.&nbsp;Use&nbsp;of&nbsp;figures&nbsp;is&nbsp;required&nbsp;to&nbsp;show&nbsp;the&nbsp;variety&nbsp;of&nbsp;flows&nbsp;during&nbsp;the&nbsp;procedure. &nbsp; &nbsp; &nbsp; 8.&nbsp;(10&nbsp;points)&nbsp;Use&nbsp;Kruskal&rsquo;s&nbsp;algorithm&nbsp;to&nbsp;find&nbsp;a&nbsp;minimal&nbsp;spanning&nbsp;tree&nbsp;of&nbsp;graph&nbsp;in&nbsp;Fig.&nbsp;2.&nbsp;The&nbsp;sequence&nbsp;of&nbsp;edges-selecting&nbsp;is&nbsp;ordered&nbsp;to&nbsp;be&nbsp;shown&nbsp;up. ykyi.net<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[107],"class_list":["post-815","post","type-post","status-publish","format-standard","hentry","category-tech_articles","tag-107"],"_links":{"self":[{"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/posts\/815","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/ykyi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=815"}],"version-history":[{"count":0,"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/posts\/815\/revisions"}],"wp:attachment":[{"href":"https:\/\/ykyi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=815"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ykyi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=815"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ykyi.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=815"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}