算法索引

離散數學、計算數學、組合數學

0. 命題邏輯

本部分除特別標註，否則不注意加斜體

0.0 命題的分類

原子命題：不可分解為更簡單的命題的命題；

複合命題：由若干原子命題通過命題連接詞和標點符號組成的命題。

悖(bei4)論：命題為1時，永遠為假的命題。

0.1 命題的規定

命題標識符：表示一個命題的符號，比如(P, Q, p, q, p₁)

命題常量：可以確定真假的命題

命題變量：暫不可確定真假的命題

命題的指派（賦值）：給定一個命題變量一個值。

0.2 命題的連接詞運算

感謝boole的貢獻，為了紀念他，很多語言中都有bool類型。

連接命題的詞語叫做命題連接詞。常見的有：

否、析取、合取、蘊含、等價、異或。

定義一命題p，那麼：

使用T(正體)或者1表示其為真命題，使用F(正體)或者0表示假命題

解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle ┐p} （程序中使用!p）表示p的反命題，讀作非p。

$p\wedge q$ （程序中使用p && q）表示p且q 或者說p與q。命題 $p\wedge q$ 稱為p, q的合取。

冪等率： $p\wedge p=p$

交換律： $p\wedge q=q\wedge p$

結合律： $\left(p\wedge q\right)\wedge r=p\wedge \left(q\wedge r\right)=p\wedge q\wedge r$

同一律： $p\wedge 1=p$

零一率： $p\wedge 0=0$

否定率： $p\wedge \neg p=0$

$p\vee q$ （程序中使用p || q）表示p或q或者說p同或q。命題 $p\vee q$ 稱為p, q的析取。

冪等率

交換律

結合律

同一律： $p\vee 0=p$

零一率： $p\vee 1=1$

否定率： $p\vee \neg p=0$

吸收律： $p\wedge \left(p\vee q\right)=p\vee \left(p\wedge q\right)=p$

德摩根率： $\neg \left(p\wedge q\right)=\neg p\vee \neg q$

析取和合取的分配率： $p\vee \left(q\wedge r\right)=\left(p\vee q\right)\wedge \left(p\vee r\right)$

$p\wedge \left(q\vee r\right)=\left(p\wedge q\right)\vee \left(p\wedge r\right)$

$p\oplus q$ 或者 $p{\overline {\vee }}q$ （程序中使用p | q表示按位異或）表示p或q或者說p異或q。命題 $p\oplus q$ 稱為p, q的不可兼析取。

交換律

結合律

合取對不可兼析取的分配率： $p\wedge \left(q\oplus r\right)=\left(p\wedge q\right)\oplus \left(q\wedge r\right)$

注意：涉及不可兼析取的分配率僅此一個

另有： $p\oplus q=\neg \left(p<->q\right)$

歸化：p⊕q == (p && !q) || (!p && q) == (p || q) && (!p || !q)

其中其真值表為，即只有兩個題設中有且只有一個為1，結果才是1：

A	B	結果
1	1	0
1	0	1
0	1	1
0	0	0

例0.2.0 判斷以下命題：

「如果今日晴，那麼我們去打醬油

這就是今日晴蘊我們去打醬油，如果今日不晴，那麼無論打不打醬油，這個命題都是真的，但是如果今天晴卻沒有打醬油，那麼這個命題就是假的。

$p\rightarrow q$ 表示以下命題：其中p叫做蘊含式前件（假設，前提），q叫做蘊含式後件（結論，後果）（蘊含關係）.

其真值表如下，即只有前提為0，但是結論為1時才是0或者說可以滿足命題p和命題q同時滿足條件時，結果可以成立便為1：

A	B	結果
1	1	1
1	0	0
0	1	1
0	0	1

表示p蘊含q的語句很多，比如：

p是q的充分條件；

若p則q；

p僅當q（時成立）；

q時p的必要條件；

q當p（時成立）；

例0.2.1 證明 $p\rightarrow q=\neg p\vee q$ ——歸化公式

p	q	p → q	!p	!p	q
0	0	1	1	q
0	1	1	1	q
1	0	0	0	0
1	1	1	0	1

例0.2.2 證明 p → q == !q → !p

p → q == !p || q == !(!q) || !p == !q → !p

例0.2.3 證明 !(p → q) == p && !q

!(p → q) == !(!p || q) == p && !q

$p<->q$ 表示當p, q同為真或假時為真，反之為假.

p等價於q

交換律

結合律

另有： $p<->q=\left(p\rightarrow q\right)\wedge \left(q\rightarrow p\right)$

規化：p ↔ q == (!p || q) && (!q || p)

== (p && q) || (!q && !p)

0.3 命題公式

由命題變項(p, q, a, b等)、邏輯聯結詞、圓括號按照一定規律組成的合式叫命題公式，簡稱公式；以下是公式在本階段的規定，[#1.0.1「每一個」和「有一個」|outline #3.1. 謂詞邏輯|outline]：

(1) 單個命題是合式公式

(2) 若A為合式公式，則 $\neg A$ 是合式公式

(3) 若A, B為合式公式，則 $A\wedge B,A\vee B,A\rightarrow B,A<-B$ 是合式公式

(4) 當且僅當有限地使用前三條原則得到的符號串叫做合式公式

0.3.1 邏輯聯結詞的優先級

邏輯聯結詞的優先級依次為：

!, && , || , → , ↔

例0.3.0 證明!(p || q) == !p && !q

p	q	p	q	!(p	q)	!p	!q	!p && !q
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

德摩根率：p || q == !(!p && !q)

p && q == !(!p || !q)

0.3.2 公式的等值

給定兩個公式A, B，如果對於給定A, B任一不同的指派時它們的值均分別相等，那麼就說A與B等值，記作「 $A\Leftrightarrow B$ 」，在本冊中簡記為「A = B」或「A == B」。

0.3.3 全動能聯結詞組

我們知道任意除「!」, 「&&」 ,「||」以外的連接詞都可用這三個進行替換。

如果任何一個公式均可以用一個一個連接詞集合中的元素進行替換，那麼這個集合叫做全功能聯結詞組或者聯結功能完備集。

如果一個全功能連接詞組中去掉任意一個連接詞就不再是全功能連接詞組，那麼就叫這個全功能連接詞組為最小全功能聯結詞組或者最小功能完備集。

以下列出兩個全功能聯結詞組：

{!, ||}, {!, &&}

0.3.3 公式分類

永真式（重言式）：取指一定為1的公式。

永假式（矛盾式）：取值一定為0的公式。

可滿足式：非矛盾式的公式。

僅可滿足式：非永真式的可滿足式。

證明永真、永假除了可以使用真值表，還可以使用否定律和零一率。

0.3.4 其他公式

等價否定等值律：A ←→ B == !A ←→ !B

假言移位：A → B == !B → !A——反證法的依據

歸謬律：(A → B) && (A → !B) == !A

A	B	A → B	A → !B	(A → B) && (A → !B)
1	1	1	0	0
1	0	0	1	0
0	1	1	1	1
0	0	1	1	1

0.4 範式

0.4.0 對偶式和對偶原理

在僅含有聯結詞 $\neg ,\wedge ,\vee$ 的公式A中，將∨換成∧，將∧換成∨，同時0和1互相替代，所得公式A^*稱為A的對偶式。

顯然，A也是A^*的對偶式。

定理2 公式的否定等於其變元否定的對偶式。

若A和B互為對偶式，設P[0] – P[n]為其變元，那麼：

!A(P[0], … , P[N]) == A(!P[0], … , !P[N])

A(!P[0], … , !P[N]) == !A(P[0], … , P[N])

定理3 對偶原理若兩個公式等值，則它們的對偶式等值。

0.4.1 簡單析取式和簡單合取式

簡單析取式：僅有有限個命題變項或其否定構成的析取式

如：p || !q ||r,p但 p || (!q ||r)不是

簡單合取式：僅有有限個命題變項或其否定構成的合取式

如：!p && q && !r,q

0.4.2 範式的定義合存在性

僅由有限個簡單合取式的析取構成的析取式稱為析取範式；

僅由有限個簡單析取式的合取構成的合取式稱為合取範式；

注意：p || r || q 是三個簡單合取式的析取，也是一個簡單析取式的合取。

定理4 任何一個公式均存在一個與之等價的析取範式和合取範式。

經簡單的構造性證明可以得到；

理論證明：

第一步化為基本三個符號組成的公式

第二步德摩根律等將否定移到命題變項之間

第三步使用分配率合結合律化去二重括號

例0.4.0 將(p → q) ↔ r化成兩種範式

原式=(!(!p || q) || r) && ( !r || (!p || q) )

=(p && !q || r) && ( !r || !p || q )

=( (p || r) && (!q || r) ) && ( !r || (!p || q) )

=(p || r) && (!q || r) && ( !r || !p || q )

原式=((!p || q) && r) || ( !r && !(!p || q) )

=!p&&r|| q&&r || !r && p && !q

0.4.3 主析取範式

1. 極小項（布爾合取）：對於公式中有n個命題變項p[0], p[1], … , p[n-1]中，每個命題變項p[i]或者其否定!p[i]出現且僅出現一個的簡單合取式，並且按照下標和字典排序。

規定：矛盾式主析取範式為0，重言式為其所有極小項析取

2. 極小項和賦值一一對應，每個極小項有且只有1個賦值使其為真，其它賦值均為假。

3. 極小項的記法：對於公示中2ⁿ個賦值，每個賦值對應一個極小項。對於任意一個極小項，將其記作解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle {m}_{\stackrel{\textasciimacron }{{a}_{1}{a}_{2}{a}_{3}}}} 或者將解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle \stackrel{\textasciimacron }{{a}_{1}{a}_{2}{a}_{3}}} 換成所對應十進制數k，即記作 ${m}_{k}$ ，其中 ${a}_{\mathrm {1,} }{a}_{\mathrm {2,} }{a}_{3}$ 分別是使其為真的賦值。

例0.4.1 將以下極小項化為命題公式的形式：

${m}_{01001}=\neg {p}_{0}\wedge {p}_{1}\wedge \neg {p}_{2}\wedge \neg {p}_{3}\wedge {p}_{4}$

${\begin{array}{c}{m}_{7}\Rightarrow {m}_{111}=p\wedge q\wedge r\\\Rightarrow {m}_{0111}=\neg o\wedge p\wedge q\wedge r\end{array}}$ 結論：表示為 ${m}_{k}$ 形式的極小項只能確定哪些變項不加「┐」，而不能確定那個應加

4. 主析取範式：若干個不同極小項的析取

5. 定理5 任何一個公式存在且僅存在一個與之等值的主析取範式。

例0.4.2 將!p&&r|| q&&r || !r && p && q 化成主析取範式

分析：每個極小項取真的取指分別為01_, _11, 100，我們知道析取式中只要一個簡單合取式為真，那麼結果就為真，所以，!p&&r可以改寫成!p&&q&&r || !p&&!q&&r同理。。。

例0.4.3 使用真值表法將!(p&&q)化為主析取範式

!(p&&q) == !p || !q

p	q	!p	!q
1	1	0
1	0	1
0	1	1
0	0	1

!(p&&q) == m₀₁ || m₁₀ || m₀₀ == (!p && q) || (p && !q) || (!p ||!q) = $\sum \left(\mathrm {0,} \mathrm {1,} 2\right)$

0.4.4 主合取範式

1. 極大項（布爾析取）：對於公式中有n個命題變項p[0], p[1], … , p[n-1]中，每個命題變項p[i]或者其否定!p[i]出現且僅出現一個的簡單析取式，並且按照下標和字典排序。

2. 極大項和賦值一一對應，每個極小項有且只有1個賦值使其為假，其它賦值均為真。

3. 極小項的記法：對於公示中2ⁿ個賦值，每個賦值對應一個極小項。對於任意一個極小項，將其記作解析失败 (未知函数“\textasciimacron”): {\displaystyle {M}_{\stackrel{\textasciimacron }{{a}_{1}{a}_{2}{a}_{3}}}} 或者將解析失败 (未知函数“\textasciimacron”): {\displaystyle \stackrel{\textasciimacron }{{a}_{1}{a}_{2}{a}_{3}}} 換成所對應十進制數k，即記作 ${M}_{k}$ ，其中 ${a}_{\mathrm {1,} }{a}_{\mathrm {2,} }{a}_{3}$ 分別是使其為假的賦值。

4. 主合取範式：若干個不同極大項的合取

5. 定理6 任何一個公式存在且僅存在一個與之等值的主合取範式。

結論： $\sum \left(\mathrm {0,} \mathrm {1,} 2\right)=\prod \left(3\right)$

0.5 邏輯推理

從已知條件、假設、前提或公理出發,根據推理規則推出結論、定理的過程,稱為推理,這是邏輯學最基本的任務,在命題邏輯中也不例外。這個過程稱為演繹或者形式證明。

設A與C是兩個命題公式,若A→C為永真式、重言式,則稱C是A的有效結論,或稱 A 可以邏輯推出C，A重言蘊含C，記為A⇒C。

由上述定義可知,當A為假時,A→C 肯定為真,因此在考慮 A⇒C 時,只要考慮A為真時,C 是否為真就可以了,因此上述定義可寫成：

設 A 與 C 是兩個命題公式,若當 A 為真時 C 也為真,則稱 C 是 A 的有效結論,或稱 A 可以邏輯推出 C,記為 A⇒C。

從上可知，當A⇒C正確時，若A為真，C為真；若C為假，A為假。

設a[0], a[1], … , a[n]是命題公式，如果(a[0], a[1], … , a[n]) → c 是重言式，那麼就稱c是集合{a[0], a[1], … , a[n]}的有效結論，或者說{a[0], a[1], … , a[n]}可以邏輯推論c。

或者寫作a[0] && a[1]&& … && a[n] ⇒ c

0.5.1 直接證法

根據已知的重言蘊涵式和基本等值式利用推理規則，推演出有效結論，這個過程成為形式演繹或抽象演繹。

P規則：任何推導的過程中，前提均可以引入

T規則：推導過程中，如果前面有一個或多個公式可以邏輯推導出命題公式S（或這些公式重演蘊含S），那麼S可以引入到推導過程中去。

推倒訣竅：假設重演蘊含號左側為真，看看是否能否推得右側——幾何推理。

基本重言蘊含式：

化簡I₁, I₂： $a\wedge b\Rightarrow a$

附加I₃, I₄： $a\Rightarrow a\vee b$

I₅：解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle \neg a\phantom{\rule{0.5em}{0ex}}=\phantom{\rule{0.5em}{0ex}}a\rightarrow b} （請用真值表證明）

I₆： $b\Rightarrow \neg b\rightarrow a\Rightarrow a\rightarrow b\vee \neg a\Rightarrow a\rightarrow b$

I₇：解析失败 (未知函数“\rule”): {\displaystyle \neg \left(a\rightarrow b\right)\phantom{\rule{0.5em}{0ex}}=\phantom{\rule{0.5em}{0ex}}\neg \left(\neg a\vee b\right)=a\wedge \neg b\Rightarrow a} （最後一步請用真值表證明）

I₈：解析失败 (未知函数“\rule”): {\displaystyle \neg \left(a\rightarrow b\right)\phantom{\rule{0.5em}{0ex}}=\phantom{\rule{0.5em}{0ex}}\neg \left(\neg a\vee b\right)=a\wedge \neg b\Rightarrow \neg b}

合取引入I₉： $a,b\Rightarrow a\wedge b$

析取三段論I₁₀：解析失败 (未知函数“\rule”): {\displaystyle \neg a,\phantom{\rule{0.5em}{0ex}}a\vee b\Rightarrow b}

假言推理I₁₁：解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle a,\phantom{\rule{0.5em}{0ex}}a\rightarrow b\Rightarrow b}

拒取式I₁₂：解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle \neg b,\phantom{\rule{0.5em}{0ex}}a\rightarrow b\Rightarrow \neg a}

假言三段論I₁₃：解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle a\rightarrow b,\phantom{\rule{0.5em}{0ex}}b\rightarrow c\Rightarrow a\rightarrow c}

構造性二論I₁₄：解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle a\vee b,\phantom{\rule{0.5em}{0ex}}a\rightarrow c,\phantom{\rule{0.5em}{0ex}}b\rightarrow d\Rightarrow c\vee d}

推論：解析失败 (未知函数“\rule”): {\displaystyle a\vee b,\phantom{\rule{0.5em}{0ex}}a\rightarrow c,\phantom{\rule{0.5em}{0ex}}b\rightarrow c\Rightarrow c}

等值式：若a ⇔ b，則a ⇒ b，b ⇒ a成立。

故，等值式亦可在形式推導中使用。

0.5.2間接證法

CP規則（附加前提證明法）：對於A ⇒ b → c，如果證明A && b ⇒ c，那麼原命題就被證明。

證明：A → (b → c) == !A || (!b || c) == !A || !b || c == !(A && b) || c == (A && b) → c

即，如果A → (b → c) == 1，那麼(A && b) → c == 1

對於公式中有n個命題變項p[0], p[1], … , p[n-1]，如果p[0] ∧ p[1] ∧ … ∧ p[n-1]可滿足，那麼我們稱p[0], p[1], … , p[n-1]是相容的。反之，如果p[0] ∧ p[1] ∧ … ∧ p[n-1]是矛盾式，那麼他們是不相容的。

歸謬法（反證法）：重言蘊涵式A ⇒ b中，若可得到A, ┐b不相容，那麼b是A的有效結論。

欲證A ⇒ c，僅需證A ∧ ┐c == 0。

證明略去。

1. 謂詞邏輯

1.0 基本定義

表示謂語部分的大寫字母,稱為「謂詞」。

如M表示需要喝水，N表示喜歡吃肉

謂詞需要主語，或者說個體。

比如用a表示「張三」，b表示「李四」；用x, y, z表示未知個體。

令P(x)為包含x的語句，D為一個集合；若對於集合D中的任一x，P(x)都是一個命題函數，其中D是P的論域或定義域。

1.0.1「每一個」和「有一個」

我們分別用旋轉了180º的「Any」和「Exist」的首字母的倒置形式「」和「」表示「所有」和「存在」。（為了省事，此處使用Any( x, P(x) )和Exist代替( x, P(x) )）

我們可以將一個命題表示為量詞語句： $\forall x\mathrm {P} \left(x\right)$ 、 $\exists x\mathrm {P} \left(x\right)$

當存在x使為P(x)為假時，我們知道 $\forall x\mathrm {P} \left(x\right)$ 為假，x稱為反例。

沒有使用「」和「」限定的變量叫做自由變量，否則成為約束變量。有自由變量的語句一般不是命題，無自由變量的語句是命題。

1.0.2 廣義的德摩根律

!( P(x₀) && P(x₁) && … && P(x_n-1) ) == !P(x₀) || !P(x₁) || … || !P(x_n-1)

!Any( x, P(x) ) == Exist( x, !P(x) )

!( P(x₀) || P(x₁) || … || P(x_n-1) ) == !P(x₀) && !P(x₁) && … && !P(x_n-1)

!Exist( x, P(x) )== Any( x, !P(x) )

所以我們得到兩個公式，它們稱為廣義的德摩根律。

[[Image:]]

1.0.3 其他的量詞運算律

分配率：

[[Image:]]量詞的收縮率和擴張率：

[[Image:]]置換規則：若B是A的子公式，且B ⇔ C，將B在A中的每次出現替換成C得到的公式D ⇔ A。（這其實是進行等值演算的一句，不需指明）

約束變元改名規則：將公式A中某量詞的指導變元和轄域中約束變元每次約束出現,全部換成公式中未出現的字母,所得到的公式記為B，則A ⇔ B。

1.1 合法公式

定義0，非邏輯符號：個體常元(如 a,b,c)、函數常元(如表示x +y 的 f(x,y))、謂詞常元(如表示人類的 H(x))。

定義1，邏輯符號：個體變元、量詞(「」和「」)、聯結詞、逗號、括號。

定義2，項：個體常元、變元及其函數式的表達式稱為項(item)。

(0)個體常元和個體變元是項,如 x,a,c

(1)若 f(x1,x2,..., xn)是 n 元函數,t1,t2,...tn 是 n 個項,則 f(t1,t2,..., tn)是項。如 f(x,y)是

項,x 2 +y 2 也是項,只要運算以後的結果仍是個體域中的對象就是項。

(2)有限次使用(1)得到的表達式是項，其他式子不是項。

定義3，原子公式：設 R(x₁ ,x₂, … ,x_n)是n元謂詞t₁, t₂, … ,t_n 是項,則 R(t₁, t₂, … ,t_n)是原子公式。

定義4，合式公式

(0)原子公式是合式公式;

(1)若 A 是合式公式,則(┐A)也是合式公式;

(2)若 A,B 合式,則 $A\wedge B,A\vee B,A\rightarrow B,A<->B$ 合式

(3)若 A 合式,則"「A」和「A」是合式

(4)有限次使用(1)~(3)得到的式子是合式。

1.2 嵌套量詞

定義命題函數P(x, y)為x駕駛過y。其中解析失败 (语法错误): {\displaystyle x\in \text{{飞行员}},\phantom{\rule{0.5em}{0ex}}y\in \text{{飞机型号}}}

我們設Q(x) = yP(x, y),

那麼xQ(x) == xyP(x, y)

從上面的結論並結合實例，我們很容易的知道：

xyP(x, y) == yxP(x, y)

xyP(x, y) == yxP(x, y)

但是以下式子可能不成立：

xyP(x, y) == yxP(x, y)

xyP(x, y) == yxP(x, y)

1.3 證明

公理

定義

未定義項

定理、引理、推論、公理

證明一個定理為真的過程稱為證明。

邏輯學中，一般的有且只有一個公理，任意命題重演蘊涵它本身。

1.3.1數學歸納法

本節整理自wikipedia。

數學歸納法（Mathematical Induction, MI）是一種數學證明方法，通常被用於證明某個給定命題在整個（或者局部）自然數範圍內成立。除了自然數以外，廣義上的數學歸納法也可以用於證明一般良基結構，例如：集合論中的樹。這種廣義的數學歸納法應用於數學邏輯和計算機科學領域，稱作結構歸納法。

最簡單和常見的數學歸納法是證明當n等於任意一個自然數時某命題成立。證明分下面兩步：

骨牌一個接一個倒下，就如同一個值到下一個值的過程。

設有一個命題函數P，

證明當n = 1时命题P(n)成立。

證明如果在n = m時命題P(n)成立，那麼可以推導出在n = m+1時命題P(n)也成立。（m代表任意自然數）

這種方法的原理在於：首先證明在某個起點值時命題成立，然後證明從一個值到下一個值的過程有效。當這兩點都已經證明，那麼任意值都可以通過反覆使用這個方法推導出來。

[[Image:]]例1.3.0 證明 ( $n\in \mathrm {N}$ )

我們易證這個公式在n == 0和1時成立，

然後我們計算[[Image:]]

下一步，將等式兩邊分別加上m + 1，得到

[[Image:]][[Image:]]

1.3.2 強數學歸納法

強數學歸納法(Strong Form of Mathematical Induction)。

證明對於命題函數P(n)，論域為D，由P(k) == 1推出對於任意n > k ≥ n₀時，P(n) == 1從而證明對於任意的n > k ≥ n₀，P(n) == 1過程。

例1.3.1 證明只要用2分和5分的郵票可以表示4分或4分以上的郵資。（方法不唯一，此處證明略去。）

1.4 邏輯謂詞的推理公理

[[Image:]]

全稱量詞的指定（US或-）： $\forall \mathrm {P} \left(x\right)\Rightarrow \mathrm {P} \left({x}_{0}\right)$ ，其中x可以為論域中任意個體。

全稱量詞的推廣（UG或+）： $\forall \mathrm {P} \left({x}_{0}\right)\Rightarrow \mathrm {P} \left(x\right)$ ，其中對P(x)為論域中任意個體成立方成立。

存在量詞的指定（ES或-）： $\exists \mathrm {P} \left(x\right)\Rightarrow \mathrm {P} \left({x}_{0}\right)$ ，其中x為某個特定的個體,不是任意的個體。

存在量詞的推廣（EG或+）： $\exists \mathrm {P} \left({x}_{0}\right)\Rightarrow \mathrm {P} \left(x\right)$ ，其中x可以為任意的個體。

2. 集合論

以下介紹集合論的內容摘自wikipedia：

集合是現代數學中一個重要的基本概念，而集合論的基本理論是在十九世紀末被創立的。這裡對被數學家們稱為「直觀的」或「樸素的」集合論進行一個簡短而基本的介紹，另外可參見樸素集合論；關於對集合作公理化的理論，可見公理化集合論。

在純數學中，樸素集合論是由德國數學家康托爾最早創立的第一個集合論，它後來被更加精確地構建為公理化集合論。

樸素集合論和公理化集合論的區別在於，前者依賴於把集合作為叫做這個集合的「元素」或「成員」的搜集（collection），未有形式化的理解。

而公理化集合論只使用明確定義的公理列表，還有從中證明的關於集合和成員關係的種種事實（公理起源自我們對對象的搜集和它們的成員的理解，但為了各種目的而被謹慎地構建，例如是避免已知的各種悖論）。

在1908年，恩斯特·策梅洛提議了第一個公理化集合論，策梅洛集合論。這個公理化理論不允許構造序數；而多數「普通數學」不使用序數就不能被開發，序數在多數集合論研究中是根本工具。此外，Zermelo的一個公理涉及「明確性」性質的概念，它的操作性意義是有歧義的。在1922年，亞伯拉罕·弗蘭克爾和陶拉爾夫·斯科倫獨立的提議了定義「明確性」性質為可以在一階邏輯中公式化的任何性質，從他們的工作促成了替代公理。Zermelo集合論接受替代公理和正規公理，產生了被稱呼為ZF的這個集合論。

2.0 集合論初步

集合（或簡稱集）是基本的數學概念，它是集合論的研究對象，指具有某種特定性質的事物的總體，（在最原始的集合論─樸素集合論─中的定義，集合就是「一堆東西」。）集合里的事物（「東西」），叫作元素。

我們可以在wikibook上看集合論的教程，我們這裡不做高一階段的討論。

我們用|A|表示集合A中元素的個數。

2.0.1 冪集

冪集：以一個集合的所有子集為與元素的集合，計為

例2.0.0 寫出A == {1, 2}的冪集：

它的子集：{}, {1}, {2}, {1, 2}

它的冪集：{ {}, {1}, {2}, {1, 2} }

我們可以看到，冪集的元素個數是2^|A|個，所以對於集合A，我們也可以記它的中、冪集為2^A。

我們也可以利用和命題邏輯中研究範式的形式來表示其子集，我們按照例題中的來做定義，解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle {A}_{\stackrel{\textasciimacron }{{a}_{\mathrm{0,}}{a}_{\mathrm{1,}}{a}_{2}\mathrm{...},{a}_{n}}}} 中的a_n表示命題「其子集中在原集中的第n個元素出現」的值。

也就是：

A₀₀ == Ø

A₀₁ == {1}

A₁₀ == {2}

A₁₁ == {1, 2}

2.1 集合的運算

設A，B為集合，

定義集合的減運算（集合的差）：

A - B = { x | $x\in \mathrm {A} ,x\notin \mathrm {B}$ }

定義集合的對稱差為：

[[Image:]]A △ B = { x | $x\in \mathrm {A} \wedge x\notin \mathrm {B}$ ∨ $x\in \mathrm {B} \wedge x\notin \mathrm {A}$ }

== { x | $x\in \mathrm {A}$ △ $x\in \mathrm {B}$ }

== (A - B) ∪ (B – A)

A ⊕ B== A ∪ B – A ∩ B

或記為A ⊕ B。

對於集合A，全集U，定義：┐A = { x | $x\in \mathrm {U} ,x\notin \mathrm {A}$ }

根據以上定義，我們得出集合的運算率：

冪等律：A∪A == A, A∩A == A;

結合律：(A∪B)∪C == A∪(B∪C), (A∩B)∩C == A∩(B∩C);

交換律：A∪B == B∪A, A∩B == B∩A;

分配率：A∪(B∩C) == (A∪B) ∩ (A∪C),

A∩(B∪C) == (A∩B) ∪ (A∩C)

同一律：A∪Ø == A

零一律：A∩Ø == Ø

排中律：A∪┐A == U

矛盾律：A∩┐A == Ø

吸收律（可通過前幾個運算率得出）：[[Image:]]

德摩根律：┐(A∪B) == ┐A ∩ ┐B

┐(A∩B) == ┐A ∪ ┐B

雙重否定：┐┐A == A

2.2 有窮集的計數

例2.2.0 某農民閒的蛋疼買了20匹馬，公母各一半，長毛5匹，短耳10匹，短毛長耳的母馬和公馬各3匹，長毛短耳的母馬和公馬各1匹。

我們假設長毛長耳母馬x匹，短毛短耳母馬y匹，如圖，得出方程組（圖中集合A表示母馬，B表示公馬）：

${\begin{array}{c}\left(5-x\right)+\left(10-y\right)+1+3=10\\x+y+1+3=10\end{array}}$

解得：

${\begin{array}{c}x=1\\y=5\end{array}}$

設P(A_n)為A_n的元素數。

二個集合的包含排斥原理：

P(A₀∪A₁) = P(A₀) + P(A₁) – P(A₀∩A₁)

因為 2 個集合的交集被重複算了一次,故要減去公共部分。

多個集合的包含排斥原理：

[[Image:]]加上奇數個集合相交，減去偶數集合相交。

2.3 有序n元組

將兩個具有固定次序的對象x, y寫成(x, y)或者<x, y>的形式，則我們稱(x, y)或者<x, y>為有序二元組或序偶。

若x == a, y == b，那麼(x, y) == (a, b)

下面我們定義有序n元組（簡稱n元組，其中 $n\in \left(\mathrm {0,} +\mathrm {\infty } \right)$ ）：

(0) 將兩個具有固定次序的對象x, y寫成(x, y)或者<x, y>的形式，則我們稱(x, y)或<x, y>為有序2元組或稱序偶，

(1) 若A == (a₀, a₁, … ,a_n-2)是有序n-1元組，那麼B == (a₀, a₁, … ,a_n-2, a_n-1)是有序n元組，簡稱n元組。

我們定義笛卡爾積（或稱直積）：

解析失败 (语法错误): {\displaystyle \mathrm{A}\times \mathrm{B}=\text{{}\left(a,b\right)\text{|}a\in \mathrm{A}\wedge b\in \mathrm{B}\text{}}}

其中，解析失败 (语法错误): {\displaystyle \text{|}\mathrm{A}\times \mathrm{B}\text{|}=\text{|}\mathrm{A}\text{|}\times \text{|}\mathrm{B}\text{|}}

注意： $\mathrm {A} \times \mathrm {B} \neq \mathrm {B} \times \mathrm {A}$

2.4 關係

例2.4 列出集合A == {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}自乘的笛卡爾積：

太長了，編者懶得列了。

反正上述積中那一大堆的元素未必都有用，於是我們就引入關係的概念，對於A×B，其直積中滿足一定條件條件的元素所組成的集合稱為關係，計為R。

根據定義，R_A×B ⊆ A×B。

若(x, y) ∈ R_x，那麼我們稱(x, y)滿足關係R_x。

算法