第三讲 谓词逻辑

第七讲

谓词逻辑的性质及前束范式

1.在命题逻辑中成立的基本等价式（详见第三讲）可以推广到谓词逻辑中：

例如：

幂等律在谓词逻辑中表述为：

∃x A（x）∧∃x A（x） ⇔ ∃x A（x）

蕴涵律在谓词逻辑中表述为：

∀x（ A（x）→B） ⇔ ∀x（┓A（x）∨B）

2.量词和否定的交换：

%

┓∀x A（x） ⇔ ∃x ┓A（x）

┓∃x A（x） ⇔ ∀x ┓A（x）

3.量词辖域的扩张和收缩

【这里注意∀x（A（x）→B） 和 ∀xA（x）→B 的区别：

比如A（x）: x遵纪守法 B：社会和谐

∀xA（x）→B 表述为：只要人人遵纪守法，社会就会和谐

∀x（A（x）→B）表述为：对于每一人，只要他遵纪守法，社会就会和谐】

以下是等价公式：

（1）∀x（A（x）∨B）⇔ ∀xA（x）∨B

（2）∀x（A（x）∧B）⇔ ∀xA（x）∧B

@

（3）∃x（A（x）∨B）⇔ ∃xA（x）∨B

（4）∃x（A（x）∧B）⇔ ∃xA（x）∧B

（5）∀x（A（x）→B）⇔ ∃xA（x）→B

该公式看上去难以理解，所以证明如下：

∀x（A（x）→B）⇔∀x（┓A（x）∨B） 蕴涵律

⇔ ∀x┓A（x）∨B

⇔ ┓∃xA（x）∨B 否定的交换

⇔ ∃xA（x）→B 蕴涵律

（6）∀x（B→A（x）） ⇔ B→∀xA（x）

（7）∃x（A（x）→B）⇔ ∀xA（x）→B （证明类似公式（5））

（

（8）∃x（B→A（x）） ⇔ B→∃xA（x）

4.量词和联结词的关系的等值式

∀xA（x）∧∀xB（x） ⇔ ∀x(A（x）∧B（x）)

∃xA（x）∨∃xB（x） ⇔ ∃x(A（x）∨B（x）)

5.量词和联结词的重言蕴含式

∀xA（x）∨∀xB（x）⇒∀x（A（x）∨ B（x））

∃x（A（x）∧ B（x））⇒∃xA（x）∧ ∃x B（x）

第三章 谓词逻辑

习题3.1

1．解 ⑪个体：离散数学；谓词：…是一门计算机基础课程。

⑫个体：田亮；谓词：…是一名优秀的跳水运动员。

⑬个体：大学生；谓词：…要好好学习计算机课程；量词：所有。

⑭个体：推理；谓词：…是能够由计算机来完成的；量词：一切。

2． 解 ⑪设)(xF：x是舞蹈演员；a：小芳。命题符号化：)(aF。

⑫设)(xF：x是一位有名的哲学家；a：苏格拉底。命题符号化：)(aF。

⑬设)(xF：x作完了他的作业家；a：张三。命题符号化：)(aF。

⑭设)(xF：x身体很好；a：我。命题符号化：)(aF。

3．解 ⑪选取个体域为整数集合。设)(xF：x的平方是奇数；)(xG：x是奇数。命题符号化：)()(xGxF。

⑫选取个体域为所有国家的集合。设)(xF：x在南半球；)(xG：x在北半球。命题符号化：)()(xxGxxF。

⑬选取个体域为所有人的集合。设)(xF：x在中国居住；)(xG：x是中国人。命题符号化：))()((xGxFx

⑭选取个体域为所有人的集合。设)(xM：x是艺术家；)(xF：x是导演；)(xG：x是演员。命题符号化：x(M(x)F(x)G(x))。

⑮选取个体域为所有猫的集合。设M(x)：x是好猫；F(x)：x捉耗子。命题符号化：xM(x)x(F(x)M(x))。

4．解 ⑪①设)(xF：x喜欢开汽车；)(xG：x喜欢骑自行车。命题符号化：)()(xxGxxF。

②设)(xF：x喜欢开汽车；)(xG：x喜欢骑自行车；)(xM：x是人。命题符号化：))()(())()((xGxMxxFxMx。

⑫①设)(xF：x必须学好数学。命题符号化：)(xxF。

②设)(xF：x必须学好数学；)(xM：x是学生。命题符号化：))()((xFxMx。

第七讲

谓词逻辑的性质及前束范式

1.在命题逻辑中成立的基本等价式（详见第三讲）可以推广到谓词逻辑中：

例如：

幂等律在谓词逻辑中表述为：

∃x A（x）∧∃x A（x） ⇔ ∃x A（x）

蕴涵律在谓词逻辑中表述为：

∀x（ A（x）→B） ⇔ ∀x（┓A（x）∨B）

2.量词和否定的交换：

┓∀x A（x） ⇔ ∃x ┓A（x）

┓∃x A（x） ⇔ ∀x ┓A（x）

3.量词辖域的扩张和收缩

【这里注意∀x（A（x）→B） 和 ∀xA（x）→B 的区别：

比如A（x）: x遵纪守法 B：社会和谐

∀xA（x）→B 表述为：只要人人遵纪守法，社会就会和谐

∀x（A（x）→B）表述为：对于每一人，只要他遵纪守法，社会就会和谐】

以下是等价公式：

（1）∀x（A（x）∨B）⇔ ∀xA（x）∨B

（2）∀x（A（x）∧B）⇔ ∀xA（x）∧B

（3）∃x（A（x）∨B）⇔ ∃xA（x）∨B

（4）∃x（A（x）∧B）⇔ ∃xA（x）∧B

（5）∀x（A（x）→B）⇔ ∃xA（x）→B

该公式看上去难以理解，所以证明如下：

∀x（A（x）→B）⇔∀x（┓A（x）∨B） 蕴涵律

⇔ ∀x┓A（x）∨B

⇔ ┓∃xA（x）∨B 否定的交换 ⇔ ∃xA（x）→B 蕴涵律

（6）∀x（B→A（x）） ⇔ B→∀xA（x）

（7）∃x（A（x）→B）⇔ ∀xA（x）→B （证明类似公式（5））

（8）∃x（B→A（x）） ⇔ B→∃xA（x）

4.量词和联结词的关系的等值式

∀xA（x）∧∀xB（x） ⇔ ∀x(A（x）∧B（x）)

∃xA（x）∨∃xB（x） ⇔ ∃x(A（x）∨B（x）)

5.量词和联结词的重言蕴含式

∀xA（x）∨∀xB（x）⇒∀x（A（x）∨ B（x））

∃x（A（x）∧ B（x））⇒∃xA（x）∧ ∃x B（x）

后者是不能推出前者的，比如对于第一个公式：

无锡祥业逻辑第三、四讲补充练习题

1 1、某公司员工都具有理财观念，有些购买基金的员工买了股票，凡是购买地方债券的员工都买了国债，但所有购买股票的员工都不买国债。

根据以上前提，以下哪一选项一定是真的？

A、有些购买了地方债券的员工没有买基金

B、有些购买了地方债券的员工买了基金

C、有些购买了基金的员工买了国债

D、有些购买了地方债券的员工买了股票

E、有些购买了基金的员工没有买地方债券

2、甲、乙、丙、丁是同班同学。

甲说：“我班同学考试都及格了。”

乙说：“丁考试没及格。”

丙说：“我班有人考试没及格。”

丁说：“乙考试也没及格。”

已知只有一人说假话，则可推断以下哪项断定是真的？

A．说假话的是乙，丙考试没及格。

B．说假话的是丙，丁考试没及格。

C．说假话的是丁，乙考试及格了。

D．说假话的是甲，丙考试没及格。

E．说假话的是甲，乙考试没及格。

3、经过宣传教育，城市市民的交通安全意识大为增强，交通秩序大为好转。但交通干警依然以高度的责任心维护交通安全，因为他们明白，今天不出交通事故并不具有必然性。

以下哪项与交通干警的想法是一致的？

A、 今天必然要出交通事故。

B、 今天可能要出交通事故。

C、 今天可能不出交通事故。

D、 今天必然不出交通事故。

E、 今天一定会出交通事故。 无锡祥业逻辑第三、四讲补充练习题

2 模态方阵：

4、“小陈不可能去北京旅游。”对这句话，甲、乙、丙三人分别理解为：

甲：小陈去北京旅游是可能的

乙：小陈不去北京旅游是可能的

丙：小陈去北京旅游不具有可能性

对上述这句话的理解，下列那一项是正确的？

A、甲、乙、丙三人都正确

B、甲、乙、丙三人都不正确

C、甲和乙正确，丙不正确