命题逻辑

逻辑中的符号系统：对自然语言的抽象，以便研究符号间的关系。

通过对复杂的语句进行编码，用逻辑学的方式讨论他们，那么语句本身的特殊性就消失了，含糊与歧义在一定程度上的被消灭了（但整个系统并非完备的，据哥德尔的证明）。这样语篇就被转化为了命题的组合，我们得以更容易地判断它们是否合乎逻辑的。

命题的定义即可判断真假的陈述句，故若将命题记作变量p，则它有两种取值，那么我们可以把它和二进制，和布尔代数联系起来。但世界上也存在多值逻辑与模糊逻辑。//虽然我根本不懂

基本概念

命题（Proposition），“往矣”“可乎”“此言谬矣”等并非命题。

否定（Negation）

合取（Conjunction），$\wedge$，and的抽象。

析取（Disjunction），$\vee$，or的抽象。

异或（Exclusive Or），在自然语言向符号系统转化的时候尤其要关注关系是exclusive还是inclusive。

异或有个很漂亮的应用，博弈论中的Nimm’s Game，它涉及的性质是a^b=0当且仅当a=b，还有异或的交换律，所以这种博弈以所有数的异或和作为判断基准。（我瞎说的）

异或还有一些简单的性质，在有的题目中可能会用到。如a ^ b = c $\Leftrightarrow$ a ^ c = b，还有a - b $\leq$ a ^ b。这些并不难证明，但要想到它们就有一些难度了。

蕴含（Implication），关注only if和if的区别，充分条件和必要条件及其他表达。蕴含式的真值规则可以在生活中找到一些很好的例子，如合同，承诺等。

等价（Equivalent），注意它和$\equiv$还有$\Leftrightarrow$的区别，后两者是等价的。

真值表（Truth Table），多用于证明，但我不大喜欢这样的证明，感觉不如Venn图直观，也不如简单的推理来得漂亮。

概念还有运算符顺序、位运算。//运算符顺序为何如此？

习题1：有100句话，第i句说的是“这些话中恰有i句是假话”（变式：“这些话中至少i句是假话”），求哪些是真话哪些是假话。（lrj在他的鬼书里也有这样递归的鬼问题，但我不会啊qwq）

习题2：判断$(p \vee \lnot q) \wedge (q \vee \lnot r) \wedge (r \vee \lnot p)$何时为真，何时为假。

习题3：判断$(p \wedge q \wedge r) \vee (\lnot p \wedge \lnot q \wedge \lnot r)$何时为真，何时为假。

应用

1.翻译自然语言并判断其间的逻辑性。

2.对一大串语言能否同时为真做判断。因为语言所涉及的多为一个系统所以这也叫System Specification。如果同时为真，称they are consistent。

3.在数据库中检索信息，在网络中查找网页。（在吴军老师的书中有进一步的介绍，但我还没好好看）

4.Puzzles，如说谎者游戏。这些游戏可能能发展小孩的智力。道奇森在这方面有一定的建树，其著作《爱丽丝漫游奇境》就蕴含了作者丰富的数学思想和对儿童的深切的关爱。

5.表示逻辑电路（香农首次大规模将逻辑与电路连接起来，从而建立了通信理论的大厦）。

Exercise 15，16，17，//题干太长懒得抄

习题2：斑马问题（zebra puzzle）

题解：先冷静下来，放松一下心情。（怪我英语不好，把to the right和on the right意思搞反了，也懒得改过来了，就这么做吧~心路历程而已）

1.先观察房子颜色，题目中出现了全部五色房子，挪威人住第一间，他右边是蓝房子。房子颜色，经过简单疏理，是黄蓝红绿白或黄蓝绿白红，推出挪威人住黄房子，他是外交官，然后蓝屋子屋主养马。

2.绿屋子人喝咖啡，而中间屋子人喝奶，所以房子排列只能是黄蓝红绿白。英国人住红房子喝奶。

3.下面看职业和饮料。𠸄人嗜奶，意人嗜茶，挪威人是外交官，日本人是画家，故而喝橙汁的音乐家是西班牙人，他养狗，不住蓝屋子（马限制），不住红屋子（英国人已占），不住绿屋子（咖啡限制），住白房子。

4.意大利人喝茶，不住绿屋子，那么他住蓝屋子。排除法得日本人住绿房子，画家，喝咖啡。

4.再看宠物。摄影师养蜗牛，西班牙人白房子养狗，意大利人蓝屋子主养马，挪威人不是摄影师，那么摄影师是意大利人或英国人，若为前者，则后者是医生，旁边没狐狸，矛盾。所以英国人是摄影师养蜗牛，挪威人养狐狸。排除得日本人养斑马。

5.英国牛奶，西班牙橙汁，意大利的茶，日本咖啡。排除出来矿泉水挪威。

疑惑：为什么错误的前提也能推出正确的结论呢？是什么影响了答案的走向与其是否自洽？另外，这个题目是如何构思出的呢？怎样保证在讯息最少的情况下可解呢？

等价

等价、同构，将复杂的问题归而为一，充分展现了数学的奇妙与瑰丽。

等价涉及了一些概念：重言式或永真式，矛盾式，将这些概念和蕴含想结合定义等价会更方便。

说到等价，势必要讲到一系列定律，其中需要记的有德·摩根律（及其n元形态）、分配律、蕴含到析取合取的转化，而对吸收律等的运用要具备一定观察能力。

判断命题为真时的取值问题，习题3是个很好的例子。

上述问题的一个应用是解数独，貌似可以用bfs实现。//但我还不会啊qwq，而且书上那个记号是啥意思咧？

习题1：探索何谓对偶命题及为何等价的命题能推出其对偶命题也等价。//不会鸭。。

习题2：Exercise 41，有无更巧妙的构造方法？

习题3：什么样的取值能使$p \vee \lnot q \vee s, \lnot p \vee \lnot r \vee s,$ $ \lnot p \vee \lnot r \vee \lnot s, \lnot p \vee q \vee \lnot s$ $, q \vee r \vee \lnot s, \lnot p \vee \lnot q \vee \lnot s, p \vee r \vee s, p \vee r \vee \lnot s$中尽可能多的值为真呢？//普遍的算法？

//NAND，NOR这些都什么东西？干嘛要提它们？

范式

命题的组和是无穷无尽的，但其真值是有限的。为了将不同形式下真值一致的复合命题归为一类，我们引入范式(normal form)的概念，其中有CNF与DNF两类(C for conjunction)，他们间也可以互相转化。//补充

不过，许多范式仍然不够漂亮，比方说$p \vee \lnot p \vee (q \wedge \lnot r)$。为了让范式更加规范，我们引入主(full)析取/合取范式的概念，这样范式就和真值表紧密相连了。而任何命题均可转化到范式，由真值表易知。

欲将复合命题转化为范式，一种做法是列真值表，这是比较容易的。如果得到了主析取范式，利用真值表也能够直接得到主合取范式。

另一种做法是直接推导。先将部分的$\lnot$（任何不是修饰原子命题的）及$\rightarrow$除去及重复的原子命题。这样原命题便被转化为$p_i, \vee, \wedge$的串，接着再大量使用结合律就好了，同时注意添项。//例子

谓词逻辑

谓词

谈到逻辑，一个相当经典的概念便是亚里士多德提出的三段论。然而，仅凭命题逻辑无法从小前提与大前提得出结论，因为前提与结论中有的只是内容而非形式上的联系（还记得么？命题逻辑中的if then前后的语句无需有任何关联。还有，包含未定变元的陈述句亦不成命题）。数学上，我们常要研究对象的性质问题，故需将问题细化，从命题逻辑深入谓词逻辑。

谓词逻辑中的对象一般是未定式，故在形式上一个谓词命题，P(x)，看上去更接近一个函数，x也有自己的定义域(domain)。看到变元就关注定义域是一个重要而良好的习惯。

量词

x的定义域是一个集合，其中的元素有的满足性质P，有的并不满足。为了表达定义域中是否存在满足性质的x这一需求，我们再引入量词(quantifier)的概念。常用的量词有$\exists, \forall$，不常见的有$\exists_1$等等。

量词的引入实则是对符号系统的一种简化，使其能更好地符合我们的思维习惯以提高推理效率。以$\forall x P(x)$为例，它等价于$\bigvee\limits_x P(x), x \in S$。因为这种等价性，含量词的复合命题在取否定有“存在转任意，任意转存在”的规则，这实则就是德摩根律的推广。

量词的一个重要要素就是它的约束范围，即它与哪一式子结合(bind)。$\forall x P(x) \wedge \forall x Q(x)$与$\forall x (P(x) \wedge Q(x))$在意义上并不一致。前者那样的写法在式子变得更加复杂时很可能引起一定程度混乱，故我们再引入前束范式(prenex normal form)的概念——将所有量词提前，可能产生歧义的变元用不同的记号标识（插一句，我觉得$\forall x (P(x, y) \wedge \forall y Q(y))$这样的写法很反人类）。

等价

涉及量词的等价，往往不能简单粗暴地列真值表了，而是要用推理了。

习题？证明$\forall x (P(x) \wedge Q(x)) \equiv \forall x P(x) \wedge \forall x Q(x)$和$\exists x (P(x) \vee Q(x)) \equiv \exists x P(x) \vee \exists x Q(x)$，举出$\exists x (P(x) \wedge Q(x)) \not\equiv \exists x P(x) \wedge \exists x Q(x)$还有$\forall x (P(x) \vee Q(x)) \not \equiv \forall x P(x) \vee \forall x Q(x)$的例子。

另外还有量词命题和无量词命题(null quantification)析取合取（如$\forall P(x) \vee A$）的等价式，一般情况下都是可以直接去括号的，但涉及蕴含的时候要小心点因为蕴含和否定是相关联的。

谓词和量词的概念就介绍到这里了，不过有了新的记号我们前面的翻译啊什么的也都升级了，毕竟这一章仍是前几章的推广嘛，中心思想仍未变。翻译中值得注意的一种类型是定义域较小的情况。比方说，令全集为生物，P(x)表示“x是狮子”，Q(x)表示“x爱喝茶”。则“所有狮子爱喝茶”是$\forall x (P(x) \rightarrow Q(x))$，而“有狮子爱喝茶”是$\exists x (P(x) \wedge Q(x))$。为什么会这样？其实只要关注狮子以外的动物就好了。

//书上的习题没怎么做，标*的也就是类似三段论的。

嵌套

上面讲的往往都是单个量词的情况，但现实是“更多量词，更多欢乐”。比如说，表示加法结合律，表示$\epsilon - \delta$语言，都要用到量词的嵌套。量词嵌套涉及到顺序的问题，里头的规则很简单：相同的能替换，不同的不能换，这也很好理解，可以在脑海中对所有元素遍历一遍来加深印象。

有新的概念引入，否定自然也是要实时更新的了，不过规则格外简单：存在变任意，任意变存在，否定移进去。

有新的概念引入，翻译自然也会更新了，除了和自然语言间转来转去，有了量词嵌套，数学语言也可以加入转换行列了，快来用最新的量词嵌套试试九种最基本的算数性质吧！

有了嵌套，命题者就可以用更新颖恶意的方式定义$\exists_1$等量词了。比如，好好的$\exists_1 b P(a, b)$会变成$\exists b \forall c (P(a, b) \wedge (b \not = c) \rightarrow \lnot P(a, c))$，更漂亮了对吧。

推理与证明

在讲命题逻辑的时候，我们都是根据已有的命题组判断其真假性，涉及到的命题组还只是个封闭的集合。那么，我们能否由已知的命题推出新的命题，比如三段论中的结论？推理规则就要派上用场了，它能让我们进行推理——在假定premises均为真的情况下推出新的命题。

推理规则

关于推理规则有一整张表，但是我不喜欢列表，就逐项分析吧。

1.Modus ponens/tollens，它们和蕴含相关联。前提真则结论真，结论假则前提假，非常好理解。关于后者的证明可以直接感受也可以列真值表也可以用逆否命题来证，个人感觉最后一项比较漂亮，因为它涉及的是化归的思想。而且，使用逆否命题有时候可以让推理变得简单。

//关于modus ponens的中文命名“假言推理”我并不是很明白。同时这些规则为什么要叫这些名字呢？

2.Hypothetical syllogism，假言三段论，这就更好理解了。可以把它和析取三段论（Disjunctive syllogism）放一块记。

3.和析取/合取有关的规则。从单项到合取式是添项（Addition，$p \Rightarrow p \vee q$），从析取式到单项是减项（Simplification，$p \wedge q \Rightarrow p$），还有析取（Conjunction，$p, q \Rightarrow p \wedge q$）。很容易推，因为前提是真的。

4.Resolution，这个比较特别，两个析取推出一个析取，起到删项的作用。有点像一个元素和他的逆相乘然后抵掉这样的感觉。

推理规则和永真式是有所联系的，比如$p_1, p_2, …, p_n \Rightarrow q$是有效（valid）推理，那么$\bigwedge\limits_i p_i\rightarrow q$便是永真式。

一般情况下我们要推理的结论都是可爱的非复合命题，如果它长得比较丑陋，比方说，$p \rightarrow q$，该怎么办呢？不用慌，把p看作新的条件而q看作新的结论就好了。而如果它是析取项，可以考虑Resolution。

5.Fallacy of affirming the conclusion，错误推理。比如，有萌新可能会发现这样的新大陆：$p \rightarrow q, q \Rightarrow p$。这非常的正确！而且它还有好多等价的涉及否定的变形，快来用它们拓展你的推理规则仓库吧！（手动滑稽）

5.涉及量词的推理，universal/existsential instantiation/generalization，共四个，可以望文生义。为什么要引入它们呢？因为我们具体推理地时候不能抽象地说“存在一个”“对任一”，而要用具体的符号表示“那一个/那一类”。但引入这些东西有时候也会造成推理的错误，但一般通过举出一个具体的例子这一方式还是能发现问题所在的。

证明初步

证明，首先有Formal Proof与Informal Proof之分，前者是上一节所要遵守的规范格式，很丑陋，很麻烦，很不人性，故现实中我们一般都采取后者，省掉一些“显然”的步骤来使证明在格式上更漂亮。但是要注意，“显然”有时并不“显然”，蕴含了跳步与可能的错误。为让愚昧的计算机理解智慧的人类的证明，我们只得采取Formal Proof。

关于证明，这里推荐张景中院士的《数学家的眼光》一书，虽然它主要面向中学生，但其中证明的思路与看待问题的眼光都是相当犀利的。（如果诸位了解同类型的优质读物请务必向我推荐，毕竟我对数学只懂些皮毛而已）

证明策略

  1. 直接法

    1-1：对$\exists$可以分类遍历，对$\forall$则可以分类枚举；

    1-2：正向或反向或正向反向一起用证明（正向曰由因导果或“综合法”，反向曰由果索因或“分析法”）。

    1-3：对$\exists$可以采用构造的方式（典例：证明存在连续10个合数），对$\forall$可以采取找反例的方式；

  2. 间接法

    如果直接法不好入手（如“无理数”是实数排除“有理数”而生的概念，本身的定义不好用），可以考虑间接法。

    2-1：证明逆否命题。

    2-2：反证法，假设结论不成立，推出矛盾之处。反证法的理论基础是$\lnot p \rightarrow (r \wedge \lnot r)$，其中r是任意矛盾的命题，在$\sqrt 2$的例子中，即“m，n互素”。

    关于反证法有很多漂亮的例子，此处列出一些，以飨读者。

    典例1（数论）：证明$\sqrt 2$为无理数。

    典例2（数论）：证明素数有无穷多个。

    典例3（组和）：证明抽屉原理。

  3. 归纳

    包括但不限于数学归纳法及其变种（第二类数学归纳法，反向数学归纳法，后者可用于证明n元的基本不等式）。

    归纳（induction）不只是种证明的方法，它更是一种思维方式，“告诸往而知来者”，从特殊到一般的思想。与之相对的是演绎（deduction），从一般到特殊的思想。我们前面所学的推理便是都是演绎的典范。

  4. 其他

    Vacuous Proof与Trivial Proof，相当没意思：证明条件为假或结论为真，于是$p \rightarrow q$必为真。

证明类别

证明可以正向也可以反向也可以结合二者，反向的一个例子是Bash Game。

存在性证明

对于存在性证明，有构造性的也有非构造性的，非构造性证明往往是分析性质，或是使用数学归纳法，而不会给出求解的算法，如霍尔婚配定理的证明。

对于“存在可被两种方式写为两立方数和的正整数”，我们可以算出$1729 = 10^3 + 9^3 = 12^3 + 1^3$。顺带一提，1729被称为“拉马努金数”，是一个“有意思的数”。（读者不妨对“有意思的数”展开一些思考，比如想想是否存在最小的正的“没意思的数”）

非构造性证明的一个漂亮例子是“证明存在无理数x, y使得$x^y$是有理数”。

对于非构造性证明，书中还给出了博弈论中的Chomp game，也是经典的例子。

穷举法

穷举往往是针对有限元的，而且数目不能太多，否则人类做着会烦。但是面对无限元也可以穷举不怂，因为把握精度或许能够将我们所面对无限集转化为“要穷举的”有限集。

//例子

唯一性

平面几何中有很多关于唯一性的证明，要用到同一律，例子有Ceva定理等。

对于一些新引入的概念我们也常要证明唯一性，如矩阵的逆（若存在）是唯一的，乘法逆元（若存在）在模p的意义下是唯一的。

等价定理

涉及一组等价定理的证明，我们可以采取$p_1 \Rightarrow p_2, p_2 \Rightarrow p_3, … , p_n \Rightarrow p_1$这样的策略，减少多余的证明。例子么，以下。

1.$f(x_1, x_2, … , x_n) = X^T A X$为正定二次型。

2.$f(x_1, x_2, … , x_n) = X^T A X$正惯性指数为n。

3.存在可逆矩阵B使得$A = B^T B$。

4.A的顺序主子式均大于0。

完备性

希尔伯特等的乐观主义使他们希望在公理之上构建出至臻至善的数学大厦。他在20年代提出了建立一组公理体系来保证数学“完备性”“独立性”“相容性”的期望。所谓完备性，指的是一切数学命题在原则上可判定真伪。然而哥德尔不完备性定理击碎了这一期望。比如古德斯坦定理，其在皮亚诺公理系统中是不可证的，但用超出这一公理系统的方法则可证明。

//这一段如出现知识性错误，请指出。

开放问题

费马大定理（已解决），3x+1猜想。

其他

证明是一个大有文章可做的话题，即便是前面讲到的看上去没啥好说的直接法，里头也包含了方方面面的子方法，它们考察的对象各不相同。如在组合中，染色法有很大的作用。在证明和式相等的时候，图形证明则将数学之美展现得淋漓尽致。（如果觉得三角形数正方形数太小儿科，不妨用图形证一证Abel恒等式）

另外，证明的时候骚话不能多说，像什么“显然”；有的话该说得说，如“不失一般性”。

上面提到用反证法证明“素数有无穷多个”。不过事实上，这一相对简单的定理能以很多种方法证明，卢昌海于这篇blog中汇总了九种方法（虽说有的有些重复），私以为这一篇的水准相当不错（卢昌海关于数学的科普写得少，但个人感觉都非超好）。这里简单分享一下欣赏完后的感想：后面的大部分方法依据的都是算术基本定理，结合或组和或数论或其他的方法精妙地推出了矛盾。而利用数列的证明还有用欧拉函数的证明看起来与其他方法均不同，较为特殊。好的科普就应该是这样的：拓宽认识问题的角度，并给予读者意料之外的收获（如对$\pi (N)$的粗略估计，各个领域的联通，等等）。

证明误区

警惕错误的前提还有错误的推理！一般通过常识还有举例都能够判断结论是否为真，然后挑错就是了。网上时常有神仙一言不合就推倒数学大厦，大家不妨从中找找乐子，顺带锻炼锻炼自己的挑错能力，好使逻辑更严密。

错误的推理包括但不限于命题逻辑中的错误推理（请参阅《推理规则》第五条），“除以0”等等也应纳入考虑范围。

还有种证明误区便是循环论证——（隐蔽地）利用结论来推结论。这和前面的错误也相仿，只不过它用的是“未定”的前提而非错误的前提。

其实，我们所用的语言本身就是循环自指的——字典上为诠释一词的意思必须用其他的词语来描述，来类比。在这样的情况下，用语言来探究哲学的基本问题是否值得？我不知道。