【离散数学必刷题】谓词逻辑（第二章 & 左孝凌版）刷完包过！

专栏：离散数学必刷题

本章需要掌握的重要知识：

1.利用谓词表达式表示命题

2.变元的约束

3.谓词公式的定义、谓词公式的赋值

4.谓词公式的翻译（注意在全总个体域时使用特性谓词）

5.有限论域上量词的消去

6.谓词公式中关于量词的等价公式和蕴含式（表2-5.1）

7.前束范式 前束析取范式 前束合取范式

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(x) : x 是教练。A(x , y) : x 钦佩 y。

则有：

6、有些大学生不钦佩运动员。

设 S(x) : x 是大学生。P(x) : x 是运动员。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))  S(x,y)

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】谓词演算的推理理论：

法一：直接证法

法二：间接证法

 【9】符号化下列命题并推证其结论：

这9种题型，轻轻松松拿下！！！