完成ENGINEERING NOTE

离散数学：数理逻辑

离散数学数理逻辑笔记，整理命题、真值、连接词、蕴含与等价等基础概念。

离散数学

这玩意就是和大学物理并列的两坨。

第1章命题逻辑的基本概念

1.1 命题与连接词

命题是指一个判断句的语义（实际表达的概念），这个概念是可以被定义并观察的现象。命题不是指判断句本身，而是指所表达的语义。
命题的真值：作为命题的陈述句所表示的判断结果。命题的真值只会有两个结果：真或假。真值为真为真命题，反之为假命题。
不能被分解成更简单的命题的命题称作简单命题/原子命题。由简单命题复合成的命题称作符合命题
悖论：由假推出真，由真推出假，从而既不能为真，也不能为假。悖论不是命题

命题符号：

命题符号	意义	说明
¬	否定
∨	析取	p ∨ q为真，当且仅当p，q为真
∧	合取	p ∧ q为假，当且仅当p，q为假
→	蕴含	p → q为假，当且仅当p为真，q为假
↔︎	等价	p ↔︎ q为真，当且仅当p，q同时为真或同时为假

需要说明： - 自然语言的或有**相容或**和**排斥或** 相容或：两者可以同时成立，*p* ∨ *q* 排斥或：两者不能同时成立，必须选择其一，(*p* ∨ ¬*q*) ∧ (¬*p* ∨ *q*) - 蕴含表达式中：p为蕴含式的前件，q为蕴含式的后件。*p* → *q*的意义是q是p的必要条件。 ## 1.2 命题公式及其赋值 - 简单命题的真值是确定的，又称为命题常项/命题常元，相当于基本数学中的常数。相应的，可以取值为0/1的变元称为**命题变项/命题变元**。*命题变项不是命题* - 将命题变项用连结词连接的符号串称为**合式公式**，简称**公式**。若公式B为A中的一部分且B也是公式，则称B为A的子公式。单个命题变项，¬*A*, (*A* ∧ *B*), (*A* ∨ *B*), (*A* → *B*), (*A* ↔︎ *B*)都是合式公式。 - 定义中A，B为元语言符号，*A* → *B*或*A* ∨ *B*为对象语言符号。使用元语言符号描述对象语言符号。 - 设*p*1, *p*2, ...*pn*组成一个合式公式A，对*p*1, *p*2, ...*pn*各指定一个值，这称为A的一个**解释**或**赋值**。若赋值使得A为真，则称为**成真赋值**，反之则为**成假赋值**。 - 将所有的取值列表，称为真值表。 - 若A的所有赋值都为真，则称A为**重言式/永真式**。若A的所有赋值都为假，则称A为**矛盾式/永假式**。若A不是矛盾式，则称A为**可满足式**。*重言式是可满足式*。 - 设公式A，B一共含有*p*1, *p*2, ...*pn*，A没有其中一部分，称这部分为**哑元**。由于A的取值和哑元无关，在讨论A，B是否有相同的真值表时，可将A，B看作都含有*p*1, *p*2, ...*pn*。 # 第2章命题逻辑等值演算 ## 2.1 等值式 - 若公式A，B构成的*A* ↔︎ *B*为重言式，则*A* ⇔ *B*，表示A和B是等值的。 - 若A是重言式，且其中含有*p*1, *p*2...*pn*，将*p*1, *p*2...*pn*替换为其他命题公式，记为B，则B也为重言式。例如：*A* ⇔ ¬¬*A*可以替换为(*p* ∧ *q*) ⇔ ¬¬(*p* ∧ *q*) - 等值式模式：相当于公理，恒成立的公式。一些有用的模式： - 分配律

$$ A\vee(B\land C) \Leftrightarrow (A\vee B)\land(A\vee C)\A\land(B\vee C)\Leftrightarrow (A\land B)\vee(A\land C) $$

- 德摩根律

$$ \lnot(A\land B) \Leftrightarrow \lnot A\vee\lnot B\ \lnot(A\vee B) \Leftrightarrow \lnot A\land\lnot B $$

- 吸收律

$$ A\land(A\vee B)\Leftrightarrow A \ A\vee(A\land B)\Leftrightarrow A $$

- 同一律

$$ A\land 1 \Leftrightarrow A \ A\vee 0 \Leftrightarrow A $$

- 假言易位

A → B ⇔ ¬B → ¬A - 蕴含等值式 A → B ⇔ ¬A ∨ B - 归谬 (A → B) ∧ (A → ¬B) ⇔ ¬A 将A，B代入以上模式，这些具体的等值式称为等值式的代入实例。

置换规则：若A ⇔ B设f(A)是包含A的公式，将B替换A称为f(B)，则f(A) ⇔ f(B)。

2.2 合取范式与析取范式

命题变项/命题变项的否定称为文字，有限个文字析取式称为简单析取式，有限个文字合取式成为简单合取式
定理：若析取式中含p和非p，A必然重言。如果A重演，则该析取式中必然有p和非p。若合取式中含p和非p，A必然矛盾。如果A矛盾，则该合取式中必然有p和非p。
由有限个简单合取式析取构成的公式称为析取范式，由有限个简单析取式合取构成的公式称为合取范式。
*每个公式都有与其等价的合取范式和析取范式。*将一般公式转化为合取/析取范式时，由于范式只含有∧∨，所以需要转化¬ → ↔︎连接符。
- 遇到→：使用蕴含等值式：A → B ⇔ ¬A ∨ B
- 遇到↔︎：使用等价等值式：A ↔︎ B ⇔ (A → B) ∧ (B → A)
- 不出现¬¬A：使用双重否定律。
- 不出现¬(A ∨ B), ¬(A ∧ B)：使用德摩根律：¬(A ∨ B) ⇔ ¬A ∧ ¬B
- 合取范式中不出现A ∨ (B ∧ C)，析取范式中不出现A ∧ (B ∨ C)：使用分配律。
极小/大项：公式A中所有的命题变项或其否定都只出现一次且按字典序排序，组成的简单合取/析取式。所有简单合取/析取式都是极小/极大项的析取/合取范式称作主析取/合取范式

第3章命题逻辑的推理理论

3.1 推理的形式构成

推理是从前提出发推出结论的过程。前提是已知的命题公式集合，结论是从前提出发推出的命题公式。
对于前提R，使得蕴含式R → B为重言式，则由前提R推出结论B的推理是有效的或正确的。B为有效的结论。
一些重要的推理定律：

$$ 附加律：A\Rightarrow\left(A\vee B\right) \ 化简律：\left(A\land B\right)\Rightarrow A \ 假言推理：\left(A\rightarrow B\right)\land A\Rightarrow B \ 拒取式：\left(A\rightarrow B\right)\land\lnot B\Rightarrow\lnot A \ 析取三段论：\left(A\vee B\right)\land\lnot B\Rightarrow\lnot A \ 假言三段论：\left(A\rightarrow B\right)\vee\left(B\rightarrow C\right)\Rightarrow\left(A\rightarrow C\right) \ 构造性二难：\left(A\rightarrow B\right)\land\left(C\rightarrow D\right)\land\left(A\vee C\right)\Rightarrow\left(B\vee D\right) \ 构造性二难（特殊形式）：\left(A\rightarrow B\right)\land\left(\lnot A\rightarrow B\right)\Rightarrow B \ 破坏性二难\left(A\rightarrow B\right)\land\left(C\rightarrow D\right)\land\left(\lnot B\vee\lnot D\right)\Rightarrow\left(\lnot A\vee\lnot C\right) $$

3.2 自然推理系统P

使用条件中的公式推理得到结论B，称为证明。每个条件之间是合取关系，所以与引入顺序无关。
在证明题中，题目通常如下出现：前提：…… 结论：…… 证明：
附加前提证明法例如需要证明的结论为s → q，那么假设s成立，将其放置于条件中，只需要证明结论s成立即可。

第4章一阶逻辑基本概念

命题逻辑具有一定局限性，我们引入量词概念，以期表达出个体和总体之间的内在联系和数量关系。

4.1 一阶逻辑命题符号化

个体词，谓词，量词是一阶逻辑命题符号化的3个基本要素。

个体词个体词是指研究对象中可以独立存在的客体，他们不受命题约束。表示具体或特定客体的个体词称为个体常项，用小写字母a，b，c表示。将抽象的，泛指的个体词称为个体变项，用x，y，z表示。个体变项的取值范围为个体域，如自然数集合N，实数集合R。有一个特殊的个体域，包含了宇宙中所有的事物，称为全总个体域，如果没有特殊说明，默认使用全总个体域。
谓词谓词是用来刻划个体词性质和其之间关系的词。通常用大写字母F,G,H表示。如F(x)可以表示x是常数，G(x, y)可以表示x<y。表示具体事物具体关系的谓词称为谓词常项，如F(a)：a是理塘丁真。表示泛指或抽象事物的谓词称为谓词变项，上面的F(x)和G(x, y)都是谓词变项。
量词量词分为两种：全程量词和存在量词。我们平时说的凡是，每一个，任意的……都是全程量词，记作∀。例如∀x∀yF(x, y)可以表示对于任何的x和y，都满足x<y。而说的存在，有一个，至少有一个都是存在量词，记作$\exist$。
特征谓词：当使用全总个体域时，为了将一样物体与其他物体区分开来，引进的谓词。

4.2 一阶逻辑公式及其解释

一阶语言是用于一阶逻辑的形式语言，可以看成命题公式加入了谓词之后的结果。
对于一个一阶逻辑公式L，命题常项、函数符号、谓词符号称为非逻辑符号，命题变项、量词、连结词，括号与逗号称为逻辑符号。注意命题变项是逻辑符号
项：个体常项，变项与函数的结合，可以看成单项式。
原子公式：单个谓词符号。
合式公式：数个谓词符号相结合。其实这些定义和第一、二章公式的概念非常类似，无非就是加上了“谓词”和“量词”这两个玩意。下面是一些零碎的定义。
在公式∀xA和公式∃xA中，x称为指导变元，公式A称为x的辖域。在辖域中出现的x称为约束出现，而其他变元称为自由出现。使用Δx表示x受约束（∀x/∃x），在Δx1A(x1, x2)中，x2可以自由出现。
如果A中不含有任何自由出现的命题变项，称A为封闭的公式，简称闭式
对公式中个体域，个体常项，函数符号，谓词的指定称为解释。对自由出现的变项的指定称为赋值
将公式A中个体域D指定为D1；出现的个体常项a替换为固定的a拔；函数f替换为固定的f拔；谓词F替换为固定的F拔；个体变项x指定为D1中出现的一个值，这样的公式值为A‘，是A的一个解释，或称为A被解释为A’。 这个东西绝壁会考
设A在任何解释下为真，则A为永真式。任何解释下为假，则A为永假式。若A可以为真，则称可满足式。（与公式那一块一样。）
将其他公式代入A，称为A的代换实例。

第5章一阶逻辑等值演算与推理

5-1 一阶逻辑等值式和量词逻辑

对于一阶逻辑中的两个公式A，B，如果A蕴含B为永真式，则称A与B等值。
下面是一阶逻辑中的基本等值式。
- 量词否定等值式

$$ \lnot \forall xF(x) \Leftrightarrow \exists x \lnot F(x)\ \lnot \exists xF(x) \Leftrightarrow \forall x \lnot F(x) $$

这个公式的直观理解是：不是所有的x满足F(x) 和存在x不满足F(x) 是等效的。 - 量词辖域收缩与扩张

$$ \forall\left(A\left(x\right)\vee B\right)\Leftrightarrow\forall xA\left(x\right)\vee B \ \forall\left(A\left(x\right)\land B\right)\Leftrightarrow\forall xA\left(x\right)\land B \ \forall\left(A\left(x\right)\to B\right)\Leftrightarrow\exists xA\left(x\right)\to B \ \forall(B \to A(x))\Leftrightarrow B \to \forall xA(x) \ $$

存在量词同理，除第三个为： ∃(A(x) → B) ⇔ ∀xA(x) → B - 量词分配等值式

$$ \forall x(F(x) \land G(x)) \Leftrightarrow \forall xF(x) \land \forall xG(x) \ \exists x(F(x) \vee G(x)) \Leftrightarrow \exists xF(x) \vee \exists xG(x) $$

注意任意量词对合取有分配律，存在量词对析取有分配律 - 换名规则在某量词辖域内，将一个约束出现的指导变元及其出现全部变为该量词辖域内另一个没有出现过的个体变项符号，换名前后公式等效。例如： ∀x(F(x, y) → ∃yG(x, y, z)) 等价于： ∀x(F(x, y) → ∃tG(x, t, z)) 其实是因为两个谓词中两个个体变项即使符号相同，意义却不同，可以任意替换。

当个体域为有限集时，可以消去量词。

$$ D = { a, b, c…z}\ \exists xF(x) \Leftrightarrow F(a) \vee F(b) \vee F(c) … \vee F(z)\ \forall xF(x) \Leftrightarrow F(a) \land F(b) \land F(C)… \land F(z) $$

感觉要考。

5-2 一阶逻辑的前束范式

具有Q1x1, Q2x2…QkxkB的一阶逻辑公式称为其前束范式，其中Q1, Q2….Qk为量词，B为不含量词的公式。 前束范式存在定理：一阶逻辑公式都存在等值的前束范式，且不唯一。

第1章 命题逻辑的基本概念