推 b10007034: 推此篇，的確是反證而不是矛盾證 10/14 11:52
→ b10007034: 矛盾的確如版主所說，是NOT與已知相反 10/14 11:53
→ b10007034: 中文真是厲害阿XD 10/14 11:53
推 skyHuan: 或是可以說反證是矛盾的一個特例 10/14 12:33
※ 引述《Russ0116 (Russ0116)》之銘言
: https://i.imgur.com/iv5yIYF.jpg
: https://i.imgur.com/E2vuHQK.jpg
: 想請問一下 中間證明我都看得懂
: 但不太知道為什麼最後會矛盾
我把問題分成這樣:
p → q
p: (若) 任意不相鄰兩點 x y 滿足 deg 和 ≧ n
q: (則) 有 hamiltonian cycle
反證
~q → ~p
~q: (若) 不具 hamiltonian cycle
~p: (則) 任意不相鄰兩點 x y 滿足 deg 和 ＜ n (也就是 和 ≦ n-1)
矛盾
已知p，~q → ~p 或與既定事實違背
p: (已知) 任意不相鄰兩點 x y 滿足 deg 和 ≧ n
~q: (若) 不具 hamiltonian cycle
~p: (則) 任意不相鄰兩點 x y 滿足 deg 和 ＜ n (也就是 和 ≦ n-1)
所以證明從取 a b 在 G 為不相鄰兩點開始，證到 deg 和必 ≦ n-1，就得證。會說矛
盾是矛盾已知的 p，也就是得出 ~p，只是因為過程沒有用到已知的p來使用(一般矛盾
證法會用到來協助證明)，所以這題他說是反證，而不是矛盾證法。
應該是這個意思，如果上述有錯還麻煩大神告知。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.78.245
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1539407668.A.D21.html