(完整word版)第二章 谓词逻辑

第二章谓词逻辑

1.什么叫做客体和客体变元？如何表示客体和客体变元？

2.么叫做谓词？

3.什么叫做论域?我们定义一个“最大”的论域叫做什么?

4.填空题：

1．存在量词：记作（），表示( ）或者（）或者（ )。

2．全称量词:记作（ ),表示( ）或者（）或者( )。

5。什么叫做量词的作用域？指出下面两个谓词公式中各个量词的作用域。

”x(F（x，y)→$yP(y)）∧Q(z）∧＄xA（x）

”x$y”z(A（x，y)→B(x,y,z))∧C(t)

6。什么叫做约束变元？什么叫做自由变元？指出下面公式中哪些客体变元是约束变元？哪些客体变元是自由变元?

”x(F(x,y）→＄yP(y）)∧Q(z）∧$xA（x)

7.填空：一个谓词公式如果无自由变元，它就表示一个（ )。

8.给出的谓词 J（x)：x是教练员， L（x） :x是运动员, S（x) ：x是大学生，O(x) ：x是年老的，V(x） :x是健壮的,C(x）：x是国家选手，W（x) ：x是女同志, H（x）：x是家庭妇女,A （x，y）：x钦佩y。客体 j：金某人.用上面给出的符号将下面命题符号化。

1．所有教练员是运动员。

2．某些运动员是大学生.

3．某些教练是年老的，但是健壮的.

4．金教练既不老，但也不是健壮的。

5．不是所有运动员都是教练。

6．某些大学生运动员是国家选手。

7．没有一个国家选手不是健壮的。

8．所有老的国家选手都是运动员。

9．没有一位女同志既是国家选手又是家庭妇女。

10．有些女同志既是教练又是国家选手。

11．所有运动员都钦佩某些教练。

12．有些大学生不钦佩运动员.

9。将下面命题符号化

1．金子闪光,但闪光的不一定都是金子.

2．没有大学生不懂外语.

3．有些液体可以溶解所有固体.

4．每个大学生都爱好一些文体活动。

5．每个自然数都有唯一的后继数。

10.令P表示天气好.Q表示考试准时进行。A（x)表示x是考生.B(x)表示x提前进入考场。C（x）表示x取得良好成绩.E(x，y）表示x=y.利用上述符号，分别写出下面各个命题的符号表达式。1．如果天气不好,则有些考生不能提前进入考场。

2．只有所有考生提前进入考场，考试才能准时进行。

3．并非所有提前进入考场的考生都取得良好成绩。

4．有且只有一个提前进入考场的考生未能取得良好成绩。

11.将下面命题符号化。

1．对一个大学生来说，仅当他刻苦学习，才能取得优异成绩。

(S（x）：x是大学生；Q（x)：x取得了优异成绩；H(x）:x刻苦学习。) 2．每个不等于0的自然数,都有唯一的前驱数。

(Z（x）:x是自然数； E(x,y)：x=y； Q(x，y）:y是x的前驱数。）

12.是偏序集，B是A的非空子集.在括号内分别写入y是B的极小元、最小元、下界相应的谓词表达式.

y是B的极小元Û（）

y是B的最小元Û（）

y是B的下界Û( )

13.设论域D={1,2｝又已知a=1 b=2 f（1）=2 f（2）=1

P（1，1)=T P(1,2）=T P（2 ,1）=F P（2，2)=F

求谓词公式”x$y(P（x,y)®P（f（x),f(y)))的真值。（要求有解题的过程)

14设论域为{2，3｝，Ａ（x,y)表示 x+y=xy。求谓词公式Ø”x$yA(x,y)的真值。（要求有解题的过程。）

15。设谓词P(x,y）表示x是y的因子,论域是{1，2,3}。求谓词公式”x＄yØA（x，y）的真值。(要

求有解题过程)

16。令论域D=｛a,b}，P（a,a)：F， Pa，b）：T， P(b，a)：T， P(b,b）：F。公式( )的真值为真。A：”x$yP（x，y） B：$x”yP（x，y) C：”x”yP（x，y) D:Ø$x$yP（x,y)

17.令论域D={a,b}，P（a，a)：F，P（a，b)：T,P（b,a):T,P（b，b）：F，公式( )的真值为真。

a：Ø＄x＄yP(x,y) b:$x”yP（x,y） c：”x"yP（x，y) d："x＄yP(x，y)

18。令Lx,y）表示x

a：自然数集合 b：整数集合 c：有理数集合 d：实数集合

19.设论域为{1,2，3｝，已知谓词公式 $xP（x,3) ®（”yØP（3，y) ®$zP（1，z）) 的真值为假，则x=2时,使P(x，3）为真。此说法是否正确？针对你的答案说明原因。

20。什么叫做对谓词公式赋值？

21。什么叫做谓词公式的永真式？

22。什么叫做谓词公式A与B等价？

23。什么叫做谓词公式A永真蕴含B?

24。设Ｂ是个不含客体变元x的谓词公式，在下面的等价公式中，哪些是不正确？说明不正确的原因。

1。”xA(x)∨BÛ”x(A(x）∨B）

2. ”xA（x）∧BÛ"x(A(x）∧B)

3。 B→”xA（x)Û"x（B→A(x))

4. "xA(x）→BÛ”x（A(x）→B)

25.证明下面等价公式 $x(A（x）→B(x)）Û”xA（x）→$xB(x)

26。证明下面等价公式 $xA(x)→"xB（x）Þ"x(A(x)→B（x）)

27.下面谓词公式等价成立吗？对你的回答给予证明或者举反例。

$xA（x）∧＄xB（x) Û＄x（A(x)∧B(x））

28.下面谓词公式等价成立吗？对你的回答给予证明或者举反例。

”x(A（x)∨B(x））Û”xA(x)∨"xB(x)

29。下面永真蕴涵式成立吗？对你的回答给予证明或者举反例.

＄xA（x）∧＄xB（x) Þ$x（A（x）∧B(x）)

30。下面永真蕴涵式成立吗？对你的回答给予证明或者举反例。

"x(A(x)∨B（x）) Þ”xA（x)∨"xB(x）

31.什么叫做谓词公式的前束范式？

32.不是谓词公式”x(A（x,y)®＄yB（x,y)）的前束范式的为（）

a: "x$y（A（x，t）® B(x，y）) b: ”x$t(A(x,y)® B（x，t))

c：”x$y（A(x，y)® B（x，y）） d：”t$y（A(t，x)® B(t，y))

33.写出谓词公式 "x（P(x）∧R（x）)→(Ø$xP(x）∧Q（x)）的前束范式.

34。分别指出推理规则US、ES、的名称、形式、作用以及使用这些规则时的注意事项。

35.举例说明在谓词推理时,使用ES时所指定的客体c不应该是在此之前用US规则所指

定的客体c (即本次用ES特指客体c，不应该是以前特指的客体)。并分析发生的错误.

36.举例说明在谓词推理时，使用ES时所指定的客体c不应该是在此之前用ES规则所

指定的客体c (即本次用ES特指客体c,不应该是以前特指的客体）。并分析发生的错误.

37。分别指出推理规则EG、UG的名称、形式、作用以及使用这些规则时的注意事项。

38.用谓词逻辑推理的方法证明下面推理的有效性。（要求按照推理的格式书写推理过程.)

"xC(x）， $x（A（x）ÚB（x)), "x（B(x）®ØC（x）) Þ＄xA（x）

39。用谓词逻辑推理的方法证明下面推理的有效性。(要求按照推理的格式书写推理过程。）“不认识错误的人，也不能改正错误.有些诚实的人改正了错误。所以有些诚实的人是认

识了错误的人。”

设A（x）:x是认识错误的人. B（x）:x改正了错误.C（x)：x是诚实的人。命题符号化为:”x(ØA（x)→ØB（x）),＄x(C（x）∧B（x）), Þ＄x（C(x）∧A（x)）

40。用谓词逻辑推理证明下面推理的有效性.（要求按照推理格式书写推理过程。)

"x(A（x)®(ØB（x）ÚØC（x）))，”x（A(x）®（ØC(x）®D（x））)， $x(A（x)ÙØD（x））Þ $x（A(x）ÙØB(x）)

41。用谓词逻辑推理证明下面推理的有效性.

$x(A（x）Ù(B（x）®ØC(x)）)， "x(A（x)®（C（x)ÚØD（x))), ”x（A（x)®D（x））

Þ $x(A（x)ÙØ B（x))

42。用谓词逻辑推理证明下面推理的有效性。（要求按照推理格式书写推理过程。）“鸟都会飞。猴子都不会飞.所以，猴子都不是鸟。”

43。用谓词逻辑推理证明下面推理的有效性。（要求按照推理格式书写推理过程。)“一些病人喜欢所有医生。任何病人都不喜欢庸医。所以没有医生是庸医。”

44. 给定谓词如下：S(x）：x是学生；L（x)：x是校领导; G(x)：x是好的;T（x)：x是老师；P(x）：x受过处分； C(x,y）:y表扬x。用上述谓词表达下面各个命题，并且用谓词逻辑推理方法证明下面推理的有效性。

“没有受过处分的学生，都受到过校领导的表扬；有些好学生,仅仅受到老师的表扬；所有好学生，都没有受过处分.所以，有的老师是校领导.”

45.用谓词逻辑推理证明下面推理的有效性。(要求按照推理格式书写推理过程。）

“任何人如果他喜欢步行,他就不喜欢乘汽车；每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因此有的人不爱步行.”

46。给定谓词 M（x):x是高山俱乐部成员。H（x):x是滑雪者. D（x)：x是登山者。

L（x,y):x喜欢y。客体：a:小杨；b:小刘；c:小林；d：雨；e：雪.用谓词逻辑推理证明方法，

解决下面问题。（要求按照推理格式书写推理过程。）

“小杨、小刘和小林为高山俱乐部成员，该俱乐部的每个成员是个滑雪者或登山者。没有一个登山者喜欢雨。而所有滑雪者都喜欢雪。凡是小杨喜欢的，小刘就不喜欢。小杨喜欢雨和雪。试证明该俱乐部是否有个是登山者而不是滑雪者的成员.如果有，他是谁?"

47.用谓词逻辑推理证明下面推理的有效性.（要求按照谓词逻辑推理格式，书写推理过程。)

$x（ØP（x）® Q（x））, ”x（ØQ（x)ÚØR(x）)， "xR（x) Þ＄xP（x)

48。用谓词逻辑推理证明下面推理的有效性。

（要求按照谓词逻辑推理格式，书写推理过程.）

”x(P(x)®(Q（x)ÙR（x))), Ø"x(R(x)®Q(x））Þ＄x（R(x）ÙØP(x)）

49。用谓词逻辑推理证明下面推理的有效性。

（要求:按照教材中推理的格式写出推理过程）

"x(ØC(x)Ú(ØA（x)ÚØB(x））), ”x(A(x）®(ØC(x）®D(x))）, Ø"x(ØA(x）ÚD(x））

Þ＄x(A(x)ÙØB(x)）

50。用谓词逻辑推理证明下面推理的有效性.

(要求：按照逻辑推理格式书写推理过程)

"x(＄y（S（x,y) ÙM（y)) ®＄z((P(z)ÙR(x,z))) ÞØ$zP（z）®"x”y (S(x，y) ®ØM（y))

51。设：Ｎ（x）表示x是自然数；Ｏ（x)表示x是奇数；Ｅ(x）表示x是偶数；Ｃ（x)表示x能被２整除.用上面给定的谓词表示下面各个命题，然后用谓词逻辑推理方法证明下面推理的有效性.（注：要按照教材中推理的书写格式描述推理过程）

“每个自然数不是奇数就是偶数；所有奇数都不能被２整除;有些自然数能被２整除；因此，有些自然数是偶数。"

52。用谓词逻辑推理方法证明下面推理的有效性。（注：要按照教材中推理的书写格式描述推理过程）

$x（A(x）ÙØ"y(ØB(y）ÚØC(x，y）))， "x（A(x）®"y（D(y ）®ØC(x，y）））Þ$y （B(y)ÙØD（y）)

53。用谓词逻辑推理证明下面推理的有效性。(要求按照教材格式写出推理过程）

”x(A（x)®$y（B（y）®ØC（x，y)））, ”x(A（x)®"y(C(x，y）ÚD(y）)）, $xA（x）Ù"yØD(y） ＄yØB（y）

54. 给定谓词如下：A（x）:x是书刊；B(x）：x是合法出版的;C（x)：x是人；D(x)：x感到忧虑。先用这些谓词将下面各个命题符号化,再用谓词逻辑推理方法证明这个推理是正确的。

“如果有些书刊是非法出版的,则所有人都感到忧虑。一些人不感到忧虑.因此，所有书刊都是合法出版的."

55。用谓词逻辑推理证明下面推理的有效性。(按照教材格式写出推理过程)

$xA(x），＄x(B(x）ÙØC(x)), ”z((A（z）Ù"x＄yD(x,y））®”y（B（y)®C（y）)）, Þ"y$xØD （x，y）

56。给定谓词：N(x):x是自然数，E(x）:x是偶数，O（x):x是奇数，D（x,y):x可被y整除.用上述谓词表达下面各命题，并用谓词逻辑推理方法证明其推理的有效性。

“每个自然数不是偶数,就是奇数。自然数为偶数,当且仅当它能被2整除.并不是所有自然数都可以被2整除。所以,有的自然数是奇数。"

57.用谓词推理证明下面推理的有效性.(注：要按照教材中推理的书写格式描述推理过程)

$x(A（x)Ù＄y（B(y）ÙC（x,y）))，”x(A（x)®”y（D(y）®ØC（x,y)））ÞØ”y（B（y)®D （y))

58.分析下面推理过程是否正确。如果有错误，请指出错误所在之处。并写出正确的推理过程。"x(A(x)→B（x）)， $xA（x）Þ $xB(x)

⑴”x（A（x)→B（x)) P

⑵ A（c）→B（c） US ⑴

⑶ $xA（x) P

⑷ A(c） ES ⑶

⑸ B（c) T ⑵⑷ I11

⑹＄xB（x） EG ⑸

59.用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。

$xP（x）， "x(Q（x)®Ø R(x)）, ”x（ØP（x）Ú R（x))Þ $xØ Q（x)

1.答案：定义：能够独立存在的事物，称之为客体，也称之为个体.它可以是具体的，也可以是抽象的事物。通常用小写英文字母a、b、c、。。。表示。

定义：用小写英文字母x、y、z。..表示任何客体,则称这些字母为客体变元。

2。答案:定义:一个大写英文字母后边有括号，括号内是若干个客体变元，用以表示客体的属性或者客体之间的关系，称之为谓词。如果括号内有n个客体变元，称该谓词为n元谓词。

3。答案：定义：在命题函数中客体变元的取值范围，称之为论域，也称之为个体域。

论域是一个集合。

定义：由所有客体构成的论域,称之为全总个体域。它是个“最大”的论域。

4.答案：1．存在量词：记作（$ ），表示 ( 有些 ) 或者( 一些 )或者（至少一个）。

2．全称量词:记作（" ），表示（每个）或者（任何一个 )或者（所有的）。

5.答案：在谓词公式中,量词的作用范围称之为量词的作用域，也叫量词的辖域.

在"x(F（x，y)→$yP（y)）∧Q(z）∧＄xA(x）中：

”x的作用域：（F(x，y)→＄yP(y））

$y的作用域：P（y)

$x的作用域：A（x）

在”x$y"z（A(x,y)→B（x,y，z））∧C（t)中：

”x的作用域：$y”z(A（x,y）→B(x，y,z）)

$y的作用域："z(A(x,y)→B（x,y,z))

"z的作用域：(A(x,y）→B(x,y,z）)

6.答案：定义：如果客体变元x在"x或者＄x的辖域内，则x在此辖域内约束出现,并称x在此辖域内是约束变元。否则x是自由出现，并称x是自由变元.

在"x(F(x，y）→$yP（y))∧Q(z)∧$xA（x)中

F(x，y）中的x和P（y)中的y以及A(x)中x是约束变元.

而F（x,y）中的y和Q（z）中的z是自由变元。

7。答案：（命题)

8. 答案：

1．"x（J(x）→L（x))

2．$x（L（x）∧S（x))

3．$x(J（x)∧O（x)∧V(x））

4．J（j)∧ØO(j)∧ØV（j）

5．Ø"x（L（x)→J(x））或者 $x（L（x）∧ØJ（x)）

6．$x(S（x）∧L（x）∧C(x）)

7．$Øx（C(x)∧ØV(x)) 或者”x（C(x)→V(x））

8．”x（（O(x）∧C(x)）→L（x))

9．Ø＄x(W(x)∧C(x)∧H（x))

10．＄x(W(x）∧J（x)∧C(x）)

11．"x(L(x）→＄y（J(y）∧A(x，y）））

12．＄x（S（x）∧”y（L（y)→ØA(x，y)))

9.答案：

1．设：G(x）：x是金子。 F(x）：x闪光。则命题的表达式为

”x(G（x）®F（x)）ÙØ"x（F（x）®G（x)）或者

"x（G（x)®F(x）) Ù＄x(F(x）ÙØG（x））

2．设 S（x)：x是大学生。F（x）:x是外语。K(x，y）：x懂得y.则命题的表达式为

Ø＄x(S（x)Ù"y（F(y）®ØK(x,y）)）或者

”x(S(x）®$y（F(y)ÙK（x，y)））

3．设F（x)：x是液体。.S（x）:x是固体。D（x，y)：x可溶解y。则命题的表达式为

$x（F(x)Ù”y（S（y）®D(x，y)))

4．设S（x)：x是大学生.L(x，y)：x爱好y。C（x)：x是文娱活动。P（x）：x是体育活动。则命题的表达式为：

"x（S（x) ®$y(（C（y)∨P（y））ÙL（x,y)））

5．设令N(x）：x是自然数。A(x,y）：y是x的后继数。 E(x,y)：x=y 则命题的表达式为

”x(N(x）→＄y(N（y）∧A(x,y）∧”z(（N（z）∧A(x，z）)→E(y，z)）））

10。答案:

1．ØP®$xA(x)ÙØB（x）

2．Q®”x(A(x)® D(x)）

3．Ø"x((A(x) Ù(B(x））® C（x)）

4．＄xA(x)ÙB（y）ÙØC(x）Ù”y(（A（y) ÙB(y）ÙC（y）)® E（x，y））)

11.答案：

1．”x(S(x）→（Q（x）→H（x）)）

2．”x（（Z(x)∧ØE（x，0))→＄y(Z（y）∧Q(x，y）∧”z((Z（z)∧Q（x,z）)→E(y，z)))）

12。答案：

y是B的极小元Û（ $y(y∈B∧Ø$x(x∈B∧x≠y∧x≤y））)

y是B的最小元Û( $y(y∈B∧”x（x∈B→y≤x）） )

y是B的下界Û（＄y（y∈A∧”x(x∈B→y≤x)))

13.答案：解：”x＄y（P（x,y）®P（f（x),f(y)))

Û$y（P（1,y) ®P（f(1）,f（y）））Ù＄y（P(2，y) ®P(f（2),f（y））)

Û（(P(1,1）®P(f(1)，f(1）)）Ú (P(1,2) ®P（f(1），f(2）))）Ù P（2，1）®P（f（2），f(1)）)Ú（P（2，2) ®P(f（2),f(2))）)

Û（(P（1,1）®P（2，2））Ú（P(1,2）®P(2，1））)Ù（（P（2,1）®P(1，2）)Ú（P（2，2) ®P（1,1))）

Û（（T®F )Ú (T®F））Ù（(F®T）Ú（F®T)）

Û（FÚ F)Ù（T Ú T)

ÛFÙT ÛF

14.答案：解: Ø”x$yA（x,y）Û＄x”yØA(x,y)

Û”yØA(2,y）Ú”yØA（3，y）

Û（ØA（2，2）ÙØA（2,3））Ú（ØA（3，2) ÙØA(3，3） )

Û（FÙ T) Ú (TÙ T）

ÛFÚ TÛT

15。答案：解： "x$yØA（x，y)

Û$yØA（1,y）Ù $yØA（2,y）Ù$yØA(3，y）

Û(ØA(1,1）ÚØA（1，2) ÚØA(1，3))Ù（ØA（2，1) ÚØA（2，2) ÚØA（2,3）) Ù (ØA（3，1) ÚØA（3，2）ÚØA（3，3）)

Û（F ÚF) ÚF)Ù (T ÚF）ÚT) Ù（T ÚT ÚT））

ÛF

16.答案:A

17。答案:令论域D={a，b}，P（a,a）:F,P（a,b)：T，P(b,a):T，P(b,b）：F，公式(d )的真值为真。

a:Ø$x＄yP(x,y） b：＄x"yP(x,y） c："x”yP(x,y) d: "x＄yP(x,y）

因为a: Ø＄x$yP（x，y)ÛØ（＄yP（a,y）Ú$yP（b,y))ÛØ(P(a，a)ÚP（a,b）)Ú（P（b，a）ÚP(b,b))

ÛØ(（FÚT)Ú(TÚF））ÛF

b:$x"yP(x，y）Û”yP(a,y）Ú”yP(b，y)Û（P(a，a)ÙP(a,b）)Ú(P（b,a)ÙP(b，b))

Û (FÙT) Ú (TÙF) ÛF

c：”x”yP(x,y）Û”yP（a，y) Ù"yP(b，y）Û(P（a,a)ÙP(a,b))Ù（P(b，a）ÙP(b,b)）

Û（FÙT)Ù（TÙF) ÛF

d："x$yP（x，y)Û$yP（a,y）Ù$yP(b,y）Û(P（a,a)ÚP（a，b））Ù（P(b,a）ÚP（b,b））

Û（FÚT)Ù（TÚF）ÛT

18。答案：a

19.答案：解：此说法正确。

因为$xP（x，3)®（"yØP(3，y)®$zP（1,z)) 的真值为假,所以＄xP(x，3）的真值为真，”yØP （3，y) 的真值为真，＄zP(1，z)）的真值为假。

由$xP（x,3) 的真值为真，得P（1，3）为真,或者P(2,3)为真，或者P(3，3)为真。

由”yØP（3，y）的真值为真,得P(3，1）、P（3，2)、P(3，3)均为假.

由$zP（1,z）) 的真值为假，得P(1,1)、P（1,2）、P（1，3）均为假。

综合上述情况得, P（2,3）为真，

20。答案：若将给定的谓词公式中的命题变元，用确定的命题代替，对公式中的客体变元用

论域中的客体代替，这个过程就称之为对谓词公式作指派，或称之为对谓词公式赋值.

21。答案：给定谓词公式A，E是其论域，如果不论对公式A作任何赋值，都使得A的真值为真，则称公式A在论域E上是永真式。如果不论对什么论域E，都使得公式A为永真式,则称A为永真式。

22。答案：给定谓词公式A、B，E是它们的论域,如果不论对公式A、B作任何赋值，都使得A与B 的真值相同(或者说A«B是永真式），则称公式A与B在论域E上是等价的。如果不论对什么论域E,都使得公式A与B等价，则称A与B等价,记作AÛB.

23。答案：给定谓词公式A、B，E是它们的论域，如果不论对公式A、B作任何赋值,使得

A→B为永真式,则称在论域E上公式A永真蕴含B。如果不论对什么论域E,都使得公式A→B为永真式，则称A永真蕴含B，记作AÞB。

24.答案：解:4式不正确。因为

"xA（x)→BÛØ”xA（x）∨BÛ＄xØA（x)∨BÛ$x(ØA（x）∨B）Û＄x(A（x)→B)

所以”xA（x）→B不等价于 "x(A(x)→B），即4式不成立.

25。答案：证明 "xA(x）→$xB(x)

ÛØ”xA（x）∨＄xB(x）

Û$xØA（x）∨＄xB（x）

Û$x（ØA(x）∨B（x）)

Û＄x（A(x）→B(x））

26。答案:证明＄xA(x）→"xB(x）

ÛØ＄xA（x）∨”xB（x）

Û"xØA（x)∨”xB（x)

Þ"x（ØA（x)∨B（x)）

Û”x(A(x)→B（x)）

27.答案:不成立。

因为根据量词分配公式知道，只有公式 $x(A(x)∧B(x)) Þ $xA（x)∧$xB（x）成立。

而没有＄xA(x）∧＄xB(x) Þ＄x(A(x）∧B(x）)。可以举如下反例说明：

令A(x）表示x是男生， B（x)表示x是女生。则 $xA（x）∧＄xB(x)表示“有些人是男生也有些人是女生"，这显然是真的命题。而$x（A（x）∧B(x））表示“有这样的人,他既是男生也是女生。”，这显然是假命题。所以＄xA(x)∧＄xB(x)Þ$ x(A（x）∧B(x）) 不成立。

所以没有等价公式 $xA(x）∧＄xB（x) Û $x（A（x)∧B（x）) 成立。

28。答案：不成立。

因为根据量词分配公式知道，只有公式”xA（x)∨"xB（x) Þ”x（A(x)∨B(x））成立。

而没有"x(A（x)∨B（x））Þ"xA（x)∨"xB(x).可以举如下反例说明:

令A（x）表示x是男生， B(x)表示x是女生。则 "x（A（x）∨B（x)）表示“任何一个人来说，他或者是男生或者是女生。”，这显然是真的命题。而”xA（x)∨”xB(x）表示“要么大家都是男生,要么大家都是女生.”,显然由”x（A（x）∨B（x）)不能推出”xA(x）∨”xB(x).

所以”x（A（x)∨B(x）) Þ "xA(x）∨"xB(x) 不成立。

所以没有等价公式 "x（A(x）∨B（x)) Û"xA(x)∨"xB(x）成立。

29.答案：不成立。可以举如下反例说明：

令A(x）表示x是男生， B(x）表示x是女生.则

前件$xA(x)∧$xB（x)表示“有些人是男生也有些人是女生”，这显然是真的命题。而后件$x（A （x)∧B（x)）表示“有这样的人，他既是男生也是女生。”这显然是假命题。

所以＄xA（x）∧$xB(x)Þ＄ x(A(x)∧B(x））不成立.

30。答案：不成立。可以举如下反例说明：

令A(x）表示x是男生， B（x）表示x是女生。

则前件”x(A(x）∨B(x））表示“任何一个人来说，他或者是男生或者是女生。”这显然是真的命题.而后件”xA（x）∨"xB（x）表示“要么大家都是男生,要么大家都是女生。”

显然由"x（A(x）∨B(x））不能推出”xA（x)∨”xB（x）。

所以"x（A(x）∨B（x)) Þ ”xA(x)∨"xB(x) 不成立.

31。答案：前束范式定义：一个谓词公式符合下面条件，就是前束范式：

所有量词前面都没有联接词；

所有量词都在公式的左面；

所有量词的辖域都延伸到公式的末尾。

32。答案：c

33。答案：解

”x（P(x)∧R（x））→（Ø＄xP（x)∧Q（x)）

ÛØ”x（P（x）∧R（x）)∨（Ø＄xP(x）∧Q(x）) （去→）

Û＄xØ(P（x)∧R（x))∨(”xØP（x)∧Q（x）) （量词转换）

Û＄x（ØP(x）∨ØR(x）)∨(”xØP（x)∧Q（x）） (后移Ø）

Û$x(ØP（x)∨ØR(x)）∨（”yØP(y）∧Q(z)) （换变元)

Û＄x（ØP（x)∨ØR（x））∨”y(ØP(y）∧Q(z)） (扩量词辖域）

Û$x"y(（ØP（x)∨ØR（x）)∨（ØP(y)∧Q(z)）） (扩量词辖域)

34.答案：US：全称特指规则（Universal Specialization)

形式： "xA（x）ÞA（c） (其中c是论域内指定客体）

作用：去掉全称量词。

注意事项：c不是A(x)中的符号。

ES：存在特指规则（Existential Specialization)

形式：＄xA(x）ÞA(c）（其中c是论域内指定客体)

作用:去掉存在量词。

注意事项：

⑴ c不是A（x)中的符号。

⑵用ES指定的客体c不应该是在此之前用US规则或者用ES规则所指定的客体c （即本次用ES

特指客体c,不应该是以前特指的客体)。

35。答案：例：令A（x）表示x是自然数，B(x）表示x是整数。

⑴”x(A（x)→B(x）) P

⑵ A(c）→B（c） US 如c=0.1

⑶＄xA（x） P

⑷ A（c）× ES A(0。1)为F

得出0.1是自然数的错误结论。

36.答案：例：令A(x)表示x是自然数,B（x）表示x是整数。

⑴ $xB(x) P

⑵ B（c） ES 如c＝－1

⑶＄xA(x） P

⑷ A(c) × ES A（－1）为F

得出－1是自然数的错误结论.

37.答案：EG：存在推广规则 (Existential Generalization)

形式： A(c)＄ÞxA（x）（其中c是论域内指定客体)

作用:添加存在量词。

注意事项：x不是A（c)中的符号。

UG:全称推广规则 (Universal Generalization）

形式： A（c)Þ”xA（x) （其中c是论域内任何指定客体)

作用：添加全称量词。

注意事项：x不是A（c）中的符号.

c一定是任意的客体,否则不可全称推广。

38。答案:⑴＄x（A(x）ÚB（x）), P

⑵ A(a)ÚB(a） ES ⑴

⑶ "xC(x) P

⑷ C(a) US ⑶

⑸ "x（B(x)→ØC（x）） P

⑹ B（a)→ØC（a) US ⑸

⑺ØB（a) T ⑷⑹ I12

⑻ A(a) T ⑵⑺ I10

⑼ $xA（x）） EG ⑻

39.答案：⑴＄x（C(x)∧B（x）） P

⑵ C(c）∧B(c） ES ⑴

⑶ C(c) T ⑵I1

⑷ B（c) T ⑵I2

⑸”x（ØA（x）→ØB(x）) P

⑹ØA（c）→ØB(c) US ⑸

⑺ØØA(c) T ⑷⑹ I12

⑻ A(c) T ⑺ E1

⑼ C（c）∧A（c) T ⑶⑻ I9

⑽＄x(C（x）∧A(x）) EG ⑼

40。答案：证明。

⑴ $x（A(x)ÙØD(x）) P

⑵ A(a)ÙØD(a） ES ⑴

⑶ A(a) T ⑵ I

⑷ØD（a) T ⑵ I

⑸”x(A(x）®（ØC（x)®D（x))） P

⑹ A（a）®（ØC(a）®D（a）) US ⑸

⑺ØC(a)®D（a)) T ⑶⑹ I

⑻ C（a） T ⑷⑺ I

⑼ "x（A（x)®（ØB(x）ÚØC（x））） P

⑽ A（a）®(ØB(a)ÚØC(a）) US ⑼

⑾ØB（a)ÚØC（a） T ⑶⑽ I

⑿ØB（a) T ⑻⑾ I

⒀ A（a)ÙØB(a) T ⑶⑿ I

⒁＄x（A(x）ÙØB(x）） EG ⒀

41。答案：证明。

⑴ $x(A（x）Ù(B(x)®ØC（x））)， P

⑵ A（a）Ù（B（a)®ØC(a）） ES ⑴

⑶ A(a） T ⑵ I

⑷ (B（a）®ØC(a）） T ⑵ I

⑸ "x(A(x)®（C（x）ÚØD(x))） P

⑹ A(a）®（C（a)ÚØD（a)） US ⑸

⑺ (C（a)ÚØD(a）） T ⑶⑹ I

⑻ "x（A(x）®D(x）） P

⑼ A(a）®D（a）） US ⑻

⑽ D(a) T ⑶⑼ I

⑾ C(a) T ⑺⑽ I

⑿ØB（a) T ⑷⑾ I

⒀ A(a)ÙØB（a) T ⑶⑿ I

⒁＄x（A（x）ÙØB（x）） EG ⒀

42.答案：证明.

设 B（x）:x是鸟;F（x):x会飞;M（x）:x是猴子。命题符号化为:

"x(B(x）→F（x）), "x（M(x）→ØF（x））Þ "x(M（x）→ØB（x）)

⑴ "x（B（x)→F（x）) P

⑵ B(a)→F（a) US ⑴

⑶ "x（M(x）→ØF(x)) P

⑷ M（a）→ØF(a） US ⑶

⑸ØF（a）→ØB(a） T ⑵ E18

⑹ M(a）→ØB(a） T ⑷⑸ I13

⑺”x（M（x)→ØB(x)） UG ⑹

43.答案:证明.

设： P（x)：x是病人, D(x）:x是医生， Q(x)：x是庸医, L（x,y）: x喜欢y. 命题符号化：

＄x（P（x)∧”y（D(y）→L(x，y））), "x(P(x）→"y（Q(y)→ØL（x，y)））

ÞØ$y(D(y）∧Q(y))

⑴＄x（P(x）∧”y（D（y）→L(x，y)）） P

⑵ P（a)∧”y(D（y)→L（a,y)) ES ⑴

⑶ P(a) T ⑵ I1

⑷ "y(D(y)→L（a，y)） T ⑵ I2

⑸ "x（P（x）→”y(Q(y)→ØL(x,y）)） P

⑹ P（a）→"y(Q（y)→ØL(a,y）) US ⑸

⑺ "y（Q（y)→ØL（a，y)） T ⑶⑹ I11

⑻ D(b）→L（a,b) US ⑷

⑼ Q(b）→ØL(a,b) US ⑺

⑽ L(a,b）→ØQ（b) T ⑼ E18

⑾ D(b)→ØQ（b) T ⑻⑽ I13

⑿ØD(b)∨ØQ（b） T ⑾ E16

⒀Ø（D（b）∧Q(b)） T ⑿ E8

⒁”yØ（D（y）∧Q（y)) UG ⒀

⒂ $Øy（D(y）∧Q（y)） T ⒁ E25

44.答案：证明. 上述各个命题符号化为：

"x(（S(x) ÙØP(x)) ®＄y(L（y）ÙC(x，y))）, $x((S（x)ÙG(x))Ù”y（C(x，y）®T （y））） ,

”x((S（x) ÙG（x）) ®ØP（x）) Þ$y(T（y）ÙL（y））

⑴＄x((S(x）ÙG(x）)Ù”y（C（x,y）®T(y))) P

⑵（S（a）ÙG(a)）Ù”y(C（a,y）®T(y）) ES ⑴

⑶ S(a)ÙG（a) T ⑵ I1

⑷ "x(（S(x）ÙG（x））®ØP(x)） P

⑸（S（a）ÙG（a））®ØP(a) US ⑷

⑹ØP（a) T ⑶⑸ I11

⑺ S（a） T ⑶ I1

⑻ S(a）ÙØP(a） T ⑹⑺I9

⑼”x(（S（x）ÙØP（x））®＄y（L（y)ÙC（x，y)）） P

⑽ (S（a）ÙØP（a）) ®$y(L(y)ÙC(a，y)) US ⑼

⑾＄y(L（y)ÙC（a,y）） T ⑵ I2

⒀ L（b）ÙC（a，b） ES ⑾

⒁ C（a，b）®T（b） US ⑿

⒂ L(b） T ⒀ I1

⒃ C(a，b） T ⒀ I2

⒄ T(b） T⒁⒃ I11

⒅ T（b)ÙL(b） T ⒂⒄I9

⒆＄y（T（y）ÙL（y)） EG ⒅

45.答案：证明。设 A（x）：x是人， B（x):x是喜欢步行， C(x）:x喜欢乘汽车，

D(x)：x喜欢骑自行车.上述各个命题符号化为：

"x(A（x）→（B(x)→ØC（x））)， "x(A（x)→（C(x）∨D(x）））， $x（A（x）∧ØD（x)）Þ＄x(A（x）∧ØB（x)）

⑴ $x(A(x）∧ØD(x）) P

⑵ A（a)∧ØD（a) ES ⑴

⑶ A（a) T ⑵ I

⑷ØD（a) T ⑵ I

⑸ "x（A（x)→（B（x）→ØC(x）)) P

⑹ A(a）→(B（a)→ØC(a)） US ⑸

⑺ B（a）→ØC(a) T ⑶⑹ I

⑻”x(A(x）→(C（x)∨D（x)）) P

⑼ A（a）→(C(a）∨D(a)) US⑻

⑽ C（a）∨D（a) T ⑶⑼ I

⑾ C（a） T ⑷⑽ I

⑿ØB（a） T ⑺⑾ I

⒀ A（a)∧ØB（a) T ⑶⑿ I

⒁＄x(A（x)∧ØB（x）） EG ⒀

46.答案：命题符号化为:

M(a）， M(b）, M(c），”x（M(x）→（ H(x）∨D（x)))，Ø＄x(D（x)∧L（x，d)), "x（H（x）→L(x，e)） "y(L(a,y）→ØL(b,y）), L（a，d）∧L（a,e)

⑴ L（a,d)∧L(a,e） P

⑵ L(a,e) T ⑴

⑶ "y(L(a,y)→ØL(b,y）) P

⑷ L（a,e）→ØL（b，e)） US ⑶

⑸ØL(b,e)) T ⑵⑷ I11

⑹”x(H（x）→L(x，e)) P

⑺ H（b)→L（b，e）) US ⑹

⑻ØH（b） T ⑸⑺ I12

⑼ "x（M(x）→(H（x)∨D(x))） P

⑽ M(b）→（H（b）∨D（b）） US ⑼

⑾ M(b) P

⑿ H（b）∨D(b) T ⑽⑾ I11

⒀ D(b) T ⑻⑿ I10

⒁ D(b)∧ØH（b） T ⑻⒀

所以小刘是登山者,而不是滑雪者。

47。答案：⑴ $x （ØP(x)® Q(x)） P

⑵ØP(a）® Q(a) ES ⑴

⑶ "xR(x） P

⑷ R(a） US ⑶

⑸”x（ØQ（x)ÚØR（x)) P

⑹ØQ（a)ÚØR(a） US ⑸

⑺ØQ（a) T ⑷⑹ I12

⑻ØØP(a) T ⑵⑺ I10

⑼ P（a) T ⑻ E1

⑽ $xA（x）) EG ⑼

48。答案：⑴Ø”x（R（x）®Q（x)） P

⑵ $ xØ (R（x）®Q(x）） T ⑴ E

⑶Ø（R（a）®Q(a)) ES ⑵

⑷Ø (ØR(a）ÚQ (a)） T ⑶ E

⑸ R(a) ÙØQ （a) T ⑷ E

⑹ R(a） T ⑸ I

⑺ØQ(a） T ⑸ I

⑻”x（P（x)®（Q（x）ÙR（x))）， P

⑼ P(a）®（Q(a）ÙR(a)) US ⑻

⑽ØQ(a）ÚØR(a) T ⑺ I

⑾Ø(Q (a) ÙR(a）) T ⑽ E

⑿ØP(a) T ⑼⑾ I

⒀ R(a) ÙØP (a） T ⑹⑿ I

⒁＄x(R（x)ÙØP（x)) EG ⒀

49。答案：⑴Ø”x（ØA（x)ÚD （x）） P

⑵ $ xØ（ØA（x）ÚD(x)） T ⑴ E

⑶Ø（ØA（a）ÚD(a）） ES ⑵

⑷ A（a）ÙØD (a) T ⑶ E

⑸ A(a) T ⑷ I

⑹ØD(a） T ⑷ I

⑺”x（A（x）®（ØC(x)®D（x）)） P

⑻ A(a)→(ØC（a)® D(a)) US ⑺

⑼ØC(a)® D(a) T ⑸⑻ I

⑽ C(a）∨D(a) T ⑼ E

⑾ C（a) T ⑹⑽ I

⑿ "x（ØC（x）Ú(ØA(x）ÚØB（x））) P

⒀ØC（a）Ú（ØA(a）ÚØB(a）) US ⑿

⒁ØA（a)ÚØB(a) T ⑾⒀ I

⒂ØB（a） T ⑷⒁ I

⒃ A(a）∧ØB(a） T ⑸⒂ I

⒄＄x(A（x）∧ØB(x）） EG ⒃

50。答案:⑴Ø＄zP(z） P (附加前提）

⑵ "zØP（z） T ⑴ E

⑶ "x（$y（S（x，y) ÙM（y)) ® $z（(P(z）ÙR(x,z)）) P

⑷ $y（S(a,y) ÙM(y）) ® $z（（P(z）ÙR（a,z）） US ⑶

⑸ØP(b） US ⑵

⑹ØP（b)ÚØR(a,b） T ⑸ I

⑺Ø(P(b）ÙR（a，b)) T ⑹ E

⑻ "zØ(P（z)ÙR(a,z）) UG ⑺

⑼Ø$z （P（z)ÙR(a,z)） T ⑻ E

⑽Ø＄y(S（a，y) ÙM（y）） T ⑷⑼ I

⑾”yØ (S（a,y) ÙM(y)) T ⑽ E

⑿”y (ØS（a,y）ÚØM（y)) T ⑾ E

⒀”y （S(a,y）®ØM（y)） T ⑿ E

⒁”x ”y （S(x,y) ®ØM(y）） US ⒀

⒂Ø$zP(z）®”x"y (S(x，y）®ØM（y)) CP

51.答案:先命题符号化为：

"x（N(x)→(ØO(x)→E(x）))， "x（O（x)→ØC（x)），＄x(N（x）∧C(x））Þ$x（N（x)∧E（x)）

⑴＄x(N（x)∧C(x）） P

⑵ N(a）∧C(a） ES ⑴

⑶ N(a） T ⑵ I

⑷ C（a） T ⑵ I

⑸”x(O(x)→ØC（x)）） P

⑹ O(a)→ØC(a） US ⑸

⑺ØO（a) T ⑷⑹ I

⑻ "x（N（x）→（ØO（x）→E（x)）) P

⑼ N(a）→(ØO（a）→E（a)) US ⑻

⑽ØO（a)→E（a） T ⑶⑼ I

⑾ E（a） T ⑺⑽ I

⑿ N（a)∧E(a) T ⑶⑾ I

⒀ $x(N(x)∧E（x)) EG ⑿

52。答案：证明.

⑴ $x(A(x）ÙØ”y(ØB（y）ÚØC(x,y））), P

⑵ A(a)ÙØ”y(ØB(y)ÚØC(a，y）) ES ⑴

⑶ A(a） T ⑵ I

⑷Ø”y（ØB(y）ÚØC（a，y))） T ⑵ I

⑸ $yØ（ØB（y）ÚØC(a,y））） T ⑷ E

⑹ $y（B（y)ÙC(a,y)） T ⑸ E

⑺ "x(A(x）®”y(D（y )®ØC(x，y）)) P

⑻ A（a)®"y（D(y ）®ØC（a，y)） US ⑺

⑼”y(D（y ）®ØC（a,y）) T ⑶⑻I

⑽ B(b)ÙC(a，b） ES ⑹

⑾ B（b） T ⑽ I

⑿ C（a,b） T ⑽ I

⒀ D(b）®ØC(a,b）） US ⑼

⒁ØD（b） T ⑿⒀ I

⒂ B（b)ÙØD(b) T ⑾⒁I

⒃＄y(B(y)ÙØD(y)) EG ⒂

53.答案：证明.

⑴ $xA（x) Ù"yØD(y） P

⑵＄xA（x) T ⑴ I

⑶ "yØD（y) T ⑴ I

⑷ A(a) ES ⑵

⑸”x(A(x）®＄y(B（y）®ØC（x，y)）） P

⑹ A（a）®＄y（B（y）®ØC（a，y）） US ⑸

⑺＄y（B(y)®ØC(a，y)） T ⑷⑹ I

⑻”x（A(x）®"y(C(x,y）ÚD（y）)） P

⑼ A(a）®”y(C（a,y）ÚD(y))) US ⑻

⑽”y(C（a，y)ÚD（y)) T ⑷⑼ I

⑾ B（b）®ØC（a,b) ES ⑺

⑿ C（a,b)Ú D（b） US ⑽

⒀ØD（b） US ⑶

⒁ C(a，b) T ⑿⒀ I

⒂ØB（b) T ⑾⒁ I

⒃＄y ØB（y） EG ⒂

54。答案:设:A（x）：x是书刊， B(x）：x是合法出版的， C(x)：x是人， D(x): x感到忧虑。

命题符号化:

$x(A(x）∧ØB(x)）→"y(C（y）→D(y））, ＄y（C(y)∧ØD(y)) Þ "x （A(x）→B(x））

⑴ $y（C（y）∧ØD（y）) P

⑵＄yØ（ØC（y)∨D(y） T ⑴ E

⑶＄yØ (C(y)→D(y)) T ⑵ E

⑷Ø”y(C（y)→D（y）) T ⑶ E

⑸＄x(A(x)∧ØB(x））→”y(C(y）→D(y)) P

⑹Ø＄x(A（x)∧ØB(x）） T ⑷⑸ I

⑺”xØ (A(x)∧ØB（x)） T ⑹ E

⑻”x （ØA（x）∨B(x）) T ⑺ E

⑼”x (A(x）→B(x)) T ⑻ E

55.答案：⑴ $xA(x) P

⑵ A(a） ES ⑴

⑶＄x（B(x）ÙØC(x）) P

⑷（B（b）ÙØC（b)) ES ⑶

⑸Ø(ØB（b）ÚC（b)） T ⑷ E

⑹Ø(B（b)®C(b）) T ⑸ E

⑺Ø(B（b)®C(b）） T ⑹ E

⑻＄yØ(B（y)®C(y)) EG ⑺ E

⑼Ø"y(B（y）®C(y)） T ⑻ E

⑽”z(（A（z)Ù"x$yD(x,y)）®”y（B(y）®C（y）)） P

⑾ $z(A(z)Ù"x$yD（x,y）)®”y（B（y）®C(y）） T ⑽ E(辖域缩小)

⑿Ø$z(A(z)Ù"x$yD(x，y)) T ⑼⑾ I

⒀”zØ(A(z）Ù"x$yD（x，y）） T ⑿ E

⒁Ø(A（a)Ù”x$yD(x,y）） US ⒀

⒂ØA(a)ÚØ"x$yD（x,y）） T ⒁ E

⒃Ø”x＄yD（x,y）) T ⑵⑸ I

⒄＄x”yØD（x,y）） T ⒃ E

56.答案：先命题符号化为：

"x(N(x)→（ØE（x）→O（x))）, "x(（N(x）∧E(x)）«D（x，2）），Ø”x(N(x）→D（x,2）) Þ $x(N(x)∧O(x））

⑴Ø”x(N(x)→D（x，2）） P

⑵＄xØ（N(x)→D(x，2）） T ⑴ E

⑶ $xØ (ØN（x)ÚD(x,2） T ⑵ E

⑷ $x （N（x)∧ØD(x，2)) T ⑶ E

⑸ N（a）∧ØD（a ，2） ES ⑷

⑹ N(a) T ⑸ I

⑺ØD(a ，2) T ⑸ I

⑻”x(N（x）→(ØE（x)→O(x））） P

⑼ N（a）→（ØE（a）→O(a）) US ⑻

⑽ØE(a）→O（a） T ⑹⑼ I

⑾”x（(N(x)∧E（x）)« D(x，2）） P

⑿”x((N（x）∧E(x））→D（x，2))∧(D（x，2)→（N（x)∧E（x）)） T ⑾ E

⒀ ((N(a）∧E(a)）→D(a，2）)∧(D（a,2）→（N（a)∧E（a））) US ⑿

⒁ (N（a)∧E（a））→D（a，2）） T ⒀ I

⒂Ø (N（a）∧E（a）) T ⑺⒁ I

⒃ØN(a）ÚØE(a）） T ⒂ E

⒄ØE(a) T ⑹⒃ I

⒅ O(a） T ⑽⒄ I

⒆ N(a）∧O（a ） T ⑹⒅ I

⒇ $x(N（x)∧O(x)） EG ⒆

57。答案:

⑴ $x（A(x）∧＄y(B(y)∧C(x，y))） P

⑵ A(a)∧$y（B（y）∧C（a，y）) ES ⑴

⑶ A(a) T ⑵ I

⑷＄y(B（y)∧C（a，y)) T ⑵ I

⑸ B(b)∧C(a，b) ES ⑷

⑹ B（b) T ⑸ I

⑺ C(a，b) T ⑸ I

⑻ "x(A(x)→"y（D(y）→ØC（x,y)）) P

⑼ A（a)→”y（D（y）→ØC（a,y）） US ⑻

⑽ "y（D(y)→ØC(a,y)） T ⑶⑼ I

⑾ D（b)→ØC(a，b） US ⑽

⑿ØD(b） T ⑺⑾ I

⒀ B（b)∧ØD（b） T ⑹⑿ I

⒁＄y （B（y）∧ØD(y)) EG ⒀

⒂＄yØ（ØB(y)∨D（y)) T ⒁ E

⒃Ø”y（ B(y）→D(y）） T ⒂ E

58。答案：有错误。不应该先去掉"x,再去掉$x时，特指成同一个客体c。正确推理为：

⑴ $xA(x） P

⑵ A（c) ES ⑴

⑶ "x（A(x）→B（x）） P

⑷ A（c)→B(c) US ⑶

⑸ B（c） T ⑵⑷ I11

⑹ $xB（x） EG ⑸

59。答案:⑴＄x P（x） P

⑵ P（a） ES ⑴

⑶ "x(ØP(x）Ú R(x)） P

⑷ØP（a）Ú R（a） US ⑶

⑸ R(a） T⑵⑷ I

⑹”x（Q（x)®Ø R(x）) P

⑺（Q（a）®Ø R(a)） US ⑹

⑻ØQ(a） T ⑸⑺ I

⑼＄x ØQ((x） EG ⑻

(完整word版)第二章 谓词逻辑

第二章谓词逻辑 1.什么叫做客体和客体变元？如何表示客体和客体变元？ 2.么叫做谓词？ 3.什么叫做论域?我们定义一个“最大”的论域叫做什么? 4.填空题： 1．存在量词：记作（），表示( ）或者（）或者（ )。 2．全称量词:记作（ ),表示( ）或者（）或者( )。 5。什么叫做量词的作用域？指出下面两个谓词公式中各个量词的作用域。 ”x(F（x，y)→$yP(y)）∧Q(z）∧＄xA（x） ”x$y”z(A（x，y)→B(x,y,z))∧C(t) 6。什么叫做约束变元？什么叫做自由变元？指出下面公式中哪些客体变元是约束变元？哪些客体变元是自由变元? ”x(F(x,y）→＄yP(y）)∧Q(z）∧$xA（x) 7.填空：一个谓词公式如果无自由变元，它就表示一个（ )。 8.给出的谓词 J（x)：x是教练员， L（x） :x是运动员, S（x) ：x是大学生，O(x) ：x是年老的，V(x） :x是健壮的,C(x）：x是国家选手，W（x) ：x是女同志, H（x）：x是家庭妇女,A （x，y）：x钦佩y。客体 j：金某人.用上面给出的符号将下面命题符号化。 1．所有教练员是运动员。 2．某些运动员是大学生. 3．某些教练是年老的，但是健壮的. 4．金教练既不老，但也不是健壮的。 5．不是所有运动员都是教练。 6．某些大学生运动员是国家选手。 7．没有一个国家选手不是健壮的。 8．所有老的国家选手都是运动员。 9．没有一位女同志既是国家选手又是家庭妇女。 10．有些女同志既是教练又是国家选手。 11．所有运动员都钦佩某些教练。 12．有些大学生不钦佩运动员.

9。将下面命题符号化 1．金子闪光,但闪光的不一定都是金子. 2．没有大学生不懂外语. 3．有些液体可以溶解所有固体. 4．每个大学生都爱好一些文体活动。 5．每个自然数都有唯一的后继数。 10.令P表示天气好.Q表示考试准时进行。A（x)表示x是考生.B(x)表示x提前进入考场。C（x）表示x取得良好成绩.E(x，y）表示x=y.利用上述符号，分别写出下面各个命题的符号表达式。1．如果天气不好,则有些考生不能提前进入考场。 2．只有所有考生提前进入考场，考试才能准时进行。 3．并非所有提前进入考场的考生都取得良好成绩。 4．有且只有一个提前进入考场的考生未能取得良好成绩。 11.将下面命题符号化。 1．对一个大学生来说，仅当他刻苦学习，才能取得优异成绩。 (S（x）：x是大学生；Q（x)：x取得了优异成绩；H(x）:x刻苦学习。) 2．每个不等于0的自然数,都有唯一的前驱数。 (Z（x）:x是自然数； E(x,y)：x=y； Q(x，y）:y是x的前驱数。） 12.是偏序集，B是A的非空子集.在括号内分别写入y是B的极小元、最小元、下界相应的谓词表达式. y是B的极小元Û（） y是B的最小元Û（） y是B的下界Û( ) 13.设论域D={1,2｝又已知a=1 b=2 f（1）=2 f（2）=1 P（1，1)=T P(1,2）=T P（2 ,1）=F P（2，2)=F 求谓词公式”x$y(P（x,y)®P（f（x),f(y)))的真值。（要求有解题的过程) 14设论域为{2，3｝，Ａ（x,y)表示 x+y=xy。求谓词公式Ø”x$yA(x,y)的真值。（要求有解题的过程。） 15。设谓词P(x,y）表示x是y的因子,论域是{1，2,3}。求谓词公式”x＄yØA（x，y）的真值。(要

《离散数学》同步练习答案

华南理工大学网络教育学院 《离散数学》练习题参考答案 第一章命题逻辑 一填空题 （1）设：p：派小王去开会。q：派小李去开会。则命题： “派小王或小李中的一人去开会”可符号化 为：(p∨?q) ∧ (?p∨q) 。 （2）设A，B都是命题公式，A?B，则A→B的真值是T。 （3）设：p：刘平聪明。q：刘平用功。在命题逻辑中，命题： “刘平不但不聪明，而且不用功”可符号化为：p∧q。 （4）设A , B 代表任意的命题公式，则蕴涵等值式为 A → B??A∨B。 （5）设，p：径一事；q：长一智。在命题逻辑中，命题： “不径一事，不长一智。”可符号化为：? p→?q 。 （6）设A , B 代表任意的命题公式，则德?摩根律为 ?（A ∧ B）??A ∨?B）。 （7）设，p：选小王当班长；q：选小李当班长。则命题：“选小王或小李中的一人当班长。”可符号化为：(p∨?q) ∧ (?p∨q) 。（8）设，P：他聪明；Q：他用功。在命题逻辑中，命题： “他既聪明又用功。”可符号化为：P∧Q 。 （9）对于命题公式A，B，当且仅当 A → B 是重言式时，称“A蕴含B”，并记为A?B。 （10）设：P：我们划船。Q：我们跑步。在命题逻辑中，命题：“我们不能既划船又跑步。”可符号化为：? (P∧Q) 。（11）设P , Q是命题公式，德·摩根律为： ?（P∨Q）??P∧?Q）。 （12）设P：你努力。Q：你失败。在命题逻辑中，命题：“除非你努力，否则你将失败。”可符号化为：?P→Q。

（13）设p：小王是100米赛跑冠军。q：小王是400米赛跑冠军。在命题逻辑中，命题：“小王是100米或400米赛跑冠军。”可符号化为： p∨q。 （14）设A，C为两个命题公式，当且仅当A→C为一重言式时，称C可由A逻辑地推出。 二．判断题 1.设A，B是命题公式，则蕴涵等值式为A→B??A∧B。（?） 2.命题公式?p∧q∧?r是析取范式。（√） 3.陈述句“x + y > 5”是命题。（?） 4.110 (p=1,q=1, r=0)是命题公式((?(p∧q))→r)∨q 的成真赋值。（√） 5.命题公式p→(?p∧q) 是重言式。（?） 6.设A，B都是合式公式，则A∧B→?B也是合式公式。（√） 7.A∨(B∧C)?( A∨B)∨(A∨C)。（?） 8.陈述句“我学英语，或者我学法语”是命题。（√） 9.命题“如果雪是黑的，那么太阳从西方出”是假命题。（?） 10.“请不要随地吐痰！”是命题。（?） 11.P →Q ??P∧Q 。（?） 12.陈述句“如果天下雨，那么我在家看电视”是命题。（√） 13.命题公式（P∧Q）∨（?R→T）是析取范式。（?） 14.命题公式(P∧?Q)∨R∨ (?P∧Q) 是析取范式。（√） 三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内。 1．设：P：天下雪。Q：他走路上班。则命题“只有天下雪，他才走路上班。” 可符号化为（2）。 （1）P→Q （2）Q → P （3）? Q →? P （4）Q ∨?P 2．(1 ) 明年国庆节是晴天。

谓词逻辑练习及答案

第二章谓词逻辑 练习一 1、指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并回答它们是否是命题： （1）?x(P(x)∨Q(x))∧R （R为命题常元） （2）?x(P(x)∧Q(x))∧?xS(x)→T(x) （3）?x(P(x)→?y(B(x,y)∧Q(y))∨T(y)) （4）P(x)→(?y?x(P(x)∧B(x,y))→P(x)) 解（1）全称量词?，辖域P(x)∨Q(x)，其中x为约束变元，?x(P(x)∨Q(x))∧R是命题。 （2）全称量词?，辖域P(x)∨Q(x)，其中x为约束变元。 存在量词?，辖域S(x) ，其中x为约束变元。 T(x)中x为自由变元。?x(P(x)∧Q(x))∧?xS(x)→T(x)不是命题。 （3）全称量词?，辖域P(x)→?y(B(x,y)∧Q(y))∨T(y)，其中x为约束变元，T(y)中y为自由变元。存在量词?，辖域B(x,y)∧Q(y)，其中y为约束变元。?x(P(x)→?y(B(x,y)∧Q(y))∨T(y))是命题。 （4）全称量词?，辖域?x(P(x)∧B(x,y))，其中y为约束变元。 存在量词?，辖域P(x)∧B(x,y)，其中x为约束变元。 不在量词辖域中的P(x)中的x为自由变元。P(x)→(?y?x(P(x)∧B(x,y))→P(x)) 不是命题。 2、对个体域{0，1}判定下列公式的真值, E(x)表示“x是偶数”： （1）?x(E(x)→┐x=1) （2）?x(E(x)∧┐x=1) （3）?x(E(x)∧x=1) （4）?x(E(x)→x=1) 再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。

第2章谓词逻辑习题及答案

谓词逻辑习题 1. 将下列命题用谓词符号化。 （1）小王学过英语和法语。 （2）2大于3仅当2大于4。 （3）3不是偶数。 （4）2或3是质数。 （5）除非李键是东北人，否则他一定怕冷。 解： (1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ? (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨ (5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ，，=，消去下列各式的量词。 （1）))()((y Q x P y x ∧?? （2）))()((y Q x P y x ∨?? （3）)()(y yQ x xP ?→? （4）))()((y yQ y x P x ?→?， 解： (1) 中))()(()(y Q x P y x A ∧?=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧?=，因此))()(())()((y Q y P y y Q x P y x ∧?∧?? ，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧? ，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧?? （2）中))()(()(y Q x P y x A ∨?=，它对y 不是自由的，故不能用UI 规则，然而，对 )(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨?，这时用UI 规则，可得： ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨? （3）略 （4）略 3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321 {，，=D 。求下列各式的真值。 （1）)3(，x xP ? （2）)1(y yP ，? （3）)(y x yP x ，?? （4）)(y x yP x ，?? （5）)(y x yP x ， ?? （6）)(y x xP y ， ??

离散数学(全)

第一章命题逻辑 内容： 命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法等证明方法。 教学目的： 1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。 2．熟练掌握常用的基本等价式及其应用。 3．熟练掌握（主）析/合取范式的求法及其应用。 4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。 5．熟练掌握形式演绎的方法。 教学重点： 1．命题的概念及判断 2．联结词，命题的翻译 3．主析（合）取范式的求法 4．逻辑推理 教学难点： 1．主析（合）取范式的求法 2．逻辑推理 1.1命题及其表示法 1.1.1 命题的概念 数理逻辑将能够判断真假的陈述句称作命题。 1.1.2 命题的表示 命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。 1.2命题联结词

（1） P↑P⇔﹁（P∧P）⇔﹁P； （2）（P↑Q）↑（P↑Q）⇔﹁（P↑Q）⇔ P∧Q； （3）（P↑P）↑（Q↑Q）⇔﹁P↑﹁Q⇔ P∨Q。 （1）P↓P⇔﹁（P∨Q）⇔﹁P； （2）（P↓Q）↓（P↓Q）⇔﹁（P↓Q）⇔P∨Q； （3）（P↓P）↓（Q↓Q）⇔﹁P↓﹁Q⇔﹁（﹁P∨﹁Q）⇔P∧Q。

1.3 命题公式、翻译与解释 1.3.1 命题公式 定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P 是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、 P↔Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。 例如，下面的符号串都是公式： （（（（﹁P）∧Q）→R）∨S） （（P→﹁Q）↔（﹁R∧S））（﹁P∨Q）∧R 以下符号串都不是公式： （（P∨Q）↔（∧Q））（∧Q） 1.3.2 命题的翻译 可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。 命题翻译时应注意下列事项： （1）确定所给句子是否为命题。 （2）句子中联结词是否为命题联结词。 （3）要正确的选择原子命题和合适的命题联结词。 例：假如上午不下雨，我去看电影，否则就在家里读书或看报。 解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。 本例可表示为：（⌝P→Q）∧（P→（R∨S））。 1.3.3 命题公式的解释定义 设P1，P2，…，P n是出现在命题公式G中的全部命题变元，指定P1，P2，…，P n的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作T I（G）。 例如， 是G的一个解释，在这个解释下G的真值为1，即T I（G）=1。 1.4 真值表与等价公式 1.4.1 真值表 定义将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。 构造真值表的方法如下： （1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，…，P n。（2）列出G的2n个解释，赋值从00…0（n个）开始，按二进制递加顺序依次写

离散数学总结

第一章命题逻辑 1-1.命题及其表示方法 表达判断语句是陈述句称作命题，命题总有一个值，称作“真值”，真值只有“真”和“假”两种，记作T和F。 在数理逻辑中常用大写字母或用带下标的大写字母或用数字。例：Ai [12]；P：今天下雨 1-2.联结词 （1）否定（?）P与?P的关系：P与?P真值相反。 （2）合取（∧）P与Q当且仅当P与Q同时为真，则P∧Q为真，反之为假。 （3）析取（∨）当且仅当P,Q同时为F时，P∨Q为F，反之P∨Q为T。 （4）条件（→）当且仅当P的真值为T，Q的真值为F时，P→Q 真值为F，否则P→Q的真值为T。 （5）双条件（?）当P和Q真值相同时，P?Q的真值为T，否则P?Q的真值为F（双条件联结词亦可记作“?”或“iff”）。 1-3.命题公式与翻译 联结词的优先顺序为：?∧∨→?。 合成公式：（1）单个命题变元本事是一个合成公式；（2）如果A是合成公式，?A也是合成公式：（3）如果A和B是合成公式，那么（A∧B）（A∨B）（A→B）和（A?B）都是合成公式。例：P:他聪明 Q：他用功他虽然聪明但不用功可表示为：P∧?Q。 1-4.真值表与等价公式 （1）对合律??P?P (2)幂等律 P∧P?P (3)结合律（P∨Q）∨R?P∨(Q∨R) （P∧Q）∧R?P∧(Q∧R) （4）交换律 P∨Q?Q∨P P ∧Q?Q∧R （5）分配律 P∨(Q∧R)?（P∨Q）∧（P∨R） P∧(Q∨R)?（P∧Q）∨（P∧R）（6）吸收律 P∨(Q∧P)?P P∧(Q∨P)? P （7）德.摩根律?（P∨Q）??P∧?Q ?（P∧Q）??P∨?Q （8）同一律 P∨F?P P ∧T?P （9）零律 P∨T?T P∧F?F （10）否定律 P∨?P?T P∧?P ?F 证明一个等价公式是否成立，可用真值表法，亦可用等价公式法。 1-5.重言式与蕴含式 1.给定一个命题公式，无论对分量作怎样的指派，其对应真值永为真，则该命题公式为重言式或永真式。 2.给定一个命题公式，无论对分量作怎样的指派，

高等数学第二章谓词逻辑练习题

一、 选择题 1．下列四个公式正确的是 ①)()())()((x xB x xA x B x A x ?∧??∧? ②)()())()((x xB x xA x B x A x ?∨??∨? ③)()())()((x xB x xA x B x A x ?∨??∨? ④))()(()()(x B x A x x xB x xA ∧???∧? A.①③ B.①④ C.③④ D.②④ 2. 谓词公式)())()((x Q y yR x P x →?∨?中量词?x 的辖域是( ) (A) ))()((y yR x P x ?∨? (B) P (x ) (C) )()(y yR x P ?∨ (D) )(x Q 3. 谓词公式))()(()(x xQ x Q x x xP ??→??→?的类型是（ ） (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 蕴涵式 4. 设个体域为整数集，下列公式中其真值为1的是( ) (A) )0(=+??y x y x (B) )0(=+??y x x y (C))0(=+??y x y x (D) )0(=+???y x y x 5. 设个体域{,}A a b =，公式()()xP x xS x ?∧?在中消去量词后应为 ( ) (A) ()()P x S x ∧ (B) ()()(()())P a P b S a S b ∧∧∨ (C) ()()P a S b ∧ (D) ()()()()P a P b S a S b ∧∧∨ 6. 在谓词演算中，下列各式正确的是( ) (A) (,)(,)x yA x y y xA x y ????? (B) (,)(,)x yA x y y xA x y ????? (C) (,)(,)x yA x y x yA x y ????? (D) (,)(,)x yA x y y xA x y ????? 7.下列各式不正确的是( ) (A) (()())()()x P x Q x xP x xQ x ?∨??∨? (B) (()())()()x P x Q x xP x xQ x ?∧??∧? (C) (()())()()x P x Q x xP x xQ x ?∨??∨? (D) (())()x P x Q xP x Q ?∧??∧

(完整word版)离散数学知识汇总

离散数学笔记 第一章命题逻辑 合取 析取 定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果……那么……”形式的语句 定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句 定义 1.2.1合式公式 (1)单个命题变元、命题常元为合式公式，称为原子公式。 (2)若某个字符串A 是合式公式，则?A、(A)也是合式公式。 (3)若A、B 是合式公式，则A ∧B、A∨B、A→B、A?B 是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。 1.3等值式 1.4析取范式与合取范式

将一个普通公式转换为范式的基本步骤

1.6推理 定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C ，记为 A => C 。（用等值演算或真值表） 第二章 谓词逻辑 2.1、基本概念 ?：全称量词 ?：存在量词 一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如"?x(H(x)→B(x))，即量词的后面为条件式，带“存在量词”的谓词公式形如?x(H(x)∨WL(x))，即量词的后面为合取式 例题 R(x)表示对象 x 是兔子，T(x)表示对象 x 是乌龟， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 与 y 一样快，则兔子比乌龟跑得快表示为： ?x ?y(R(x)∧T(y)→H(x,y)) 有的兔子比所有的乌龟跑得快表示为：?x ?y(R(x)∧T(y)→H(x,y)) 2.2、谓词公式及其解释 定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22 y x 的 f(x,y))、 谓词常元(如表示人 类的 H(x))。 定义 2.2.2、逻辑符号：个体变元、量词(??)、联结词(﹁∨∧→?)、逗号、括号。 定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。 定义 2.2.4、原子公式：设 R(n x x ... 1)是 n 元谓词，n t t ...1是项，则 R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。 定义 2.2.5 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，则(﹁A)也是合式公式；(3)若 A,B 合式，则 A ∨B, A ∧B, A →B , A ?B 合式(4)若 A 合式，则?xA 、?xA 合式(5)有限次使用(2)~(4)得到的式子是合式。 定义 2.2.6 量词辖域：?xA 和?xA 中的量词?x/?x 的作用范围，A 就是作用范围。 定义 2.2.7 约束变元：在?x 和?x 的辖域 A 中出现的个体变元 x ，称为约束变元，这是与量词相关的变元，约束变元的所有出现都称为约束出现。 定义 2.2.8 自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。 注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。 定义 2.2.9 闭公式是指不含自由变元的谓词公式

逻辑学入门书

逻辑学入门书 逻辑学入门书 第一章：引言（500字） 逻辑学是一门研究思维和推理的学科，它帮助我们通过正确的思考和推理方法来处理问题。逻辑学广泛应用于数学、科学、法律、哲学等领域，对我们的日常生活也有着重要的影响。本书将引导读者走进逻辑学的世界，了解逻辑学的基本概念和原则，帮助读者提升思维能力和解决问题的能力。 第二章：命题逻辑（1200字） 命题逻辑是逻辑学的基石，它研究的是命题和命题之间的关系。命题是陈述或表达一个判断的句子，命题可以是真的，也可以是假的。命题逻辑使用符号来表示命题和命题之间的逻辑关系，通过逻辑运算符（如非、与、或、蕴含等）来描述和推理命题之间的连接。 第三章：谓词逻辑（1200字） 谓词逻辑是一种扩展的逻辑形式，它允许我们更精确地表达关系和属性。在命题逻辑中，我们只能处理简单的命题，而在谓词逻辑中，我们可以引入变量和量词来描述复杂的命题和关系。谓词逻辑在数学、计算机科学和人工智能等领域有广泛的应用。 第四章：推理和证明（1500字）

推理是逻辑学的核心内容，它是根据已知的命题和逻辑规则来得出新的结论的过程。推理可以分为演绎推理和归纳推理两种形式。演绎推理是从普遍的原则推出特殊的结论，而归纳推理是从个别的观察得出一般的结论。证明是对一个命题的有效推理过程，它要求通过逻辑规则和已知的真实信息来建立一个合理的论证。 第五章：逻辑谬误（1000字） 逻辑谬误是逻辑推理过程中的错误，它可以导致推理的无效性和错误的结论。逻辑谬误分为形式谬误和内容谬误两种类型。形式谬误是源于推理过程中的逻辑错误，例如陷阱论证和违反关联的错误。内容谬误是指推理中的假设或前提有问题，例如虚假的因果关系和非直接的证据。了解逻辑谬误可以帮助我们更好地评估和分析推理过程中的错误。 第六章：模态逻辑（1000字） 模态逻辑研究的是命题的可能性和必然性。它通过引入模态操作符（如可能性、必然性等）来描述不同命题的状态。模态逻辑在哲学、认知科学和形式验证等领域有广泛的应用，它帮助我们理解现实世界中可能发生的事件和必然发生的规律。 第七章：逻辑思维训练（1000字） 逻辑思维是一种基本的思维能力，它帮助我们识别和评估不同的论点和观点。逻辑思维训练可以帮助我们提升思维的敏锐度

谓词逻辑定义

谓词逻辑定义 谓词逻辑是一种用来描述事物真假性的语言，它的核心是谓词（Predicate）和符号表示法，它可以用来表达自然语言中的复杂概念和描述一些事实及其关系。谓词逻辑是一种强大的数学模型，可以用来表示我们对自然现象的知识，并且可以推断出未来的情况。 谓词逻辑的发展源自上世纪六十年代，受到欧几里得的哲学思想的启发，以便为数学模型提供更完整的语言。它发展成为一种用来描述事物的语言，可以用来描述一些事实及其关系，实现机器模拟思维的目的，它主要用于计算机科学领域，其他领域如哲学也有广泛的应用。 谓词逻辑通过谓词（predicates）来描述一般状况和条件，它是一种抽象的数学语言，可以表达自然语言中的复杂概念，以符号表示法来表达一些有关真假性的概念，并通过推断技术来完成其任务。 谓词逻辑由以下几个部分组成： 1.尔谓词：它是一些布尔谓词（Boolean predicates），用来描述一般状况和条件，比如P（x），Q（x），R（x）等等。 2.号表示：谓词逻辑使用比较简单的符号表示法，以表达一些有关真假性的概念，比如“&”（且），“”（否定），“∨”（或）等等。 3.词逻辑语句（Logical Sentences）：谓词逻辑语句是谓词逻辑中使用的一种有用结构，它由谓词和符号表示法组成，可以表达一些真假性概念。 4.型：谓词逻辑的模型是一种强大的数学模型，它可以用来描述

自然现象的知识，它可以用来表达一些事实及其关系（fact and relationship）。 谓词逻辑的最大优势在于它是一种可以描述一些有关真假性的 复杂概念的语言，它不但可以用来表达自然语言中的复杂概念，也可以用来描述一些事实及其关系，实现机器模拟思维的目的，从而实现机器智能。 谓词逻辑使用比较简单的符号表示法，可以表达一些有关真假性的概念，可以用来计算机科学中的解释和推理，可以用来描述一些事实及其关系，实现机器模拟思维的目的，也可以用于哲学等其他领域。 谓词逻辑是一种可以表达复杂概念的强大数学模型，它可以用来描述自然现象的知识，可以用来描述一些事实及其关系，可以用来实现机器模拟思维的目的，并在计算机科学领域和哲学领域有着广泛的应用。 谓词逻辑通过谓词（predicates）和符号表示法来描述一般状况和条件，可以表达自然语言中的复杂概念，比如“&”（且），“”（否定），“∨”（或）等等，可以用来表达一些有关真假性的概念，并通 过推断技术来完成其任务，实现机器模拟思维的目的。谓词逻辑的发展源自上世纪六十年代，它是一种可以表达复杂概念的强大数学模型，它可以用来描述一些事实及其关系，实现机器模拟思维的目的，在计算机科学领域和哲学领域有着广泛的应用。

谓词逻辑表示法

谓词逻辑表示法是把一些知识表示为经典逻辑中的谓词表示式。它只能表示出精确的知识，而对不确定的知识无法有效表示，同时这种表示方式也不能很好地体现知识的内在联系。在进行教学时，首先需要通过实例让学生了解什么是命题和命题公式，什么是谓词和谓词公式，然后用实例来分析讲解将知识表示为谓词公式的过程： 1）定义谓词和个体 例：王先生是李文的老师。首先定义谓词：TEACHER(X,Y):X 是Y 的老师，而后定义个体：王先生(Wang)，李文（LiWen ）； 2）为每个谓词中的变元赋以特定的值：TEACHER(Wang,LiWen)； 3）根据所要表达的知识语义，以适当的连接词和量词符号将各个谓词连接起来，得到知识的谓词公式：TEACHER(Wang,LiWen)。 在理解连接词∧(逻辑与)、∨（逻辑或）、┐（逻辑非）时可以参考我们平时的语言 中的“并且”、“或者”、“不”，对P →Q 的理解可以参考┐P ∨Q 。在此节只要求学生对谓词表示法有了解，命题的证明等内容不做要求，可以将相关内容放在辅助教学网站的拓展篇，以满足不同学生的需求。 在教学中除了书本中介绍的例子之外，还可以使用以下例子。 例1：用谓词逻辑和公式表达意境。 分析如下命题和谓词逻辑，并尽可能正确表达它的含义： （1） 蓝的（天）∧飘（白云）∧奔跑（马儿）∧飞翔歌唱（鸟儿）； 答：这是一个由“与”关系连接起来的谓词逻辑公式，它表达了一种大自然的景观：蓝色的天上白云飘飘，马儿在奔跑，鸟儿在飞翔歌唱。 （2） )(x {好姑娘（x ）∧居住的地方(z,x) ∧遥远的(z) ∧(y)[人(y) ∧行走 经过(y,z) →回头留恋地张望(y)]} 答：这是一个既有谓词表示，又有命题逻辑表达，既有连接词，又有全称量词和存在量词的较复杂的谓词公式，它表达的意思是：在那遥远的地方，有位好姑娘，人们经过她的身旁，都要回头留恋地张望。这就是青海民歌《在那遥远的地方》（王洛宾词曲）中的意境。 例2:用谓词逻辑表示知识单元。 设有下述记录：①小李给小王送礼物；②小李是工程师；③小王是程序员；④小李的地址是南京路115号；⑤小王的地址是黄山路458号。 请用谓词逻辑（中或英文）表示上述记录，并分成必要的知识单元。 答：1）定义谓词，GIVE(x,y,p),x 给Y 送礼物p ； OCCUPATION(x,y)，X 是Y 职业； ADDRESS （x,y ）,x 的地址是Y ； 2）定义个体 小李(xiaoli)，小王(xiaowang)，工程师（engineer ），程序员(programmer)、 南京路115号（115-nianjing-road ），黄山路458号（458-huangshan-road)。 3）知识谓词公式： ① GIVE(xiaoli,xiaowang,presents)； ② OCCUPATION(xiaoli,engineer)； ③ OCCUPATION （xiaowang,programmer ）； ④ ADDRESS （xiaoli,115-nianjing-road ）； ⑤ ADDRESS(xiaowang,458-huangshan-road)；

第二章 谓词逻辑 1.原子命题的内部结构

第二章 谓词逻辑 一、原子命题的内部结构 12．谓词逻辑·谓词和个体词·量词、全称量词和存在量词·个体域·量词的辖域·自由 个体变项和约束个体变项·一阶谓词逻辑 什么是谓词逻辑 在第一章中，我们知道，命题逻辑的根本特征，就在于把原子命题作为基本的单位，对原子命题的内部结构不再进行分析。在思维实际中，有时我们不涉及原子命题的内部结构，例如，命题推理只涉及命题之间的关系，这时命题逻辑的工具就足够了。但在更多的情况下需要涉及原子命题的内部结构。例如： 推理1： 所有的人都是要死的。 苏格拉底是人。 所以，苏格拉底是要死的。 推理1包括三个不同的原子命题，经过相应的设定后，它的真值形式是()r q p →∧。这不是一个重言式。因此，这个显然有效的推理在命题逻辑个被判定无效。这是因为，推理1的有效性的根据不在原于命题之间的关系，而在于原子命题内部的构成要素之间的关系。命题逻辑无法解决这样的推理的判定问题。传统逻辑中的词项逻辑把原子命题进一步分析为主项、谓项、量项和联项的合式构成，这样它就能处理命题逻辑所无法处5理的许多推理，如推理1这样的三段论。但是，词项逻辑的处理能力有着很大的局限。例如： 推理2： 所有的罪犯或者是故意犯罪，或者是过失犯罪。 有些罪犯不是故意犯罪。 因此，有些罪犯是过失犯罪。 这个有效性同样明显的推理的判定，命题逻辑解决不了，词项逻辑同样解决不了。 为了更为有效和尽量不失—般性地解决推理的判定，需要提出新的逻辑工具，进—步分析原子命题的内部结构。这就是谓词逻辑的任务。 在谓词逻辑中，原子命题被进一步分析为谓词、个体词、量词和联结词这样几个基本成分。谓词、个体词和量词是谓词逻辑中新引入的概念，联结词作为符号就是真值联结词。 谓词和个体词 我们通过以下实例来说明什么是谓词和个体词。 (1) 这张桌子是方的。 (2) 陈先生是贾女土的丈夫。 显然，以上两个命题都是原子命题。 在(1)中，今F(x)表示“x 是方的”，a 表示“这张桌子”，这样，F(a)就表示“这张桌子是方的”，也就是说，命题(1)的表达式是F(a)。这里，F 就是谓词，表示“方”这种性质；x 和a 就是个体词，表示具有“方”这种性质的个体。其中，x 称为个体变项，它只表示某一个个体，而不表示一个确定的个体；a 称为个体常项，它表示一个确定的个体，即这张桌子。 在(2)中，令H(x ，y)表示“x 是y 的丈夫”，a 表示陈先生，b 表示贾女士，这样，H(a ，b)就表示“陈先生是贾女士的丈夫”，也就是说，命题(2)的表达式是H(a ，b)。这里，H 是谓词，表示某人是某人的丈夫”这种关系，x 、y 和a 、b 是个体词，同样，x 和y 是个体变项，a 和b 是个体常项。

《离散数学》课程教学大纲

《离散数学》教学大纲 一、课程基本信息 1.课程中文名称：离散数学 2.课程英文名称：Discrete Mathematics 3.课程类别：必修 4.适用专业：信息工程 5.总学时：54学时 6.总学分：3 二、本课程在教学计划中的地位、作用和任务 离散数学是现代数学的一个重要分支，是计算机科学的核心基础课程。通过该课程的学习，培养和锻炼学生抽象思维和缜密概括的能力，为专业基础课和专业课的学习打下坚实的理论基础。 三、理论教学内容与教学基本要求 1. 第一章命题逻辑（10学时） 教学内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、其他联结词、对偶与范式、推理理论。 教学目的及要求：掌握命题逻辑中的基本概念和命题逻辑推理的证明方法。 教学重点：命题逻辑中的基本概念和基本推理方法。 教学难点：推理理论。 2. 第二章谓词逻辑（8学时） 教学内容：谓词的概念与表示、命题函数与量词、谓词公式与翻译、变量的约束、谓词演算的等价式与蕴涵式、前束范式、谓词演算的推理理论。 教学目的及要求：理解和掌握谓词逻辑的基本概念和基本推理方法。 教学重点：谓词逻辑中的基本概念和基本推理方法。 教学难点：谓词演算的推理理论。 3. 第三章集合与关系（12课时） 教学内容：集合的概念与表示、集合的运算、包含排斥原理、序偶与笛卡尔积、关系及

表示、关系的性质、复合关系和逆关系、关系的闭包运算、集合的划分和覆盖、等价关系与等价类、相容关系、序关系。 教学目的及要求：掌握有关集合和关系的基本概念、性质、运算以及应用。 教学重点：关系及关系的运算、等价关系、序关系。 教学难点：关系的闭包运算、等价关系、等价类。 4. 第四章函数（2学时） 教学内容：函数的概念、逆函数和复合函数、特征函数与模糊子集、基数的概念、可数集与不可数集、基数的比较。 教学目的及要求：理解和掌握本章的基本概念。 教学重点：逆函数和复合函数、可数集与不可数集的概念。 教学难点：基数的概念。 5. 第五章代数结构（12学时） 教学内容：代数系统的引入、运算及性质、半群、群与子群、阿贝尔群和循环群、倍集与拉格朗日定理、同态与同构、环和域。 教学目的及要求：掌握本章的基本概念和基本运算及证明方法。 教学重点：代数系统、同构和同态、群、环、域的概念及运算。 教学难点：同构和同态的概念以及群的证明。 6. 第六章格与布尔代数（2学时） 教学内容：格的概念、分配格、有补格、布尔代数、布尔表达式。 教学目的及要求：理解格与布尔代数的基本概念和基本运算。 教学重点：格、布尔代数、布尔表达式。 教学难点：布尔代数、布尔表达式。 7. 第七章图论（8学时） 教学内容：图的基本概念、路与回路、图的矩阵表示、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用。 教学目的及要求：深刻理解和掌握图的有关概念、性质和应用。 教学重点：图、路、图的矩阵表示、欧拉图与汉密尔顿图、平面图、图着色、树与生成树。 教学难点：特殊图的性质、证明与应用。 四、实验教学内容与要求

离散数学(谓词逻辑)课后总结

第二章谓词逻辑 2—1基本概念 例题１. 所有的自然数都是整数。 设N(x)：x是自然数。I(x)：x是整数。此命题可以写成∀x(N(x)→I(x)) 例题２. 有些自然数是偶数。 设E(x)：x是偶数。此命题可以写成∃x(N(x)∧E(x)) 例题3. 每个人都有一个生母。 设P(x):x是个人。M(x,y):y是x的生母。此命题可以写成：∀x(P(x)→∃y(P(y)∧M(x,y))) 2-2 谓词公式及命题符号化 例题1. 如果x是奇数，则2x是偶数。 其中客体x与客体2x之间就有函数关系，可以设客体函数g(x)=2x， 谓词O(x)：x是奇数，E(x)：x是偶数， 则此命题可以表示为：∀x(O(x)→E(g(x))) 例题2 小王的父亲是个医生。 设函数f(x)=x的父亲，谓词D(x):x是个医生，a:小王，此命题可以表示为D(f(a))。 例题3 如果x和y都是奇数，则x+y是偶数。 设h(x,y)=x+y ，此命题可以表示为:∀x∀y((O(x)∧O(y))→E(h(x,y)) 命题的符号表达式与论域有关系 两个公式：一般地，设论域为{a1,a2,....,an}，则有 (1). ∀xA(x)⇔A(a1)∧A(a2)∧......∧A(an) (2). ∃xB(x)⇔B(a1)∨B(a2)∨......∨B(an) 1.每个自然数都是整数。该命题的真值是真的。 表达式∀x(N(x)→I(x))在全总个体域的真值是真的,因∀x(N(x)→I(x))⇔(N(a1)→I(a1))∧(N(a2)→I(a2))∧…∧(N(an)→I(an)) 式中的x不论用自然数客体代入，还是用非自然数客体代入均为真。例如(N(0.1)→I(0.1))也为真。 而∀x(N(x)∧I(x))在全总个体域却不是永真式。 ∀x(N(x)∧I(x))⇔(N(a1)∧I(a1))∧(N(a2)∧I(a2)) ∧…∧(N(an)∧I(an)) 比如x用0.2代入(N(0.2)∧I(0.2))就为假。所以此表达式不能表示这个命题。 2.有些大学生吸烟。此命题的真值也是真的。 ∃x(S(x)∧A(x))⇔(S(a1)∧A(a1))∨(S(a2)∧A(a2))∨…∨(S(an)∧A(an)) 且x只有用吸烟的大学生代入才为真，例如a2不是大学生 或者不会吸烟的客体，则(S(a2)∧A(a2))为假。所以用∃x(S(x)∧A(x))表示此命题是对的。 而∃x(S(x)→A(x))中的x用非大学生的客体代入时也为真，例如(S(a2)→A(a2))为真。所以表达式∃x(S(x)→A(x))不能表示这个命题。 3.所有大学生都喜欢一些歌星。 令S(x)：x是大学生，X(x)：x是歌星，L(x,y)：x喜欢y。则命题的表达式为： ∀x(S(x)→∃y(X(y)∧L(x,y))) 4.没有不犯错误的人。 此话就是“没有人不犯错误”，“没有”就是“不存在”之意。令P(x)：x是人，F(x)：x犯错误，此命题的表达式为：⌝∃x(P(x)∧⌝F(x)) 或者∀x(P(x)→F(x)) 5.不是所有的自然数都是偶数。 令N(x)：x是自然数，E(x)：x是偶数，命题的表达式为: ⌝∀x(N(x)→E(x)) 或者∃x(N(x)∧⌝E(x))

(完整word版)离散数学复习提纲(完整版)

《离散数学》期末复习大纲（完整版）（含例题和考试说明) 一、命题逻辑 [复习知识点］ 1、命题与联结词(否定￢、析取∨、合取∧、蕴涵→、等价↔）,复合命题 2、命题公式与赋值(成真、成假）,真值表,公式类型（重言、矛盾、可满足),公式的基本等值式 3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式 4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法） 5、命题逻辑的推理理论 本章重点内容:命题与联结词、公式与解释、(主)析取范式与（主)合取范式、公式类型的判定、命题逻辑的推理 ［复习要求] 1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法. 2、理解公式与赋值的概念;掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。 3、了解析取(合取）范式的概念；理解极大（小）项的概念和主析取(合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取)范式的方法. 4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。 5、掌握命题逻辑的推理理论。 [疑难解析］ 1、公式类型的判定 判定公式的类型,包括判定公式是重言的、矛盾的或是可满足的。具体方法有两种，一是真值表法,二是等值演算法。 2、范式 求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点:一是准确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中律、矛盾律）,结果的前一步适当使用幂等律，使相同的短语(或子句）只保留一个. 3、逻辑推理

掌握逻辑推理时，要理解并掌握12个（除第10，11）推理规则和3种证明法(直接证明法、附加前提证明法和归谬法）. 例1.试求下列公式的主析取范式: (1）))()((P Q Q P P ⌝∨⌝⌝∧→→；（2）)))((R Q Q P P →⌝∨→⌝∨ （))()(())()((:)1P Q Q P Q P P P Q Q P P ∧∧∨∧∧⌝∨⌝=∧∧∨⌝∨⌝=原式解 Q P P P Q P P Q P ∨⌝=∨⌝∧∨⌝=∧∨⌝=)()()( ))(())((Q P P Q Q P ∧∨⌝∨∨⌝∧⌝= )()()(Q P Q P Q P ∧∨∧⌝∨⌝∧⌝= )))((()))(((:)2R Q Q P P R Q Q P P ∨∨∨∨=→⌝∨→⌝∨解 )()()()(R Q P R Q P R Q P R Q P R Q P ∧⌝∧∨∧∧⌝∨⌝∧∧⌝∨∧⌝∧⌝=∨∨= )()()(R Q P R Q P R Q P ∧∧∨⌝∧∧∨⌝∧⌝∧∨） 2．用真值表判断下列公式是恒真?恒假？可满足？ （1)（P P ）Q （2)（P Q) Q （3）（（P Q)(Q R ））（P R) 解： （1） 真值表 P Q P P P （P P)Q 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0 因此公式(1)为可满足. （2） 真值表

离散数学复习要点

离散数学复习要点第一章命题逻辑 一、典型考查点 1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律┐∧∨→记住特殊的：1∧1⇔1，0∨0⇔0，1→0⇔0，11⇔1，00⇔1详见P5 3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9 5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。 6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15 7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A⇔B的充要条件是A⇒B且B⇒A。主要等价式：(1)双否定：⎤⎤A⇔A。(2)交换律：A∧B⇔B∧A，A∨B⇔B∨A，A↔B⇔B↔A。3)结合律：(A∧B)∧C⇔A∧(B∧C)，(A∨B)∨C⇔A∨(B∨C)，(A↔B)↔C⇔A↔(B↔C)。(4) 分配律：A∧(B∨C)⇔(A∧B)∨(A∧C)，A∨(B∧C)⇔(A∨B)∧(A∨C)。(5) 德·摩根律：⎤(A∧B)⎤⇔A∨⎤B，⎤(A∨B)⎤⇔A∧⎤B。(6) 等幂律：A∧A⇔A，A∨A⇔A。(7) 同一律：A∧T⇔A，A∨F⇔A。(8) 零律：A∧F⇔F，A∨T⇔T。(9) 吸收律：A∧(A∨B)⇔A，A ∨(A∧B)⇔A。(10) 互补律：A∧⎤A⇔F，(矛盾律)，A∨⎤A⇔T。(排中律)(11) 条件式转化律：A→B⎤⇔A∨B，A→B⎤⇔B→⎤A。(12) 双条件式转化律：A↔B⇔(A→B)∧(B→A)⇔(A∧B)∨(⎤A∧⎤B) 8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A⇒B，即证A→B 是永真式。 9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和⎤以外公式中出现的所有联结词；②使用⎤(⎤P)⇔P和德·摩根律，将公式中出现的联结词⎤都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。 10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P⇔P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P⇔P ∧（⎤Q∨Q)或P⇔P∨（⎤Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。 注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q⇔m1∨m3⇔M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16 11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。 重点规则（主要蕴含式）：(1) P∧Q⇒P化简(2) P∧Q⇒Q化简(3) P⇒P∨Q附加(4) ⎤P⇒P→Q变形附加(5)Q⇒P→Q变形附加(6) ⎤(P→Q)⇒P变形化简(7) ⎤(P→Q)⎤⇒Q变形化简(8) P，(P→Q)⇒Q假言推理(9) ⎤Q，(P→Q)⎤⇒P拒取式(10) ⎤P，(P∨Q)⇒Q析取三段论(11) (P→Q)，(Q→R)⇒P→R条件三段论(12) (P↔Q)，(Q↔R)⇒P↔R 双条件三段论 文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21 二、强化练习 1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗? 2.下列式子为重言式的是( )