it产品网站建设方案企业邮箱注册申请入口
专栏：离散数学必刷题
本章需要掌握的重要知识：
1.利用谓词表达式表示命题
2.变元的约束
3.谓词公式的定义、谓词公式的赋值
4.谓词公式的翻译（注意在全总个体域时使用特性谓词）
5.有限论域上量词的消去
6.谓词公式中关于量词的等价公式和蕴含式（表2-5.1）
7.前束范式 前束析取范式 前束合取范式
8.谓词推理
8种题型（速通版）：
【1】用谓词表达式写出下面几个命题（都是容易写错的经典例题）：
1、某些大学生运动员是国家选手。
设 S(x) : x 是大学生 。 L(x) : x 是运动员 。C(x) : x 是国家选手。
则有：
2、没有一个国家选手不是健壮的。
设 S(x) ：x 是国家选手。L(x)：x 是健壮的。
则有：
或者
3、所有老的国家选手都是运动员。
设 S(x) : x 是国家选手。P(x) : x 是老的 。 L(x) : x 是运动员。
则有：
4、没有一位女同志既是国家选手又是家庭妇女。
设 S(x) : x 是女同志。 P(x) : x 是国家选手 。Q(x) : x 是家庭妇女。
则有：
5、所有运动员都钦佩某些教练。
设 S(x) : x 是运动员。 P(y) : y 是教练。A(x , y) : x 钦佩 y。
则有：
6、有些大学生不钦佩运动员。
设 S(x) : x 是大学生。P(y) : y 是运动员。A(x , y) : x 钦佩 y。
则有：
【例题】
【2】利用谓词公式翻译下面几个命题：
1、如果有限个数的乘积为零，那么至少有一个因子等于零。
设 N(x) : x 是有限个数的乘积。z(y) : y 等于零 。P(x) : x 的乘积为零。F(y) : y 是乘积中的一个因子。
则有： (∀x)( N(x)∧P(x)→(∃y)( F(y)∧z(y) ) )
2、对于每个实数x，存在一个更大的实数y。
设 R(x)：x 是实数。Q(x,y)：y 大于 x 。
则有： (∀x)( R(x)→(∃y)( Q(x,y)∧R(y) ) )
3、存在实数x，y 和 z ，使得x 与 y之和大于 x 与 z 之积。
R(x): x 是实数 。G(x,y) : x 大于 y 。
则有：(∃x)(∃y)(∃z)( R(x) ∧ R(y) ∧ R(z) ∧ G(x+y , x⋅z) )。
【3】 对下列谓词公式中的约束变元进行换名：
1、(∀x)(∃y)(P(x,z)→Q(y))S(x,y)
则为：(∀u)(∃v)(P(u,z)→Q(v))
2、((∀x)(P(x)→(R(x)∨Q(x)))∧(∃x)R(x))→(∃z)S(x,z)
则为：((∀u)(P(u)→(R(u)∨Q(u)))∧(∃v)R(v))→(∃z)S(x,z)
这里可能有些同学会疑惑了，为什么第2题的 z 变元不换名啊？
首先我们要明确进行约束变元换名的前提：
换名是为了避免出现同一个变量既是约束变元，又是自由变元的情况出现。如果不是这种情况，可以不换。
【4】对下列谓词公式中的自由变元进行代入：
【5】 有限论域消去量词，并对以下公式赋值后求真值：
【6】 请记住以下的谓词公式的等价式和蕴含式：
⚠️注意：全称量词与存在量词在公式中出现的次序，不能随意更换。
如果你想记下这个，可以通过如下图辅助性记忆：
用双向箭头表示等价，单向箭头表示蕴含，见它们之间的关系。
【例题】
【7】 求前束合取范式：
前束合取范式的定义：（注意：可以
，也可以
，所以我们只需要简单得满足合取范式、析取范式的结构就可以了，不用满足主合取范式和主析取范式得结构哦！）
前束析取范式定义：
做题时，可能遇到的三种情况：
- 假设求出的前束合取范式，它的每一个
都唯一，那么可以采用主合取范式和主析取范式的性质：
求出前束合取范式后，根据第一章主合取范式和主析取范式的知识：
在真值表中,一个公式的真值为T的指派所对应的小项的析取,即为此公式的主析取范式。
那剩下的真值为F的指派所对应的大项的合取,即为此公式的主合取范式。
我们可以直接通过前束合取范式求出前束析取范式：
【例题】
- 假设求出的前束合取范式，存在有
例如求：(∀x)(P(x)→Q(x,y))→((∃y)P(y)∧(∃z)Q(y,z)) 它的前束合取范式和前束析取范式
答：先求其前束合取范式
(∀x)(P(x)→Q(x,y))→((∃y)P(y)∧(∃z)Q(y,z))
⇔¬(∀x)(¬P(x)∨Q(x,y))∨((∃y)P(y)∧(∃z)Q(y,z))
⇔(∃x)(P(x)∧¬Q(x,y))∨((∃u)P(u)∧(∃z)Q(y,z))
⇔(∃x)(∃u)(∃z)((P(x)∧¬Q(x,y))∨(P(u)∧Q(y,z)))
我们发现P(x) 和 p(u) ，Q(x,y) 和 Q(y,z)它们的
(∃x)(∃u)(∃z)( (P(x)∨P(u))∧(P(x)∨Q(y,z))∧(¬Q(x,y)∨P(u))∧(¬Q(x,y)∨Q(y,z)))
- ⚠️注意:
当我们求一个wff的前束合取范式或析取范式时，有些可以直接求出了它的真值（T或F），
例如求：(∃x)P(x)∨(∃x)Q(x))→(∃x)(P(x)∨Q(x))的前束合取范式和前束析取范式
则：
((∃x)P(x)∨(∃x)Q(x))→(∃x)(P(x)∨Q(x))
⇔¬((∃x)P(x)∨(∃x)Q(x))∨(∃x)(P(x)∨Q(x))
⇔¬(∃x)(P(x)∨Q(x))∨(∃x)(P(x)∨Q(x))
⇔T
那么 T 既是前束析取范式，也是前束合取范式，这就是最终结果！！！
我们知道：
单个变元既是简单合取式，又是简单析取式。把T看成简单合取式，它就构成了一个析取范式，类似的，把T 看成一个简单析取式，它就构成了一个合取范式。
因此这是一种特殊的范式。
总之，前束合取范式 <= 前束主合取范式；前束析取范式 <= 前束主析取范式，
【8】谓词演算的推理理论：
法一：直接证法
法二：间接证法
- CP规则
- 矛盾规则
结尾
这8种题型，轻轻松松拿下！！！
