离散数学学习要点—

文章目录

数理逻辑
- 命题逻辑
- - 命题
  - 命题的种类
  - 命题的表示
- 逻辑连接词
- - 否定联结词¬
  - 合取联结词∧
  - 析取联结词∨
  - - 或
    - 异或
  - 条件➡
  - - 等价（双条件）联结词↔
    - 联结词真值表
- 命题逻辑中的命题的符号化
- 命题公式及其真值表
- - 命题公式
  - 真值表
- 命题公式的等价
- 重言式与重言蕴含式
- - 重言式
  - 重言蕴含式
- 析取范式与合取范式
- - 析取范式
  - 合取范式
  - 析取范式与合取范式的写法
- 主析取范式
- 主合取范式
- 命题逻辑推理
- - 直接推理
  - 间接推理
谓词逻辑
- 谓词逻辑的基本概念
- - 谓词的出现
  - 相关的基本概念
  - - 个体
    - 谓词
    - 命题函数
    - 个体域
    - 量词
- 谓词公式及变元的辖域
- - 原子谓词公式
  - 谓词合式公式
  - 量词的作用域（辖域）
  - 自由变元与约束变元
  - 说明
  - 变元换名
- 谓词逻辑中的命题符号化
- 谓词演算的等价式与蕴含式
- - 对谓词公式赋值
  - 谓词公式的永真式
  - 谓词公式的等价公式
  - 谓词公式的永真蕴含式
  - 谓词演算的等价式与蕴含式
  - - 由命题演算推广出的公式
    - 有限个体域消去量词的等价公式

数理逻辑

命题逻辑

命题

判断一句话是否是命题有两个关键

1、是陈述句
2、有且只有一个真值

2是个素数
- 是命题
x + y < 5
- 不是命题，是命题函数
我正在说谎
- 不是命题，是悖论（从它的真可以判断它的假，从它的假又可以判断他的真。）。如果真值为T，那么他就正在说谎话，“我在说谎”这句话就是假的；若真值为F，那么他就没有说谎，“我正在说谎”这句话就是真的。

命题的种类

原子命题（简单命题）

不能再分解成更简单陈述句的命题

复合命题（分子命题）

由若干个连接词、标点符号及原子命题符合构成的命题

命题的表示

简单命题用大写字母表示，例如：

P：今天下雨
Q₁：小王是大学生

复合命题则由若干个连接词、标点符号及原子命题复合构成的命题。

逻辑连接词

复合命题用“逻辑联结词”将原子命题联结起来表达
归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：
在这里插入图片描述

否定联结词¬

表示：“并非···”，“不···”等
用于对一个命题P的否定，写成“¬P”，并读成“非P”。

定义：

设P为一命题，P的否定是一个新命题，记为¬P。¬P的真值与P的真值相反。

合取联结词∧

表示：“并且”、“不但…而且…”、“即…又…”、“尽管…还…”等。

相当于“&”

例：

P：小王能唱歌
Q：小王能跳舞
P∧Q：小王能歌善舞

定义：

两个命题P和Q的合取是一个复合命题，记作P∧Q。当且仅当P和Q的真值均为T时，P∧Q的真值为T，其他情况下，P∧Q真值均为F。

析取联结词∨

联结词“或者”的表达分为两种情况：

可兼取的或，即两件事情可以同时发生。用析取**“∨”**表达。
不可兼取的或，即两件事情不能同时发生。用异或（也称排斥或）表达。（符号如下所示）

或

例：

P：小王能唱歌
Q：小王能跳舞
P∨Q：小王能唱歌或者能跳舞
小王能唱歌与能跳舞可以同时发生，我们用析取”∨“表达

定义：

两个命题P和Q的析取是一个复合命题，记作P∨Q。当且仅当P和Q的真值均为F时，P∨Q的真值为F，其他情况下，P∨Q的真值均为T。

异或

在这里插入图片描述
当且仅当P与Q的真值相同时，P异或Q的真值为F，真值不同时为T

条件➡

表示“如果…那么…”，“若…则…”等。

例：

P：土壤缺少水分
Q：这颗植物会死亡
P➡Q：如果土壤缺少水分，这颗植物就会死亡。

P➡Q读成“若P则Q”。
称P是P➡Q的前件，Q是P➡Q的后件。也可以说P是Q的充分条件，Q是P的必要条件
在这里插入图片描述

当且仅当P为T，Q为F时，P➡Q的真值为F；在其他指派下，P➡Q的真值均为T。
用“➡”表达必须前件是后件的充分条件，即若前件成立，后件一定成立。

注意哪个是前件，哪个是后件！

等价（双条件）联结词↔

表示“当且仅当”、“充分必要”等。

定义

当且仅当P与Q的真值相同时，P↔Q的真值为T，否则为F。

maybe同或

联结词真值表

在这里插入图片描述

命题逻辑中的命题的符号化

命题符号化，就是将自然语言表达的句子用符号化的命题公式来表达。

命题符号化的步骤：

1、先将语句分解成原子命题。
2、将每个原子命题用大写祖母表示。注意每个原子命题都必须是一个完整的句子。
3、用确切的逻辑联结词联结原子命题，构成给定命题的符号表达式。

命题公式及其真值表

命题公式

在命题公式中有三种数据类型:

命题常项：即命题的真值
常值命题：即具体命题
命题变元：用大写字母表示的任一命题。命题变元本身不是命题，因为它没有固定真值，只有给它赋值，才变成命题。

将一个命题常项或常值命题赋予命题变元的过程称为给命题变元赋值，也称为对命题变元作指派

合式公式（合法的命题公式）定义：

1、单个命题变元、常值命题及命题常项是合式公式。
2、若A是合式公式，则¬A是合式公式。
3、若A和B都是合式公式，则（A∧B），（A∨B），（A➡B），（A↔B）都是合式公式。
4、当且仅当有限次地应用1、2、3所得到地符号串是合式公式

为了简化命题公式，约定：

1、最外层括号可省
2、不影响运算次序地括号可省
运算次序由高到底为：¬，∨，∧，➡，↔

真值表

定义:

一个含有命题变元的命题公式不是命题，因为它没有固定真值，但是给其中的所有命题变元赋值以后它就有了唯一的真值。将所有各种赋值情况汇列成表，即为该命题公式地真值表

构造真值表的步骤

由于每个命题变元都有两种赋值可能性（T，F），所以含有n（n≥1）个命题变元的命题公式真值表有2ⁿ行。
将n个命题变元按字母次序排列
将F记为0，T记为1，按照二进制的次序赋值。
赋值从00…0开始,然后按二进制加法依次加1，直到11…1为止。
对每个赋值，计算命题公式的真值。

命题公式的等价

在这里插入图片描述

定义：

A、B是含有命题变元P₁、P₂、…，P_n的命题公式，如不论对P₁，P₂，…P_n作何种赋值，A和B的真值均相同，则称命题公式A与B等价，记作A↔B
若两个命题公式的真值表相同，则它们等价。

基础等价公式
在这里插入图片描述

等价公式的证明方法

方法一：列真值表
方法二：用等价公式变换。（用置换定律）

置换定律：A是一个命题公式，X是A中的一部分且也是合式公式，如果X⇔Y，用Y代替A中的X得到公式B，则A⇔B。

对偶式

在一个只含有联结词¬，∨，∧的公式A中，将∨换成∧，将∧换成∨，T换成F，F换成T，其余部分不变，得到另一个公式A^*，称A与A^*互为对偶式

等价的性质：

1、有自反性：对任何命题公式A，均有A⇔A。
2、有对称性：若A⇔B，则有B⇔A。
3、有传递性：若A⇔B且B⇔C，则有A⇔C。

重言式与重言蕴含式

重言式

在这里插入图片描述

¬P∨P为重言式（永真式）
¬P∧P为矛盾式（永假式）

重言式定义

若公式A⇔T，则A为重言式或永真式
若公式A⇔F，则A为矛盾式或永假式

重言蕴含式

定义

当且仅当A➡B是重言式，则称A重言（永真）蕴含B，记作A⇒B
即若A➡B⇔T，则A⇒B

证明A⇒B

假设前件A为真，若在此假设下能推出后件B也为真，则A⇒B成立
假设后件B为假，若在此假设下能推出前件A也为假，则A⇒B成立。

基础重言
在这里插入图片描述

重言蕴含的性质

1、有自反性：对任何命题公式A，有A⇒A。
2、有传递性：若A⇒B且B⇒C，则A⇒C。
3、有反对称性：若A⇒B且B⇒A,则A⇒B
4、若A⇒B且A⇒C，则A⇒B∧C。

析取范式与合取范式

析取范式

定义

命题公式A如果可等价地写成如下形式：A₁∨A₂∨…∨A_n（n≥1）
其中每个项A_i（i=1，2…，n）是命题变元或其他否定形式的合取式，称该公式为A的析取范式。

合取范式

定义

命题公式A如果可等价地写成如下形式：A₁∧A₂∧…∧A_n（n≥1）
其中每个项A_i（i=1，2…，n）是命题变元或其否定形式地析取式，称该公式为A的合取范式

析取范式与合取范式的写法

1、用去掉“➡”和“↔”
2、将“¬”移到命题变元前。
用对偶式
3、用分配律、幂等律等公式进行整理，使之成为所要求的形式。

主析取范式

小项定义

是n个命题变元的合取式，其中每个变元必出现且仅出现一次（以本身或否定形式），称这个合取式为小项
若有n个变元，则由有2ⁿ个小项

含有两个变元的小项只有以下情况
在这里插入图片描述

小项编码

含有n个变元的小项的角标用n位二进制码表示。
变元按字母次序排列
用1表示变元本身，0表示变元的否定形式。

规律：

每个小项当且仅当其赋值与编码相同时，其真值为T；而其余2ⁿ-1组赋值均使该小项的真值为F。
全体小项的析取式为永真式，记为：∑m_i ⇔m₀∨m₁∨…∨m_2^n^-1⇔T

主析取范式定义

若一个命题公式的析取范式为A₁∨A₂∨…∨A_n（n≥1），其中每个A_i（i=1，2，…，n）都是小项，则称之为该命题公式的主析取范式。

主析取范式的求法

1、先写出给定公式的析取范式：A₁∨A₂∨…∨A_n
2、为使每个A_i都变成小项，对缺少变元的项。A_i要补全变元，比如缺变元R，就用“∧（R∨¬R）”的形式补R。
3、用分配律等公式加以整理

在这里插入图片描述

求主析取范式的真值表法

1、列出给定公式的真值表
2、找出该公式真值表中每个为“T”行的赋值所对应的小项
3、用“∨”联结上述小项，即可。

定理

在真值表中，一个使公式的真值为T的赋值所对应的小项的析取，即为此公式的主析取范式。

思考

那永真式的主析取范式呢？所有小项的析取。

主合取范式

大项定义

主合取范式是n个命题变元的析取式，其中每个变元必出现且仅出现一次（以本身或否定形式），称该析取式为大项
有n个变元，则有2ⁿ个大项。

大项的编码

大项的编码正好与小项相反。用0表示变元本身，1表示变元的否定形式。

如何记忆：析取是11出1，合取是00出0，这是两者的唯一出1和0的情况。

在这里插入图片描述

每个大项当且仅当其赋值与编码相同时，其真值为F
其余2^n-1组赋值均使该大项的真值为T。
全体大项的合取式必为永假式。

主合取范式定义

若一个命题公式的合取范式为A₁∧A₂∧…∧A_n（n≥1），其中每个A_i（i=1，2，…，n）都是大项，则称之为命题公式的主合取范式。

求主合取范式的步骤

先写出给定公式的合取范式A₁∧A₂∧…∧A_n。
为了使每个A_i变成大项，对缺少变元的项A_i补全变元，比如缺变元R，用“∨（R∧¬R）”的形式补R
3、用分配率等公式加以整理

主合取范式的真值表求法

1、列出给定公式的真值表
2、找出该公式真值表中的每个为“F”行的赋值所对应的大项。
3、用“∧”联结上述大项，即可。

定理

在真值表中，一个使公式的真值为F的赋值所对应的大项的析取，即为此公式的主合取范式。

在这里插入图片描述

命题逻辑推理

直接推理

推理的过程就是证明永真蕴含式的过程。

令H₁，H₂，…，H_n是已知的命题公式（前提）
若有H₁∧H₂∧…∧H_n⇒C
则称C是H₁，H₂，…，H_n的有效结论，简称结论

两个推理规则

P规则（引入前提规则）：在推理过程中，可以随时引入前提。
T规则（引入结论规则）：在推理过程中，如果前面有一个或几个公式重言蕴含公式S，则可将S纳入推理过程中。

推理方法

直接推理
间接推理
- 条件论证
- 反证法

在这里插入图片描述

推理格式

第一列为步骤号
第二列为给定前提或得出的结论
第三列为注释列，标明是前提还是得到的结论，以及此结论是从哪几步得到的，所用公式得类型。

间接推理

CP规则：
如果要证明的结论是R➡S的形式，则可以把结论中R➡S的前件R作为附加前提，与给定的前提一起推出后件S即可。

在这里插入图片描述

定义：

设H₁，H₂，…，H_n是命题公式，P₁，P₂，…，P_m是公式中的命题变元。如果对P₁，P₂，…，P_m，至少有一组赋值使得H₁∧H₂∧…∧H_n的真值为T，则称公式集合{H₁，H₂，…，H_n}是相容的（也称是一致的）
如果对P₁，P₂，…，P_m的每一组赋值，都使得H₁∧H₂∧…∧H_n的真值为F，则称公式集合{H₁，H₂，…，H_n}是不相容的（也称是不一致的）

反证法：
在这里插入图片描述

谓词逻辑

谓词逻辑的基本概念

谓词的出现

问题提出：

所有的金属都导电，铜是金属，所以铜导电。
设：
A：所有的金属都导电
B：铜是金属
C：铜导电
该推理符号化为：A，B⇒C

这是著名的三段论推理，A是大前提，B是小前提，C是结论。显然，这个推理是有效的，但是这个推理用命题逻辑是无法推证的。

Why

因为命题A、B、C在句子内部是有联系的，而且把命题表示成一个大写字母，就掩盖了这种联系。也就是说一个命题仅用一个大写字母表示的方式太粗了，我们必须加以细化，用另外的表示方式来表达命题。
命题是表达判断的陈述句，将其细分，表达出主语、谓语及宾语（若有的话），而一个句子中“谓语”最重要，这就提出了谓词的概念。