离散数学第二章 谓词逻辑 习题课.ppt

离散数学第二章谓词逻辑习题课一.命题符号化60页(2)n(x)(J(x)→L(x))n(x)(L(x)∧S(x))n(x)(J(x)∧O(x)∧V(x))nJ(j)∧O(j)∧V(j)n(x)(L(x)→J(x))或者(x)(L(x)∧J(x)n(x)(S(x)∧L(x)∧C(x))n(x)(C(x)∧V(x)或者(x)(C(x)→V(x))h)(x)((C(x)∧O(x))→L(x))i)(x)(W(x)∧C(x)∧H(x))j)(x)(W(x)∧J(x)∧C(x))k)(x)(L(x)→y(J(y)∧A(xy)))l)(x)(S(x)∧y(L(y)→A(xy)))习题课62页(2)(x)y((P(x)∧P(y)∧E(xy))→z(L(z)∧R(xyz)∧t((L(t)∧R(xyt))→E(tz))))(3)b)设R(x):x是实数，G(xy):x＞y(x)(R(x)→y(R(y)∧G(yx)))c)设R(x):x是实数，G(xy):x＞yf(xy)=x+yg(xy)=xy(x)yz(R(x)∧R(y)∧R(z)∧G(f(xy)g(xz)))或者(x)yz(R(x)∧R(y)∧R(z)∧G(x+yxz))习题课5)b)设N(x):x是数，A(xy):y是x的后继数(x)(N(x)∧A(x1))(6)设A(x):x是戴眼镜的B(x):x是用功的C(x):x是大学生D(x):x是大的E(x):x是厚的，F(x):x是巨著A(xy):x在看ya:那位，b:这本A(a)∧B(a)∧C(a)∧D(b)∧E(b)∧F(b)∧A(ab)补充题：1.每个人的叔叔都是他父亲的弟弟。

设：P(x):x是人，U(xy):y是x的叔叔，B(xy):x是y的弟弟，f(x)=x的父亲(x)(P(x)→y(U(xy)→B(yf(x)))2.下面是判定一个年号是否为闰年的命题:“年号能被4整除并且不能被100整除的为闰年.或者年号能被400整除的也是闰年.”设Y(x):x是年号D(xy):x可整除yR(x):x是闰年(x)(Y(x)→(((D(4x)∧D(100 x))→R(x))∨(D(400 x)→R(x))))66页(3)b)P:21Q(x):x≤3R(x):x5a:5{-236}(x)(P→Q(x))∨R(a)(P→(x)Q(x))∨R(a)(P→(Q(-2)∧Q(3)∧Q(6)))∨R(5)(T→(T∧T∧F))∨F(T→F)∨FF∨FF4)b)对约束变元换名(x)(P(x)→(R(x)∨Q(x)))∧(x)R(x)→zS(xz)y(P(y)→(R(y)∨Q(y)))∧tR(t)→uS(xu)(5)a)对自由变元代入(yA(xy)→(x)B(xz))∧(x)zC(xyz)(yA(uy)→(x)B(xv))∧(x)zC(xwz)习题课72页(2)d)论域为{12}P(1)P(2)Q(11)Q(12)Q(21)Q(22)FTTTFF(x)y(P(x)∧Q(xy))y(P(1)∧Q(1y))∧y(P(2)∧Q(2y))((P(1)∧Q(11))∨(P(1)∧Q(12)))∧((P(2)∧Q(21))∨(P(2)∧Q(22)))((F∧T)∨(F∧T))∧((T∧F)∨(T∧F))(F∨F)∧(F∨F)F6)判断下面推证是否正确。

x)(A(x)→B(x))⑴(x)(A(x)∨B(x))⑵(x)(A(x)∧B(x)⑶(x)(A(x)∧B(x))⑷((x)A(x)∧(x)B(x))⑸(x)A(x)∨(x)B(x)⑹(x)A(x)∨(x)B(x)⑺(x)A(x)→(x)B(x)第⑷步错，由⑶到⑷用的是公式：(x)(A(x)∧B(x))((x)A(x)∧(x)B(x))无此公式，而是(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)，应将⑷中的换成即：(x)(A(x)→B(x))(x)(A(x)→B(x))⑴(x)(A(x)∨B(x))⑵(x)(A(x)∧B(x)⑶(x)(A(x)∧B(x))⑷((x)A(x)∧(x)B(x))⑸(x)A(x)∨(x)B(x)⑹(x)A(x)∨(x)B(x)⑺(x)A(x)→(x)B(x)因为由公式E18P→QQ→P(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)，PQ得((x)A(x)∧(x)B(x))(x)(A(x)∧B(x))75页(1)b)(x)(yP(xy)→(zQ(z)→R(x)))(x)(yP(xy)∨(zQ(z)∨R(x)))(x)(yP(xy)∨(zQ(z)∨R(x)))(x)(yP(xy)∨z(Q(z)∨R(x)))(x)yz(P(xy)∨(Q(z)∨R(x)))(2)c)(x)P(x)→(x)(zQ(xz)∨zR(xyz))(x)P(x)∨(x)(zQ(xz)∨zR(xyz))(x)P(x)∨(x)(zQ(xz)∨zR(xyz))(x)P(x)∨u(zQ(uz)∨tR(uyt))(x)uzt(P(x)∨(Q(uz)∨R(uyt)))(x)uzt(P(x)∨Q(uz)∨R(uyt))此式既是前束析取范式，也是前束合取范式。

79页(2)a)用CP规则证明(x)(P(x)∨Q(x)(x)P(x)∨(x)Q(x)因为(x)P(x)∨(x)Q(x)(x)P(x)→(x)Q(x)⑴(x)P(x)P(附加前提)⑵(x)P(x)T⑴E⑶P(a)ES⑵⑷(x)(P(x)∨Q(x)P⑸P(a)∨Q(a)US⑷⑹Q(a)T⑶⑸I⑺(x)Q(x)EG⑹⑻(x)P(x)→(x)Q(x)CP习题课3)a)所有有理数是实数，某些有理数是整数，因此某些实数是整数设Q(x):x是有理数R(x):x是实数I(x):x是整数(x)(Q(x)→R(x))(x)(Q(x)∧I(x))(x)(R(x)∧I(x))⑴(x)(Q(x)∧I(x))P⑵Q(a)∧I(a)ES⑴⑶Q(a)T⑵I⑷I(a)T⑵I⑸(x)(Q(x)→R(x))P⑹Q(a)→R(a)US⑸⑺R(a)T⑶⑹I⑻R(a)∧I(a)T⑷⑺I⑼(x)(R(x)∧I(x))EG⑻习题课b)任何人如果他喜欢步行，他就不喜欢乘汽车；每个人或者喜欢乘汽车或者喜欢骑自行车有的人不爱骑自行车，因此有的人不爱步行设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⒀习题课c)每个大学生不是文科生就是理工科生，有的大学生是优等生，小张不是理工科生，但他是优等生，因此如果小张是大学生，他就是文科生。

设A(x):x是大学生B(x):x是文科生C(x):x是理工科生，D(x):x是优等生a:小张(x)(A(x)→(B(x)→C(x)))(x)(A(x)∧D(x))C(a)∧D(a)A(a)→B(a)习题课(x)(A(x)→(B(x)→C(x)))(x)(A(x)∧D(x))C(a)∧D(a)A(a)→B(A)⑴A(a)P(附加前提)⑵(x)(A(x)→(B(x)→C(x)))P⑶A(a)→(B(a)→C(a))US⑵⑷B(a)→C(a))T⑴⑶I⑸C(a)∧D(a)P习题课补充题：小杨、小刘和小林为高山俱乐部成员，该俱乐部的每个成员是个滑雪者或登山者没有一个登山者喜欢雨而所有滑雪者都喜欢雪凡是小杨喜欢的，小刘就不喜欢小杨喜欢雨和雪试证明该俱乐部是否有个是登山者而不是滑雪者的成员如果有，他是谁？设：M(x):x是高山俱乐部成员H(x):x是滑雪者D(x):x是登山者L(xy):x喜欢ya:小杨；b:小刘；c:小林；d:雨；e:雪M(x):x是高山俱乐部成员H(x):x是滑雪者D(x):x是登山者L(xy):x喜欢ya:小杨；b:小刘；c:小林；d:雨；e:雪。

命题符号化为：M(a)M(b)M(c)(x)(M(x)→(H(x)∨D(x)))(x)(D(x)∧L(xd))(x)(H(x)→L(xe))(x)(L(ax)→L(bx))L(ad)∧L(ae)⑴L(ad)∧L(ae)P⑵L(ae)T⑴⑶(x)(L(ax)→L(bx))P⑷L(ae)→L(be))US⑶⑸L(be))T⑵⑷I11⑹(x)(H(x)→L(xe))P⑺H(b)→L(be))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⑻⒀谓词逻辑解决这个问题的方法：在表示命题时，既表示出主语，也表示出谓语，就可以解决上述问题这就提出了谓词的概念令S(x)表示x是大学生，a:小张，b:小李命题P表示成S(a):小张是大学生命题Q表示成S(b):小李是大学生从符号S(a)、S(b)可看出小张和小李都是大学生的共性谓词逻辑令N(x):x是自然数I(x):x是整数表示所有的A:(x)(N(x)→I(x))B:N(8)C:I(8)N(8)I(8)推理如此实现：N(8)→I(8)符号S(x)、N(x)、I(x)就是所谓的谓词。

习题选讲—命题符号化1.在一阶逻辑中将下列命题符号化1）每个人都有心脏2）有的狗会飞3）没有不犯错误的人4）发光的不都是金子5）一切人都不一样高6）并不是所有的汽车都比火车快7）没有一个自然数大于等于任何自然数8）有唯一的偶素数9）不管黑猫白猫，抓住老鼠就是好猫10）对平面上任意两点，有且仅有一条直线通过这两点习题选讲—命题符号化解：由于没指出个体域，故用全总个体域（1）每个人都有心脏本命题的含义：对于每一个x，如果x是人，则x有心脏因而应首先从宇宙间的一切事物中，将人分离出来，这就必须引入特性谓词令M(x):x是人，H(x):x有心脏命题符号化为：(x)(M(x)→H(x))如果将其中的→改为∧，即(x)(P(x)∧H(x))，它表示的意思是：“对于每个x，x是人且x有心脏”这是一个假命题，而“每个人都有心脏”是真命题这说明将命题“每个人都有心脏”符号化为(x)(P(x)∧H(x))是错误的习题选讲—命题符号化（2）有的狗会飞命题的意思是：存在一个x，使得x是狗，并且x会飞设D(x)：x是狗，F(x)：x会飞命题符号化为：(x)(D(x)∧F(x))如果将其中的∧改为→，即(x)(D(x)→F(x))，如果用a表示某只猫，则D(a)为假，因而，D(a)→F(a)为真，所以(x)(D(x)→F(x))为真，而“有的狗会飞”为假，这说明将“有的狗会飞”符号化为(x)(D(x)→F(x))是错误的。

3）没有不犯错误的人命题的意思是：①存在不犯错误的人是不可能的。