离散数学（课件上习题）
第一章
例1-1.1 判定下面这些句子哪些是命题。
⑴2是个素数。
⑵雪是黑色的。
⑶2013年人类将到达火星。
⑷如果a>b且b>c，则a>c 。（其中a,b,c都是
确定的实数）
⑸x+y<5
⑹请打开书！
⑺您去吗？
⑴⑵⑶⑷是命题
例1-2.1 P：2是素数。
?P：2不是素数。
例1-2.2 P：小王能唱歌。
Q：小王能跳舞。
P∧Q：小王能歌善舞。
例1-2.3. 灯泡或者线路有故障。（析取“∨”）
例1-2.4. 第一节课上数学或者上英语。（异或、排斥或。即“?”）
注意：P ?Q 与(P∧?Q)∨(Q∧?P ) 是一样的。
归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：（1）否定“?”(2) 合取“∧”(3) 析取“∨”(4) 异或“?”(5) 蕴涵“→”(6) 等价“?”
例1-2.5：P表示：缺少水分。
Q表示：植物会死亡。
P→Q：如果缺少水分，植物就会死亡。
P→Q：也称之为蕴涵式，读成“P蕴涵Q”，“如果P则Q”。
也说成P是P→Q 的前件，Q是P→Q的后件。
还可以说P是Q的充分条件，Q是P的必要条件。
以下是关于蕴含式的一个例子
P：天气好。Q：我去公园。
1.如果天气好，我就去公园。
2.只要天气好，我就去公园。
3.天气好，我就去公园。
4.仅当天气好，我才去公园。
5.只有天气好，我才去公园。
6.我去公园，仅当天气好。
命题1.、2.、3.写成：P→Q
命题4.、5.、6.写成：Q→P
例1-2.6：P：△ABC 是等边三角形。Q ：△ABC是等角三角形。
P?Q ：△ABC 是等边三角形当且仅当它是等角三角形。
课后练习：填空
已知P∧Q为T，则P为( )，Q为( )。
已知P∨Q为F，则P为( )，Q为( )。
已知P为F，则P∧Q为( )。
已知P为T，则P∨Q为( )。
已知P∨Q为T，且P为F ，则Q为( )。
已知P→Q为F，则P为( )，Q为( )。
已知P为F，则P→Q为( )。
已知Q为T，则P→Q为( )。
已知?P→?Q为F，则P为( )，Q为( )。
已知P为T，P→Q为T，则Q为( )。
已知?Q为T, P→Q为T，则P为( )。
已知P?Q 为T ，P 为T , 则Q 为( ).
已知P?Q 为F ，P 为T , 则Q 为( ).
P?P 的真值为( ).
P→P 的真值为( )。
1—3节
例1.说离散数学无用且枯燥无味是不对的。
P：离散数学是有用的。
Q：离散数学是枯燥无味的。
该命题可写成：? (?P∧Q)
例2. 如果小张与小王都不去，则小李去。
P ：小张去。Q ：小王去。R ：小李去。
该命题可写成：(?P∧?Q)→R
如果小张与小王不都去，则小李去。
该命题可写成：?(P∧Q)→R
也可以写成：(?P∨?Q)→R
例3. 仅当天不下雨且我有时间，才上街。
P：天下雨。Q：我有时间。R：我上街。
分析：由于“仅当”是表示“必要条件”的，既“天不下雨且我有时间”，是“我上街”的必要条件。所以
该命题可写成：R→(?P∧Q)
例4. 人不犯我，我不犯人；人若犯我，我必犯人。
P ：人犯我。Q ：我犯人。
该命题可写成：(?P→?Q)∧(P→Q)或写成：P?Q
例5 .若天不下雨，我就上街；否则在家。
P：天下雨。Q ：我上街。R：我在家。
该命题可写成：(?P→Q)∧(P→R).
注意：中间的联结词一定是“∧”，而不是“∨”，也不是“?”。
1—4节
重言(永真)蕴涵式证明方法
方法1.列真值表。
方法2.假设前件为真，推出后件也为真。
例如求证：
((A∧B)→C)∧?D∧(?C∨D) ??A∨?B
证明:设前件((A∧B)→C)∧?D∧(?C∨D) 为真则((A∧B)→C)、?D、(?C∨D)均真，?D为T，则D为F
?C∨D为T 得C为F
((A∧B)→C )为T 得A∧B为F
如果A为F，则?A为T，所以?A∨?B为T。
如果B为F，则?B为T，所以?A∨?B 为T。
∴((A∧B)→C)∧?D∧(?C∨D) ??A∨?B
方法3.假设后件为假，推出前件也为假。
例如求证：((A∧B)→C)∧?D∧(?C∨D) ??A∨?B
证明: 假设后件?A∨?B 为F, 则A 与B 均为T 。
1. 如C 为F ，则(A∧B)→C为F，所以前件((A∧B)→C)∧?D∧(?C∨D) 为F 。
2. 如C 为T ，则
⑴若D 为T ，则?D 为F ，所以前件((A∧B)→C)∧?D∧(?C∨D) 为假；
⑵若D为F，则?C∨D 为F ，所以前件((A∧B)→C)∧?D∧(?C∨D) 为假。 ∴((A∧B)→C)∧?D∧(?C∨D) ??A∨?B
重要的重言蕴涵式( 如教材第43 页所示)（课件中出现过多次，可不用记忆）
I1. P∧Q?P I2. P∧Q?Q
I3. P?P∨Q I4. Q?P∨Q
I5. ?P?P→Q I6. Q?P→Q
I7. ?(P→Q)?P I8. ?(P→Q)??Q
I9. P,Q ?P∧Q I10. ?P∧(P∨Q)?Q
I11. P∧(P→Q)?Q I12. ?Q∧(P→Q)??P
I13. (P→Q)∧(Q→R)?P→R
I14. (P∨Q)∧(P→R)∧(Q→R)?R
I15. A→B ?(A∨C)→(B∨C)
I16. A→B ?(A∧C)→(B∧C)
1—5节
重要的等价公式（课件中出现多次，可不用记忆）
⑴对合律??P ?P ⑵幂等律P∨P?P P∧P?P
⑶结合律P∨(Q∨R)?(P∨Q)∨R P∧(Q∧R)?(P∧Q)∧R
⑷交换律P∨Q?Q∨P P∧Q?Q∧P
⑸分配律P∨(Q∧R)?(P∨Q)∧(P∨R) P∧(Q∨R)?(P∧Q)∨(P∧R)
⑹吸收律P∨(P∧Q)?P P∧(P∨Q)?P
⑺底-摩根定律?(P∨Q)??P∧?Q ?(P∧Q)??P∨?Q
⑻同一律P∨F?P P∧T?P ⑼零律P∨T?T P∧F?F
⑽互补律P∨?P?T P∧?P?F ⑾P→Q ??P∨Q
⑿P→Q ??Q→?P ⒀P?Q ?(P→Q)∧(Q→P)
⒁P?Q ?(?P∨Q)∧(P∨?Q) ⒂P?Q ?(P∧Q)∨(?P∧?Q )
例题1. 求证吸收律 P ∧(P ∨Q)?P
证明 ： P ∧(P ∨Q)
? (P ∨F)∧(P ∨Q) (同一律)
?P ∨(F ∧Q) (分配律)
?P ∨F (零律)
?P (同一律)
例题2. 求证 (?P ∨Q)→(P ∧Q) ?P
证明 (?P ∨Q)→(P ∧Q)
??(?P ∨Q)∨(P ∧Q) ( 公式E16)
? (??P ∧?Q)∨(P ∧Q) ( 摩根定律)
? (P ∧?Q)∨(P ∧Q) ( 对合律)
?P ∧(?Q ∨Q) ( 分配律)
?P ∧T ( 互补律)
?P ( 同一律)
公式E16 ： P →Q ??P ∨Q
例题3.化简?(P ∧Q)→(?P ∨(?P ∨Q))
解 原公式???(P ∧Q)∨((?P ∨?P)∨Q) (E16,结合)
?(P ∧Q)∨(?P ∨Q) (对合律，幂等律)
?(P ∧Q)∨(Q ∨?P) (交换律)
?((P ∧Q)∨Q)∨?P (结合律)
?Q ∨?P (吸收律)
公式E16 ： P →Q ??P ∨Q
1-6.范式(Paradigm)
例1. 求 P →Q 和P ?Q 的 主析取范式
方法一：真值表
P →Q ? m0∨m1∨m3
?(?P ∧?Q)∨(?P ∧Q)∨(P ∧Q)
P ?Q ?m0∨m3
? (?P ∧?Q)∨(P ∧Q)
方法Ⅱ ：用公式的等价变换
⑴ 先写出给定公式的析取范式 A1∨A2∨...∨An 。
⑵ 为使每个Ai 都变成小项，对缺少变元的Ai
补全变元，比如缺变元R ， 就用∧ 联结永真式(R ∨?R) 形式补R 。
⑶ 用分配律等公式加以整理。
P →Q ??P ∨Q
?(?P ∧(Q ∨?Q))∨((P ∨? P)∧ Q)
?(?P ∧Q)∨(?P ∧?Q)∨(P ∧Q)∨(?P ∧Q)
?(?P ∧Q)∨(?P ∧?Q)∨(P ∧Q)
T
T T T F
F F T F
T T F T
T F F PQ
PQ Q P
思考题: 永真式的主析取范式是什么样 ？（包含所有小项）
例2.求 P →Q 和P ?Q 的 主合取范式
P →Q ? M2 ? ?P ∨Q
P ?Q ? M1∧M2
? (P ∨?Q )∧(?P ∨Q)
方法Ⅱ：用公式的等价变换
⑴ 先写出给定公式的合取范式 A1∧A2∧...∧An 。
⑵ 为使每个Ai 变成大项，对缺少变元的析取式Ai 补全变元，比如缺变元R ， 就用∨联 结永假式(R ∧?R) 形式补R 。
⑶ 用分配律等公式加以整理。
例如，求(P →Q)→R 的主合取范式
(P →Q)→R
? ?(?P ∨Q)∨R
? (P ∧?Q)∨R
? (P ∨R)∧(?Q ∨R)
? (P ∨(Q ∧?Q)∨R)∧((P ∧?P)∨?Q ∨R)
? (P ∨Q ∨R)∧ (P ∨?Q ∨R)∧
(P ∨?Q ∨R)∧(?P ∨?Q ∨R)
? (P ∨Q ∨R)∧(P ∨?Q ∨R)∧ (?P ∨?Q ∨R)
例3. 安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师 希望将课程安排在第二或第三节；教原理课的教师希望将课程安排在第一或第二节。
如何安排课表，使得三位教师都满意。令L1 、L2 、L3 分别表示语言课排在第一、第二、
第三节。
M1 、M2 、M3 分别表示数学课排在第一、第二、第三节。 P1 、P2 、P3 分别表示原理课排在第一、 第二、第三节。
三位教师都满意的条件是：
(L1∨L3)∧(M2∨M3)∧(P1∨P2 ) 为真。
将上式写成析取范式( 用分配律) 得：
((L1∧M2)∨(L1∧M3)∨(L3∧M2)∨
(L3∧M3))∧(P1∨P2)
?(L1∧M2∧P1)∨(L1∧M3∧P1)∨
(L3∧M2∧P1)∨(L3∧M3∧P1)∨
(L1∧M2∧P2)∨(L1∧M3∧P2)∨
(L3∧M2∧P2)∨(L3∧M3∧P2)
可以取(L3 ∧M2∧P1)、(L1∧M3∧P2) 为T ， 得到两种排法。 T T T T F F F T F T T F T
T F F PQ PQ Q P
课堂练习： 1.已知A(P,Q,R)的真值表如图： 求它的主析取和主合取范式。
2.已知A(P,Q,R)的主析取范式中
含有下面小项m1, m3, m5, m7 求它的主合取范式. 3.已知A(P1,P2,…,Pn)的主合取范式中
含有k 个大项，问它的主析取范式
中有多少个小项？ 课堂练习答案
1.A(P,Q,R)的主析取范式:
A(P,Q,R)? m0∨m3∨m4∨m6∨m7
?(?P ∧?Q ∧?R)∨(?P ∧Q ∧R)∨
(P ∧?Q ∧?R)∨(P ∧Q ∧?R)∨(P ∧Q ∧R)
A(P,Q,R)的主合取范式：
A(P,Q,R)? M1∧M2∧M5 ?(P ∨Q ∨?R)∧(P ∨?Q ∨R)∧(?P ∨Q ∨?R)
2. A(P,Q,R)? M0∧M2∧M4 ∧M6
?(P ∨Q ∨R)∧(P ∨?Q ∨R)∧(?P ∨Q ∨R) ∧(?P ∨?Q ∨R)
3. A(P1,P2,…,Pn)的主析取范式中含有2n-k 个小项.
1-7. 命题逻辑推理
例题１求证 P →Q ，Q →R ，P ? R
证明
序号 前提或结论 所用规则 从哪几步得到 所用公式
(1) P P
(2) P →Q P
(3) Q T (1)(2) I11
(4) Q →R P
(5) R T (3)(4) I11
例题２求证
?(P ∧Q)∧(Q ∨R)∧?R ? ?P
(1) Q ∨R P
(2) ?R P
(3) Q T (1)(2) I10
(4) ?(P ∧Q) P
(5) ?P ∨?Q T (4) E8
(6) ?P T (3)(5) I10
注公式I10为： ? P,P ∨Q ? Q
公式E8为： ?(P ∧Q) ? ?P ∨?Q
例题３ 用命题逻辑推理方法证明下面推理的有效性：
如果我学习，那么我数学不会不及格。如果我不热衷于玩朴克，那么我将学习。但是我数学不及格。因此，我热衷于玩朴克。
解:设 P ：我学习。
Q ：我数学及格。 T T T T T F T T F
T F T T F F T T T T F F
F T F F T F F T F F F A(P,Q,R)
R Q P
R：我热衷于玩朴克。
于是符号化为：
P→Q，?R→P，?Q ? R
P→Q，?R→P，?Q ? R
(1) P→Q P
(2) ?Q P
(3) ?P T (1)(2) I12
(4) ?R→P P
(5) ??R T (3)(4) I12
(6) R T (5) E1
注：公式I12为：?Q，P→Q ??P
公式E1 为：??R?R
例题４求证P→(Q→S),?R∨P,Q ?R→S
证明(1) P→(Q→S) P
(2) ?P∨(?Q∨S) T (1) E16
(3) ?P∨(S∨?Q) T (2) E3
(4) (?P∨S)∨?Q T (3) E5
(5) Q P
(6) ?P∨S T (4)(5) I10
(7) P→S T (6) E16
(8) ?R∨P P
(9) R→P T (8) E16
(10) R→S T (7)(9) I13
例题５用条件论证，证明例题４
P→(Q→S),?R∨P,Q ? R→S
证明(1) R P(附加前提)
(2) ?R∨P P
(3) P T (1)(2) I10
(4) P→(Q→S) P
(5) Q→S T (3)(4) I11
(6) Q P
(7) S T (5)(6) I11
(8) R→S CP
例题６用命题逻辑推理方法证明下面推理的有效性：
如果体育馆有球赛，青年大街交通就拥挤。在这种情况下，如果小王不提前出发，就会迟到。因此，小王没有提前出发也未迟到，则体育馆没有球赛。
证明先将命题符号化。
设P：体育馆有球赛。
Q：青年大街交通拥挤。
R：小王提前出发。
S：小王迟到。
P→Q，(Q∧?R)→S ?(?R∧?S)→?P
P→Q，(Q∧?R)→S ?(?R∧?S)→?P
证明
(1) ?R∧?S P(附加前提)
(2) ?R T (1) I1
(3) ?S T (1) I2
(4) (Q∧?R)→S P
(5) ?(Q∧?Ｒ) T (3)(4) I12
(6) ?Q∨R T (5) E8
(7) ?Q T (2)(6) I10
(8) P→Q P
(9) ?P T (7)(8) I12
(10)(?R∧?S)→?P CP
例７P→Q,(?Q∨R)∧?R, ?(?P∧S)??S
证明
(1) ??S P(假设前提)
(2) S T (1) E1
(3) ?(?P∧S) P
(4) P∨?S T (3) E8
(5) P T (2)(4) I10
(6) P→Q P
(7) Q T (5)(6) I11
(8) (?Q∨R)∧?R P
(9) ?Q∨R T (8) I1
(10) ?R T (8) I2
(11) R T (7)(9) I10
(12) R∧?R T (10)(11) I9
第一章习题课
1.有工具箱A、B、C、D，各个箱内装的工具如下表所示。试问如何携带数量最少工具箱，而所包含的工具种类齐全。
工具箱改锥扳手钳子锤子
A 有有
B 有有有
C 有有
D 有有
解：设A、B、C、D分别表示带A、B、C、D箱。
则总的条件为：
(A∨C)∧(A∨B∨D)∧(B∨C)∧(B∨D) 为真。
改锥扳手钳子锤子
将(A∨C)∧(A∨B∨D)∧(B∨C)∧(B∨D)写成析取范式，上式 ((A∨C)∧(B∨C))∧((A ∨(B∨D))∧(B∨D)) (交换)
((A∧B)∨C))∧(B∨D)
(分配(提取C)、吸收)
(A∧B∧B )∨(C∧B )∨(A∧B∧D)∨(C∧D) (分配)
(A∧B)∨(C∧B )∨(A∧B∧D)∨(C∧D) 分别可以取(A∧B)、(C∧B )、(C∧D)为真。
于是可以得到三种携带方法：
带A和B箱，带B和C箱，带C和D箱。
请根据下面事实，找出凶手：
1. 清洁工或者秘书谋害了经理。
2. 如果清洁工谋害了经理，则谋害不会发生在午夜前。
3.如果秘书的证词是正确的，则谋害发生在午夜前。
4.如果秘书的证词不正确，则午夜时屋里灯光未灭。
5. 如果清洁工富裕，则他不会谋害经理。
6.经理有钱且清洁工不富裕。
7.午夜时屋里灯灭了。
令A:清洁工谋害了经理。 B:秘书谋害了经理。
C:谋害发生在午夜前。 D:秘书的证词是正确的. E:午夜时屋里灯光灭了。H:清洁工富裕.
G:经理有钱.
命题符号为：
A∨B,A?→C,D→C,?D?→E,H?→A,G∧?H,E ??
A∨B,A?→C,B→C, D→C ?D?→E,H?→A,G∧?H,E ??
⑴ E P
⑵?D?→E P
⑶??D T ⑴⑵ I
⑷ D T ⑶ E
⑸ D→C P
⑹ C T ⑷⑸ I
⑺ A?→C P
⑻?A T ⑹⑺ I
⑼ A∨B P
⑽ B T ⑻⑼ I
结果是秘书谋害了经理。
第一章小结
本章的重点内容、及要求：
１.逻辑联结词，要熟练掌握联结词的真值表定义以及它们在自然语言中的含义。其中特别要注意“∨”和“→”的用法。２.会命题符号化。
３.掌握永真式的证明方法：
(1).真值表。
(2).等价变换，化简成Ｔ。
(3).主析取范式。
４.掌握永真蕴含式的证明方法，熟练记忆并会应用
43页中表1-8.3中的永真蕴含式。
５.掌握等价公式的证明方法，熟练记忆并会应用
43页表1-8.4中的等价公式。
６.熟练掌握范式的写法及其应用。
７.熟练掌握三种推理方法。
以上自己是不是都已经熟练掌握了呢？？
第二章 命题逻辑 习题．解 ⑴不是陈述句，所以不是命题。 ⑵x 取值不确定，所以不是命题。 ⑶问句，不是陈述句，所以不是命题。 ⑷惊叹句，不是陈述句，所以不是命题。 ⑸是命题，真值由具体情况确定。 ⑹是命题，真值由具体情况确定。 ⑺是真命题。 ⑻是悖论，所以不是命题。 ⑼是假命题。 2．解 ⑴是复合命题。设p ：他们明天去百货公司；q ：他们后天去百货公司。命题符号化为q p ∨。 ⑵是疑问句，所以不是命题。 ⑶是悖论，所以不是命题。 ⑷是原子命题。 ⑸是复合命题。设p ：王海在学习；q ：李春在学习。命题符号化为p q 。 ⑹是复合命题。设p ：你努力学习；q ：你一定能取得优异成绩。p q 。 ⑺不是命题。 ⑻不是命题 ⑼。是复合命题。设p ：王海是女孩子。命题符号化为：p 。 3．解 ⑴如果李春迟到了，那么他错过考试。 ⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。 ⑶李春错过考试当且仅当他迟到了。 ⑷如果李春迟到了并且错过了考试，那么他没有通过考试。 4．解 ⑴p (q r )。⑵p q 。⑶q p 。⑷q p 。 习题 1．解 ⑴是1层公式。 ⑵不是公式。 ⑶一层： p q ，p 二层： p q 所以，)()(q p q p ??→∨是3层公式。 ⑷不是公式。 ⑸(p q )(q ( q r ))是5层公式，这是因为 一层：p q ，q ，r 二层：q r 三层：q ( q r ) 四层： (q ( q r )) 2．解 ⑴A =(p q )q 是2层公式。真值表如表2-1所示： 表2-1 p q q p ∨ A 0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 ⑵p q p q A →→∧=)(是3层公式。真值表如表2-2所示：
离散数学（课件上习题） 第一章 例1-1.1 判定下面这些句子哪些是命题。 ⑴2是个素数。 ⑵雪是黑色的。 ⑶2013年人类将到达火星。 ⑷如果a>b且b>c，则a>c 。（其中a,b,c都是 确定的实数） ⑸x+y<5 ⑹请打开书！ ⑺您去吗？ ⑴⑵⑶⑷是命题 例1-2.1 P：2是素数。 ?P：2不是素数。 例1-2.2 P：小王能唱歌。 Q：小王能跳舞。 P∧Q：小王能歌善舞。 例1-2.3. 灯泡或者线路有故障。（析取“∨”） 例1-2.4. 第一节课上数学或者上英语。（异或、排斥或。即“?”） 注意：P ?Q 与(P∧?Q)∨(Q∧?P ) 是一样的。 归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：（1）否定“?”(2) 合取“∧”(3) 析取“∨”(4) 异或“?”(5) 蕴涵“→”(6) 等价“?” 例1-2.5：P表示：缺少水分。 Q表示：植物会死亡。 P→Q：如果缺少水分，植物就会死亡。 P→Q：也称之为蕴涵式，读成“P蕴涵Q”，“如果P则Q”。 也说成P是P→Q 的前件，Q是P→Q的后件。 还可以说P是Q的充分条件，Q是P的必要条件。 以下是关于蕴含式的一个例子 P：天气好。Q：我去公园。 1.如果天气好，我就去公园。 2.只要天气好，我就去公园。 3.天气好，我就去公园。 4.仅当天气好，我才去公园。 5.只有天气好，我才去公园。 6.我去公园，仅当天气好。 命题1.、2.、3.写成：P→Q 命题4.、5.、6.写成：Q→P 例1-2.6：P：△ABC 是等边三角形。Q ：△ABC是等角三角形。 P?Q ：△ABC 是等边三角形当且仅当它是等角三角形。
离散数学命题逻辑练习 题 TTA standardization office【TTA 5AB- TTAK 08- TTA 2C】
一、选择题 1. 设命题公式) ?，记作G，使G的真值指派为1的P，Q，R的真值是( ) P∧ → (R Q 2. 与命题公式P（QR）等价的公式是( ) A () →→ D () P Q R P Q R →∨ P Q R ∨→ B () P Q R ∧→ C () 3. 下列各组公式中，哪组是互为对偶的 ( ) A ,P P B ,P P A A** D ,A A ? C ,() (其中P为单独的命题变元，A为含有联结词的公式) 4. 命题公式(P∧(P→Q))→Q是_____式。 A 重言 B 矛盾 C 可满足 D 非永真的可满足 5. 下面命题联结词集合中，哪个是最小联结词 ( ) A {,} ∧→ ?∧∨ C {}↑ D {,} ? B {,,} 6. 命题公式() ?∧→的主析取范式种含小项的个数为 ( ) P Q R A 8 B 3 C 5 D 0 7. 如果A B ?成立，则以下各种蕴含关系哪一个成立 ( ) A B A ?? ??? D A B ??? C B A ? B A B 8. 命题公式()() →∧→的主析取范式中包含小项 ( ) P Q P R A P Q R ∧?∧? ∧?∧ D P Q R ∧∧? C P Q R ∧∧ B P Q R 9. ,, A B C为任意命题公式，当（）成立时，有A B ?。 A A B ∧?∧ D C A C B →?→??? B A C B C ∨?∨ C A C B C 10. 下面4个推理定律中，不正确的是 ( ) A () ∨∧?? A B A B A A B ?∧ B () C () →∧??? A B B A A B A B →∧? D ()
数理逻辑部分 第1章命题逻辑 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令p：是有理数，则p 的真值为0 q：2 + 5 = 7，则q 的真值为1 联结词与复合命题 1.否定式与否定联结词“” 定义设p为命题，复合命题“非p”（或“p的否定”）称 为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假. 2.合取式与合取联结词“∧” 定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q. ∧称作合取联结词，并规定p∧q为真当且仅当p与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解令p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q. 令r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令t : 张辉与王丽是同学，t 是简单命题. 说明:
一、选择题 1、 设命题公式)(R Q P ∧→?,记作G ,使G 的真值指派为1的P ,Q ,R 的真值就是( ) 0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A ( 2、 与命题公式P →(Q →R )等价的公式就是( ) A ()P Q R ∨→ B ()P Q R ∧→ C ()P Q R →→ D ()P Q R →∨ 3、 下列各组公式中,哪组就是互为对偶的 ( ) A ,P P B ,P P ? C ,()A A ** D ,A A (其中P 为单独的命题变元,A 为含有联结词的公式) 4、 命题公式(P ∧(P →Q))→Q 就是_____式。 A 重言 B 矛盾 C 可满足 D 非永真的可满足 5、 下面命题联结词集合中,哪个就是最小联结词 ( ) A {,}?€ B {,,}?∧∨ C {}↑ D {,}∧→ 6、 命题公式()P Q R ?∧→的主析取范式种含小项的个数为 ( ) A 8 B 3 C 5 D 0 7、 如果A B ?成立,则以下各种蕴含关系哪一个成立 ( ) A B A ? B A B ??? C B A ??? D A B ?? 8、 命题公式()()P Q P R →∧→的主析取范式中包含小项 ( ) A P Q R ∧∧ B P Q R ∧∧? C P Q R ∧?∧ D P Q R ∧?∧? 9、 ,,A B C 为任意命题公式,当( )成立时,有A B ?。 A A B ??? B A C B C ∨?∨ C A C B C ∧?∧ D C A C B →?→ 10、 下面4个推理定律中,不正确的就是 ( ) A ()A A B ?∧ B ()A B A B ∨∧?? C ()A B A B →∧? D ()A B B A →∧??? 11、 下列命题公式就是等价公式的为( ). A.?P ∧?Q ?P ∨Q B.A →(?B →A) ??A →(A →B) C.Q →(P ∨Q )??Q ∧(P ∨Q ) D.?A ∨(A ∧B) ?B
第二章 命题逻辑 习题2、11.解 ⑴不就是陈述句,所以不就是命题。 ⑵x 取值不确定,所以不就是命题。 ⑶问句,不就是陈述句,所以不就是命题。 ⑷惊叹句,不就是陈述句,所以不就是命题。 ⑸就是命题,真值由具体情况确定。 ⑹就是命题,真值由具体情况确定。 ⑺就是真命题。 ⑻就是悖论,所以不就是命题。 ⑼就是假命题。 2.解 ⑴就是复合命题。设p :她们明天去百货公司;q :她们后天去百货公司。命题符号化为q p ∨。 ⑵就是疑问句,所以不就是命题。 ⑶就是悖论,所以不就是命题。 ⑷就是原子命题。 ⑸就是复合命题。设p :王海在学习;q :李春在学习。命题符号化为p ∧q 。 ⑹就是复合命题。设p :您努力学习;q :您一定能取得优异成绩。p →q 。 ⑺不就是命题。 ⑻不就是命题 ⑼。就是复合命题。设p :王海就是女孩子。命题符号化为:?p 。 3.解 ⑴如果李春迟到了,那么她错过考试。 ⑵要么李春迟到了,要么李春错过了考试,要么李春通过了考试。 ⑶李春错过考试当且仅当她迟到了。 ⑷如果李春迟到了并且错过了考试,那么她没有通过考试。 4.解 ⑴?p →(q ∨r )。⑵p →q 。⑶q →p 。⑷q → p 。 习题2、2 1.解 ⑴就是1层公式。 ⑵不就是公式。 ⑶一层: p ∨q ,?p 二层:?p ?q 所以,)()(q p q p ??→∨就是3层公式。 ⑷不就是公式。 ⑸(p →q )∧?(?q ?( q →?r ))就是5层公式,这就是因为 一层:p →q ,?q ,?r 二层:q →?r 三层:?q ?( q →?r ) 四层:?(?q ?( q →?r )) 2.解 ⑴A =(p ∨q )∧q 就是2层公式。真值表如表2-1所示: 表2-1 ⑵p q p q A →→∧= )(就是3层公式。真值表如表2-2所示:
一、选择题 1. 设命题公式)(R Q P ∧→?，记作G ，使G 的真值指派为1的P ，Q ，R 的真值是( ) 0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A ( 2. 与命题公式P →（Q →R ）等价的公式是( ) A ()P Q R ∨→ B ()P Q R ∧→ C ()P Q R →→ D ()P Q R →∨ 3. 下列各组公式中，哪组是互为对偶的 ( ) A ,P P B ,P P ? C ,()A A ** D ,A A (其中P 为单独的命题变元，A 为含有联结词的公式) 4. 命题公式(P ∧(P →Q))→Q 是_____式。 A 重言 B 矛盾 C 可满足 D 非永真的可满足 5. 下面命题联结词集合中，哪个是最小联结词 ( ) A {,}?€ B {,,}?∧∨ C {}↑ D {,}∧→ 6. 命题公式()P Q R ?∧→的主析取范式种含小项的个数为 ( ) A 8 B 3 C 5 D 0 7. 如果A B ?成立，则以下各种蕴含关系哪一个成立 ( ) A B A ? B A B ??? C B A ??? D A B ?? 8. 命题公式()()P Q P R →∧→的主析取范式中包含小项 ( ) A P Q R ∧∧ B P Q R ∧∧? C P Q R ∧?∧ D P Q R ∧?∧? 9. ,,A B C 为任意命题公式，当（ ）成立时，有A B ?。 A A B ??? B A C B C ∨?∨ C A C B C ∧?∧ D C A C B →?→ 10. 下面4个推理定律中，不正确的是 ( ) A ()A A B ?∧ B ()A B A B ∨∧?? C ()A B A B →∧? D ()A B B A →∧??? 11. 下列命题公式是等价公式的为（ ）． A ．?P ∧?Q ?P ∨Q B ．A →(?B →A) ??A →(A →B) C ．Q →(P ∨Q )??Q ∧(P ∨Q ) D ．?A ∨(A ∧B) ?B
第一章命题逻辑 1.1 命题与联结词 一、单项选择题 1、 A．明年“五一”是晴天。 B．这朵花多好看呀！。 C．这个男孩真勇敢啊！ D．明天下午有会吗？ 在上面句子中，是命题的是( ) 2. A．1＋101＝110 B．中国人民是伟大的。 C．这朵花多好看呀！ D．计算机机房有空位吗？ 在上面句子中，是命题的是( ) 3. A．如果天气好，那么我去散步。 B．天气多好呀！ C．x=3。 D．明天下午有会吗？ 在上面句子中( )是命题 4．下面的命题不是简单命题的是( ) A．3是素数或4是素数 B．2018年元旦下大雪 C．刘宏与魏新是同学 D．圆的面积等于半径的平方与π之积 5．下面的表述与众不一致的一个是( ) A．P：广州是一个大城市 B．?P：广州是一个不大的城市 C．?P：广州是一个很不小的城市 D．?P：广州不是一个大城市 6．设，P：他聪明；Q：他用功。在命题逻辑中，命题： “他既聪明又用功。” 可符号化为：( ) A．P ∧Q B．P→Q C．P∨?Q D．P∧?Q 7．设：P ：刘平聪明。Q：刘平用功。在命题逻辑中，命题： “刘平不但聪明，而且用功”可符号化为：( ) A．P ∧Q B．?P∨Q C．P∨?Q D．P∧?Q 8．设：P：他聪明；Q：他用功。则命题“他虽聪明但不用功。” 在命题逻辑中可符号化为( ) A．P ∧Q B．P→Q C．P∨?Q D．P∧?Q 9．设：P：我们划船。Q：我们跑步。在命题逻辑中，命题： “我们不能既划船又跑步。” 可符号化为：( ) A．P→Q B．?（P ∧Q） C．P∨Q D．P∧?Q 10．设：P：王强身体很好；Q：王强成绩很好。命题“王强身体很好，成绩也很好。”在命题逻辑中可符号化为( ) A．P ∨Q B．P→Q C．P∧?Q D．P∧Q 11．设：P：你努力；Q：你失败。则命题“除非你努力，否则你将失败。”
离散数学之命题逻辑考试 1、分析下列语句那些是命题，哪些不是命题。（每小题1分，正确 “T ”错误写 “F ”，共10分） (1)、北京是中国首都。 (2)、大连是多么美丽啊！ (3)、素数只有有限个。 (4)、请勿吸烟！ (5)、6+8≥14。 (6)、明天有离散数学课吗？ (7)、不存在最大素数。 (8)、9<+Y X 。 (9)、所有素数都是奇数。 (10)实践出真理。 2、设P 表示命题“我学习努力”。Q 表示命题“我考试通过”。R 表示命题“我很快乐”。（每小题2分，共6分） 试用符号表示下列命题： 1) 我考试没通过，但我很快乐。 2) 如果我努力学习，那么我考试通过。 3) 如果我学习努力并且考试通过，那么我很快乐。 3、将下列命题符号化：（每小题2分，共14分） 1) 我美丽而又快乐。 2) 如果我快乐，那么天就下雨。 3) 电灯不亮，当且仅当灯泡或开关发生故障。 4) 仅当你去，我将留下。 5) 如果老张和老李都不去，他就去。 6) 你不能既吃饭又看电视。 7) 张刚总是在图书馆看书，除非图书馆不开门或张刚生病。 4、给出下列公式的真值表 （每小题5分，共10分） ⑴ )(R Q P ∨→ ⑵ )(Q P ∨??)(Q P ?∧? 5、证明下列等价式。（每小题3分，共12分） 1) P Q P Q P ??∧∨∧)()( 2) P Q Q P P ?→??→→)(
3) C B A C B A →?∧?∨→)()( 4) C A D B C D B C B A →→∧?∨→∧→∧))(())(())(( 6、求下列命题公式的主析取范式和主合取范式。（每小题10分，共20分） 1) )()(Q R Q P →∧→ 2) R Q P →∨?)( 7、对于下列一组前提，请给出它们的有效结论并证明。（每小题4分，共8分） a) 如果我努力学习，那么我能通过考试，但我没有通过考试。 b) 统计表有错误，其原因有两个：一个原因是数据有错误；另一个原因是 计算有错误。现在查出统计表有错误，但计算没有错误。 8、符号化下述论断，并证明其有效性。（6分） 如果今天是周一，则要进行离散数学或C 语言程序设计两门课中的一门课考试。如果C 语言程序设计老师有会，则不考C 语言程序设计。今天是周一，C 语言程序设计老师有会，所以进行离散数学考试。 9、符号化下列命题，并推证。（6分） 如果厂方拒绝增加工资，则罢工不会停止，除非罢工超过一年并且工厂厂长辞职。因此，若厂方拒绝增加工资，而罢工又刚刚开始，罢工是不会停止的。 11、请根据下面事实，找出凶手：（8分） 1. 清洁工或者秘书谋害了经理。 2. 如果清洁工谋害了经理，则谋害不会发生在午夜前。 3.如果秘书的证词是正确的，则谋害发生在午夜前。 4.如果秘书的证词不正确，则午夜时屋里灯光未灭。 5. 如果清洁工富裕，则他不会谋害经理。 6.经理有钱且清洁工不富裕。 7.午夜时屋里灯灭了。 令A:清洁工谋害了经理。 B:秘书谋害了经理。 C:谋害发生在午夜前。 D:秘书的证词是正确的. E:午夜时屋里灯光灭了。H:清洁工富裕. G:经理有钱.
第二章 命题逻辑 1 习题2.11．解 ⑴不是陈述句，所以不是命题。 2 ⑵x 取值不确定，所以不是命题。 3 ⑶问句，不是陈述句，所以不是命题。 4 ⑷惊叹句，不是陈述句，所以不是命题。 5 ⑸是命题，真值由具体情况确定。 6 ⑹是命题，真值由具体情况确定。 7 ⑺是真命题。 8 ⑻是悖论，所以不是命题。 9 ⑼是假命题。 10 2．解 ⑴是复合命题。设p ：他们明天去百货公司；q ：他们后天去百货11 公司。命题符号化为q p 。 12 ⑵是疑问句，所以不是命题。 13 ⑶是悖论，所以不是命题。 14 ⑷是原子命题。 15 ⑸是复合命题。设p ：王海在学习；q ：李春在学习。命题符号化为p q 。 16 ⑹是复合命题。设p ：你努力学习；q ：你一定能取得优异成绩。p q 。 17 ⑺不是命题。 18 ⑻不是命题 19 ⑼。是复合命题。设p ：王海是女孩子。命题符号化为：p 。 20 3．解 ⑴如果李春迟到了，那么他错过考试。 21 ⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。 22
⑶李春错过考试当且仅当他迟到了。 23 ⑷如果李春迟到了并且错过了考试，那么他没有通过考试。 24 4．解 ⑴p (q r )。⑵p q 。⑶q p 。⑷q p 。 25 习题2.2 26 1．解 ⑴是1层公式。 27 ⑵不是公式。 28 ⑶一层： p q ，p 29 二层：p q 30 所以，)()(q p q p ??→∨是3层公式。 31 ⑷不是公式。 32 ⑸(p q )(q ( q r ))是5层公式，这是因为 33 一层：p q ，q ，r 34 二层：q r 35 三层：q ( q r ) 36 四层：(q ( q r )) 37 2．解 ⑴A =(p q )q 是2层公式。真值表如表2-1所示： 38 表2-1 39 p q q p ∨ A 0 0 0 0 0 1 1 1
一、选择题 1. 设命题公式) ?，记作G，使G的真值指派为1的P，Q，R的真值是( ) P∧ → (R Q 2. 与命题公式P?（Q?R）等价的公式是( ) A () →→ D () P Q R P Q R →∨ P Q R ∨→ B () P Q R ∧→ C () 3. 下列各组公式中，哪组是互为对偶的 ( ) A ,P P B ,P P A A** D ,A A ? C ,() (其中P为单独的命题变元，A为含有联结词的公式) 4. 命题公式(P∧(P→Q))→Q是_____式。 A 重言 B 矛盾 C 可满足 D 非永真的可满足 5. 下面命题联结词集合中，哪个是最小联结词 ( ) A {,} ∧→ ?∧∨ C {}↑ D {,} ?€ B {,,} 6. 命题公式() ?∧→的主析取范式种含小项的个数为 ( ) P Q R A 8 B 3 C 5 D 0 7. 如果A B ?成立，则以下各种蕴含关系哪一个成立 ( ) A B A ?? ??? D A B ??? C B A ? B A B 8. 命题公式()() →∧→的主析取范式中包含小项 ( ) P Q P R A P Q R ∧?∧? ∧?∧ D P Q R ∧∧? C P Q R ∧∧ B P Q R 9. ,, A B C为任意命题公式，当（）成立时，有A B ?。 A A B ∧?∧ D C A C B →?→??? B A C B C ∨?∨ C A C B C 10. 下面4个推理定律中，不正确的是 ( ) A () ∨∧?? A B A B A A B ?∧ B () C () →∧??? A B B A A B A B →∧? D ()