第一章命题逻辑基本概念课后练习题答案
1、是命题的为（1）、（2）、（3）、（6）、（7）、（10）、（11）、（12）、（13）
是简单命题的为（1）、（2）、（7）、（10）、（13）
是真命题的为（1）、（2）、（3）、（10）、（11）
真值现在不知道的为（13）
2、3略
4.将下列命题符号化，并指出真值：
（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；
（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；
（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；
（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；
（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.
5.将下列命题符号化，并指出真值：
（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；
（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；
（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；
（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；
（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；
6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；
（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.
7.因为p与q不能同时为真.
8. 设p:2<1，q:3<2
(1) p→q，真值为1
(2) p→┐q，真值为1
(3) ┐q→p，真值为0
(4) ┐q→p，真值为0
(5) ┐q→p，真值为0
(6) p→q，真值为1
9.（2）、（6）真值为0，其余为1
10. （1）、（4）真值为0，其余为1
11、12略
13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：
（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；
（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；
（3）p q，真值为1；
（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.
14略
15、p、q为真命题，r为假命题，（4）的真值为1，其余为0
16、（4）的真值为1，其余为0
17、真
18、小王会唱歌，小李不会跳舞
19、（1）（4）（6）为重言式，（3）为矛盾式，其余为非重言式的可满足式
20、（1）01,10,11
（2）00,10,11
（3）00,01,10
（4）01,10,11
21、（1）011；（2）010,110,101,100；（3）100,101
22、无成真赋值
23、无成假赋值
24、均为重言式
25、均为矛盾式
26、前者为矛盾式，后者为重言式
27略；28不能；29略；30不能
返回
第二章命题逻辑等值演算
本章自测答案
3、（1）矛盾式；（2）重言式；（3）可满足式
5.(1)：∨∨,成真赋值为00、10、11；
(2)：0，矛盾式，无成真赋值；
(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；
7.(1)：∨∨∨∨?∧∧；
(2)：∨∨∨?∧∧∧；
8.(1)：1?∨∨∨,重言式；
(2)：∨?∨∨∨∨∨∨；
(3)：∧∧∧∧∧∧∧?0，矛盾式.
11.(1)：∨∨?∧∧∧∧；
(2)：∨∨∨∨∨∨∨?1；
(3)：0?∧∧∧.
12.A?∧∧∧∧?∨∨.
第三章命题逻辑的推理理论
本章自测答案
6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系
(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确
(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为
(p→q)∧p→q(记作*1)
在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.
可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即
(p→q)∧p→q ? q
(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为
(p→q)∧p→q(记作*2)
可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等
(p→q)∧q→p
?(┐p∨q) ∧q →p
?q →p
?┐p∨┐q
??∨∨
从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.
9.设p:a是奇数，q:a能被2整除，r:a：是偶数
推理的形式结构为
(p→q┐)∧(r→q)→(r→┐p) (记为*)
可以用多种方法证明*为重言式，下面用等值演算法证明：
(p→┐q)∧(r→q)→(r→┐p)
?(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律)
?(p∨q)∨(┐p∧r)∨┐q∨┐r
?(┐p∨q)∨(┐q∧┐r)
?┐p∨(q∨┐q)∧┐r
?1
10.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.
推理的形式结构为
(p→q)∧┐p→(┐q∧┐r)
?(┐p∨q) ∧┐p→(┐q∧┐r)
?┐p→(┐q∧┐r) (使用了吸收律)
?p∨(┐q∧┐r)
?∨∨∨
由于主析取范式中只含有5个W极小项，故推理不正确.
11.略
14.证明的命题序列可不惟一，下面对每一小题各给出一个证明
① p→(q→r) 前提引入
② P 前提引入
③ q→r ①②假言推理
④ q 前提引入
⑤ r ③④假言推理
⑥ r∨s 前提引入
（2）证明：
①┐(p∧r) 前提引入
②┐q∨┐r ①置换
③ r 前提引入
④┐q ②③析取三段论
⑤ p→q 前提引入
⑥┐p ④⑤拒取式
（3）证明：
① p→q 前提引入
②┐q∨q ①置换
③ (┐p∨q)∧(┐p∨p) ②置换
④┐p∨(q∧p ③置换
⑤ p→(p∨q) ④置换
15.(1)证明：
① S 结论否定引入
② S→P 前提引入
③ P ①②假言推理
④ P→(q→r) 前提引入
⑤ q→r ③④假言推论
⑥ q 前提引入
⑦ r ⑤⑥假言推理
（2）证明：
① p 附加前提引入
② p∨q ①附加
③ (p∨q)→(r∧s) 前提引入
④ r∧s ②③假言推理
⑤ s ④化简
⑥ s∨t ⑤附加
⑦ (s∨t)→u 前提引入
⑧ u ⑥⑦拒取式
16.(1)证明：
① p 结论否定引入
② p→┐q 前提引入
③┐q ①②假言推理
④┐r∨q 前提引入
⑤┐r ③④析取三段论
⑥ r∧┐s 前提引入
⑦ r ⑥化简
⑧┐r∧r ⑤⑦合取
（2）证明：
①┐(r∨s) 结论否定引入
②┐r∨┐s ①置换
③┐r ②化简
④┐s ②化简
⑤ p→r 前提引入
⑥┐p ③⑤拒取式
⑦ q→s 前提引入
⑧┐q ④⑦拒取式
⑨┐p∧┐q ⑥⑧合取
⑩┐(p∨q) ⑨置换
口 p∨q 前提引入
⑾①口┐(p∨q) ∧(p∨q) ⑩口合取
17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。
前提：(p∧┐q) →r , p ,q →s , ┐s
结论：r
证明：
① q→s 前提引入
②┐s 前提引入
③┐q ①②拒取式
④ p 前提引入
⑤ p∧┐q ③④合取
⑥（p∧┐q）→r 前提引入
⑦ r ⑤⑥假言推理
18．（1）设 p：今天是星期六，q：我们要到颐和园玩，s：颐和园游人太多。
前提：p→(p∨r) , s→┐q , p , s
结论：r
证明：
① s→┐q 前提引入
② s 前提引入
③┐q ①②假言推理
④ p 前提引入
⑤ p→(q∨r) 前提引入
⑥ q∨r ④⑤假言推理
⑦r ③⑥析取三段论
（2）设p:小王是理科学生，q：小王数学成绩好，r：小王是文科学生。
前提：p→q ,┐r→p ,┐q
结论：r
证明：
① p→q 前提引入
②┐q 前提引入
③┐p ①②拒取式
④┐r→p 前提引入
⑤ r ③④拒取式
返回
第四章 (一阶)谓词逻辑基本概念
本章自测答案
4.(1)┐x(F(x)∧ ┐G(x))?x( F (x) →G (x) ),其中,F(x)：x是有理数,G(x) ：x能表示成分数；
(2)┐x( F (x) →G (x) ) ?x(F(x)∧ ┐G(x)),其中,F (x)：x在北京卖菜,G (x) ：x是外地人；
(3)x( F (x) →G (x) ),其中,F (x)：x是乌鸦,G (x) ：x是黑色的；
(4)xF(x)∧ G(x)),其中,F (x)：x是人,G (x) ：x天天锻炼身体。
因为本题中没有指明个体域,因而使用全总个体域。
5.(1)x y (F(x) ∧ G( y ) → H(x,y)),其中,F(x)：x是火车,G(y) ：y是轮船,H(x,y)：x比y快；
(2)x y (F(x) ∧ G( y ) → H(x,y)),其中,F(x)：x是火车,G(y) ：y是汽车,
H(x,y)：x比y快；
(3)┐x(F(x)∧y(G (y) → H (x,y)))?x(F(x) → y(G(y) ∧ ┐H(x,y))),其中,F(x)：x是汽车,G (y) ：y是火车,H(x,y)：x比y快；
(4)┐x(F(x)→y(G(y) → H(x,y)))?x y(F(x)∧G(y)∧┐H(x,y))),其中,F(x)：x是汽车,G(y) ：y是火车,H(x,y)：x比y慢。
6.各命题符号化形式如下：
(1)x y (x ．y = 0)；
(2)x y (x ．y = 0)；
(3)x y (y =x+1)
(4)x y(x ．y = y．x)
(5)x y(x ．y =x+ y)
(6)x y (x + y ＜0 )
9.(1)对任意数的实数x和y,若x ＜y,则x ≠ y；
(2)对任意数的实数x和y,若x–y = 0,则x＜y；
(3)对任意数的实数x和y,若x＜y,则x–y≠0；
(4)对任意数的实数x和y,若x–y ＜0,则x=y.
其中,(1)(3)真值为1(2)与(4)真值为0.
11.(1)、(4)为永真式,(2)、(6)为永假式,(3)、(5)为可满足式。
这里仅对(3)、(4)、(5)给出证明。
(3)取解释I 为：个体域为自然数集合N,F(x,y)：x ≤ y,在下,x y F(x,y)为真,而x y F(x,y)也为真(只需取x =0即可),于是(3)中公式为真,取解释为：个体域仍为自然数集合N,而F(x,y)：x = y。此时,x yF(x,y)为真(取y为x即可),可是x yF(x,y)为假,于是(3)中公式在下为假,这说明(3)中公式为可满足式。
(4)设I为任意一个解释,若在I下,蕴涵式前件xy F(x,y)为假,则
x yF(x,y)→y xF(x,y)为真,若前件x yF(x,y)为真,必存在I的个体域D1中的个体常项x0,使yF(x0,y)为真,并且对于任意
y∈,F(x0,y)为真,由于有x0∈,F(x0,y)为真,所以xF(x,y)为真,又其中y是任意个体变项,所以y xF(x,y )为真,由于I的任意性,所以(4)中公式为永真式(其实,次永真式可用第五章的构造证明法证明之)。
(5)取解释为：个体域为自然数集合,F(x,y)：x = y在下,(5)中公式为真,而将F(x,y)改为F(x,y)：x ＜ y,(5)中公式就为假了,所以它为可满足式。
13．（1）取解释为：个体域为自然数集合N，F（x）：x为奇数，G（x）：x为偶数，在下， x（F（x）∨G（x））为真命题。
取解释为：个体域为整数集合Z，F（x）：x为正整数，G（x）：x为为负整数，在下， x（F（x）∨G（x））为假命题。
（2）与（3）可类似解答。
14．提示：对每个公式分别找个成真的解释，一个成假的解释。
返回
第五章谓词逻辑等值演算与推理
本章自测答案
2.(1) (F(a)∧ F(b)∧ F (c)) ∧ (G (a )∨G (b)∨G (c))
(2) (F(a)∧ F(b)∧ F (c)) ∨ (G (a)∧G (b)∧G (c))
(3) (F(a)∧ F(b)∧ F (c)) → (G (a)∧G (b)∧G (c))
(4) (F(a ,y) ∨ F(b,y)∨ F (c,y)) → (G (a)∨G (b)∨G (c))
5.提示：先消去量词，后求真值，注意，本题3个小题消去量词时，量词的辖域均不能缩小，经过演算真值分别为：1,0,1 .
(1) 的演算如下：
x yF(x,y)
?x (F(x,3)∨F(x,4))
?(F(3,3)∨F(3,4))∧(F(4,3)∨F(4 ,4))
?1∧1?1
6.乙说得对，甲错了。本题中，全称量词的指导变元为x ，辖域为(F (x)→G(x,y)),其中F(x )与G(x,y)中的x都是约束变元，因而不能将量词的辖域缩小。
7.演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定联结词“ ┐”。演算的第二步，在原错的基础上又用错了等值式，即
(F(x)∧(G(y)→ H(x,y))) ≠(F(x) ∧G(y)→H (x,y))
12.公式的前束范式不唯一，下面每题各给出一个答案。
(1) x y (F(x)→ G(z,y));
(2) x t (x,y) → G(x,t,z));
(3) x4 ((F(,y) →G(,y))∧(G(,y) →F(x4,y)));
(4) ((F()→G(,)) → (H () → L(,)));
(5) (F(,)→(F() → ┐G (,))).
13.(1)x y(F(x) ∧G(y) ∧H(x ,y)),其中，F(x):x是汽车，G(y)：y是火车，H(x，y)：x比y跑的快；
(2)x y(F(x) ∧G(y)→H(x ,y)),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快；
(3)x y(F(x) ∧G(y) ∧┐H(x ,y)),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快；
(4)x y(F(x) ∧G(y) → ┐H(x ,y)),其中，F(x):x是飞机，G(y)：y是汽车，H(x，y)：x比y慢；
14.(1)对F(x) → xG(x)不能使用EI规则，它不是前束范式，首先化成前束范式。
F(x) → xG(x) <=> x(F(y)→G(x))
因为量词辖域(F(y)→G(x))中，除x外还有自由出现的y，所以不能使用EI规则。
(2)对x F(x) → y G(y)也应先化成前束范式才能消去量词，其前束范式为x y(F(x) →G(y)),要消去量词，既要使用UI规则，又要使用EI 规则。
(3)在自然推理系统F中EG规则为
A(c)/∴x(x)
其中c为特定的个体常项，这里A(y) = F(y) →G(y)不满足要求。
(4)这里，使F(a)为真的a不一定使G(a)为真，同样地使G(b)为真的b不一定使F(b)为真，如，F(x):x为奇数，G(x):x为偶数，显然F(3)∧G(4)为真，但不存在使F(x)∧G(x)为真的个体。
(5)这里c为个体常项，不能对F(c)→G(c)引入全称量词。
15.(1)证明：①xF(x) 前提引入
②xF(x)→ y((F(y)∨G(y)) →R(y)) 前提引入
③y((F(y)∨G(y)) →R(y) ①②假言推理
④F(c) ①EI
⑤(F(c)∨G(c))→R(c) ③UI
⑥F(c)∨G(c)④附加
⑦R(c)⑤⑥假言推理
⑧xR(x) ⑦EG
(2)证明①xF(x) 前提引入
②x((F(x)→G(a)∧R(x)))前提引入
③F(c)①EI
④F(c)→G(a)∧R(a)②UI
⑤G(a)∧R(c)③④假言推理
⑥R(c) ⑤化简
⑦F(c)∧R(c)③⑥合取
⑧x(F(x)∧R(x))⑦EG
(3)证明：①┐xF(x) 前提引入
②x┐F(x)①置换
③┐F(c)②UI
④x(F(x)∨G(x))前提引入
⑤F(c)∨G(c)④UI
⑥F(c)③⑤析取三段论
⑦xF(x) ⑥EG
(4)证明①x(F(x)∨G(x))前提引入
②F(y)∨G(y)①UI
③x(┐G(x)∨┐R(x))前提引入
④┐G(y)┐R(y)③UI
⑤x R(x) 前提引入
⑥R(y)⑤UI
⑦┐G(y)④⑥析取三段论
⑧F（y）②⑦析取三段论
⑨xF(x) ⑧UG
17．本题不能用附加前提证明法.
20.(1)与(2)均可用附加前提证明法。
22.(1)设F(x)：x为偶数，G(x):x能被2整除。
前提:x(F(x)→G(x))，F(6)
结论：G(6)
(2)设F(x)：x是大学生，G(x):x是勤奋的，a：王晓山。
前提:x(F(x)→G(x))，┐G(a)
结论：┐F(a)
23.(1)设F(x)：x是有理数，G(x):x是实数，H(x)：x是整数。
前提:x( F(x)→G(x))，x(F(x)∧H(x))
结论:x(G(x)∧H(x))
证明提示：先消存在量词。
(2)设F(x)：x是有理数，G(x):x是无理数，H(x)：x是实数，I(x)：x是虚数。
前提:x((F(x)∨G(x)) →H(x))，x( I(x)→┐H(x))
结论:x(I(x)→(┐F(x)∧┐G(x)))
证明①x(I(x)→(┐H(x))前提引入
②I(y)→H(y)①UI
③x((F(x)∨G(x))→H(x))前提引入
④(F(y)∨G(y))→H(y)③UI
⑤┐H(y)→(┐F(y)∧┐G(y))④置换
⑥I(y)→(┐F(y)∧┐G(y))②⑤假言三段论
⑦x(I(x)→(┐F(x)∧┐G(x))⑧UG
24.设F(x)：x喜欢步行，G(x)：x喜欢骑自行车，H(x)：x喜欢乘汽车。
前提:x(┐F(x)→┐G(x))，x(G(x)∨H(x))，x┐H(x)
结论:x┐F(x)
证明①x┐H(x)前提引入
②┐H(c)①UI
③x(G(x)∨H(x))前提引入
④G(c)∨H(c)③UI
⑤G(c)②④析取三段论
⑥x(F(x) →G(x))前提引入
⑦F(c)→┐G(c)⑥UI
⑧┐F(c)⑤⑦拒取式
⑨x┐F(x)⑧UG
25.设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在事业中获得成功。
前提:x(F(x)→G(x))，x(G(x)∧H(x)→I(x))，a：王大海，F(a)，H(a)
结论：I(a)
证明①F(a)前提引入
②x(F(x)→G(x))前提引入
③F(a)→G(a)②UI
④G(a)①③假言推理
⑤H(a)前提引入
⑥x(G(x)∧H(x)→I(x))前提引入
⑦G(a)∧H(a)→I(a)⑥UI
⑧G(a)∧H(a)④⑤合取
⑨I(a)⑦⑧假言推理
返回
第六章集合代数
4.(1) ③ (2) ④ (3) ⑤ (4) ⑦ (5) ⑧
6.只有(2)为真，其余为假。
9.(1) {4}；(2) {1,3,5,6}；(3) {2,3,4,5,6}；(4) {, { 1 }}；(5) {{ 4 },{1,4}}.
11.(1)； (2) {1,4,5}.
22.(2)、(3)、(4)、(8)、(10)为真，其余为假。
24.(1)为真，其余为假，因为
(P-Q) = P ? (P-Q)∩Q = P∩Q ?= P∩Q
(2)(3)(4)的反例：P ={1} ，Q ={2}
26.(A–B)∪(B–A) = (A∩B)∪(B∩A)
=(A∪B)∩(B∪B)∩(A∪A)∩(B∪A)
=(A∪B)∩E∩(A∩B)=(A∪B)-(A∩B)
27.(1)(A-B)-C = A∩B∩ C =A∩(B∪C) = A-(B∪C)
(2)(A-C)-(B-C)A∩C∩(B∩C)
=A∩C∩(B∪C) = (A∩C∩B)∪(A∩C∩C)
=A∩∩C=(A–B)- C
(3)(A–B-C=A∩B∩ C =A∩C∩B=(A–C)–B
28.(1)A∩(B∪A) = (A∩B)∪(A∩A) =(A∩B)∪
=A∩B=B∩A
(2)((A∪B)∩A) = (A∪B)∪ A
=(A∩B)∪A = A
29.由第26题有(A-B)∪(B-A)=(A∪B)–(A∩B)，故(A-B)∪(B-A)A∪B。假若x∈A∩B，那么x∈A∪B，因此x(A∪B)-(A∩B),与(A-B)∪(B-A) = (A∪B)-(A∩B) = A∪B矛盾.
30.A B?x(x∈A→x∈B)?x(x B→x A)
?x(x∈B→x∈A)?B A
A B ?A∪A A∪B ? E A∪B
而A∪B E，因此A B ?A∪B=E反之，
A∪B = E ? A∩(A∪B)= A ? A∩B = A ? A B
综合上述，A B?A∪B = E
A B ? A-B =? A-B B
反之A-B B ? (A-B)∪B B ? A∪B B ? A∪B = B ? A B
综合上述A B?A-B B
31.任取x ,x∈A ? {x} A=>{x}∈P(A)=>{x}∈P(B)=>{x}B ? x∈B
32.先证C A∧C B ? C A∩B,任取x,x∈C ? x∈C∧x∈C ? x∈A∧x∈B ? x∈A∪B,从而得到C A∪B.再证C A∩B ? C A∧C B，这可以由C A∩B A,C A∩B B得到。
33.P Q ? P-Q=? P-Q P，反之，P-Q P ?P∩(P-Q)P∩P ? P-Q=? P Q
34.令X=，则有∪Y =，即Y = .
35.A B ? A∪A B∪ A ? E B∪A因为E为全集,B∪A E综合上述B∪A=E.
36.由A∩C B∩C,A-C B-C，利用A∪C B∪D有：
(A∩C)∪(A-C) (B∩C)∪(B-C)
? (A∩C)∪(A∩C)(B∩C)∪(B∩C)
? (A∩(C∪C)(B∩(C∪C) ? A∩E B∩E ? A B
B=B∩(B∪A)=B∩(AB)=B∩(AC)
=(B∩A)∪(B∩C)=(A∩C)∪(B∩C)
=(A∪B)∩C=(A∪C)∩C=C
39.任取x，有x∈P(A) ? x A ? x B ? x∈P(B)，因此P(A)P(B).
40.(1)任取x有
x∈P(A)∩P(B)?x∈P(A)∧x∈P(B)?x A∧x B
?x A∩B?x∈P(A∩B)
(2)任取x有
x∈P(A)∪P(B)?x∈P(A)∨x∈P(B)?x A∧x B
? x A∪B?x∈P(A∪B)
注意与(1)的推理不同，上面的推理中有一步是“ ?”符号，而不是“?”符号。
(3)反例如下：A = {1}，B = {2}，则
P(A)∪P(B)= {,{1},{2}}
P(A∪B)={,{1},{2},{1,2}}
返回
第七章二元关系
本章自测答案
3.(1) 任取< x,y >,有
?x ∈A∧x ∈ B∧y ∈C∧y ∈ D
?(x ∈A∧y ∈C )∧(x∈B∧y∈D)
?
?
(2)都为假,反例如下:
A ={1},
B ={1,2},
C ={2},
D ={3}
4.(1)为假,反例如下:A ={1}, B =,C = {2};
(2)为真,证明如下:任取
?(x∈A∧y∈B)∧(x∈A∧y∈C)
?
(3)为真,令A = 即可;
(4)为假,反例如下: A =
7.={<2,2>,<3,3 >,<4,4>}
={<2 . 3>,<2,4>,<3,2>,<3,4>,<4,2>,<4,3>} ∪
L A={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}
D A={<2,2>,<2,4>,<3,3>,<4,4>}
9.(1){<1,2>,<1,4>,<1,6>,<2,1>,<2,2>,<2,4> <2,6>,<4,1>,<4,2>,<4,4>, <4,6> <6,1>, <6,2>,<6,4> <6,6>}
(2){<1,2>,<2,1>};
(3){<1,1>,<2,1>,<4,1>,<6,1>,<2,2>,<4,2>,<4,4>,<6,6>}
(4){<1,2>,<2,2>,<4,2>,<6,2>}
12.（略）
13.A∩B = {<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}, A ∩ B ={<2,4>}
domA = {1,2,3},domB = {1,2,4},dom(A ∪ B) = {1,2,3,4}
ranA = {2,3,4},ranB = {2,3,4},ran(A ∪ B) = {4},fld(A - B) = {1,2,3}
14.R R = {<0,2>,<0,3>,<1,3>}
R= {<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}
R{0,1} = {<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}
R[{1,2}] = {2,3}
18.(1)F(G∪H) = F G∪F H
任取
?t(
?t((
?t(
?
(2)和(4)类似可证
19.(2)任取y,有
y∈R[T∪W]?x(x∈T∪W∧
?x((x∈T∨x∈W)∧
?x((x∈A∧
?x(x∈T∧
?y∈R[T]∨y∈R[W]?y∈R[T]∩R[W]
(3)任取
?x∈A∧x∈B∧
?(x∈A∧
?
?
20.(1)任取
?
?
?
(2)和(1)类似可证.
21.只有对称性,因为1+1≠10,<1,1>R,R不是自反的,又由于<5,5>∈R,因此R不是反自反的,根据xRy?x+y = 10=>yRx ,可知R是对称的,又由于<1,9>,<9,1>都是属于R,因此R不是反对称的, <1,9>,<9,1>都属于R,如果R是传递的,必有<1,1>属于R.但这是不成立的,因此R也不是传递的.
22.(1)关系图如图7.15所示; (P148)
(2)具有反自反性、反对称性、传递性.
26.(1)R={<3,3>,<3,1>,<3,5>}, = {<3,3>,<3,1>,<3,5>}
(2)r(R)={<1,1>,<1,5>,<2,2>,<2,5>,<3,3>,<3,1>,<4,4>,<4,5>,<5,5>,<6,6>}
s(R)={<1,5>,<5,1>,<2,5>,<5,2>,<3,3>,<3,1>,<1,3>,<4,5>,<5,4>}
T(R)={<1,5>,<2,5>,<3,3>,<3,1>,<3,5>,<4,5>}
31.(1)R = {<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}∪；(2)R； (3)R.
32.(1)不是等价关系，因为<1,1> R，R不是自反的；
(2)不是等价关系，因为R不是传递的，1R3，3R2但是没有1R2；
(3)不是等价关系，因为<2,2> R，R不是自反的；
(4)不是等价关系，因为R不是传递的。
(5)是等价关系。
33．关系图如图7.17说示 (P151)
[a] = [b] ={a,b},[c] = [d] = {c,d}
38.现取x，有x∈A ?
?
任取
?
任取
?
? (
?
42.x,x∈A ?
x,y∈A,
?
x,y,z∈A,
?
?
?
T是传递的。
43．哈斯图如下图所示.
44.(a)偏序集
(b)偏序集
(c)偏序集
45.(a)A={a,b,c,d,e,f,g}, ={
46.哈斯图如图7.19所示 （P153）
（1）极大元e,f ；极小元a,f ；没有最大与最小元。
（2）极大元a,b,d,e ；极小元a,b,c,e ；没有最大与最小元。
返回
5、设无向图G 有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G 至少有多少个顶点？在最少顶点的情况下，写出度数列、)()(G G δ、?。 解：由握手定理图G 的度数之和为：20102=?
3度与4度顶点各2个，这4个顶点的度数之和为14度。
其余顶点的度数共有6度。
其余顶点的度数均小于3，欲使G 的顶点最少，其余顶点的度数应都取2,
所以，G 至少有7个顶点, 出度数列为3,3,4,4,2,2,2,2)(,4)(==?G G δ.
7、设有向图D 的度数列为2，3，2，3，出度列为1，2，1，1，求D 的入度列，并求)(),(D D δ?，
)(),(D D ++?δ,)(),(D D --?δ.
解：D 的度数列为2，3，2，3，出度列为1，2，1，1，D 的入度列为1,1,1,2. 2)(,3)(==?D D δ,1)(,2)(==?++D D δ,1)(,2)(==?--D D δ
14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。
(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4
解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化；
(2) 2＋2+2+2+3+3+4+4=16, 是偶数，可图化；
第一章命题逻辑的基本概念 一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）你去图书馆吗？ （7）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3≥2。 （3）只有2<1，才有3≥2。 （4）除非2<1，才有3≥2。 （5）除非2<1，否则3≥2。 （6）2<1仅当3<2。 三、将下列命题符号化 (1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。 - 1 -
四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r) （2）（p?r）∧(﹁q∨s) （3）（?p∧?q∧r）?(p∧q∧﹁r) (4)（?r∧s）→(p∧?q) 五．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 六、用真值表判断下列公式的类型： (1) p∧(p→q)∧(p→?q) (2) (p∧r) ?(?p∧?q) (2)((p→q) ∧(q→r)) →(p→r) - 2 -
第二章命题逻辑等值演算 一、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 二、用等值演算法证明下面等值式 (1)(p→q)∧(p→r)?(p→(q∧r)) (2)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) - 3 -
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，
一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）解：A={1,2} R={（1,1），（2,2）} 二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>}，既不具有对称性，又不具有反对称性 三、设A={1，2}，请给出A上的所有关系。（10分） 答：A上的所有关系: 空关系，{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<1,1>,<1,2>} {<1,1>,<2,1>} {<1,1>,<2,2>} {<1,2>,<2,1>} {<1,2>,<2,2>} {<2,1>,<2,2>} {<1,1>,<1,2>,<2,1>} {<1,1>,<1,2>,<2,2>}
{<1,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1，2，3}，问A 上一共有多少个不同的关系。（10分） 设A={1，2，3}，A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分） 证明：设公式G 的合取范式为：G ’=G1∧G2∧…∧Gn 若公式G 恒真，则G ’恒真，即子句Gi ；i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中，也就是说无论一个解释I 使这个原子为1或0 ，Gi 都取1值。 若不然，假设Gi 恒真，但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。证明：n ≤2m C ，其中2m C 表 示m 中取2的组合数。（10分） 证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G)
离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
《离散数学》+答案 一、选择或填空: 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44
命题逻辑的基本概念 一、单项选择题 1．下列语句中不是命题的有（ ）. A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。
第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试
3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?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规则 第五章
离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q
离散数学作业 软件0943 张凌晨38 李成16 1.设S={1,2,3,4}，定义S上的二元运算*如下： x*y=(xy) mod 5任意x,y属于S 求运算*的运算表. 解(xy) mod 5表示xy除以5的余数，所以运算表如下： 2.设*为Z+上的二元运算，任意x,y属于Z+， x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律？ (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元.
解 (1)由题得：4*6=min(4,6)=4； 7*3=min(7,3)=3. (2)由题分析知： *运算是取x和y之中的较小数，即x和y调换位置不影响结果，所以*在Z+上满足交换律. *运算满足结合律，因为任意x,y属于Z+，有 (x*y)*z=min(x,y)*z=min(min(x,y),z) x*(y*z)=x*min(y,z)=min(x,min(y,z)) 无论x,y,z三数中哪个较小，*运算的最终结果都是较小的那个，所以满足结合律. *运算满足幂等律，因为在Z+上任意 x*x=min(x,x)=x (3)在Z+中最小的数字是1 任意x属于Z+，有 x*1=1=1*x 所以1是*运算的零元，*运算没有单位元，也没有可逆元素的逆元。
3．令S={a,b},S 上有四个二元运算：*，&,@和#，分别由下表确定. (1)这四个运算中哪些运算满足交换律、结合律、幂等律？ (2)求每个运算的单位元、零元及所有可逆元素的逆元. 解 （1）*，&和@满足交换律；*，@和#满足结合律；#满足幂等律。 （2）*运算没有单位元和可逆元素，a 是零元；&运算的单位元为a ,没有零元,每个元素都是自己的逆元；@运算和#运算没有单位元, 零元和可逆元素.
华南理工大学网络教育学院 2014–2015学年度第一学期 《离散数学》作业 （解答必须手写体上传，否则酌情扣分） 1．设命题公式为?Q∧（P→Q）→?P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。 解：（1）真值表如下： P Q ?Q P →Q ?Q∧（P→Q）?P ?Q∧（P→Q）→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2）?Q∧（P→Q）→?P??(?Q∧(?P∨ Q)) ∨? P ?( Q∨? (?P∨ Q)) ∨? P ?? ( ?P∨ Q) ∨ (Q∨?P) ?1（析取范式） ?(?P∧? Q) ∨ (?P∧ Q) ∨ (P∧? Q) ∨（P∧ Q）（主析取范式） （3）该公式为重言式 2．用直接证法证明 前提：P∨Q，P→R，Q→S 结论：S∨R 解：（1）?S P (2)Q →S P (3) ? Q (1)(2) (4)P∨ Q P
(5)P (3)(4) (6) P → R P (7)R (5)(6) (8)?S→ R （1）（7） 即SVR得证 3．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。 令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解：前题：?x (F (x) →?G(x)), ?x (G (x) ∨H (x)) ? x ?H (x) 结论:? x ?F (x) 证：（1）? x ?F (x) p (2) ?H (x) ES(1) (3) ?x (G (x) ∨H (x))P (4)G(c) vH(c)US(3) (5)G(c) T(2,4)I (6)?x (F (x) →?G(x)), p (7)F (c) →?G(c) US(6) (8) ?F (c) T(5,7)I (9)( ? x) ?F (x) EG(8) 4．用直接证法证明： 前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。 证： （1）（?x）（C（x）∧Q（x））P (2) C (c) ∧Q（c）ES(1) (3)（?x）（C（x）→W（x）∧R（x））P
离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}}，A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={
《离散数学》课程作业（2）-------数理逻辑部分 一、 填空题 1. 将几个命题联结起来，形成一个复合命题的逻辑联结词主要有否定、 、 、 和等值。 2、命题公式G=（P ∧Q ）→R ，则G 共有 个不同的解释；把G 在其所有解释下所 取真值列成一个表，称为G 的 ；解释（?P ，Q ，?R ）或（0，1，0）使G 的真值为 。 3、 已知命题公式R Q P G →∧?=)(，则G 的析取范式是 。 4、 求公式)()(R P Q P ∧?∨∧的主析取范式 。 5、 设命题公式)(R Q P G →?→=，则使公式G 为假的解释是 、 和 。 6、在谓次词逻辑中将下面命题符号化：在北京工作的人未必都是北京人（提示：设F （x ）：x 在北京工作。G （x ）：x 是北京人。） 。 7、将公式化成等价的前束范式，=→?→???)))()((),((x R z zQ y x yP x 。 8、设谓词的定义域为},,{c b a ，将表达式)()(x xS x xR ?∧?中的量词消除，写成与之等价的 命题公式是 。 二、 单项选择题 1、下列语句中，（ ）是命题。 A ．下午有会吗？ B ．这朵花多好看呀！ C ．2是常数。 D ．请把门关上。 2、一个公式在等价意义下，下面哪个写法是唯一的（ ）。 A ．析取范式 B ．合取范式 C ．主析取范式 D ．以上答案都不对
3、设命题公式P Q P G →∧=)(，则G 是（ ）。 A. 恒假的 B. 恒真的 C. 可满足的 D. 析取范式 4、设命题公式)(), (P Q P H Q P G ?→→=→?=，则G 与H 的关系是（ ）。 以上都不是。.;.;.;.D H G C G H B H G A =?? 5、已知命题))((R Q P G ∧→?=，则所有使G 取真值1的解释是（ ）。 A （0，0，0），（0，0，1），（1，0，0） B （1，0，0），（1，0，1），（1，1，0） C （0，1，0），（1，0，1），（0，0，1） D （0，0，1），（1，0，1），（1，1，1） 6、设I 是如下一个解释，0 101),(),(),() ,(},,{b b P a b P b a P a a P b a D =， 则在解释I 下取真值为1的公式是（ ）。 ),(.);,(.);,(.);,(.y x yP x D x x xP C y x yP x B y x yP x A ??????? 7、下面给出的一阶逻辑等价式中，（ ）是错的。 )). (()(.)); (()(.); ()())()((.); ()())()((.x B A x x xB A D x A x x xA C x xB x xA x B x A x B x xB x xA x B x A x A →?=?→??=???∨?=∨??∨?=∨? 三、 计算题 1. 求命题公式?（P ∨Q ）?（P ∧Q ）的析取范式与合取范式。
02任务_000 1 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={
5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集
2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-1 1.利用素因子分解法求2545与360的最大公约数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最大公约数的方法 gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn) 360=2332515090 2545=2030515091 gcd(2545,360) =2030515090=5 2.求487与468的最小公倍数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最小公倍数的方法 lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn) ab=gcd(a, b)﹡lcm (a, b) 487是质数，因此gcd(487,468)=1 lcm(487,468)= (487*468)/1=487*468=227916 3.设n是正整数，证明：6|n(n+1)(2n+1) 证明：用数学归纳法： 归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6 归纳假设：假设当n=m时，6|m(m+1)(2m+1) 归纳推导：当n=m+1时， n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1] =(m+1)(m+2)(2m+3) = m(m+1)(2m+3)+2(m+1)(2m+3) = m(m+1)(2m+1+2)+2(m+1)(2m+3) = m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3) = m(m+1)(2m+1)+ 2(m+1)(m+2m+3) = m(m+1)(2m+1)+ 2(m+1)(3m+3) = m(m+1)(2m+1)+ 6(m+1)2 因为由假设6|m(m+1)(2m+1)成立。 而6|6(m+1)2 所以6|m(m+1)(2m+1)+ 6(m+1)2 故当n=m+1时，命题亦成立。 所以6| n(n + 1)(2n + 1) 5-2 1 已知 6x ≡7 (mod 23),下列式子成立的是( D ): A. x ≡7 (mod 23) B. x ≡8 (mod 23) C. x ≡6 (mod 23) D. x ≡5 (mod 23) 2 如果a ≡b (mod m) , c是任意整数，则（A ）：
离散数学(第2版)_在线作业_1 交卷时间：2017-01-12 10:34:32 一、单选题 1. (5分) ? A. P∨┐Q ? B. P∧┐Q ? C. ┐P ∧Q ? D. ┐P∨Q 纠错 得分：5 知识点：离散数学(第2版) 收起解析 答案A 解析 2. (5分) ? A. ? B. ? C. 命题变元P和Q的极大项M1表示( )。 设，下面集合等于A的是( )。
? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 B 解析 3. (5分) ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 4. 下面既是哈密顿图又是欧拉图的是( )。
? A. 水开了吗？ ? B. ? C. 请不要抽烟! ? D. 再过5000年，地球上就没有水了 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 D 解析 5. (5分) ? A. 2n-1 ? B. n ? C. n+1 ? D. n-1 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 D 解析 6. 下列语句中为命题的是( )。 n 个结点、m 条边的无向连通图是树当且仅当m=( )。
? A. P ∨┐Q ? B. ┐P ∨Q ? C. ┐P ∧Q ? D. P ∧┐Q 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 7. (5分) ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 B 解析 命题变元P 和Q 的极小项m 1表示( )。 公式的前束范式为( )。
离散数学作业 一、选择题 1、下列语句中哪个就是真命题(C )。 A.我正在说谎。 B.如果1+2=3,那么雪就是黑色的。 C.如果1+2=5,那么雪就是白色的。 D.严禁吸烟！ 2、设命题公式))((r q p p G →∧→=,则G 就是( C )。 A 、 恒假的 B 、 恒真的 C 、 可满足的 D 、 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ??→中的变元x ( C )。 A.就是自由变元但不就是约束变元 B.既不就是自由变元又不就是约束变元 C.既就是自由变元又就是约束变元 D.就是约束变元但不就是自由变元 4、设A={1,2,3},则下列关系R 不就是等价关系的就是(C ) A.R={<1,1>,<2,2>,<3,3>} B.R={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>} C.R={<1,1>,<2,2>,<3,3>,<1,4>} D.R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>,<2,1>, <3,1>,<3,2>} 5、设R 为实数集,映射σ=R →R,σ(x)= -x 2+2x-1,则σ就是( D )。 A.单射而非满射 B.满射而非单射 C.双射 D.既不就是单射,也不就是满射 6、下列二元运算在所给的集合上不封闭的就是( D ) A 、 S={2x-1|x ∈Z +},S 关于普通的乘法运算 B 、 S={0,1},S 关于普通的乘法运算 C 、 整数集合Z 与普通的减法运算 D 、 S={x | x=2n ,n ∈Z +},S 关于普通的加法运算 7、*运算如下表所示,哪个能使({a,b},*)成为含幺元半群( D ) b b b a a a b a * a b b b a a b a * 8( A )
离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) xF ?，在（a）中为假命题，在(b)中为真命题。 (x (2)在两个个体域中都解释为) ?，在（a）(b)中均为真命题。 xG (x 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ ? x ?? ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) F x→ ?? x ) H ( ( (x 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F x G y x→ ? ? ∧ y H )) ( , x ( ((y ( ) (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快
命题符号化为: ))) y F x G y→ ?? ∧ ? H x ) x , ( ( (y ( ( ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素=0. (c) 特定函数(x,y)=x y,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x
相关主题
文本预览