离散数学-数理逻辑知识整理(修改版)

阅读量：669 次

发布时间：2019-03-15

本文共 7236 字，大约阅读时间需要 24 分钟。

文章目录

离散数学

数理逻辑

命题逻辑

基本概念

命题：具有确切真值的陈述句称为命题。

真值：一个命题总有一个值，一般来讲，命题是正确的则真值为真，命题为错误的真值为假，这称为命题的真值。真值只有真假两种，分别用“T”（1）和“F”（0）表示。

原子（简单）命题：不能再分解为更简单命题的命题。

复合命题：可以分解的命题

命题变量：一个表示确定命题的命题标识符

命题变元：表示任一命题的命题标识符。（命题变元不是命题）

原子变元：命题变元是原子命题

指派/解释：当命题变元P用一个特定的命题取代时，P才能确定真值，称为对P进行指派。若公式G在解释I下是真，则称I满足G，I是G的成真赋值。反之称I弄假于G。

命题公式：由命题变量、命题变元、联结词和括号等组成的复合命题形式，这些符号不能任意组合，必须按下列定义：
1. 命题变元本身是一个公式
2. 若P是公式，┐P也是公式
3. 如PQ是公式，则P $\land$ Q、P $\lor$ Q,P $\rightarrow$ Q,P $\leftrightarrow$ Q也是公式
4. 仅由有限步骤使用规则1-3后产生的结果。

真值表：公式G在其所有可能的解释下所取真值的表。

等价公式：给定两个命题公式A和B，P1，P2，…Pn为所有于出现、并A和B中的原子变元，若给所有命题变元任一组真值指派，A和B的真值相同，则称A和B是等价的或者逻辑相等。充分必要条件是，G $\leftrightarrow$ H

[基本等价公式](#### 基本等价公式)

子公式：如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。

等价置换：设X是合式公式A的子公式，若X $\leftrightarrow$ Y,如果将A中的X用Y来置换，所得公式B和公式A等价。

合取范式：一个命题公式称为合取范式，当且仅当它具有形式： $A_{1}\land A_{2}\land \cdots \land A_{n}(n\geq 1)$ 其中A都是由命题变元或其否定所组成的析取式。

析取范式： $A_{1}\lor A_{2}\lor \cdots A_{n}(n\geq 1)$ 其中A都是由命题变元或其否定所组成的合取式。

命题公式的析取范式可以指出公式何时为真，而合取范式可以指出公式何时为假，从而代替真值表。

小项：n个命题变元的合取式，称为布尔合取或小项，但是每个变元和和他的否定不能同时存在，但两者必须出现且仅出现一次。
1. 每个小项当其真值指派与编码相同时，其真值为T，其余情况都是F
2. 两个不同小项的合取永假
3. 全体小项的析取式永真

主析取范式：对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价公式称作原式的主析取范式。在真值表中，是真值为1的指派所对应小项的析取。

大项：n个命题变元的析取式，称作布尔析取或大项，其中每个变元和她的否定不能同时存在，但两者必须出现且仅出现一次。
1. 每个大项当其真值指派与编码相同时，其真值是F，其余均为T
2. 任何两个不同大项的析取式永真
3. 全体大项的合取式永假

主合取范式：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取组成，则该等价式称为原式的主合取范式。在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。

命题公式永真但且仅当它的主析取范式包含所有的小项，主合取范式为空。永假公式反之。

两个命题公式相等当且仅当它们的主析取范式、主合取范式相等。

永真公式（重言式）：所有解释之下都是真

永假公式（矛盾式）：在所有的解释之下都是假

可满足的，不是永假

蕴含：当且仅当P→Q是一个重言式时，称P蕴含Q，记作P $\rightarrow$ Q。

推理：设A和C是两个命题公式，当且仅当A $\rightarrow$ C为永真公式，成C是A的有效结论。C由A逻辑地推出。定义可以推广到n个前提的情况，C为一组前提的有效结论。

其他联结词：

最小联结词组：设有一联结词集合A，A中的联结词的等价公式可表达任何命题公式，删除A中的任何一个联结词，至少有一个命题公式B不能表达。

联结词

联结词	记号	记法	真值结果
否定	┐	┐P	┐P为真当且仅当P为假
合取	$\land $	P$\land $Q	P$\land $Q为真当且仅当PQ同时为真
析取	$\lor $	P$\lor $Q	当且仅当PQ中至少一个是真
条件	$\rightarrow$	P $\rightarrow$ Q	为假当且仅当P为真Q为假
	$\leftrightarrow$	P $\leftrightarrow$ Q	当且仅当PQ同真假

联结词的优先级：非，合取，析取，条件，双条件

命题符号化

确定给定句子是否为命题

列出原子命题

句子中连词是否为命题联结词

根据命题含义，正确表示原子和适当选择命题联结词

基本等价公式

$KaTeX parse error: Undefined control sequence: \and at position 112: …or H)\lor S\\ G\̲a̲n̲d̲ ̲(H\land S)=(G\l…$

判断命题公式逻辑等价的方法

真值表

基本等价公式

等值置换

等值关系的传递性

求合取范式和析取范式的方法

简化联结词：将公式中的联结词化归成合取，析取以及非。

否定深入：利用德摩根律将“非”直接移到各个命题变元之前。

归约：利用分配律、结合律归约成合取范式或析取范式

求出主析取范式的方法

公式的真值表

基本等价公式
1. 化归为析取范式
2. 除去析取范式中所有永假的析取项
3. 将析取式中重复出现的析取项和相同的变元合并
4. 对析取项补入没有出现的命题变元，添加（P析取非P），然后，用分配律展开

求主合取范式的方法

真值表

基本等价公式
1. 划归为合取范式
2. 除去合取范式中永真的合取项
3. 合并相同的合取项和相同的变元
4. 对合取项补入没有出现的命题变元，即添加（P合取非P）式，然后，分配律展开

主范式间的转换

证明永真（假）的方法

真值表

证明和T（F）等价

证明蕴含的方法

指定前件真值为T，若由此推出Q的真值也是T，得证

指定后件Q的真值是F，若由此推出P的真值也是F，得证

常用的蕴含式

推理的方法

真值表法
1. 在所有行中，只要有一行的前提是真，结论是真，则得证
2. 在所有行中，只要有一行的结论是假，且前提也是假，则得证

直接证法

推理规则：
1. 规则P（前提引入规则）：前提在推到过程中随时引入。
2. 规则T（逻辑结果引入规则）：在推导过程中，如果有一个、多个公式蕴含着公式S，则公式S可以引入推导之中。
3. 规则CP（附加前提规则）：如果能从给定的前提集合T和公式P推导出S，则能从此T推导出P $\rightarrow$ S(使用场景是结论公式是蕴含式或者析取式)

间接证法

谓词逻辑

基本概念

在句子中可以独立存在的客体称为个体词，而用以刻画客体的属性或者客体之间关系的是谓词。

表示具体或者特定的个体词称为个体常量

表示抽象或者泛指的个体词称为个体变量

个体词的取值范围叫做个体域或论域，常用D表示。而宇宙间所有个体域聚集在一起所构成的个体域称为全总个体域

简单命题函数：由一个谓词、一些客体变元组成的表达式

复合命题函数：由一个或者n个简单命题函数以及逻辑连接词组合而成的表达式

命题函数：简单命题函数和复合命题函数的统称

命题函数不是命题，只有客体变元取特定的名称时才能成为一个命题。

全称量词： $\forall$ ,存在量词： $\exist$

( $\forall$ x)F(x)或( $\exist$ x)F(x)中，x称为作用变量，F(x)称为量词的辖域。

特性谓词加入命题函数中是遵循的原则：
1. 对于全程量词，刻画其对应个体域的特性谓词作为蕴含的前件加入
2. 对于存在量词，刻画其对应个体域的特性谓词作为合取式之合取项加入

谓词公式：
- 原子谓词公式是谓词公式
- 若A是谓词公式，非A也是谓词公式
- 若AB是谓词公式，则他们的合取，析取，条件，双条件都是谓词公式
- 若A是谓词公式，X是A中出现的变元，则（ $\forall$ x）A与( $\exist$ x)A也是谓词公式
- 有限次上述过程得到的

函数符号：表示个体词之间的转换，如F(x):x的父亲

项：任意的常量符号或者任意的变量符号是项。若f(x1,x2,…xn)是n元函数符号，t1,t2…tn是项，则f（t1,…tn）是项

原子公式：若P(x1,…xn)是n元谓词，t1…tn是项，则称P(t1…tn)为原子公式

合式公式：
- 原子公式
- 原子公式的非，析取，合取，条件，双条件
- 原子公式前加量词
- 以上三种的有限次组合

作用变元：量词后所跟的x叫做量词的指导变元或作用变元

作用域：P（x）叫做相应量词的作用域或辖域

约束变元：在作用域中变元x的出现称为约束出现，此时的变元x称为约束变元

自由变元：若x的出现不是约束出现，则称它为自由出现，此时的变元称为自由变元。

闭式：无自由变元的公式

约束变元的改名：（约束变元的改名规则）
- 将量词中出现的变元以及该量词辖域中此变量之所有约束出现都用新的变元替换
- 新的变元一定要有别与改名辖域中所有其它变量

自由变元的代入（自由变元的代入规则）
- 将公式中出现该自由变元的每一处都用新的变元替换
- 新变元不允许在原公式中以任何约束形式出现

赋值/解释：在谓词公式中客体变元由确定的客体取代，命题变元由确定的命题取代。

等价式：给定的两个谓词公式，设他们有共同的个体域E，若对A与B的任一组变元进行赋值，所得命题的真值相同，则称谓词公式A和B在E上是等价的。

前束范式：一个公式，如果量词全在公式开头，它们的作用域延伸到公式末尾，则该公式叫做前束范式。

谓词中的基本等价公式

$改名等价规则：\\ (\exist x)G(x)=(\exist y)=G(y)\\ (\forall x)G(x)=(\forall y)G(y)\\ (\forall x)G(x)\lor (\forall x)H(x)=(\forall x)(\forall y)(G(x)\lor H(y))\\ (\exist x)G(x)\land (\exist x)H(x)=(\exist x)(\exist y)(G(x)\land H(y))\\ 量词转换律：\\ ┐(\exist x)G(x)=(\forall x)┐G(x)\\ ┐(\forall x)G(x)=(\exist x)┐G(x)\\ 量词分配律：\\ (\forall x)(A(x)\land B(x))=(\forall x)A(x)\land (\forall x)B(x)\\ (\exists x)(A(x)\lor B(x))=(\exists x)A(x)\lor (\exists x)B(x)\\ 量词作用域的扩张和收缩：\\ (\forall x)(A(x)\lor B)=(\forall x)A(x)\lor B\\ (\forall x)(A(x)\land B)=(\forall x)A(x)\land B\\ (\exists x)(A(x)\lor B)=(\exists x)A(x)\lor B\\ (\exists x)(A(x)\land B)=(\exists x)A(x)\land B\\ (\forall x)(\forall y)A(x,y)=(\forall y)(\forall x)A(x,y)\\ (\exist x)(\exist y)A(x,y)=(\exist y)(\exist x)A(x,y)$