离散证明题集锦
离散证明题集锦
一．命题逻辑
例：给出┐(P∧Q)?(┐P∨┐Q)的真值表
解：
一般说来，n个命题变元组成的命题公式共有2n种真值指派。
●定理1：任何两个重言式的合取或析取，仍然是重言式。
证明：设A、B为两个重言式，则A∧B和A∨B的真值分别等于T∧T和T∨T。
●定理2：对一个重言式的同一分量都用任何一个命题公式置换，
所得命题公式仍为一个重言式。（即代入规则）
证明：由于重言式的真值与分量的真值指派无关，故对同一分量以
任何一个命题公式置换后，重言式的真值不变。
●定理3：设A、B是两个命题公式，A?B当且仅当A?B是一
个重言式。（前面已证）
证明：若A?B，则对于A、B所包含的分量的任意指派，A、B 均取相同的真值，即A?B是一个重言式；若A?B是一个重言式，即对于分量的任意指派，A、B均取相同的真值，即A?B
●定理1：设A1是命题公式A的子公式，若A1?B1，则若将A
中的A1用B1来替换，得到公式B ，则B与A等价，即A?B.(替换规则)。
证明：因为对变元的任一组指派，A1与B1真值相同，故以B1取代A1后，公式B与公式A相对于变元的任一指派的真值也必相同，所以A?B。
●证明下列命题公式(可以利用基本等价式)
Q→(P∨(P∧Q))?Q→P
(P∧Q)∨(P∧┐Q)?P
(P→Q)→(Q∨R)?P∨Q∨R
P∧┐Q∨Q?P∨Q
解：1.原式?Q→(P∨P) ∧(P∨Q) ?Q→P∧(P∨Q) ?Q→P
2.原式? (（P∧Q）∨P) ∧((P∧Q) ∨┐Q) ? (P∨P) ∧(P∨Q) ∧(P∨┐Q) ∧(Q∨┐Q) ?P∧(P∨Q) ∧(P∨┐Q) ?P∧P?P
3.原式?┐（┐P∨Q）∨(Q∨R) ?(P∧┐Q) ∨(Q∨R) ?(P∨Q∨R) ∧(Q∨┐Q∨R) ?P∨Q∨R（零率）
4.原式?（P∧┐Q）∨Q?（P∨Q）∧(┐Q∨Q) ?P∨Q（运算次序优先级：┐，∧，∨，→，?）
例: 求证: (P →Q) ∨┐(P →Q) 为永真式。
解：原式?（┐P∨Q）∨（P∧┐Q）?(┐P∨Q∨P) ∧（┐P∨Q ∨┐Q）?T
例：求证┐Q∧(P→Q)?┐P
证法1：前件真推导后件真
证法2：后件假推导前件假
证法3：定义
定理：设P、Q为任意两个命题公式，P?Q的充分必要条件是P?Q 且Q?P。
证明：若P?Q，则P?Q为重言式，即P→Q和Q→P是重言式；若有P?Q且Q?P，则P→Q和Q→P是重言式，即P?Q为重言式
例已知A是B的充分条件, B是C的必要条件，C是D的必要条件, D是B的必要条件, 问：
(1) A是D的什么条件?
(2) B是D的什么条件?
解已知A?B, C?B, D?C, B?D, 故有
(1) A?B, B?D, 所以A?D, 即A是D的充分条件
(2) D?C, C?B, 所以D?B, 又因为B?D, 所以B?D, 即B是D 的充要条件。
定理：如果A?B，则A* ? B*。
证明：设P1,P2,…,Pn是出现在命题公式A、B中的原子变元，因为A?B，即：A(P1,P2,…,Pn)?B(P1,P2,…,Pn)是一个重言式。故有：A(┐P1,┐P2,…,┐Pn)?B(┐P1,┐P2,…,┐Pn)是一个重言式。即A(┐P1,┐P2,…,┐Pn)?B(┐P1,┐P2,…,┐Pn)
┐A* ?┐B* ，即A* ? B*
例判断下面各推理是否正确.
(1)如果天气凉快,小王就不去游泳.天气凉快,所以小王没去游泳.
(2)如果我上街,我一定去新华书店.我没上街.所以我没去新华书店. 解: 解上述类型的推理问题,应先将命题符号化,然后写出前提、结论和推理的形式结构,最后进行判断.
(1)P：天气凉快; Q：小王去游泳.
前提：P→?Q, P.
结论：?Q.
推理的形式结构为
((P→?Q)∧P)→? Q. (*)
判断(*)是否为重言式.
①真值表法
真值表的最后一列全为1,因而(*)是重言式.所以推理正确.
②等价演算法
(P→? Q)∧P)→? Q ?1.
③主析取范式法
((P→?Q)∧P)→? Q
?m0∨m1∨m2∨m3
由②,③同样能判断推理正确.
(2)P：我上街; Q：我去新华书店.
前提：P→Q, ?P. 结论：?Q.
推理的形式结构为
((P→Q)∧?P) →?Q. (**)
((P→Q)∧?P)→?Q
?m0∨m2∨m3
可见(**)不是重言式,所以推理不正确.还可用其他方法判断之.
例证明下列前提是不相容的。
1. 若A因病缺了许多课, 那么他中学考试失败。
2. 若A中学考试失败, 则他没有知识。
3. 若A读了许多书, 则他有知识。
4. A因病缺了许多课, 而且读了许多书。
证明符号化题目:
P: 因病缺了许多课,
Q: 中学考试失败,
R: 有知识,
S: 读了许多书。
问题要证明前提
P→Q, Q?→R, S→R, P∧S是不相容的。
下面我们用另外一种形式的格式证明
（即后面讲的―构造证明‖的格式）：
编号公式依据
(1) P∧S P
(2) P (1); I1
(3) S (1); I2
(4) P→Q P
(5) Q (2),(4); I8
(6) S→R P
(7) R (3),(6); I8
(8) Q?→R P
(9) ?R (5),(8); I9
(10) R∧?R (7),(9)
例张三说李四在说谎, 李四说王五在说谎, 王五说张三、李四都在说谎。问谁说真话, 谁说假话？
解设A:张三说真话; B:李四说真话; C:王五说真话
依题意有A??B, B??C, C??A∧?B。
(A ??B)∧(B ??C)∧(C ??A∧?B)
?(A?→B)∧(?B→A)∧(B?→C)∧(?C→B) ∧(C→(?A∧?B))∧((?A∧?B)→C)
?(?A∧B∧?C)∧((A∨B)∧C)) ∧((?A∧?B∧?C)∨(A∧?C)∨(B∧?C))
??A∧B∧?C
即: 李四说真话, 张三和王五说假话。
●例1.9.3：求证：S是前提W，W→┐Q,┐Q→R和R→S的有
效结论。
●证明：
{1} (1) W→┐Q P
{2} (2) ┐Q→R P
{1,2} (3) W→R T,(1)(2)I11
{3} (4) W P
{1,2,3} (5) R T,(3)(4)I8
{4} (6) R→S P
{1,2,3,4} (7) S T,(5)(6)I8
（这部分的T，I8等是另外一本书的内容，所以不用管，只要会推就行）
例前提: 如果马会飞或羊吃草, 则母鸡就会是飞鸟; 如果母鸡是飞鸟, 那么烤熟的鸭子还会跑; 烤熟的鸭子不会跑。结论: 羊不吃草。解符号化上述语句, P: 马会飞, Q: 羊吃草, R: 母鸡是飞鸟, S: 烤熟的鸭子还会跑, ?S: 烤熟的鸭子不会跑, ?Q: 羊不吃草。
前提集合{P∨Q→R, R→S, ?S}, 结论C : ?Q。
(1) ?S P
(2) R→S P
(3) ?R (1), (2), I9
(4) P∨Q→R P
(5) ?(P∨Q) (3), (4), I9
(6) ?P∧?Q (5), E5
(7) ?Q (6), I 2
例如果我的考试通过, 那么我很快乐。如果我快乐, 那么阳光很好。现在是凌晨一点, 天很暖和。试给出结论。
解设P: 我的考试通过, Q: 我很快乐, R: 阳光很好, S: 天很暖和。把―凌晨一点‖理解为阳光不好。
前提为: P→Q, Q→R, ?R∧S。
编号公式依据
(1) P→Q P
(2) Q→R P
(3) P→R (1), (2)；I11
(4) ?R∧S P
(5) ?R (4)；I1
(6) ?P (3), (5)；I9
结论: ?P, 我的考试没通过。
例前提: ?P∨?Q, ?P→R, R?→S; 结论: S?→Q。
证明(1) S CP
(2) R?→S P
(3) S?→R (2), E
(4) ?R (1), (3), I
(5) ?P→R P
(6) ?R→P (5), E
(7) P (4), (6), I
(8) ?P∨?Q P
(9) P?→Q (8), E
(10) ?Q (7), (9), I
(11) S?→Q (1), (10), CP
（CP规则这部分因为好像多了一个条件，所以用起来可能会比较简单）
例1.9.5：证明R→S可从前提P→(Q→S)，┐R∨P和Q推出。
证明：(CP规则，因为结论R→S为条件式)
{1} (1) ┐R∨P P
{2} (2) R P(附加前提)
{1,2} (3) P T,(1)(2)I10
{3} (4) P→(Q→S) P
{1,2,3} (5) Q→S T, (3,4)I8
{4} (6) Q P
{1,2,3,4} (7) S T,(5)(6)I8
{1,3,4} (8) R→S CP,(2)(7)
例1.9.4：证明从前提P→Q，┐(Q∨R)可演绎出┐P.
证明：(反证法)
{1} (1) P P（附加前提）
{2} (2) P→Q P
{1,2} (3) Q T,(1)(2)I8
{3} (4) ┐(Q∨R) P
{3} (5) ┐Q∧┐R T, (4)E5
{3} (6) ┐Q T，(5)I1
{1,2,3} (7) Q∧┐Q T,(3)(6)
例―如果春暖花开, 燕子就会飞回北方。如果燕子飞回北方, 则冰雪融化。所以, 如果冰雪没有融化, 则没有春暖花开。‖证明这些语句构成一个正确的推理。证: 令P: 春暖花开。Q: 燕子飞回北方。R:冰雪融化。则上述问题转化成证明:
P→Q, Q→R ??R?→P
利用CP规则, 将?R作为附加前提, 推导?P, 从而推导出?R?→P。
编号公式依据
(1) Q→R P
(2) ?R P(附加前提)
(3) ?Q (1),(2); I9
(4) P→Q 前提
(5) ?P (3),(4); I9
课堂练习：
1. 用基本等价公式的转换方法验证下列推断是否有效。
(1)P → Q，R∧S，?Q ? R∧S；
(2)?P → Q，Q → R，R → P ? P∨Q∨R；
(3)P，Q → R，R∨S ? Q → S；
(4)?Q∧R，R∧P，Q ? P∨?Q。
2. 用推理规则证明下述论断的正确性。
(1)P，P→ (Q → (R∧S)) ? Q → S；
(2)P→ (Q → R)，R→ (Q → S) ? P → (Q → S)；
(3)P → (Q → R) ? (Q→ (R → S)) → (P→ (Q → S))；
(4)?(P → Q) →?(R∨S)，(Q→ P)∨?R，R ? P ? Q。
3. A, B, C, D四人中要派两个人出差，按下述三个条件有几种派法？如何派？
(1)若A去，则C 和D中要去一人。(2)B和C不能都去。
(3)C去则D要留下。
4. A, B, C, D四人参加考试后，有人问它们，谁的成绩最好。A说―不是我‖，B说―是D‖，C说―是B‖，D说―不是我‖。四人的回答只有一人符合实际，问是谁的成绩最好？只有一人成绩最好的是谁？
5. 判断下列推理是否正确：
(1)如果我是小孩，我会喜欢熊猫。我不是小孩，所以我不喜欢熊猫。
(2)如果太阳从西边出来，那么地球停止转动。太阳从西边出来了，所以地球停止了转动。
二．谓词逻辑
例试用量词、谓词表示下列命题：
①所有大学生都热爱祖国；
②每个自然数都是实数；
③一些大学生有远大理想；
④有的自然数是素数。
解①令S(x)：x是大学生，L(x)：x热爱祖国，则
所有大学生都热爱祖国(?x)(S(x)→L(x))
②令N(x)：x是自然数，R(x)：x是实数，则
每个自然数都是实数(?x)(N(x)→R(x))
●全称量词(?x)后跟条件式。
③令S(x)：x是大学生，I(x)：x有远大理想，则
一些大学生有远大理想(?x)(S(x)∧I(x))
④令N(x)：x是自然数，P(x)：x是素数。则
有的自然数是素数(?x)(N(x)∧P(x))
●存在量词(?x)后跟合取式。
例令f(x):x小于88，g(x):x是奇数，
(?x) (f(x)∧g(x)) 。个体变元x是约束变元。
这已经不是一个命题函数, 而是一个命题。它相当于说―存在有小于88的奇数‖, 这是一个真命题
例令f(y): y是辣椒，g(y): y是红的，
(?y) (f(y) →g(y))。个体变元y是约束变元。
这也不是一个命题函数,而是一个命题。
对于其中的个体变元不需要再作代入, 它的含义是确定的, 它断定―一切辣椒都是红的‖, 这当然是一个假命题。
例：将公式(?x)(P(x)→Q(x,y))∧R (x,y)中的约束变元改名。下面哪个正确？（注意到此公式中，约束变元只有x）,
1）(?y)(P(y) →Q (y,y))∧R (x,y)
2）(?z)(P(z) →Q (x,y))∧R (x,y)
3）(?z)(P(z) →Q (z,y))∧R (x,y)
例：将公式(?x)(P(y)→Q(x,y))∧R (x,y)中的自由变元代入。
（注意到此公式中y为自由变元，x既是约束出现，也是自由出现。）我们以y为例，试判断下面哪个正确？
1）(?x)(P(z) →Q (x,z))∧R (x,y)
2）(?x)(P(x) →Q (x,z))∧R (x,x)
3）(?x)(P(z) →Q (x,z))∧R (x,z)
例在公式(?x) (Q(x) →R(x, y))∨(?z) P(x, z)中，x既为约束出现，又为自由出现，下面用两种方法，使变元x在公式中只呈一种形式出现
解用约束变元的改名规则得:
(?u) (Q(u) →R(u, y))∨(?z) P(x, z);
或用自由变元得代入规则得:
(?x )(Q(x) →R(x, y))∨(?z) P(u, z)。
（重做前一例题，将自由出现的x进行代入）
重做例：将公式(?x)(P(y)→Q(x,y))∧R (x,y)中的自由变元代入。
注意到此公式中y为自由变元，x既是约束出现，也是自由出现。这次，我们将自由出现的x代入，得：(?x)(P(y) →Q (x,y))∧R (z,y)
例试证明下面苏格拉底论证：
所有人都是要死的，
苏格拉底是人，
因此，苏格拉底是要死的。
证明：令M(x):x是人，D(x):x是要死的，s:苏格拉底，原题可符号化为：
(?x)(M(x)→D(x))，M(s) ┣D(s)
推证如下：
{1} (1) (?x)(M(x)→D(x)) P
{1} (2) M(s)→D(s) UI,(1)
{3} (3) M(s) P
{1,3} (4) D(s) T,(2),(3),I
例证明(?x)A(x)→(?x)B(x) ? (?x)(A(x)→B(x))
证明：反证法
(1) ?(?x) (A(x) → B(x)) P(附加前提)
(2) (?x) ?(A(x) → B(x)) T, (1), E
(3) ?(A(a) → B(a)) T, (2), ES
(4) A(a)∧?B(a) T, (3), I
(5) A(a) T, (4), I
(6) ?B(a) T, (4), I
(7) (?x) A(x) T, (5), EG
(8) (?x) A(x) → (?x) B(x) P前提
(9) (?x) B(x) T, (7)(8), I
(10) B(a) T, US
(11) B(a)∧?B(a) (6)(10)矛盾
三．集合
例在一个住着一些人家的僻静孤岛上, 岛上只有一个理发师a, a给且只给岛上所有不能自己理发的人理发。问谁给a理发？
解: 设S = {x | x 是不能自己理发的人}。
(1) 若a?S, 则a给自己a理发。又由题意知, a只给不能自己理发的人理发, 所以a是不能自己理发的人, 即a∈S, 矛盾。
(2) 若a∈S, 则a是不能自己理发的人。又由题意知, a只给集合S 中的人理发, 所以a要给a理发, 即a?S , 矛盾。
无论如何, 都有a∈S和a?S同时成立。
这是著名的罗素悖论paradox。
例令A={{1,2},{3},4}, B={4,{5},{5,6}},则
∪A={1,2}∪{3}={1,2,3},
∪B={5}∪{5,6}={5,6},
∩A={1,2}∩{3}=?,
∩B={5}∩{5,6}={5}
四．关系
例设 A = {1, 3, 5}, B = {2, 4, 6, 8}, 定义A到B的二元关系R: ?a, b?∈R当且仅当a?b, 则称R为A到B的―小于‖关系。
R = {?1,2?, ?1,4?, ?1,6?, ?1,8?, ?3,4?, ?3,6?, ?3,8?, ?5,6?, ?5,8?}
是A到B的一个关系, 显然R ? A×B。
而?3,2??R, ?5,2??R, ?5,4??R。
例设A = {1, 2, 3, 4, 5, 6}, B = {a, b, c, d},
关系R = {?2, a?, ?2, b?, ?3, b?, ?4, d?, ?6, d?}, 则
dm(R) = {2, 3, 4, 6},
rn(R) = {a, b, d},
fl(R)={2,3,4,6,a,b,d}。
例设A = {1, 2, 3}, B={1, 2, 3, 4},从A到B上的关系R={?1,1?,?2,2?,?3,3?},
S={?1,1?,?1,2?,?1,3?,?1,4?}，
则
R∪S={?1,1?,?2,2?,?3,3?, ?1,2?,?1,3?,?1,4?}
R∩S={?1,1?}
R-S={?2,2?,?3,3?}
S-R={?1,2?,?1,3?,?1,4?}
R'={?1,2?,?1,3?,?1,4?, ?2,1?,?2,3?,?2,4?, ?3,1?,?3,2?,?3,4?}
要注意的是, 作为关系, 补运算是对全域关系而言的, 并不是对全集U而言的。
例设A和B分别是学校的所有学生和所有课程的集合。假设R由所有有序对?a,b?组成，其中a是选修课程b的学生。S由所有有序对?a,b?构成，其中课程b是a的必修课。什么是关系R∪S，R∩S，R⊕S，R-S和S-R？
解：关系R∪S由所有的有序对?a,b?组成，其中a是一个学生，他或者选修了课程b，或者课程b是他的必修课。R∩S是所有有序对?a,b?的集合，其中a是一个学生，他选修了课程b并且课程b也是a的必修课。R⊕S由所有有序对?a,b?组成，其中学生a已经选修了课程b，但课程b不是a的必修课，或者课程b是a的必修课，但a没有
选修它。R-S是所有有序对?a,b?的集合，其中a已经选修了课程b 但课程b不是a的必修课。S-R是所有有序对?a,b?的集合，其中课程b是a的必修课，但a没有选它。
例设A = {a, b, c, d}, A上的关系
R = {?a, a?, ?a, b?, ?b, d?},
S = {?a, d?, ?b, c?, ?b, d?, ?c, b?}。
求R*S 和S*R。
解: R*S = {?a, d?, ?a, c?}；
S*R = {?c, d?}。
显然R*S ≠S*R
从本例可知复合关系不满足交换律。
兄弟关系和父子关系的复合是——叔侄关系
例设A = {a, b, c, d, e, f },
R ={?a, b?, ?b, c?, ?c, d?, ?d, e?, ?e, f?}。
求Rn (n =1, 2, 3, 4, …)。
解：R1 = R；
R2 = R*R ={?a, c?, ?b, d?, ?c, e?, ?d, f?}；
R3 = R2*R ={?a, d?, ?b, e?, ?c, f?}；
R4 = R3*R ={?a, e?, ?b, f?}；
R5 = R4*R = {?a, f?}；
R6 = R5*R = ?；
R7 = ?；
…
Rn = ?( n＞5 )。
例设A = {a, b, c, d, 1, 2, 3, 4}, A上的关系
R = {?a, 2?, ?b, 2?, ?b, 3?, ?d, 4?},
则
R–1 = {?2, a?, ?2, b?, ?3, b?, ?4, d?}。
例设A = {a, b, c}, B = {0, 1}, 有A到B的关系
R = {?a, 0?, ?b, 0?, ?c, 1?}, S = {?a, 1?, ?b, 1?, ?c, 1?}
则R–1={?0, a?,?0, b?, ?1,c?}, S–1={?1, a?,?1, b?,?1, c?} R∪S = {?a, 0?, ?b, 0?, ?c, 1?, ?a, 1?, ?b, 1?}；
(R∪S) –1 = R–1∪S–1
= {?0, a?, ?0, b?, ?1, c?, ?1, a?, ?1, b?}；
R∩S = {?c, 1?};
(R∩S) –1 = R–1∩S–1= {?1, c?};
R – S = {?a, 0?, ?b, 0?}；
(R –S) –1 = R–1 – S–1 = {?0, a?, ?0, b?}；
离散数学题库
常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={
1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设
离散数学题库及答案
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。
离散数学期末考试试题(有几套带答案)
离散数学试题(A卷及答案） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分） 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D
(7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍 证明设 1 a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数 只能是0，1，…，m－1，由抽屉原理可知， 1 a，2a，…，1+m a这m＋1个整 数中至少存在两个数 s a和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵x∈ A-（B∪C）? x∈ A∧x?（B∪C）? x∈ A∧（x?B∧x?C）?（x∈ A∧x?B）∧（x∈ A∧x?C）? x∈（A-B）∧x∈（A-C）? x∈（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C） 六、已知R、S是N上的关系，其定义如下：R={
离散数学证明题
离散数学证明题离散数学证明题:链为分配格 证明设a,b均是链A的元素，因为链中任意两个元素均可比较，即有a≤b或a≤b，如果a ≤b，则a,b的最大下界是a,最小上界是b，如果b≤a，则a,b的最大下界是b,最小上界是a，故链一定是格,下面证明分配律成立即可,对A中任意元素a,b,c分下面两种情况讨论: ⑴b≤a或c≤a ⑵a≤b且a≤c 如果是第⑴种情况,则a∪(b∩c)=a=(a∪b)∩(a∪c) 如果是第⑵种情况,则a∪(b∩c)=b∩c=(a∪b)∩(a∪c) 无论那种情况分配律均成立,故A是分配格. 一.线性插值(一次插值) 已知函数f(x)在区间[xk ,xk+1 ]的端点上的函数值yk =f(xk ), yk+1 = f(xk+1 ),求一个一次函数y=P1 (x)使得yk =f(xk ),yk+1 =f(xk+1 ), 其几何意义是已知平面上两点(xk ,yk ),(xk+1 ,yk+1 ),求一条直线过该已知两点。 1. 插值函数和插值基函数 由直线的点斜式公式可知： 把此式按照 yk 和yk+1 写成两项: 记 并称它们为一次插值基函数。该基函数的特点如下表： 从而 P1 (x) = yk lk (x) + yk+1 lk+1 (x) 此形式称之为拉格朗日型插值多项式。其中, 插值基函数与yk 、yk+1 无关，而由插值结点xk 、xk+1 所决定。一次插值多项式是插值基函数的线性组合, 相应的组合系数是该点的函数值yk 、yk+1 . 例1: 已知lg10=1,lg20=1.3010, 利用插值一次多项式求lg12的近似值。 解: f(x)=lgx,f(10)=1,f(20)=1.3010, 设 x0 =10 ,x1 =20 ,y0 =1 ,y1 =1.3010 则插值基函数为： 于是, 拉格朗日型一次插值多项式为: 故 : 即lg12 由lg10 和lg20 两个值的线性插值得到,且具有两位有效数字(精确值lg12=1.0792). 二.二次插值多项式 已知函数y=f(x)在点xk-1 ,xk ,xk+1 上的函数值yk-1 =f(xk-1 ),yk =f(xk ), yk+1 =f(xk+1 ), 求一个次数不超过二次的多项式P2 (x), 使其满足, P2 (xk-1 )=yk-1 , P2 (xk )=yk , P2 (xk+1 )=yk+1 . 其几何意义为:已知平面上的三个点 (xk-1 ,yk-1 ),(xk ,yk ),(xk+1 ,yk+1 ), 求一个二次抛物线, 使得该抛物线经过这三点。 1.插值基本多项式 有三个插值结点xk-1 ,xk ,xk+1 构造三个插值基本多项式，要求满足： (1) 基本多项式为二次多项式; (2) 它们的函数值满足下表： 因为lk-1 (xk )= 0,lk-1 (xk+1 )=0, 故有因子(x-xk )(x-xk+1 ), 而其已经是一个二次多项式, 仅相差一个常数倍, 可设 lk-1 (x)=a(x-xk )(x-xk+1 ),
离散数学试题与答案
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
离散数学复习题及答案
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨) ()(Q P Q P Q P ?∧?∨∧??Q) P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)() ()(R P Q P ∨∧∧?
①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??
离散数学证明题
离散数学证明题 离散数学证明题离散数学证明题:链为分配格 证明设a,b均是链A的元素，因为链中任意两个元素均可比较，即有a≤b或a≤b，如果a≤b，则a,b的最大下界是a,最小上界是b，如果b≤a，则a,b的最大下界是b,最小上界是a，故链一定是格,下面证明分配律成立即可,对A中任意元素a,b,c分下面两种情况讨论: ⑴b≤a或c≤a ⑵a≤b且a≤c 如果是第⑴种情况,则a∪(b∩c)=a=(a∪b)∩(a∪c) 如果是第⑵种情况,则a∪(b∩c)=b∩c=(a∪b)∩(a∪c) 无论那种情况分配律均成立,故A是分配格. 一.线性插值(一次插值) 已知函数f(x)在区间[xk ,xk+1 ]的端点上的函数值yk =f(xk ), yk+1 = f(xk+1 ),求一个一次函数y=P1 (x)使得yk =f(xk ),yk+1 =f(xk+1 ), 其几何意义是已知平面上两点(xk ,yk ),(xk+1 ,yk+1 ),求一条直线过该已知两点。 1. 插值函数和插值基函数 由直线的点斜式公式可知： 把此式按照 yk 和yk+1 写成两项: 记
并称它们为一次插值基函数。该基函数的特点如下表： 从而 P1 (x) = yk lk (x) + yk+1 lk+1 (x) 此形式称之为拉格朗日型插值多项式。其中, 插值基函数与yk 、yk+1 无关，而由插值结点xk 、xk+1 所决定。一次插值多项式是插值基函数的线性组合, 相应的组合系数是该点的函数值yk 、yk+1 . 例1: 已知lg10=1,lg20=1.3010, 利用插值一次多项式求lg12的近似值。 解: f(x)=lgx,f(10)=1,f(20)=1.3010, 设 x0 =10 ,x1 =20 ,y0 =1 ,y1 =1.3010 则插值基函数为： 于是, 拉格朗日型一次插值多项式为: 故 : 即lg12 由lg10 和lg20 两个值的线性插值得到,且具有两位有效数字(精确值lg12=1.0792). 二.二次插值多项式 已知函数y=f(x)在点xk-1 ,xk ,xk+1 上的函数值yk-1 =f(xk-1 ),yk =f(xk ), yk+1 =f(xk+1 ), 求一个次数不超过二次的多项式P2 (x), 使其满足, P2 (xk-1 )=yk-1 , P2 (xk )=yk , P2 (xk+1 )=yk+1 . 其几何意义为:已知平面上的三个点 (xk-1 ,yk-1 ),(xk ,yk ),(xk+1 ,yk+1 ),
离散数学试题及答案(1)
离散数学试题及答案 一、填空题 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变成完全图。
电大离散数学证明题参考题
五、证明题 1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等． 证明：设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边删去E 所得到的．所以对于任意结 点u V ∈，u 在G 和G 中的度数之和等于u 在n K 中的度数．由于n 是大于等于3的奇数，从而n K 的每个结点都是偶数度的（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等． 2．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加 2 k 条边才能使其成为欧拉图． 证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数． 又根据定理4.1.1的推论，图G 是欧拉图的充分必要条件是图G 不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图． 故最少要加2 k 条边到图G 才能使其成为欧拉图． 五、证明题 1．试证明集合等式：A ? (B ?C )=(A ?B ) ? (A ?C )． 证：若x ∈A ? (B ?C )，则x ∈A 或x ∈B ?C ， 即x ∈A 或x ∈B 且x ∈A 或x ∈C ． 即x ∈A ?B 且x ∈A ?C ， 即x ∈T =(A ?B ) ? (A ?C )， 所以A ? (B ?C )? (A ?B ) ? (A ?C )． 反之，若x ∈(A ?B ) ? (A ?C )，则x ∈A ?B 且x ∈A ?C ， 即x ∈A 或x ∈B 且x ∈A 或x ∈C ， 即x ∈A 或x ∈B ?C ， 即x ∈A ? (B ?C )， 所以(A ?B ) ? (A ?C )? A ? (B ?C )． 因此．A ? (B ?C )=(A ?B ) ? (A ?C )． 2．对任意三个集合A , B 和C ，试证明：若A ?B = A ?C ，且A ≠?，则B = C ． 证明：设x ∈A ，y ∈B ，则
离散数学章练习题及答案
离散数学练习题 第一章 一．填空 1.公式) ∨ ? ∧的成真赋值为 01；10 ? p∧ ( (q ) p q 2.设p, r为真命题，q, s 为假命题，则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01；10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式，B为重言式，则B A∨的类型为重言式 5．设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二．将下列命题符合化 1. 7不是无理数是不对的。 解：) ? ?，其中p: 7是无理数；或p，其中p: 7是无理数。 (p 2.小刘既不怕吃苦，又很爱钻研。 解：其中 ?p: 小刘怕吃苦，q：小刘很爱钻研 p∧ ,q 3.只有不怕困难，才能战胜困难。 解：p →，其中p: 怕困难，q: 战胜困难 q? 或q →，其中p: 怕困难， q: 战胜困难 p? 4.只要别人有困难，老王就帮助别人，除非困难解决了。 解：) → ?，其中p: 别人有困难，q:老王帮助别人，r: 困难解决了 p (q r→ 或：q ?) (，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。 解：q p?，其中p: 整数n是偶数，q: 整数n能被2整除 三、求复合命题的真值 P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解：p, q 为假命题，r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r
离散数学期末考试试题及答案
离散数学试题(B卷答案1） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P
《离散数学》题库及答案
《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( A ) (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) 给我一杯水吧！
离散数学题目5
离散数学试题（A卷答案） 一、（10分）证明?(A∨B)→?(P∨Q)，P，(B→A)∨?P A。 证明：(1)?(A∨B)→?(P∨Q)P (2)(P∨Q)→(A∨B) T(1)，E (3)P P (4)A∨B T(2)(3)，I (5)(B→A)∨?P P (6)B→A T(3)(5)，I (7)A∨?B T(6)，E (8)(A∨B)∧(A∨?B) T(4)(7)，I (9)A∧(B∨?B) T(8)，E (10)A T(9)，E 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 解符号化命题，设A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛。 依题意有， (1)甲和乙只有一人参加，符号化为A⊕B?(?A∧B)∨(A∧?B)； (2)丙参加，丁必参加，符号化为C→D； (3)乙或丁至多参加一人，符号化为?(B∧D)； (4)丁不参加，甲也不会参加，符号化为?D→?A。 所以原命题为：(A⊕B)∧(C→D)∧(?(B∧D))∧(?D→?A) ?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A) ?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A)) ?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T 但依据题意条件，有且仅有两人参加竞赛，故?A∧B∧?C∧?D为F。所以只有：(A∧?B∧?C∧ D)∨(A∧?B∧D)?T，即甲、丁参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。 (1)?x(P(x)→Q(x)) P
离散数学试题
087ynu离散数学试题与答案试卷一 一、填空 20% （每小题2分） 1．设（N：自然数集，E+正偶数）则。 2．A，B，C表示三个集合，文图中阴影部分的集合表达式为 。 3．设P，Q 的真值为0，R，S的真值为1，则 的真值= 。 4．公式的主合取范式为 。 5．若解释I的论域D仅包含一个元素，则在I下真值为 。 6．设A={1，2，3，4}，A上关系图为 则 R2 = 。 7．设A={a，b，c，d}，其上偏序关系R的哈斯图为 则 R= 。 8．图的补图为。 9．设A={a，b，c，d} ，A上二元运算如下： 那么代数系统
逆元分别为。 10．下图所示的偏序集中，是格的为。 二、选择 20% （每小题 2分） 1、下列是真命题的有（） A．；B．； C．； D．。 2、下列集合中相等的有（） A．{4，3}；B．{，3，4}；C．{4，，3，3}；D． {3，4}。 3、设A={1，2，3}，则A上的二元关系有（）个。 A． 23 ；B． 32 ；C．； D．。 4、设R，S是集合A上的关系，则下列说法正确的是（） A．若R，S 是自反的，则是自反的； B．若R，S 是反自反的，则是反自反的； C．若R，S 是对称的，则是对称的； D．若R，S 是传递的，则是传递的。 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 则P（A）/ R=（） A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}； D．{{}，{2}，{2，3}，{{2，3，4}}，{A}}0 6、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为（） 7、下列函数是双射的为（） A．f : IE , f (x) = 2x ； B．f : NNN, f (n) =
离散数学题目及答案
数理逻辑习题 判断题 1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式)(q p p →?→是永真式 （ √ ） 3．命题公式p q p →∧)(是永真式 （ √ ） 4．命题公式r q p ∧?∧的成真赋值为010 （ × ） 5．))(()(B x A x B x xA →?=→? （ √ ） 6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p q p p =∧∨)( （ √ ） 8．))()((x G x F x →?是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． )()(x xG x xF ?→?是永真式（ √ ） 11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p q p p =∨∧)( （ √ ） 13．))()((x G x F x →?是永假式 （ × ） 14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若雪是黑色的:p ，则q →p 公式是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．q →p 公式的特异（主）析取式为q p ∨? （ × ） 18．命题公式 )(r q p →∨?的成假赋值是110 （ √ ） 19．一阶逻辑公式)),()((y x G x F x →?是闭式（ × ） 单项选择题 1． 下述不是命题的是（ A ）
A ． 花儿真美啊! B ． 明天是阴天。 C ． 2是偶数。 D ． 铅球是方的。 2．谓词公式（?y ）（?x ）（P （x ）→R （x,y ））∧?yQ （x,y ）中变元y （ B ） A ． 是自由变元但不是约束变元 B ． 是约束变元但不是自由变元 C ． 既是自由变元又是约束变元 D ． 既不是自由变元又不是约束变元 3．下列命题公式为重言式的是（ A ） A ．p→ （p ∨q ） B ．（p ∨┐p ）→q C ．q ∧┐q D ．p→┐q 4． 下列语句中不是．．命题的只有（ A ） A ．花儿为什么这样红？ B ．2+2=0 C ．飞碟来自地球外的星球。 D ．凡石头都可练成金。 5．在公式),()())(),()()((z y P y z Q y x P y x ?→∧??中变元y 是（ B ） A ．自由变元 B ．约束变元 C ．既是自由变元，又是约束变元 D ．既不是自由变元，又不是约束变元 6．下列命题公式为重言式的是（ A ） A ．p→ （p ∨q ） B ．（p ∨┐p ）→q C ．q ∧┐q D ．q→┐p 7．给定如下4个语句: （1）我不会唱歌。 （2）如果天不下雨,我就上街。 （3）我每天都要上课。 （4）火星上有人吗? 其中不是复合命题的是（ B ） A ．（1）（4） B ．（3）（4） C ．（1）（3） D ．（1）（3）（4） 8．下列含有命题p ，q ，r 的公式中，是特异（主）析取范式的是 （ D ） A ．（p ∧ q ∧ r ） ∨ （?p ∧ q ） B ．（p ∨ q ∨ r ） ∧ （?p ∧ q ） C ．（p ∨ q ∨ r ） ∧ （?p ∨ q ∨ r ） D ．（p ∧ q ∧ r ） ∨ （?p ∧ q ∧ r ） 9．设个体域为整数集,则下列公式中值为真的是（ A ）。 A ． （?y ）（?x ）（x ·y=2） B ．（?x ）（?y ）（x ·y=2） C ． （?x ）（x －y=x ） D ．（?x ）（ ?y ）（x+y=2y ） 10． 下述不是命题的是（ D ）
离散数学题库与答案
试卷二十二试题与答案 一、单项选择题：（每小题1分，本大题共15分） 1．设A={1，2，3，4，5}，下面（ ）集合等于A 。 A 、{1，2，3，4，5，6}； B 、 } 25{2 ≤x x x 是整数且； C 、}5{≤x x x 是正整数且； D 、} 5{≤x x x 是正有理数且 。 2．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（ ）是错的。 A 、A ?Φ； B 、{6，7，8}∈A ； C 、{{4，5}}?A ； D 、{1，2，3}?A 。 3．六阶群的子群的阶数可以是（ ）。 A 、1，2，5； B 、2，4； C 、3，6，7； D 、2，3 。 4．设B A S ??，下列各式中（ ）是正确的。 A 、 domS ? B ； B 、domS ?A ； C 、ranS ?A ； D 、domS ? ranS = S 。 5．设集合Φ≠X ，则空关系X Φ不具备的性质是（ ）。 A 、自反性； B 、反自反性； C 、对称性； D 、传递性。 6．下列函数中，（ ）是入射函数。 A 、世界上每个人与其年龄的序偶集； B 、、世界上每个人与其性别的序偶集； B 、 一个作者的专著与其作者的序偶集； D 、每个国家与其国旗的序偶集。 7．><,*G 是群，则对*（ ）。 A 、满足结合律、交换律； B 、有单位元，可结合； C 、有单位元、可交换； D 、每元有逆元，有零元。 8．下面（ ）哈斯图所描述的偏序关系构成分配格。 9．下列（ ）中的运算符都是可交换的。 A 、→∨∧,,； B 、?→,； C 、???,,； D 、∧∨,。 10．设G 是n 个结点、m 条边和r 个面的连通平面图，则m 等于（ ）。 A 、n+r-2 ； B 、n-r+2 ； C 、n-r-2 ； D 、n+r+2 。 11．n 个结点的无向完全图n K 的边数为（ ）。
《离散数学》试题及答案
一、填空题 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变成完全图。 16. 设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________.