計算的數學基礎：前半教怎麼證明，後半教什麼證不出來｜Stanford CS103 課程總覽
CS103 是 Stanford 的計算數學基礎課：前半教集合、邏輯、圖與歸納法的證明寫作，後半教有限自動機、圖靈機、可判定性與 P 對 NP。投影片、作業題目、起始檔與自製講義全部公開，自動評分的題目可以在本機自測；解答、練習考題與上課錄影要 Stanford 登入。
29 篇文章
Stanford CS103 Mathematical Foundations of Computing 導讀
逐講讀 Stanford CS103：離散數學、邏輯、證明、集合、可計算性，以及它們如何成為後續 CS 課程的共同語言。
從集合語言走到 Cantor 對角線｜Stanford CS103 第 0 堂
從集合的元素、子集合與冪集開始，最後用 Cantor 對角線證明任何集合都不可能和自己的冪集一樣大。
從 even／odd 定義寫出第一個直接證明｜Stanford CS103 第 1 堂
用偶數平方與兩奇數相加兩個例題，練習任取、假設、見證與 want-to-show 如何組成可逐行檢查的直接證明。
否定、逆否證明與反證法｜Stanford CS103 第 2 堂
本講先精確刻畫蘊涵何時為假，再把量詞否定、逆否命題與反證法變成可檢查的證明工具。
命題邏輯、真值表與等價式｜Stanford CS103 第 3 堂
命題邏輯把英文陳述抽象成真假變數，再用真值表檢查連接詞、翻譯方向與 De Morgan 等價式。
一階邏輯的物件、量詞與型別｜Stanford CS103 第 4 堂
本講把命題邏輯擴充成能談論物件的一階邏輯：分清常數、predicate、function 與命題的型別，再用存在與全稱量詞表達 some 與 every。
一階邏輯 II——巢狀量詞、否定與唯一性｜Stanford CS103 第 5 堂
把自然語言逐層翻成一階邏輯：辨認全稱與存在句型，再處理量詞順序、否定、限制量詞與唯一性。
函數 I，從定義到單射與滿射證明｜Stanford CS103 第 6 堂
函數不只是一條公式：定義域、陪域、全域有定義與確定性缺一不可，而 involution、單射與滿射的量詞正好決定證明怎麼寫。
函數 II——滿射、假設與函數合成｜Stanford CS103 第 7 堂
本講以滿射與鳥類證明釐清『假設』和『證明』的不同操作，再證明 involution 必為單射與滿射，並把同一套推理帶進函數合成。
用雙射定義基數與 Cantor 對角論證｜Stanford CS103 第 8 堂
兩個集合等大，意思是它們之間存在雙射；Cantor 的對角集合則能對任意 S 到其冪集的函數造出一個漏接值。
圖論 I｜Stanford CS103 第 9 堂
本講從圖與有向圖的形式定義，推進到獨立集、頂點覆蓋，以及兩者的補集關係。
走訪、圖的補集與鴿籠原理｜Stanford CS103 第 10 堂
從 walk、path、cycle 與連通分量出發，以補圖必有一者連通、同度數節點、廣義鴿籠原理及朋友與陌生人定理練習完整證明。
廣義鴿籠原理、Ramsey Theory 與平均負載｜Stanford CS103 第 11 堂
以廣義鴿籠原理證明六人派對必有三位共同朋友或共同陌生人，再用平均負載與反證解出電影偏好 puzzle。
數學歸納法、假幣問題與不變量｜Stanford CS103 第 12 堂
數學歸納法不是把幾個案例排在一起，而是證明起點成立、任意一步能把真命題傳給下一步，再由歸納原理涵蓋所有自然數。
數學歸納法 II｜Stanford CS103 第 13 堂
本講從「從上一講的標準歸納法出發」推進到「起點不必是零」，依官方例題重建定義、推導與易錯邊界。
有限自動機 I｜Stanford CS103 第 14 堂
本講從「為什麼先研究一台很弱的電腦」推進到「從裝置行為抽出狀態機」，依官方例題重建定義、推導與易錯邊界。
有限自動機 II｜Stanford CS103 第 15 堂
本講從「DFA 的形式定義把前半學期串起來」推進到「regular 語言 是「存在一台 DFA」」，依官方例題重建定義、推導與易錯邊界。
有限自動機 III｜Stanford CS103 第 16 堂
本講從「自動機階梯：能力要用語言區分」推進到「DFA transition table 是圖的精確轉寫」，依官方例題重建定義、推導與易錯邊界。
正規表示式｜Stanford CS103 第 17 堂
本講從「從 closure 性質 走向描述語言的語法」推進到「regex 是數學表示式，不等於某套程式庫」，依官方例題重建定義、推導與易錯邊界。
非正規語言｜Stanford CS103 第 18 堂
本講從「四種 regular 的說法已經等價」推進到「finite memory 的精確直覺」，依官方例題重建定義、推導與易錯邊界。
上下文無關語言｜Stanford CS103 第 19 堂
本講從「從有限狀態限制轉向遞迴結構」推進到「arithmetic grammar 的四組規則」，依官方例題重建定義、推導與易錯邊界。
圖靈機 I｜Stanford CS103 第 20 堂
本講從「為何 CFG 之後還要換模型」推進到「長加法揭示 local access 原則」，依官方例題重建定義、推導與易錯邊界。
圖靈機 II｜Stanford CS103 第 21 堂
本講從「sample TM：從最後一格回看第一格」推進到「TM 能做的工作遠超逐格配對」，依官方例題重建定義、推導與易錯邊界。
圖靈機 III｜Stanford CS103 第 22 堂
本講從「recognizer 與 decider 的快速量詞稽核」推進到「為何所有問題都能寫成 語言」，依官方例題重建定義、推導與易錯邊界。
不可解問題 I｜Stanford CS103 第 23 堂
本講從「從 R、RE 與 UTM 接回來」推進到「self-reference 回顧的三個程式」，依官方例題重建定義、推導與易錯邊界。
不可解問題 II｜Stanford CS103 第 24 堂
本講從「HALT 的定義與位置」推進到「為何 HALT 可辨識」，依官方例題重建定義、推導與易錯邊界。
不可解問題 III｜Stanford CS103 第 25 堂
本講從「Lava Diagram 的兩個辨識任務」推進到「Rice's Theorem 的 投影片 版判讀」，依官方例題重建定義、推導與易錯邊界。
複雜度理論｜Stanford CS103 第 26 堂
本講從「decidable 不等於 feasible」推進到「efficiency 要先選 resource」，依官方例題重建定義、推導與易錯邊界。
全課總結：四條知識主線與下一門課｜Stanford CS103 課程總覽
最後一講把證明、圖論、自動機與可計算性重新接起來，再對照會直接使用這些基礎的 Stanford 後續課程。