离散数学复习指导Ⅰ
命题逻辑部分 一 学习要求
1．理解命题、联结词的含义，掌握命题的符号化；
2．理解命题公式的赋值，能求出公式的真值表，判断公式的类型； 3. 理解公式等值的定义,记住一些基本等值式,能进行等值演算;
4. 体会公式的主范式与公式赋值之间的关系,能利用等值演算求出范式; 5. 理解公式的蕴涵及推理的含义及联系,记住一些基本的推理规则,能用演绎 推理方法进给出推理证明; 二 范例
例1 将下列命题符号化 ⑴小王聪明但不用功；
⑵ 说数理逻辑枯燥无味或毫无价值，那是不对的； ⑶ 你不及格就要补考。 ⑷ 不经一事，不长一智；
解：⑴ 设p：小王聪明，q：小王用功，则该命题可符号化为：p??q。
⑵ p：数理逻辑枯燥无味，q：数理逻辑毫无价值，则：?(p?q)。
⑶ p：你及格了；q：你要参加补考，则：?p?q。 ⑷ p：经一事；Q：长一智，则：?p??q。 ⑸ 这是简单命题，则p：李卫与李星是兄弟。
例2 求命题公式(p?q)?r的主析取范式和主合取范式，指出公式的成真赋值和成假赋值，并判断公式的类型。
解：(p?q)?r?((p?q)?(q?p))?r
?((p?q)?r)?((q?p)?r) ?(?p?q?r)?(?q?p?r)
?M2?M4 （主合取范式） ?m0?m1?m3?m5?m6?m7
??(0,1,3,5,6,7) (主析取范式)
公式的成真赋值为：000，001，011，101，110，111 成假赋值为：010，100 公式为非重言式的可满足式 。
例3 构造下面推理的证明：
前提：p??q,p?r,q?s 结论：s?r 证：(1) p??q P;
(2) p T(1)化简规则;
(3) ?q T(1)化简规则 (4) p?r P;
(5) r T(3)(4)假言推理; (6) q?s P; (7) s T(3)(6)析取三段论;
(8) s?r T(5)(7)合取式.
例4. 先将下列相关命题符号化,给出推理证明
如果4是偶数,则2不能整除5. 或者7不是素数或者2整除5. 7是素数.因此4不是偶数.
解: 设p: 4是偶数; q: 2能整除5; r: 7是素数; s: 2整除5,则
前提： p??q,?r?q,r, 结论：?p. 证明: (1) ?(?p) 结论之否定; (2) p T(1)等值式;
(3) p??q P;
(4) ?q T(2)(3)假言推理; (5) ?r?q P;
(6) ?r T(4)(5)析取三段论;
(7) r P;
(8) r??r T(6)(7)合取式.
谓词逻辑部分 一 学习要求
1．理解谓词逻辑的三要素，掌握命题的符号化；
2．理解谓词公式中量词的辖域、约束关系,及公式的解释，能求出在一个解释下公式的
真值，能判断公式的类型；
3. 理解公式等值的定义,记住谓词公式的特殊的基本等值式,能进行等值演算; 4. 理解前束范式的定义,能利用等值演算求出公式的前束范式;
5. 理解公式的蕴涵及推理的含义及联系,特别记住谓词中的一些推理规则,能用演绎 推理方法进给出推理证明; 二 范例
例1 将下列命题符号化
⑴ 不是所以的人都要补考,但就有人要补考. ⑵ 天下乌鸦一般黑。
⑶ 不是所有火车都比汽车快，但有的火车比所有汽车快。 解：⑴P(x)：x是人； Q(x)：x要补考，则： ??x(P(x)?Q(x))??x(P(x)?Q(x)) （注意特性谓词的用法） ⑵ 设D={乌鸦}，P(x)：x是黑的，则：?xP(x) （本题使用了论域）
⑶P(x)：x是火车；Q(x)：x是汽车；R(x,y)：x比y快，则：
??x?y((P(x)?Q(y))?R(x,y))??x(P(x)??y(Q(x)?F(x,y))
或：??x(P(x)??y(Q(y)?R(x,y)))??x(P(x)??y(Q(x)?F(x,y))。
例2 设解释I如下:
D={2,3},f(2)?3,f(3)?2,F(2,2)?1,F(2,3)?0,F(3,2)?1,F(3,3)?0. 试求出下列公式在解释I下的真值.
⑴ ?x?yF(x,f(y)) ⑵?xF(x,f(x))??x?yF(x,y) 解: 在解释I下:
⑴ ?x?yF(x,f(y))??yF(2,f(y))??yF(3,f(y))
?(F(2,f(2))?F(2,f(3)))?(F(3,f(2))?F(3,f(3))) ?(F(2,3)?F(2,2))?(F(3,3)?F(3,2)) ?(0?1))?(0?1) ?1
⑵?xF(x,f(x))??x?yF(x,y)
?(F(2,f(2))?F(3,f(3)))?(?yF(2,y)??yF(3,y))?(F(2,3)?F(3,2))?(F(2,2)?F(2,3))?(F(3,2)?F(3,3)) ?(0?1)?((1?0)?(1?0)) ?1
例3 求公式?xF(x)??yQ(y)的前束范式.
解: ?xF(x)??yQ(y)?(?xF(x)??yQ(y))?(?yQ(y)??xF(x))
?(??xF(x)??yQ(y))?(??yQ(y)??xF(x)) ?(?x?F(x)??yQ(y))?(?y?Q(y)??xF(x))?(?x?F(x)??xQ(x))?(?y?Q(y)??xF(x)) ??x(F(x)?Q(x))??y?x(Q(y)?F(x)) ??x(F(x)?Q(x))??y?z(Q(y)?F(z))
??x?y?z((F(x)?Q(x))?(Q(y)?F(z))) (前束范式)
例4 构造推理证明，前题: ?x(F(x)??H(x))，?x(H(x)?G(x))
结论:?xF(x)??yG(y)
证明:(1) ?xF(x) 附加前题; (2) F(a) T(1) EI规则; (3) ?x(F(x)??H(x)) P;
(4) F(a)??H(a) T(3) UI规则;
(5) ?H(a) T(2)(4)假言推理规则; (6) ?x(H(x)?G(x)) P;
(7) H(a)?G(a) T(6) UI规则; (8) G(a) T(5)(7)析取三段论. (9) ?yG(y) T(8) EG规则.
集合论部分 一 学习要求
1．领会集合的各种运算，掌握各种集合式的谓词演算的证明方法；
2．领会序偶及笛卡积的定义,理解二元关系的定义,掌握及关系的运算(定义域、值域、
逆、复合、闭包)；掌握关系的三种表示方法(集合、关系图、关系矩阵). 3. 领会关系的性质,能判断或证明一个关系所具有的性质, 4. 理解等价关系及划分的定义，掌握等价类及集合商集的求法，理解等价关系与划分的关系。
5. 理解偏序关系的定义，特别注意偏序集中元素的可比性（“大小”的含义），能画出哈斯图，并能求出集合中的特殊元及集合的界；
⒍ 理解函数的定义，掌握函数的复合及逆运算，领会特殊函数（单射，满射，双射）的概念。 二 范例
例1 已知E?{1,2,3,4,5,6,7,10,12}，A?{x2?x?10}，B?{x5?x?11}，求： ⑴ ~A；A?B；A?B ；A?B；A?B
⑵A；?（B）；B??A?B?；
3，4，5，6，7}，B?{6，7，10} 解：A?{2，，10，12}；A?B?{6，7}；A?B?{2，3，4，5，6，7，10} ； ⑴ ~A?{13，4，5，10} A?B?{2，3，4，5}；A?B?{2，⑵A?6；?（B）?{?，{6}，{7}，{10}，{6，7}，{6，10}，{7，10}，{6，7，10}}；
B??A?B??{6，6，6，7，7，6，7，7，10，6，10，7}
例2 已知A?{a,b,c,d},R?{a,a,a,b,b,c,b,d},
S?{a,b,a,d,b,d,d,c}?IA, 求:
⑴ R; R,R?S , S?R ⑵ r(R),s(R),t(R),rst(R) 解: ⑴ R?1?122={a,a,b,a,c,b,d,b}; R={a,b,a,c,a,d}
2R?S={a,a,a,b,a,d,b,c,b,d}
R?S={a,b,a,d,a,c,a,d} ⑵ r(R)={a,b,b,c,b,d}?IA
s(R)?{a,a,a,b,b,a,b,c,c,b,b,d,d,b}
2t(R)?{a,a,a,b,b,c,b,d,a,c,a,d}
rst(R)?{a,b,b,ab,c,c,b,b,d,d,b,a,c,c,a,a,d,d,a}?IA
例3 已知X={a,b,c},给出X上的所有等价关系。
解:X的划分其有五种:
S1={{a,b,c}}, S2={{a,b},{c}},S3={{a,c},{b}},S4={{a},{b,c}}, S5={{a},{b},{c}},
因为X上划分与等价关系一一对应,故x上共有五个等价关系，它们是：
R1＝{,
例4 已知偏序集〈X,R〉,其中X={a,b,c,d,e}, Y={d,e},
R的关系矩阵为
求：(1).用集合的列举法写出R
(2).画出R的哈斯图；
(3).找出X的极大元、极小元、最大 元、最小元； (4).找出Y的上界、下界、最小上界、最大下界。
?1?1?MR??1??1??10000?1000??1100??0011?0001??解:(1). R?{c,b,c,a,b,a,d,,e,d,a,e,a}?IA (2).略
(3)．X的极大元:a; 极小元:c，d ; 最大元:a ; 最小元: 无.
(4). Y的上界e,a; 下界d ; 最小上界e; 最大下界d。
例5 ⑴ 实数集R上的函数f(x)?x?3,g(x)?3x?5,
⑵ A?{a,b,c} , A上函数f?{a,b,b,c,c,a},g?{a,c,b,b,c,a} 判断f是否单射、满射、双射,并求g?f, (f?g)?1,g?f解: ⑴f(x)?x?3 为双射, g(x)?3x?5为双射
?1.
g?f(x)?f(g(x))?f(3x?5)?3x?8,
x14?, 33 f?1(x)?x?3 , g?f?1(x)?f?1(g(x))?f?1(3x?5)?3x?2. ⑵f,g均为双射
f?g(x)?g(f(x))?g(x?3)?3x?14 , (f?g)?1(x)?g?f?{a,a,b,c,c,b},
f?g?{a,b,b,a,c,c}, (f?g)?1?{b,a,a,b,c,c} f?1?{b,a,c,b,a,c}, g?f?1?{a,b,b,a,c,c}.
代数结构部分 一 学习要求
1．理解二元运算的含义及代数系统中的运算的性质及特殊元（单位元、零无、逆元）的定义；
2．了解代数系统的同态与同构的定义；知道满同态下的保持性;
3. 记住半群的定义,掌握特殊半群（独异点、循环半群、可交换半群等）的证明方法。 4. 记住群的定义,了解群的性质，掌握群的证明方法（从定义出发）。 ; 二 范例
例1. Z为整数集，S={x|x?Z?(?5?x?10)},在S 上定义二元运算*:
x*y=min{x,y},证明
∴*是二元运算，
⑵ 对任意x,y,z?S
∵(x*y)*z=(min{x,y})*z=min{x,y,z}
x*(y*z)= z * (min{x,y}) =min{x,y,z} ∴*运算满足结合律，
∵x*10=10*x=x
∴10是单位元，
⑷ x*y=min{x,y}= min{y,x}=y*x, ∴*运算满足交换律； 故
例 2．（10分） Zn={0,1,2,?,n-1 },在Zn上定义二元运算·:
x·y=(x+y) mod n, 其中+、-是普通加法、减法，证明
证(1)对任意x,y∈Zn, 因
x·y=(x+y) mod n∈Zn
所以·是二元运算,
(2) 对任意x,y,z∈Zn,因
(x·y) ·z=((x+y) mod n) ·z=(x+y+z) mod n
x·(y·z)=x·((y+z) mod n)=(x+y+z) mod n 有(x·y) ·z= x·(y·z) 所以·满足结合律,
(3) 对任意x, 因
0·x=x·0=x
所以,0是单位元; （2分） (4) 0?1?0,
对任意x∈Zn且x?0时,
x·(n-x)=(n-x) ·x=0 所以 x?1?n?x
由(1)(2(3)(4)知
（
