正文內(nèi)容

離散數(shù)學(xué)復(fù)習(xí)題-資料下載頁

2026-07-16 05:02本頁面

　　

【正文】加前提引入法構(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è)無向圖G中只有兩個奇度頂點(diǎn)u與v，試證明u與v必連通。證明：用反證法。假設(shè)u與v不連通，即u與v之間無通路，則u與v處于G的不同連通分支中。不妨設(shè)u在G1，v在G2中。于是，G1與G2作為G的子圖，他們中均只含有一個奇度頂點(diǎn)，這與握手定理的推論矛盾。設(shè)n階無向簡單圖G有m條邊，已知m≥(n1)(n2)+1，證明G必連通。證明：（1）任何n階簡單圖的邊數(shù)m均小于等于完全圖Kn的邊數(shù)n(n1)。（2）若G中無孤立點(diǎn)，則δ(G)≥1。用歸納法。 ① n=1時，G為平凡圖，顯然G連通。 ② n=2時，m≥(n1)(n2)+1=1，此時G為K2，當(dāng)然連通。 ③ 設(shè)n=k(k≥2)，m≥(k1)(k2)+1時結(jié)論成立，要證明當(dāng)n=k+1,m≥k(k1)+1時結(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的簡單圖矛盾，故G中不可能含孤立點(diǎn)。 (iii) 由(i)、(ii)可知，只需對G不為完全圖、又不含孤立點(diǎn)的情況加以證明。 G中存在v0，使1≤d(v0)≤k1（G中無孤立點(diǎn)，又不是k+1階完全圖），令G39。=Gv0，則G39。為k階簡單圖，且G39。的邊數(shù) m39。≥ k(k1)+1(k1) =( k(k1)(k1))+1 =(k1)(k2)+1 由歸納假設(shè)可知，G39。是連通圖，而G39。為G的子圖，故G也連通。設(shè)G為n階無向簡單圖，證明以下題目：（1）當(dāng)δ(G)≥時，證明G連通。證明（1）用反證法。假設(shè)G至少有兩個連通分支，設(shè)G1,G2為其中的兩個，并設(shè)G1,G2的階數(shù)分別為n1和n2，則n1+n2≤n，且min{n1,n2}≤ 。于是，對任意的 v∈V(G1)， dG1(V)= dG(V)≤ 1 ，這與δ(G)≥矛盾，所以G連通。（2）當(dāng)δ(G)≥(n+k1)時，證明G是k連通圖。證明：設(shè)V39。為V(G)的任意子集，且|V39。|=k1。令 G39。=GV39。，則G39。為n(k1)=nk+1=n39。階無向簡單圖，而 δ(G39。)≥δ(G)(k1) ≥ (n+k1)(k1) = (n+k12k+2) = (nk+1) =n39。由當(dāng)δ(G)≥時，G連通可知，G39。連通，故G39。為k連通圖。

點(diǎn)擊復(fù)制文檔內(nèi)容

高考資料相關(guān)推薦

鄂ICP備17016276號-1

<meter id="nncua"></meter>

離散數(shù)學(xué)復(fù)習(xí)題-資料下載頁

離散數(shù)學(xué)考試復(fù)習(xí)資料-資料下載頁

離散數(shù)學(xué)課后習(xí)題答案-資料下載頁

離散數(shù)學(xué)習(xí)題及答案-資料下載頁

哈工大離散數(shù)學(xué)教科書習(xí)題答案-資料下載頁

離散數(shù)學(xué)作業(yè)-資料下載頁

離散數(shù)學(xué)-資料下載頁

離散數(shù)學(xué)練習(xí)題1-資料下載頁

離散數(shù)學(xué)第1—7章習(xí)題詳解-資料下載頁

離散數(shù)學(xué)總結(jié)-資料下載頁

離散數(shù)學(xué)1212離散概率-資料下載頁

離散數(shù)學(xué)題庫答案-資料下載頁

離散數(shù)學(xué)-數(shù)論-資料下載頁

離散數(shù)學(xué)總結(jié)-資料下載頁

離散數(shù)學(xué)——樹-資料下載頁

離散數(shù)學(xué)作業(yè)冊-資料下載頁

離散數(shù)學(xué)復(fù)習(xí)題(存儲版)

離散數(shù)學(xué)復(fù)習(xí)題-文庫吧在線文庫

離散數(shù)學(xué)復(fù)習(xí)題(完整版)

離散數(shù)學(xué)復(fù)習(xí)題(更新版)

離散數(shù)學(xué)復(fù)習(xí)題(專業(yè)版)