华东师范大学离散数学章炯民课后习题第4,5章答案 VIP免费

1P591（1）.用谓词公式表达语句“所有的运动员都钦佩某些教练”，个体域为全总个体域。解：P(x):x是运动员，G(y):y是教练，R(x,y):x钦佩y。原题量词表达为：x(P(x)y(R(x,y)G(y)))此题错误较多：1.xyR(P(x),G(y))2.xy(P(x)G(y)R(x,y))3.R(x):x钦佩某些教练3.将x(C(x)y(C(y)F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y)表示x和y是同班同学，个体域是学校全体学生的集合。解：学校的全体学生要么自己有电脑，要么其同班同学有电脑。80%能正确解释。5.给定解释I如下：个体域D：{-2,3,6}；个体常元a：6；谓词P：2>1，Q(x)：x3，R(x)：x>5。求出谓词公式x(PQ(x))R(a)在解释I下的真值。解：R(a)总为1,故x(PQ(x))R(a)为x(PQ(x))1＝1都能做对最后答案。有的学生将D的每个元素代入求得，有的学生做法如上。9（2）.指出谓词公式xy(P(x,y)Q(y,z))xR(x,y)的指导变元、量词的辖域、约束变元和自由变元。解：第一个x是指导变元，相应的辖域是y(P(x,y)Q(y,z))；第二、四个x是约束变元；第三个x是指导变元，相应的辖域是R(x,y)；第一个y是指导变元，相应的辖域是：(P(x,y)Q(y,z))；第二，三个y是约束变元；第四个y是自由变元；第一个z是自由变元。即：指导变元：第一个x，第三个x，第一个y辖域：y(P(x,y)Q(y,z))，R(x,y)，(P(x,y)Q(y,z))约束变元：第二个x，第四个x，第二个y，第三个y自由变元：第四个y，第一个z约一半学生错在第一个X为指导变元时的辖域，错写为(P(x,y)Q(y,z))，其余的正确。10（1）.求谓词公式xy(P(x,y)Q(x,y))xyR(x,y)的前束范式。解：xy(P(x,y)Q(x,y))xyR(x,y)=xy(P(x,y)Q(x,y))uvR(u,v)=xy(P(x,y)Q(x,y)(Q(x,y)P(x,y))uvR(u,v)=xy(((P(x,y)Q(x,y))(Q(x,y)P(x,y))uvR(u,v))=xyuv((P(x,y)Q(x,y))(Q(x,y)P(x,y))R(u,v))三分之一的学生出错。1.不化简2.没有改变相同的量词，并将相同的量词合并。3.计算错误。11.构造x(P(x)Q(x)),x(Q(x)R(x)),xR(x)xP(x)的形式证明。2解：①xR(x)前提引入②R(e)①US规则③x(Q(x)R(x))前提引入④Q(e)R(e)③US规则⑤Q(e)②④析取三段论⑥x(P(x)Q(x))前提引入⑦P(e)Q(e)⑥US规则⑧P(e)⑤⑦析取三段论⑨x(P(x))⑧EG规则此题出错较多：1.误用量词的推理规则，如①xR(x)前提引入②R(x)①US规则2.形式证明的格式不规范15.证明下面的推理：“每个科研工作者都是努力工作的。每个努力工作而又聪明的人都取得事业的成功。某个人是科研工作者并且聪明。所以，某人事业取得成功。”解：命题符号化，个体域为人。定义谓词P(x):x是科研工作者，Q(x):x努力工作，R(x):x是聪明的人，M(x):x事业取得成功.前提：x(P(x)Q(x)),x((Q(x)R(x))M(x)),x(P(x)R(x))结论:xM(x)构造形式证明①x(P(x)R(x))前提引入②P(a)R(a)①ES规则③P(a)②化简规则④x(P(x)Q(x))前提引入⑤P(a)Q(a)④US规则⑥Q(a)③⑤假言推理规则⑦R(a)Q(a)③附加规则⑧x((Q(x)R(x))M(x))前提引入⑨(Q(a)R(a))M(a)⑧US规则⑩M(a)⑦⑨假言推理规则⑪xM(x)⑩EG规则基本正确补充：1.用谓词公式表达语句“本班的学生都已学过微积分”，个体域分别取ECNU的学生集合和本班的学生集合。解：个体域取ECNU的学生集合:P(x):x是本班学生，G(x):x学过微积分。则x(P(x)G(x))个体域取本班的学生集合:P(x):x学过微积分，则xP(x)个体域取ECNU的学生集合时出错较多：H(x):X是ECNU的学生x(h(x)G(x))32.用谓词公式表达语句“班上无人恰给另外两个同班同学发过电子邮件”，个体域取本班学生的集合。解：p(x,y)：x给y发过电子邮件，论域为班上学生。原题量词表达为：xyz(p(x,y)p(x,z)(y≠z)(x≠z)(x≠y)w(p(x,w)((w=y)(w=z))))正确解答此题的学生很少。大都只表达了“给另个两个同学发过电子邮件”，忽略“恰恰”。P812.集合X={a,b,c}上的一个关系R的关系矩阵如下（左），请写出这个关系。（注：矩阵的第1、2、3行以及第...