[理工] 離散圖論6-1台大證明 st945732 PTT批踢踢實業坊

作者: st945732 (A7777J) 2018-04-14 15:24:24

http://i.imgur.com/E98TdLk.jpg
想請問各位大大，
為什麼倒數第二行這樣就算產生矛盾呢？？
不太懂這解答的想法..

作者: jojojen (JJJ) 2018-04-14 19:08:00

我覺得這看起來像反證法https://i.imgur.com/OSa3NIX.jpg

作者: ILYY (毅力) 2018-04-15 00:41:00

矛盾證法的好處是P也可以拿來用所以disconnected下di+dj<=n-2與P:di+dj>=n-1矛盾應該矛盾的好處是除了P以外可以拿其他的的東西來矛盾除了P以外還可以拿其他東西來矛盾少個字意思差很多XD不過這題剛好反證也是很像會跟j大一樣記得改成只取某兩點就好

作者: jojojen (JJJ) 2018-04-15 11:28:00

https://i.imgur.com/GmCpcup.jpg這題我也不知怎套矛盾證法的邏輯

作者: ILYY (毅力) 2018-04-15 12:31:00

一樣把前面設為真後面設P is False套入前面結果為false與"前面設為真"矛盾不過這題我會直接畫真值表XD如果有小黃的線代可以看課本0.2章有說明證明方法看他舉的例子應該就懂了

作者: jojojen (JJJ) 2018-04-15 14:55:00

了不過這樣解答前面應該加個設di+dj>=n-1為真比較清楚

繼續閱讀