離散數學 學習筆記

這裡是離散數學的學習筆記 qwq，也是我嘗試使用 Markdown 記課上筆記的開始，離散數學是一門研究離散量的科學，是資料結構、算法設計的基礎，這裡不僅有有趣的邏輯與集合，還會有“超級好玩”的群論和圖論等待你去探索。就讓我們一起暢遊這“魔法”的世界吧！

本筆記采用在課上簡記，課後完善的模式，有可能因時間不夠停更

本學科為 28 課時講課 + 4 課時實驗 （office 315）

1.數理邏輯

首先給出命題的概念：能表達判斷且有确切的真值的陳述句。命題的真值隻有兩種即 True 和 False，但悖論這種自相沖突的陳述句不是命題，因為它不可能有确切的真值。

我們可以根據命題的描述複雜程度将命題分為原子命題和複合命題，原子命題是一種不可分解為更簡單語句的陳述句，複合命題是由若幹原子命題通過聯結詞構成的命題。

為了便于數學的符号化表示，我們需要對聯結詞進行明确規定并給出其符号表示，下面是一些基本的聯結詞：（按照優先級排序）

名稱	符号	意義
否定	\(\lnot\)	取反
合取	\(\and\)	且
析取	\(\or\)	可兼或
條件	\(\rightarrow\)	若…則…
雙條件	\(\leftrightarrow\)	當且僅當

對于條件句，我們總是遵循善意的推并，即目前件（前提）為假時，無論後件（結論）真值為何，我們總是認為條件句的真值為真。并且在條件句和雙條件句中，我們并不要求它們的前件與後件有實際的聯系。

有了以上的概念，我們就可以将現實生活中的一些可以被視為命題的陳述句翻譯為我們的數學語言了，下文給出了翻譯的大緻方法：

1. 找到原語句中包含的原子命題；
2. 将原語句中的關聯詞翻譯成适當的邏輯聯結詞；
3. 将其用數學的符号寫出。

值得注意的一點是，關聯詞 ”隻有…才…“ 其實構成的是雙條件句。

命題常量為表示确定命題的符号，命題變元為表示任意命題的符号，但其不是命題，原子變元為表示原子命題的命題變元，給命題變元指定值的操作叫做指派。

命題公式采用遞歸的定義，規定為：

1. 單個命題變元本身為命題公式；
2. 如果 \(P\) 為合法的命題公式，則 \(\lnot P\) 也為合法的命題公式；
3. 如果 \(P, Q\) 為合法的命題公式，則 \((P \and Q), (P \or Q), (P \rightarrow Q), (P \leftrightarrow Q)\) 均為合法的命題公式。
4. 當且僅當通過若幹個命題變元和聯結詞通過法則 1. 2. 3. 進行有限次的拼接所形成的字元為命題變元。

對于一個命題公式中分量真值的各種指派所形成的各種組合所彙列成表，即為命題公式的真值表。

當給兩個命題公式任意一組真值指派，它們的真值始終相等，則兩個命題公式等價。我們如果想要證明兩個問題中，兩個命題公式是否等價，可以通過分别列出其真值表，而由 \(n\) 個命題變元所組成的命題有 \(2^n\) 種不同的真值指派，是以如果要依靠真值表證明，顯然過于繁瑣。我們可以通過一些法則來化簡它們，這裡選取了一些列在下面：

\[P \rightarrow Q \Leftrightarrow \lnot P \or Q \\

P \leftrightarrow Q \Leftrightarrow (P \rightarrow Q) \and (Q \rightarrow P) \\

P \and (P \or Q) \Leftrightarrow P \\

P \or (P \and Q) \Leftrightarrow P \\

\lnot (P \or Q) \Leftrightarrow (\lnot P \and \lnot Q) \\

\lnot (P \and Q) \Leftrightarrow (\lnot P \or \lnot Q)

\]