離散數(shù)學(xué)復(fù)習(xí)題-資料下載頁(yè)
2025-07-25 05:02本頁(yè)面
【正文】 加前提引入法構(gòu)造下面的推理證明：前提：P→(Q→S)，R∨P , Q 結(jié)論：R→S 證明： (1)R∨P 前提引人 (2) R→P (1)置換 (3)R 附加前提引人 (4)P (2)(3)分離 (5)P→(Q→S) 前提引入 (6)Q→S (4)(5)分離 (7)Q 前提引人 (8)S (6)(7)分離 (9)R→S 條件證明規(guī)則在自然推理系統(tǒng)P中，構(gòu)造下面的推理證明：前提：P∨Q ，P→R，Q→S， 結(jié)論：S∨R 證明: (1) P∨Q 前提引入 (2)P→Q (1)置換 (3) Q→S 前提引入 (4) →S (2)(3)三段論 (5)S→P (4)置換 (6) P→R 前提引入 (7)SR (5)(6)三段論 (8)S∨R (7)置換設(shè)無(wú)向圖G中只有兩個(gè)奇度頂點(diǎn)u與v，試證明u與v必連通。證明：用反證法。假設(shè)u與v不連通，即u與v之間無(wú)通路，則u與v處于G的不同連通分支中。不妨設(shè)u在G1，v在G2中。于是，G1與G2作為G的子圖，他們中均只含有一個(gè)奇度頂點(diǎn)，這與握手定理的推論矛盾。設(shè)n階無(wú)向簡(jiǎn)單圖G有m條邊，已知m≥(n1)(n2)+1，證明G必連通。證明： （1）任何n階簡(jiǎn)單圖的 邊數(shù)m均小于等于完全圖Kn的邊數(shù)n(n1)。 （2）若G中無(wú)孤立點(diǎn)，則δ(G)≥1。用歸納法。 ① n=1時(shí)，G為平凡圖，顯然G連通。 ② n=2時(shí)，m≥(n1)(n2)+1=1，此時(shí)G為K2，當(dāng)然連通。 ③ 設(shè)n=k(k≥2)，m≥(k1)(k2)+1時(shí)結(jié)論成立，要證明當(dāng)n=k+1,m≥k(k1)+1時(shí)結(jié) 論也成立。(i) 若G為Kk+1，G當(dāng)然連通。(ii) 若G中含孤立點(diǎn)，一定推出矛盾。刪去G中的孤立點(diǎn)，記作G1。則G1的邊數(shù)m≥ k(k1)+1，這與G1為階數(shù)小于等于k的簡(jiǎn)單圖矛盾，故G中不可能含孤立點(diǎn)。 (iii) 由(i)、(ii)可知，只需對(duì)G不為完全圖、又不含孤立點(diǎn)的情況加以證明。 G中存在v0，使1≤d(v0)≤k1（G中無(wú)孤立點(diǎn)，又不是k+1階完全圖）， 令G39。=Gv0，則G39。為k階簡(jiǎn)單圖，且G39。的邊數(shù) m39?！?k(k1)+1(k1) =( k(k1)(k1))+1 =(k1)(k2)+1 由歸納假設(shè)可知，G39。是連通圖，而G39。為G的子圖，故G也連通。 設(shè)G為n階無(wú)向簡(jiǎn)單圖，證明以下題目： （1）當(dāng)δ(G)≥時(shí)，證明G連通。證明（1）用反證法。假設(shè)G至少有兩個(gè)連通分支，設(shè)G1,G2為其中的兩個(gè)，并設(shè)G1,G2的階數(shù)分別為n1和n2，則n1+n2≤n，且min{n1,n2}≤ 。于是，對(duì)任意的 v∈V(G1)， dG1(V)= dG(V)≤ 1 ，這與δ(G)≥矛盾，所以G連通。 （2）當(dāng)δ(G)≥(n+k1)時(shí)，證明G是k連通圖。證明：設(shè)V39。為V(G)的任意子集，且|V39。|=k1。令 G39。=GV39。，則G39。為n(k1)=nk+1=n39。階無(wú)向簡(jiǎn)單圖，而 δ(G39。)≥δ(G)(k1) ≥ (n+k1)(k1) = (n+k12k+2) = (nk+1) =n39。 由當(dāng)δ(G)≥時(shí)，G連通可知，G39。連通，故G39。為k連通圖。
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1