东北大学：《离散数学》课程教学资源（PPT课件讲稿）期末总复习（各章复习）

例如(1)金子闪光,但闪光的不一定都是金子 设:G(x):x是金子,F(x):x闪光 Vx(G(x)>F(x)入Vx(F(x)→>G(x) Vx(G(x)→>F(x))Ax(F(x)∧_G(x)) (2)没有大学生不懂外语. S(x):x是大学生F(x)∷x外语.K(x,y):x懂得y 3x s(x)Vy(F(y-K(x, y)) Vx(S(x)y ( FyAK(x, y)) (3)有些液体可以溶解所有固体 F(x)∷x是液体S(x)x是固体D(xy):x可溶解y x(F(x)∧y(S(y)→>D(x,y) (4每个大学生都爱好一些文体活动。 S(x):x是大学生,Lx2y):x爱好y,C(x):x是文娱活动, P(x):x是体育活动)Vx(S(x)→3y(C(y)VP(y)入L(x,y)

例如⑴金子闪光,但闪光的不一定都是金子. 设: 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)) ⑵没有大学生不懂外语. 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))) ⑶有些液体可以溶解所有固体. F(x):x是液体.S(x):x是固体.D(x,y):x可溶解y. x(F(x)y(S(y)D(x,y))) ⑷每个大学生都爱好一些文体活动。 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)))

3掌握常用的等价公式和永真蕴涵式包括: 带量词的公式在论域内展开式,量词否定,量词辖域扩充, 量词分配公式 设论域为{a1,a2,,an},则 1).VxA(x)分A(a1)∧A(a2)∧ ∧A(an) 2).丑xB(x)分B(a1)∨B(a2)∨..VB(an2 1).-xA(x)彐x-A(x 2).一彐xA(x)冷→x-A(x) 1).xA(x)∨B分Vx(A(x)VB) 2).xA(x)∧B分→x(A(x)∧B 3).彐xA(x)∨B彐x(A(x)∨B) 4).彐xA(x)∧B分彐x(A(x)∧B) 5).B→∨xA(x)分x(B→A(x)

3.掌握常用的等价公式和永真蕴涵式.包括: 带量词的公式在论域内展开式,量词否定,量词辖域扩充, 量词分配公式. 设论域为{a1,a2,....,an}，则 1). xA(x)A(a1)∧A(a2)∧......∧A(an) 2). xB(x)B(a1)∨B(a2)∨......∨B(an) 1). xA(x)xA(x) 2). xA(x)xA(x) 1). xA(x)∨Bx(A(x)∨B) 2). xA(x)∧Bx(A(x)∧B) 3). xA(x)∨Bx(A(x)∨B) 4). xA(x)∧Bx(Ａ(x)∧B) 5). B→xA(x)x(B→A(x))

6).B→彐xA(x)冷彐x(B→A(x) 7).∨xA(x)→B分→3x(A(x)→B) 8).彐xA(x)→B分Vx(A(x)→B 1).彐x(A(x)VB(x))令彐xA(x)∨彐xB(x) 2).Yx(A(x)∧B(x)分xA(x)∧∨xB(x) 3).彐x(A(x)∧B(x))→彐xA(x)∧彐xB(x) 4).YxA(x)∨xB(x)→Vx(A(x)VB(x) 4会用等价公式求谓词公式的真值(如P66题(3 例设论域为{1,2},A(x2y):x+y=xy,求一xByA(x,y)的真值 xyA(x,y)→玉xVyA(xy) 冷y→A(1y)yyA(2,y) 冷>(A(1,1)∧-A(1,2)(-A(2,1)入_A(2,2) (T∧T(T∧F)分冷T

6). B→xA(x)x(B→A(x)) 7). xA(x)→Bx(A(x)→B) 8). xA(x)→Bx(A(x)→B) 1). x(A(x)∨B(x))xA(x)∨xB(x) 2). x(A(x)∧B(x))xA(x)∧xB(x) 3). x(A(x)∧B(x))xA(x)∧xB(x) 4). xA(x)∨xB(x)x(A(x)∨B(x)) 4.会用等价公式求谓词公式的真值.(如P66题(3)) 例设论域为{1,2},A(x,y):x+y=xy, 求xyA(x,y)的真值. xyA(x,y) xyA(x,y) yA(1,y)yA(2,y) (A(1,1)A(1,2))(A(2,1)A(2,2)) (TT)(TF) T

5将下面谓词公式写成前束范式 VxF(xy)→彐yG(y)-VxH(x,y) (-√xF(x,y)y3yG(!y)∨xH(xy)(去 台∨xF(xy)∧3yG(y)xH(x2y)(摩根) 台∨xF(xy)∧y-G(y)∨xH(xy)(量词否定) 兮∨xF(x,)∧y-G(y) vtH(,1)(变元换名) 兮∨xyvt(F(x,z)∧-G(y)vH(t,z)(辖域扩充)

*5.将下面谓词公式写成前束范式 (xF(x,y)yG(y)xH(x,y)  (xF(x,y)yG(y)xH(x,y) (去) xF(x,y) yG(y) xH(x,y) (摩根) xF(x,y) yG(y) xH(x,y) (量词否定) xF(x,z) yG(y) tH(t,z) (变元换名) xyt((F(x,z) G(y) H(t,z)) (辖域扩充)

6.熟练掌握谓词逻辑推理 1)注意使用ES、US、EG、UG的限制条件,特别是ES,UG 2)对于同一个客体变元,既有带∨也有带彐的前提,去量 词时,应先去彐后去,这样才可以特指同一个客体c 3)去量词时,该量词必须是公式的最左边的量词,且此 量词的前边无任何符号,它的辖域作用到公式末尾。 下面的作法是错误的: 正确作法: (1)xP(x)→彐xQ(x)P (1)yxP(x)→彐xQ(x)P (2)P(c)*3xQ(x)US(1)(2)/xP(x)V3x Q(x)T(1)E 或(2)xP(x)→Q()E)(3)彐x-P(x)VxQ(x)T(2)E 实际上x的辖域扩充后(4)3x(-P(x)VQ(x)T()E 量词改成为彐x (5)-P(c)VQ(c) ES(4 (6)P(c)→Q(c) T5E

6.熟练掌握谓词逻辑推理. 1).注意使用ES、US、EG、UG的限制条件,特别是ES,UG 2).对于同一个客体变元，既有带也有带的前提，去量 词时，应先去后去，这样才可以特指同一个客体 c. 3).去量词时，该量词必须是公式的最左边的量词，且此 量词的前边无任何符号，它的辖域作用到公式末尾。 下面的作法是错误的： 正确作法: ⑴ xP(x)→xQ(x) P ⑴ xP(x)→xQ(x) P ⑵ P(c)→xQ(x) US⑴ ⑵ xP(x)∨xQ(x) T ⑴E 或⑵xP(x)→Q(c)ES⑴ ⑶ xP(x)∨xQ(x) T ⑵E 实际上x的辖域扩充后 ⑷x(P(x)∨Q(x)) T⑶ E 量词改成为x ⑸ P(c)∨Q(c) ES⑷ ⑹ P(c)→Q(c) T⑸E