# indirect proof & 3n + 1

(個人見解) 數學是一門學，一個 science，一套規則跟思考方法，不意外古希臘時數學是哲學的其中一個派別，也可以解釋為什麼絕大多數的理工科系是建立在數學之上的。

資工的日常畢竟還是工程系列，所以不會碰這麼多形式概念邏輯上的數學，但碰得也比一般工程科系多，因為資工是軟體，軟體是摸不到的東西，全套想像、(被[抽象化](https://zh.wikipedia.org/zh-tw/%E6%8A%BD%E8%B1%A1%E5%8C%96_(%E8%A8%88%E7%AE%97%E6%A9%9F%E7%A7%91%E5%AD%B8))之後的) 電流、還有邏輯。

大家最喜歡提到的微積分個人覺得是一個最基礎簡單的工具，銜接算術數學與抽象數學的東西

如果想要往視覺化（做遊戲、影像等等）方面的軟體，才會需要大量有數字的數學，或者用大學生的說法就是線性代數（用微積分算的）。
如果要處理很多大數據（幫會計統計系商學院做工具）的軟體，會需要統計的數學（用微積分算）。
至於其他方向的軟體日常，可以很直接的說，資工只有邏輯。
:::spoiler 所謂邏輯
一直提到邏輯，理組都笑文組沒邏輯的邏輯，個人認為是一種對問題的切入方式。
資工強調的是把問題拆解，然後一步一步的方式去解決。
維度高例如要怎麼分類資料讓搜尋更快速？維度中像是一段程式要怎麼重複使用才最有效率？維度低例如加法的進位到底是怎麼做出來的？

像是要怎麼把大象放進冰箱？
第一步是打開冰箱，第二步是把大象放進去，第三步是關上冰箱門。
資工不在乎冰箱夠不夠大，在乎的是順序與步驟合不合理。
那怎麼把長頸鹿放進冰箱呢？
資工就是會記得把大象先拿出來的人

:::
<br>

thanks for coming to my ted talk
以下介紹兩個有趣的數學，一個幾乎只能用程式證明，另一個是純數學

## 考拉茲猜想
[wiki](https://en.wikipedia.org/wiki/Collatz_conjecture)
被稱為 3n + 1 problem，指每一個正整數，如果它是奇數，則對它乘3再加1，如果它是偶數，則對它除以2，如此循環，最終都能夠得到1

這個目前沒有辦法用紙筆數學上證明，但可以用程式半證實他存在，所以來寫個程式跑跑看吧

:::spoiler 參考架構
- 使用者輸入一個數字來驗證
- 一個 function來表示下面那個數學 function
- 一個 loop 來不斷對使用者輸入的數字執行那上述 function
- 印出結果是不是 1
:::

## Indirect proof
回到數學的世界，有很多很多的證明方式，像是數學歸納法是用歸納法證明，或是以前常用的 direct proof 都是常見的證明法，這裡介紹 indirect proof，也有人說這叫 proof by contradiction
顧名思義，他就是用反例來證明的

邏輯學(或更確切地，[命題邏輯](https://zh.wikipedia.org/zh-tw/%E5%91%BD%E9%A2%98%E9%80%BB%E8%BE%91)) 裡，在一條又一條的規則下，contradiction 可以證明任何事
:::spoiler 有興趣的話證明在這裡
p · ~p proof everything (why we don't allow contradiction

1. p · ~p
2. p (simplification 1
3. p v everything (add 2
4. ~p (simplification 1
5. everything (Disjunctive Syllogism 3, 4

（這是修哲學系的邏輯課學到的東西，但我在那堂課強得誇張，因為這點（哲學系引以為傲的？）邏輯概念，對資工來說，非常簡單）
:::
<br>

扯遠了，indirect proof 很少用但最有名的地方就是用來證明根號二是無理數
證明如下
<br></br>
:::info
[BACK](https://hackmd.io/@lhsueh1/python101)
:::