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

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

例如⑴金子闪光,但闪光的不一定都是金子. 设: 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).xA(x)台→A(a1)∧A(a2)∧ ∧A(a 2).彐xB(x)÷B(a)∨B(a2)V..B(an 1).-xA(x)分彐x-A(x) 2).-3xA(x)冷x-A(x) ) VxA(xVBEVX(A (XVB 2).xA(x)∧B分→Vx(A(x)∧B) 3).彐xA(x)∨B<彐x(A(x)∨B) 4).彐xA(x)∧B<→3x(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)分3x(B→A(x)) 7).VxA(x)→B→彐x(A(x)→B) 8).彐xA(x)→B→Vx(A(x)→B) 1).彐x(A(x)VB(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).YxA(x)∨YxB(x)→x(A(x)VB(x)) 4会用等价公式求谓词公式的真值(如P66题3) 例设论域为{1,2},A(x,y):xty=xy,求一∨xyA(x,y)的真值 VxyA(x,y)令→彐xyA(x,y) 冷y-A(1,y)yvyA(2,y) 分(_A(1,1)∧_A(1,2)V(A(2,1)∧-A(2,2) 冷(TTv(TAF分→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将下面谓词公式写成前束范式 (xF(x,y)→>yG(y)→>VxH(x,y) 台(-YxF(xyv3yG(yxH(xy)(去少) 台∨xF(x2y)∧3yG(y)vxH(x2y)(摩根) 台→VxF(x2y)Vy-G(y)xH(x2y)(量词否定) 兮xF(x,z)∧Vy-G(y)VtH(t,x)(变元换名) 兮xyvt(F(x,z)∧_G(y)√H(〔,)(辖域扩充)

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

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