离散数学习题解答第3章谓词逻辑

1、 #G）合取引入G）合取引入量词辖域收缩与扩张等值式置换规则Vx(S(x)T-iP(x)A(S(x)TQ(x)GVx(S(x)t(-JP(x)a-iQ(x)4填写卜列证明过程中的推理规则。前提：Vx(P(x)aG(x),3x(P(x)tR(x),Vx(R(x)tH(x)结论：3x(G(x)aH(x)证明：3x(P(x)R(x)（前提引入规则）P(c)tR(c)（El规则）Vx(P(x)AG(x)提引入）P(c)AG(c)（UI规则）P(c)（化简规则）(6)Vx(R(x)tH(x)（前提引入）R(c)tH(c)（UI规则）R(c)（假言推理规则）H(c)（假言推理规则）G(c)（化简规则）5.

2、指出下列证明过程中的错误，并加以改正。（1）前提：Vx（P（x）G（x）,3x（P（x）vR（x）,Vx（-iR（x）结论：3xG（x）证明：Vx(-R(x)（前提引入规则）-R(c)（UI规则）3x(P(x)vR(x)（前提引入规则）P(c)vR(c)（EI规则）P(c)（Q析取三段论规则）Vx(P(x)TG(x)（前提引入规则）P(c)TG(c)（ui规则）G(c)（假言推理规则）3xG(x)（规则）解：证明过程中的和次序错误，应把放在前，Q在后。(2)前提：Vx(P(x)t-iG(x),3x(P(x)aR(x)结论：mx（G（x）证明：3x(P(x)aR(x)（前提引入规则）P(c)AR

3、(c)（US规则，EI规则）Vx(P(x)-iG(x)（前提引入规则）P(c)tG(c)（ES规则，UI规则）P(c)（Q合取引入规则，化简规则）G(c)（假言三段论规则）mx(G(x)（EG规则）解：蓝色字体为有错误的地方，修改好的内容跟在后面。G(c)aH(c)G(c)aH(c)3x(G(x)aH(x)（合取引入）（UG规则）前提：3xR(x)tVx(M(x)aG(x),-dx(M(x)aG(x),结论：3x(-nR(x)证明：m曲(x)TVx(M(x)AG(x)（前提引入规则）R(c)t(M(c)/G(c)（ES规则，US规则）-3x(M(x)aG(x)（前提引入规则）-(M(c)aG(

4、c)（ES规则）-iR(c)（拒取式规则）3x-iR(x)（EG规则）解：正确答案如下:证明：-3x(M(x)aG(x)-3x(M(x)aG(x)Vx-(M(x)aG(x)(M(aG(a3xR(x)tVx(M(x)aG(x)3yB(tVXM(初G(VyVXR9t(M(x)G(:R(a)T(M(叭G(M(a)/G(a)片-iRiR(a)3x-R(x)(前提引入规则)(量词变换等值式)(UI规则)(前提引入规则)(换名规则)(屋词辖域收缩与扩张等值式)(UI规则)(逆否蕴涵等值式)(假言推理)(EG规则)6在谓词逻辑系统中用自然演绎推理证明下列推理是有效的。所有偶数都能被2整除，8是偶数，所以8能

5、被2整除。所冇计算机系的学生都要学计算机组成原理，这些同学中有计算机系的学生和数学系的学生，所以这些同学中有些要学计算机组成原理。每个自然数不是奇数就是偶数：非负偶数都能被2整除；不是每个自然数都能被2整除，因此有的自然数是奇数。每个科学工作者都是刻苦钻研的人；每个刻苦钻研而又聪明的人在他的事业中都获得成功；张三是科学工作者，并且是个聪明人，所以张三在他的事业中将获得成功。解：(1)令P(X)表示：X是偶数：Q(x)表示：X能被2整除，则问题可表述为：条件：0 x(P(x)tQ(x),P(8)：结论：Q(8).推导过程：0 x(P(x)tQ(x)前提引入P(8)tQ(8)UI规则P(8)前提引

6、入Q(8)假言扌C)令P(x)表示：x是计算机系的学生；Q(x)表示：x要学计算机组成原理：M(x)表示：x是数学系的学生，则问题可表述为：条件：Vx(P(x)Q(x),3?dP(x),3xM(x):结论：3xQ(x)推导过程：3xP(x)前提引入P(a)EI规则0 x(P(x)tQ(x)前提引入P(a)TQ(a)UI规则Q(a)假言推理3xQ(x)EG规则(3)令N(x)表示：x是自然数；P(x)表示：x是偶数：H(x)表示：x是奇数：Q(x)表示：X能被2整除，则问题可表述为：条件：Vx(N(x)tP(x)VH(x),Vx(P(x)tQ(x),-Vx(N(x)-Q(x).结论：3x(N(x

7、)aH(x).推导过程：-Vx(N(x)Q(x)前提引入%(N(x)tQ(x)逆否蕴涵等值式(N(a)TQ(a)EI规则(N(a)TQ(a)5规则N(a)A-.Q(a)等值代换Vx(P(x)tQ(x)前提引入P(a)TQ(a)UI规则N(a)化简QG)化简P(a)拒取式Vx(N(x)P(x)vH(x)前提引入N(a)P(a)vH(a)UI规则P(a)vH(a假言推理H(a)析取三段论N(a)AH(a)合取引入3x(N(x)H(xEG规则(4)令S(x)表示：x是科学工作者；D(x)表示：x是刻苦钻研的人；W(x)表示：x是聪明人；Q(x)表示：x在事业中获得成功；a表示：张三，则问题可表述为：条件：Vx(S(x)D(x),0 x(D(x)/W(x)tQ(x),S(a),W(a).结论：Q(a).证明过程