离散数学课后练习1
练习1.1
1、判断下列语句是否是命题，若是命题则请将其形式化：
（1）a+b
（2）x>0
（3）“请进！”
（4）所有的人都是要死的，但有人不怕死。
（5）我明天或后天去苏州。
（6）我明天或后天去苏州的说法是谣传。
（7）我明天或后天去北京或天津。
（8）如果买不到飞机票，我哪儿也不去。
（9）只要他出门，他必买书，不管他余款多不多。
（10）除非你陪伴我或代我雇辆车子，否则我不去。
（11）只要充分考虑一切论证，就可得到可靠见解；必须充分考虑一切论证，才能得到可靠见解。
（12）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。
（13）不管你和他去不去，我去。
（14）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》）
（15）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。（荀况：《荀子?劝学》）
解（1）a+b 不是命题
（2）x>0 不是命题（x是变元）
（3）“请进！”不是命题
（4）所有的人都是要死的，但有人不怕死。是命题
可表示为p∧┐q，其中p：所有的人都是要死的，q：所有的人都怕死
（5）我明天或后天去苏州。是命题
可表示为p∨q，其中p：我明天去苏州；q：我后天去苏州
（6）我明天或后天去苏州的说法是谣传。是命题
可表示为┐(p∨q)，其中p、q同（5）
（7）我明天或后天去北京或天津。是命题
可表示为p∨q∨r∨s，其中p：我明天去北京，q：我明天去天津，r：我后天去北京，s：我后天去天津
（8）如果买不到飞机票，我哪儿也不去。是命题
可表示为┐p→┐q，其中，p：我买到飞机票，q：我出去
（9）只要他出门，他必买书，不管他余款多不多。是命题
可表示为(p∧q→r)∧(┐p∧q→r)或q→r，其中p：他余款多，q：他出门，r：他买书
（10）除非你陪伴我或代我雇辆车子，否则我不去。是命题
可表示为(p∨q) ? r，其中p：你陪伴我，q：你代我雇车，r：我去
（11）只要充分考虑一切论证，就可得到可靠见解；必须充分考虑一切论证，才能得到可靠见解。是命题
可表示为(p→q) ∧(q→p )或p ?q，其中p：你充分考虑了一切论证，q：你得到了可靠见解
（12）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。是命题可表示为(q→p ) →┐q，其中p：我懂得希腊文，q：我了解柏拉图
（13）不管你和他去不去，我去。是命题
可表示为(p→r) ∧(q→r) ∧( ┐p→r) ∧( ┐q→r)或r，其中p：你去，q：他去，r：我去
（14）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》）是命题
可表示为((p∧q)→r) ∧((┐p∧┐q)→┐r)，其中p：你奢侈，q：你懒惰，r：你贫困
（15）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。（荀况：《荀子?劝学》）是命题
可表示为(p→┐q) ∧(s→r) ∧(m∧n→┐o) ∧(m∧┐n→v)，其中p：骐骥一跃，q：骐骥一跃十步，r：驽马行千里，s：驽马不断奔跑，m：你雕刻，n：你放弃，o：将朽木折断，v：金石可雕刻
2、判定下列符号串是否为公式，若是，请给出它的真值表，并请注意这些真值表的特点（公式中省略了可以省略的括号）：
（1）┐(p)（p为原子命题）
（2）(p∨qr)→s
（3）(p∨q)→p
（4）p→(p∨q)
（5）┐(p∨┐p)
（6）p∧(p→q)→q
（7）p∧(p→q)∧(p→┐q)
（8）(p→q) ? (┐q→┐p)
（9）┐(p∨q) ?┐q∧┐p
（10）┐p∨q? (p→q)
（11）(p→q)∧(q→r)→(p→r)
（12）(p∨q→r) ? (p→r)∧(q→r)
解（1）┐(p) 不是公式
（2）(p∨qr)→s 不是公式
（4）p→(p∨q) 是公式（真值表见上表，恒真）
（5
（6
（7
（8
（9
（10
（11
（
*3、A国的人只有两种，一种永远说真话，一种永远说假话。你来到A国，并在一个二叉路口不知如何走才能到达首都。守卫路口的士兵只准你问一个问题，而且他只答“是”或“不是”。你应该如何发问，才能从士兵处获知去首都的道路。
解设p：你是说真话的；q：我应当向右走去首都
你应当问：p?q ?
当回答“是(真)”，你选择向右走；当回答“不（假）”时，你选择向左走。因为p?q真，当且仅当p真且q真（士兵说真话且应当向右走）
或p假且q假（士兵说假话且应当向左走）
p?q假，当且仅当p真且q假（士兵说真话且应当向左走）
或p假且q假（士兵说假话且应当向右走）
练习1.2
1、试判定以下各式是否为重言式：
（1）(p→q)→(q→p)
（2）┐p→(p→q)
（3）q→(p→q)
（4）p∧q→(p?q)
（5）(p→q)∨(r→q)→((p∨r)→q)
（6）(p→q)∨(r→s)→((p∨r)→(q∨s))
解（1）否
（2）是
（3）是
（4）是
（5）否
（6）否
2、试用真值表验证E6，E8，E10，E11，E23。
证
（2）E8 A∧(B∨C) ?(A∧B)∨(A∧C)
（3
3、不用真值表，用代入、替换证明E12，E13，E24。
证（1）E12：A∨(A∧B) ┝┥A
A∨(A∧B) ┝┥(A∧t)∨(A∧B) 据E17用RR
┝┥A∧(t∨B) 对E8用RS
┝┥A∧t 据E16用RR
┝┥A据E17
（2）E13：A∧(A∨B) ┝┥ A
A∧(A∨B)┝┥(A∨f)∧(A∨B) 据E18用RR
┝┥A∨(f∧B) 对E9用RS
┝┥A∨f 据E19用RR
┝┥A据E18
（3）E24：A→B ┝┥┐B→┐A
┐B→┐A┝┥┐┐B∨┐A对E14用RS
┝┥B∨┐A据E1用RR
┝┥┐A∨B 对E4用RS
┝┥A→B 据E14
4、试用真值表验证I3，I4，I5，I6。
证（1
（2
（3
（4
5、不用真值表，用代入、替换证明I7，I8。
证（1）I7：(A→B)∧(C→D)┝(A∧C)→(B∧D)
(A→B)∧(C→D)┝┥(┐A∨B)∧(┐C∨D)
(A∧C)→(B∧D)┝┥(┐A∨┐C)∨(B∧D)
┝┥(┐A∨┐C∨B)∧(┐A∨┐C∨D)
由于
(┐A∨B)∧(┐C∨D)┝(┐A∨┐C∨B)∧(┐A∨┐C∨D)
故(A→B)∧(C→D)┝(A∧C)→(B∧D)。
（2）I8：(A?B)∧(B?C)┝(A?C)
(A?B)∧(B?C)┝┥(A→B)∧(B→A)∧(B→C)∧(C→B)
┝┥((A→B)∧(B→C)) ∧((C→B)∧(B→A))
┝(A→C)) ∧(C→A)
┝┥(A?C)
6、用三种不同方法证明下列逻辑等价式：
（1）A?B┝┥(A∧B)∨(┐A∧┐B)
（2）A→(B→C)┝┥B→(A→C)
（3）A→(A→B)┝┥A→B
（4）A→(B→C)┝┥(A→B)→(A→C)
┝┥(┐A∨B)∧(┐B∨A)
┝┥(┐A∧┐B)∨(┐A∧A)∨(B∧┐B)∨(B∧A)
┝┥(A∧B)∨(┐A∧┐B)
证法3：先证A?B┝(A∧B)∨(┐A∧┐B) (a)
设α为任一指派，使α(A?B)=1，那么α(A)= α(B)=1或α(A)= α(B)=0，从而
α(A∧B)=1或α(┐A∧┐B)=1，即α((A∧B)∨(┐A∧┐B))=1。(a)得证；
再证(A∧B)∨(┐A∧┐B)┝A?B(b)
设α为任一指派，使α(A?B)=0，那么α(A)=1，α(B)=0，或者α(A)=0，α(B)=1，从而α(A ∧B)=0且α(┐A∧┐B)=0，即α((A∧B)∨(┐A∧┐B))=0。(b)得证。
（2
┝┥(┐A∨┐B)∨C
┝┥(┐B∨┐A)∨C
┝┥┐B∨(┐A∨C)
┝┥B→(A→C)
证法3：先证A→(B→C)┝B→(A→C) (a)
设α为任一指派，使α(A→(B→C))=1，那么
ⅰ）α(A)= 0，则α( A→C)=1，从而α( B→(A→C))=1
ⅱ）α(A)= 1，α(B)=0，则α( B→(A→C))=1
ⅲ）α(A)=α(B)=α(C)=1，则α( B→(A→C))=1
综上，(a)得证；同理可证B→(A→C)┝A→(B→C)。
（3
┝┥(┐A∨┐A)∨B
┝┥┐A∨B
┝┥A→B
证法3：先证A→(A→B)┝A→B (a)
设α为任一指派，使α( A→B)=0，那么α(A)=1，α(B)=0，从而α( A→(A→B))=0。
(a)得证；
再证A→B┝A→(A→B)(b)
设α为任一指派，使α(A→(A→B))=0，那么α(A)=1，α(A→B)=0。(b)得证。
（
┝┥(A∧┐B) ∨(┐A∨C)
┝┥( (A∧┐B)∨┐A)∨C
┝┥((A∨┐A)∧(┐B∨┐A) )∨C
┝┥(t∧(┐A∨┐B) )∨C
┝┥(┐A∨┐B)∨C
┝┥┐A∨(┐B∨C)
┝┥A→(B→C)
证法3：先证A→(B→C)┝(A→B)→(A→C) (a)
设α为任一指派，使α((A→B)→(A→C))=0，那么α( A→B)=1，α( A→C)=0，
即α(A)= α(B)=1，α(C)=0，从而α( B→C)=0，α( A→(B→C))=0。(a)得证；
再证(A→B)→(A→C)┝A→(B→C)(b)
设α为任一指派，使α( A→(B→C))=0，那么α(A)=1，α(B→C)=0，即α(B)=1，α(C)=0，从而α(A→B)=1，α( A→C)=0，α((A→B)→(A→C))=0。(b)得证。
7、用三种不同方法证明下列逻辑蕴涵式：
（1）A∧B┝A?B
（2）(A→B)→A┝ A
（3）A→B┝((A?B)→A)→B
（4）(A∨B)∧(A→C)∧(B→C)┝ C
证（1
┝┥A?B
证法3：设α为任一指派，使α(A∧B)=1，则α(A)= α(B)=1，从而α( A?B)=1。A ∧B┝A?B得证。
（2
┝┥(A∧┐B) ∨A
┝┥(A∨A)∧(┐B∨A)
┝┥A∧(┐B∨A)
┝A
证法3：设α为任一指派，使α(A)=0，则α(A→B)= 1，从而α((A→B)→A)=0。(A →B)→A┝A得证。
（3
((A?B)→A)→B┝┥┐((A?B)→A)∨B
┝┥((A?B)∧┐A)∨B
┝┥(((A∧B)∨(┐A∧┐B))∧┐A)∨B
┝┥(┐A∧┐B)∨B
┝┥┐A∨B
∴A→B┝((A?B)→A)→B
证法3：设α为任一指派，使α( A→B)=1，则（ⅰ）α(A)= 0；（ⅱ）α(B)= 1。对（ⅱ）显然有α( ((A?B)→A)→B)=1；
对（ⅰ）则可令α(B)= 0（α(B)= 1的情况已证），于是α(A?B)=1，α((A?B)→A)=0，α(((A?B)→A)→B) =1。
A→B┝((A?B)→A)→B得证。
┝┥(A∨B∨C)∧(A∨B∨┐C)∧(┐A∨B∨C)∧(┐A∨┐B∨C)∧(A
∨┐B∨C)
┝(A∨B∨C)∧(A∨┐B∨C)∧(┐A∨B∨C)∧(┐A∨┐B∨C)
┝┥(A∨C)∧(┐A∨C)
┝┥C
证法3：设α为任一指派，使α((A∨B)∧(A→C)∧(B→C))=1，则α(A∨B)= α( A→C)= α( B →C)=1。由α(A∨B)=1有两种情况：
（ⅰ）α(A)=1，由α( A→C)=1得α(C)=1；
（ⅱ）α(B)= 1，由α( B→C)=1得α(C)=1。
(A∨B)∧(A→C)∧(B→C)┝C得证。
△8、验证下列逻辑等价式和逻辑蕴涵式，并写出它们的对偶式：
（1）┐(┐A∨┐B)∨┐(┐A∨B)┝┥A
（2）(A∨┐B)∧(A∨B)∧(┐A∨┐B)┝┥┐(┐A∨B)
（3）B∨┐((┐A∨B)∧A)┝┥t
（4）┐A∨(┐B∨C)┝┐(┐A∧B)∨(┐A∨C)
（5）┐(A∨B)∨C┝A∨(┐B∨C)
解（1）┐(┐A∨┐B)∨┐(┐A∨B)┝┥(A∧B)∨(A∧┐B)
┝┥A∧(B∨┐B)
┝┥A
对偶式：┐(┐A∧┐B)∧┐(┐A∧B)┝┥A
（2）(A∨┐B)∧(A∨B)∧(┐A∨┐B)┝┥A∧(B∨┐B)∧(┐A∨┐B)
┝┥A∧(┐A∨┐B)
┝┥A∧┐B
┝┥┐(┐A∨B)
对偶式：(A∧┐B)∨(A∧B)∨(┐A∧┐B)┝┥┐(┐A∧B)
（3）B∨┐((┐A∨B)∧A)┝┥B∨((A∧┐B)∨┐A)
┝┥B∨(┐B∨┐A)
┝┥t
对偶式：B∧┐((┐A∧B)∨A)┝┥f
（4）┐A∨(┐B∨C)┝A∨┐B∨┐A∨C
┝┐(┐A∧B)∨(┐A∨C)
对偶式：┐(┐A∨B)∧(┐A∧C)┝┐A∧(┐B∧C)
（5）┐(A∨B)∨C┝(┐A∧┐B)∨C
┝(┐A∨C)∧(┐B∨C)
┝┐B∨C
┝A∨(┐B∨C)
对偶式：A∧(┐B∧C)┝┐(A∧B)∧C
练习1.3
1、求下列公式的析取范式、合取范式及主析取范式、主合取范式，并据主析（合）取范式直接确定弄真该公式的指派和弄假该公式的指派：
（1）(┐p∨┐q)→(p?┐q)
（2）q∧(p∨┐q)
（3）p∨(┐p→(q∨(┐q→r)))
（4）(p→(q∧r))∧(┐p→(┐q∧┐r))
（5）p→(p∧(q→r))
解（1）(┐p∨┐q)→(p?┐q)┝┥┐(┐p∨┐q)∨((┐p∨┐q)∧(p∨q))
┝┥(p∧q)∨(┐p∧q)∨(p∧┐q) （主析取范式）
┝┥q∨(p∧┐q) （析取范式）
┝┥p∨q （合取范式、主合取范式）
弄真指派：p 1 0 1 弄假指派：p 0
q 1 1 0 q 0
（2）q∧(p∨┐q)┝┥q∧(p∨┐q) （合取范式）
┝┥((p∧┐p)∨q)∧(p∨┐q)
┝┥(p∨q)∧(┐p∨q)∧(p∨┐q) （主合取范式）
┝┥p∧q （析取范式、主析取范式）
弄真指派：p 1 弄假指派：p 0 1 0
q 1 q 0 0 1
（3）p∨(┐p→(q∨(┐q→r)))┝┥p∨(p∨(q∨(q∨r)))
┝┥p∨q∨r （合取范式、主合取范式）┝┥(p∧(q∨┐q)∧(r∨┐r))∨(q∧(p∨┐p)∧(r∨┐r))∨(r∧(p∨┐p)∧(q∨┐q)) ┝┥(p∧q∧r)∨(p∧q∧┐r)∨(p∧┐q∧r)∨(p∧┐q∧┐r)∨(┐p∧q∧r)∨
(┐p∧q∧┐r)∨(┐p∧┐q∧r) （析取范式、主析取范式）
弄真指派：p 1 1 1 1 0 0 0 弄假指派：p 0
q 1 1 0 0 1 1 0 q 0
r 1 0 1 0 1 0 1 r 0
（4）(p→(q∧r))∧(┐p→(┐q∧┐r))┝┥(┐p∨(q∧r ))∧(p∨(┐q∧┐r))
┝┥(┐p∨q)∧(┐p∨r )∧(p∨┐q)∧(p∨┐r) （合取范式）┝┥(┐p∨q∨r)∧(┐p∨q∨┐r)∧(┐p∨┐q∨r )∧(p∨┐q∨r)∧(p∨┐q∨┐r)∧(p ∨q∨┐r) （主合取范式）
┝┥(┐p∧p)∨(q∧r∧p)∨(┐p∧┐q∧┐r)∨(q∧r∧┐q∧┐r) （析取范式）
┝┥(p∧q∧r)∨(┐p∧┐q∧┐r) （主析取范式）
弄真指派：p 1 0 弄假指派：p 1 1 1 0 0 0
q 1 0 q 0 0 1 1 1 0
r 1 0 r 0 1 0 0 1 1
（5）p→(p∧(q→r))┝┥┐p∨(p∧(┐q∨r ))
┝┥┐p∨(p∧┐q)∨(p∧r ) （析取范式）┝┥(┐p∧q∧r)∨(┐p∧q∧┐r)∨(┐p∧┐q∧r)∨(┐p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧┐q∧┐r)∨(p∧q∧r) （主析取范式）
┝┥(┐p∨p)∧(┐p∨┐q∧r ) （合取范式）
┝┥┐p∨┐q∧r （主合取范式）
弄真指派：p 0 0 0 0 1 1 1 弄假指派：p 1
q 1 1 0 0 0 0 1 q 1
r 1 0 1 0 1 0 1 r 0
2、主析取范式的两个不同析取项可能在同一指派下均真吗？为什么？主合取范式的两个不同合取项可能在同一指派下均假吗？为什么？
答主析取范式的两个不同析取项不可能在同一指派下均真。因为给定命题公式，其每个命题变元p1, …,p n在每个析取项中均恰出现一次，要使某个析取项在某指派下为真，则该指派下p1, …,p n的取值完全确定，而两个析取项又不相同，所以一个指派最多弄真一个析取项。同理可知主合取范式的两个不同合取项不可能在同一指派下均假。
3、利用范式证明下列公式为永真式（证明合取范式的每一个合取项中含有互补文字、或其主析取范式中含有2n个析取项，n是公式中变元的个数）
（1）(p→q)∧p→q
（2）((p→q)→(┐p→┐q)) →(( ┐q→┐p)→(q→p))
（3）(p?q) ?((p∧q)∨(┐p∧┐q))
（4）(p?q) ?((r∧p) ?(r∧q))∧((r∨p) ?(r∨q))
（5）┐(p↓q) ?┐p↑┐q
（6）┐(p↑q) ?┐p↓┐q
证（1）(p→q)∧p→q┝┥┐((┐p∨q)∧p)∨q
┝┥┐(┐p∨q)∨┐p∨q
┝┥(p∧┐q)∨┐p∨q
┝┥(p∨┐p∨q)∧(┐q∨┐p∨q)
∵合取范式的每一个合取项中均含有互补文字
∴原式为永真式
（2）((p→q)→(┐p→┐q)) →(( ┐q→┐p)→(q→p))
┝┥┐(┐(┐p∨q)∨(p∨┐q)) ∨(┐( q∨┐p)∨(┐q∨p))
┝┥( (┐p∨q)∧(┐p∧q)) ∨((┐q∧p)∨(┐q∨p))
┝┥(┐p∧┐p∧q)∨(q∧┐p∧q)∨(┐q∧p)∨(┐q∧p)∨(┐q∧┐p)∨(p∧q)∨(p∧┐
q)
┝┥(┐p∧q)∨(┐q∧┐p)∨(p∧q)∨(p∧┐q)
∵主析取范式中含有22个析取项
∴原式为永真式
（3）(p?q) ?((p∧q)∨(┐p∧┐q))
┝┥(((p→q)∧(q→p))→((p∧q)∨(┐p∧┐q))) ∧(((p∧q)∨(┐p∧┐q))→((p→q)∧(q→p))) ┝┥(┐((┐p∨q)∧(┐q∨p)) ∨((p∧q)∨(┐p∧┐q))) ∧(┐((p∧q)∨(┐p∧┐q)) ∨((┐p ∨q)∧(┐q∨p)))
┝┥((p∧┐q)∨(q∧┐p)∨(p∧q)∨(┐p∧┐q)) ∧(((┐p∨┐q)∧(p∨q)) ∨((┐p∨q)∧(┐q∨p)))
┝┥((p∧┐q)∨(q∧┐p)∨(p∧q)∨(┐p∧┐q)) ∧((┐p∨┐q∨┐p∨q)∧(p∨q∨┐p∨q)∧(┐p∨┐q∨┐q∨p)∧(p∨q∨┐q∨p))
┝┥(p∧┐q)∨(q∧┐p)∨(p∧q)∨(┐p∧┐q)
∵主析取范式中含有22个析取项
∴原式为永真式
（4）(p?q) ?((r∧p) ? (r∧q))∧((r∨p) ?(r∨q))
┝┥(p→q)∧(q→p) ?(((r∧p)→(r∧q))∧((r∧q)→(r∧p)))∧(((r∨p)→(r∨q))∧((r∨q)→(r∨p)))
┝┥(┐p∨q)∧(┐q∨p) ? ((┐(r∧p)∨(r∧q))∧(┐(r∧q)∨(r∧p)))∧((┐(r∨p) ∨(r∨q))∧(┐(r∨q)∨(r∨p)))
┝┥(p∧q)∨(┐p∧┐q) ? (┐p∨q∨┐r)∧(p∨┐q∨┐r)∧(p∨┐q∨r)∧(┐p∨q∨r) ┝┥(┐((p∧q)∨(┐p∧┐q))∨((┐p∨q∨┐r)∧(p∨┐q∨┐r)∧(p∨┐q∨r)∧(┐p∨q∨r))) ∧(┐((┐p∨q∨┐r)∧(p∨┐q∨┐r)∧(p∨┐q∨r)∧(┐p∨q∨r))∨((p∧q)∨
(┐p∧┐q)))
┝┥((┐p∨┐q∨q∨r)∧(p∨q∨┐p∨r)∧(┐p∨┐q∨p∨r)∧(p∨q∨┐q∨r) ∧(┐p∨┐q∨p∨┐r)∧(p∨q∨┐q∨┐r)∧(┐p∨┐q∨q∨┐r)∧(p∨q∨┐p∨┐r)) ∧
((p∧┐q∧┐r)∨(┐p∧q∧┐r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q)∨(┐p∧┐q)) ┝┥(p∧┐q∧┐r)∨(┐p∧q∧┐r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q)∨(┐p∧┐q) ┝┥(p∧┐q∧┐r)∨(┐p∧q∧┐r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q∧┐r)∨(p∧q∧r)∨(┐p∧┐q∧┐r)∨(┐p∧┐q∧r)
∵主析取范式中含有23个析取项
∴原式为永真式
（5）┐(p↓q) ?┐p↑┐q┝┥┐┐(p∨q) ?┐(┐p∧┐q)
┝┥p∨q ? p∨q
┝┥(┐(p∨q)∨(p∨q)) ∧(┐(p∨q)∨(p∨q))
┝┥(┐p∨p∨q) ∧(┐q∨p∨q)
∵合取范式的每一个合取项中均含有互补文字
∴原式为永真式
（6）┐(p↑q) ?┐p↓┐q┝┥┐┐(p∧q) ?┐(┐p∨┐q)
┝┥p∧q ? p∧q
┝┥(┐(p∧q)∨(p∧q)) ∧(┐(p∧q)∨(p∧q))
┝┥(┐p∨┐q∨p) ∧(┐p∨┐q∨q)
∵合取范式的每一个合取项中均含有互补文字
∴原式为永真式
4、把公式(p→q) ?(┐q→┐p)变换为与之等价的、只含联结词↓或↑的公式。
解(p→q) ?( ┐q→┐p)┝┥(┐(┐p∨q)∨( q∨┐p)) ∧(┐( q∨┐p)∨(┐p∨q))
┝┥((┐p↓q)∨┐( q↓┐p)) ∧( ( q↓┐p)∨┐(┐p↓q))
┝┥┐(┐((┐p↓q)∨┐( q↓┐p)) ∨┐(( q↓┐p)∨┐(┐p↓q)))
┝┥((┐p↓q) ↓┐( q↓┐p)) ↓ (( q↓┐p) ↓┐(┐p↓q))
┝┥(((p↓p)↓q)↓((q↓(p↓p))↓(q↓(p↓p))))↓((q↓(p↓p))↓(((p↓p)↓q)
↓((p↓p)↓q)))
(p→q) ?( ┐q→┐p)┝┥(┐(┐p∨q)∨( q∨┐p)) ∧(┐( q∨┐p)∨(┐p∨q))
┝┥┐(┐(p∧┐q)∧(┐q∧p)) ∧┐(┐(┐q∧p)∧(p∧┐q))
┝┥┐(((p↑┐q) ↑┐(┐q↑p)) ↑ ((┐q↑p) ↑┐(p↑┐q)))
┝┥(((p↑(q↑q))↑(((q↑q)↑p)↑((q↑q)↑p))↑(((q↑q)↑p)↑((p↑(q↑q))↑(p↑(q↑q)))))↑
(((p↑(q↑q)) ↑(((q↑q)↑p) ↑((q↑q)↑p))↑ (((q↑q)↑p)↑((p↑(q↑q))↑ (p↑(q↑q)))))
△5、求证┐, →及Δ1,→都是完备联结词组。你还能找到恰由两个联结词组成的完备联结词组吗？
证利用已知完备联结词组┐,∧,∨证明
（1）┐, →
p∨q┝┥┐┐p∨q┝┥┐p→q
p∧q┝┥┐(┐p∨┐q)┝┥┐(p→┐q)
∵完备联结词组┐,∧,∨中的任一个都可以用┐, →表示
∴┐, →构成完备联结词组
（2）Δ1, →
┐p┝┥p→f┝┥p→Δ1(p)
∵完备联结词组┐, →中的任一个都可以用Δ1, →表示
∴Δ1, →构成完备联结词组
其他恰由两个联结词组成的完备联结词组还有(┐,∧)，(┐,∨),( Δ4, →)等。
(完整版)离散数学作业答案一
离散数学作业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 .请将语句“今天是天晴”翻译成命题公式
离散数学复习要点
离散数学复习要点第一章命题逻辑 一、典型考查点 1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5 3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9 5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。 6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15 7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A?B的充要条件是A?B且B?A。主要等价式：(1)双否定：??A?A。(2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。3)结合律：(A∧B)∧C?A ∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等幂律：A∧A?A，A∨A?A。(7) 同一律：A∧T?A，A∨F?A。(8) 零律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。(10) 互补律：A∧?A?F，(矛盾律)，A∨?A?T。(排中律)(11) 条件式转化律：A→B??A∨B，A→B??B→?A。(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B) 8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A?B，即证A→B是永真式。 9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P?P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P?P∧（?Q∨Q)或P?P∨（?Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。 注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q?m1∨m3?M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16 11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。 重点规则（主要蕴含式）：(1) P∧Q?P化简(2) P∧Q?Q化简(3) P?P∨Q附加(4) ?P?P→Q变形附加(5)Q?P→Q变形附加(6) ?(P→Q)?P变形化简(7) ?(P→Q)??Q变形化简(8) P，(P→Q)?Q假言推理(9) ?Q，(P→Q)??P拒取式(10) ?P，(P∨Q)?Q析取三段论(11) (P→Q)，(Q→R)?P→R条件三段论(12) (P?Q)，(Q?R)?P?R 双条件三段论 文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21 二、强化练习 1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗? 2.下列式子为重言式的是( ) A.P→P∨Q B.(┐P∧Q)∧(P∨┐Q) C.┐ (P Q) D.(P∨Q) (P→Q) 3．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 4．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的 5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q） 6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式 7．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 8．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）
离散数学必备知识点总结
离散数学必备知识点总 结 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT
总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；
2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系；
离散数学(第五版)清华大学出版社第2章习题解答
离散数学（第五版）清华大学出版社第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令F(x):x是鸟 G(x):x会飞翔. 命题符号化为 ?x(F(x)→G(x)). (2)令F(x):x为人. G(x):x爱吃糖 命题符号化为 ??x(F(x)→G(x)) 或者 ?x(F(x)∧?G(x)) (3)令F(x):x为人. G(x):x爱看小说. 命题符号化为 ?x(F(x)∧G(x)). (4) F(x):x为人. G(x):x爱看电视. 命题符号化为 ??x(F(x)∧?G(x)). 分析1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的F(x)都是特性谓词。 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 27 ?x(F(x)∧G(x)) 即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。
3°（2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 ?xF(x) 其中F(x):(x+1)2=x2+2x+1,此命题在(a),(b),(c)中均为真命题。 （2）在(a),(b),(c)中均符号化为 ?xG(x) 其中G(x):x+2=0，此命题在（a）中为假命题，在(b)(c)中均为真命题。 （3）在(a),(b),(c)中均符号化为 ?xH(x) 其中H(x):5x=1.此命题在(a),(b)中均为假命题，在(c)中为真命题。 分析1°命题的真值与个体域有关。 2°有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 ?xF(x) 这里，F(x):x呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ?x(F(x)→G(x)) 这里，F(x):x为人，且F(x)为特性谓词。G(x):x呼吸。 28 2．3 因题目中未给出个体域，因而应采用全总个体域。 （1）令：F(x):x是大学生，G(x):x是文科生，H(x):x是理科生，命题符号化为?x(F(x)→(G(x)∨H(x)) （2）令F(x):x是人，G(y):y是化，H(x):x喜欢，命题符号化为 ?x(F(x)∧?y(G(y)→H(x,y))) （3）令F(x):x是人，G(x):x犯错误，命题符号化为 ??x(F(x)∧?G(x)), 或另一种等值的形式为 ?x(F(x)→G(x)
电大 离散数学作业7答案
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1或T ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如 果他生病或出差了，我就同意他不参加学习”符号化的结果为 （P ∨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 },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) ∨A(b)) ∨((B(a) ∧B(b)) ． 6．设个体域D ＝{1, 2, 3}，A (x )为“x 大于3”，则谓词公式(?x )A (x ) 的真值为 0(F) ． 7．谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y ． 8．谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ，y ))中的约束变元为 x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 设P ：今天是晴天。 姓 名： 学 号： 得 分： 教师签名：
离散数学第四章二元关系和函数知识点总结
集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y，按照一定的顺序组成的 二元组称为有序对，记作
不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律 A(B C)=(A B)(A C) (B C)A=(B A)(C A) A(B C)=(A B)(A C) (B C)A=(B A)(C A) 若A或B中有一个为空集，则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证明A(B C)=(A B)(A C) 证任取
离散数学 第1章 习题解答
习题 1. 下列句子中，哪些是命题哪些不是命题如果是命题，指出它的真值。 ⑴中国有四大发明。 ⑵计算机有空吗 ⑶不存在最大素数。 ⑷21+3＜5。 ⑸老王是山东人或河北人。 ⑹2与3都是偶数。 ⑺小李在宿舍里。 ⑻这朵玫瑰花多美丽呀! ⑼请勿随地吐痰! ⑽圆的面积等于半径的平方乘以。 ⑾只有6是偶数，3才能是2的倍数。 ⑿雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。 解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。 2. 将下列复合命题分成若干原子命题。 ⑴李辛与李末是兄弟。 ⑵因为天气冷，所以我穿了羽绒服。 ⑶天正在下雨或湿度很高。 ⑷刘英与李进上山。 ⑸王强与刘威都学过法语。 ⑹如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题； ⑵p：天气冷；q：我穿羽绒服； ⑶p：天在下雨；q：湿度很高； ⑷p：刘英上山；q：李进上山； ⑸p：王强学过法语；q：刘威学过法语； ⑹p：你看电影；q：我看电影； ⑺p：我看电视；q：我外出；r：我睡觉； ⑻p：天下大雨；q：他乘班车上班。 3. 将下列命题符号化。 ⑴他一面吃饭，一面听音乐。 ⑵3是素数或2是素数。 ⑶若地球上没有树木，则人类不能生存。
⑷8是偶数的充分必要条件是8能被3整除。 ⑸停机的原因在于语法错误或程序错误。 ⑹四边形ABCD是平行四边形当且仅当它的对边平行。 ⑺如果a和b是偶数，则a+b是偶数。 解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p∧q ⑵p：3是素数；q：2是素数；原命题符号化为：p∨q ⑶p：地球上有树木；q：人类能生存；原命题符号化为：p→q ⑷p：8是偶数；q：8能被3整除；原命题符号化为：pq ⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→p ⑹p：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：pq。 ⑺p：a是偶数；q：b是偶数；r：a+b是偶数；原命题符号化为：p∧q→r 4. 将下列命题符号化，并指出各复合命题的真值。 ⑴如果3+3=6，则雪是白的。 ⑵如果3+3≠6，则雪是白的。 ⑶如果3+3=6，则雪不是白的。 ⑷如果3+3≠6，则雪不是白的。 ⑸3是无理数当且仅当加拿大位于亚洲。 ⑹2+3=5的充要条件是3是无理数。(假定是10进制) ⑺若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。 ⑻当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。 解：设p：3＋3＝6。q：雪是白的。 ⑴原命题符号化为：p→q；该命题是真命题。 ⑵原命题符号化为：p→q；该命题是真命题。 ⑶原命题符号化为：p→q；该命题是假命题。 ⑷原命题符号化为：p→q；该命题是真命题。 ⑸p：3是无理数；q：加拿大位于亚洲；原命题符号化为：pq；该命题是假命题。 ⑹p：2+3＝5；q：3是无理数；原命题符号化为：pq；该命题是真命题。 ⑺p：两圆O1,O2的面积相等；q：两圆O1,O2的半径相等；原命题符号化为：pq；该命题是真命题。 ⑻p：王小红心情愉快；q：王小红唱歌；原命题符号化为：pq；该命题是真命题。 习题
离散数学作业答案一
离散数学作业7 离散数学数理逻辑部分形成性考核书 面作业 本课程形成性考核书面作业共3次,内容主要分别就是集合论部分、图论部分、数理逻辑部分的综合练习,基本上就是按照考试的题型(除单项选择题外)安排练习题目,目的就是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业就是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”与“交卷”按钮,以便教师评分。 一、填空题 1.命题公式()P Q P →∨的真值就是 T 或1 . 2.设P :她生病了,Q :她出差了.R :我同意她不参加学习、 则命题“如果她生病或出差了,我就同意她不参加学习”符号化的结果为 (P ∨Q)→R . 3.含有三个命题变项P ,Q ,R 的命题公式P ∧Q 的主析取范式就是 )()(R Q P R Q P ?∧∧∨∧∧ . 4.设P (x ):x 就是人,Q (x ):x 去上课,则命题“有人去上课.” 可符号化为 ))()((x Q x P x ∧? . 5.设个体域D ＝{a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 ))()(())()((b B a B b A a A ∧∨∨ . 6.设个体域D ＝{1, 2, 3},A (x )为“x 大于3”,则谓词公式(?x )A (x ) 的真值为 F 或0 . 7.谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y . 8.谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ,y ))中的约束变元为 x . 三、公式翻译题 1.请将语句“今天就是天晴”翻译成命题公式. P 。，P 则今天是天晴设答:: 2.请将语句“小王去旅游,小李也去旅游.”翻译成命题公式. Q 。P ；，Q P ∧则小李去旅游小王去旅游设答::: 3.请将语句“如果明天天下雪,那么我就去滑雪”翻译成命题公式. Q 。P ；，Q P →则我去滑雪明天下雪设答;:: 4.请将语句“她去旅游,仅当她有时间.”翻译成命题公式.
离散数学知识点整理
离散数学 一、逻辑和证明 1.1命题逻辑 命题：是一个可以判断真假的陈述句。 联接词：∧、∨、→、?、?。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。 系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。 1.3命题等价式 逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。
谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x>0P(x)。 当论域中的元素可以一一列举，那么?xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理，?xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。 两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。 量词表达式的否定：??xP(x) ??x?P(x)，??xP(x) ??x?P(x)。 1.5量词嵌套 我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。 1.6推理规则 一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证
二、集合、函数、序列、与矩阵 2.1集合 ∈说的是元素与集合的关系，?说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。 A和B相等当仅当?x(x∈A?x∈B)；A是B的子集当仅当?x(x∈A→x∈B)；A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。 幂集：集合元素的所有可能组合，肯定有?何它自身。如?的幂集就是{?}，而{?}的幂集是{?，{?}}。 考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。 一对一或者单射：B可能有多余的元素，但不重复指向。 映上或者满射：B中没有多余的元素，但可能重复指向。 一一对应或者双射：符合上述两种情况的函数关系。 反函数：如果是一一对应的就有反函数，否则没有。 合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。 2.4序列 无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。 如果A和B是可数的，则A∪B也是可数的。
离散数学1-6章练习题及答案
离散数学练习题 第一章 一?填空 1?公式(p q) ( p q)的成真赋值为01; 10 2?设p, r为真命题，q, s为假命题，则复合命题(p q) ( r s)的真值为0 3?公式(p q)与(p q) ( p q)共同的成真赋值为01 ；10 4?设A为任意的公式，B为重言式，则A B的类型为重言式 5. 设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二.将下列命题符合化 1. ■ 7不是无理数是不对的。 解：(p)，其中p：. 7是无理数；或p,其中p: . 7是无理数。 2?小刘既不怕吃苦，又很爱钻研。 解：p q,其中p:小刘怕吃苦，q :小刘很爱钻研 3?只有不怕困难，才能战胜困难。 解：q p，其中p:怕困难，q:战胜困难 或p q，其中p:怕困难，q:战胜困难 4?只要别人有困难，老王就帮助别人，除非困难解决了。 解：r (p q)，其中p:别人有困难，q:老王帮助别人，r:困难解决了 或：(r p) q，其中p：别人有困难，q:老王帮助别人，r:困难解决了 5?整数n是整数当且仅当n能被2整除。 解：p q，其中p:整数n是偶数，q:整数n能被2整除 三、求复合命题的真值 P：2能整除5, q：旧金山是美国的首都，r：在中国一年分四季
1. ((p q) r) (r (p q)) 2?((q p) (r p)) (( p q) r 解：p, q为假命题，r为真命题 1. (( p q) r) (r (p q))的真值为0 2. (( q p) (r p)) (( p q) r 的真值为1 四、判断推理是否正确 设y 2x为实数，推理如下： 若y在x=0可导，则y在x=0连续。y在x=0连续，所以y在x=0可导。 解：y 2x，x为实数，令p: y在x =0可导，q: y在x=0连续。P为假命题，q为真命题，推理符号化为：(p q) q p，由p, q得真值可知，推理的真值为0,所以推理不正确。 五、判断公式的类型 1，( (q p) ((p q) ( p q))) r 2. (p (q p)) (r q) 3. (p r) (q r)
离散数学作业答案完整版
离散数学作业答案 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={
离散数学第一章命题逻辑知识点总结
数理逻辑部分 第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 是简单命题 . 说明:
离散数学第二章一阶逻辑知识点总结
数理逻辑部分 第2章一阶逻辑 2.1 一阶逻辑基本概念 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n≥2): 表示事物之间的关系 如L(x,y)：x与y有关系L，L(x,y)：x≥y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项 量词: 表示数量的词 全称量词?: 表示任意的, 所有的, 一切的等 如?x 表示对个体域中所有的x
存在量词?: 表示存在, 有的, 至少有一个等 如?x表示在个体域中存在x 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲 在命题逻辑中, 设p:墨西哥位于南美洲 符号化为p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a) 例2 在一阶逻辑中将下面命题符号化 (1)人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 . 解：(a) (1) 设G(x)：x爱美, 符号化为?x G(x) (2) 设G(x)：x用左手写字, 符号化为?x G(x) (b) 设F(x)：x为人，G(x)：同(a)中
离散数学 第2章 习题解答
第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令x (是鸟 x F:) (会飞翔. G:) x x 命题符号化为 x F ?. G x→ ) ( )) ( (x (2)令x x (为人. F:) (爱吃糖 G:) x x 命题符号化为 x F x→ G ?? )) ( ) ( (x 或者 F x? x ∧ ? ) )) ( ( (x G (3)令x x (为人. F:) G:) (爱看小说. x x 命题符号化为 x F ?. G x∧ (x ( )) ( ) (4) x (为人. x F:) (爱看电视. G:) x x 命题符号化为 F x? ∧ ??. x G ( ) ( )) (x 分析 1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的) F都是特性谓词。 (x 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 F x ? G x∧ ( )) ( ) (x
即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。 3° （2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 )(x xF ? 其中,12)1(:)(22++=+x x x x F 此命题在)(),(),(c b a 中均为真命题。 （2） 在)(),(),(c b a 中均符号化为 )(x xG ? 其中02:)(=+x x G ，此命题在（a ）中为假命题，在(b)(c)中均为真命题。 （3）在)(),(),(c b a 中均符号化为 )(x xH ? 其中.15:)(=x x H 此命题在)(),(b a 中均为假命题，在(c)中为真命题。 分析 1°命题的真值与个体域有关。 2° 有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 )(x xF ? 这里，x x F :)(呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ))()((x G x F x →? 这里，x x F :)(为人，且)(x F 为特性谓词。x x G :)(呼吸。 2．3 因题目中未给出个体域，因而应采用全总个体域。
离散数学作业答案
第一章 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规则 第五章
离散数学1和2章作业
集合论部分： 1.若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（）。 2.若A-B=Ф，则下列哪个结论不可能正确？( ) (1) A=Ф (2) B=Ф(3) A?B (4) B?A 3.判断下列命题哪几个为正确？( ) (1) {Ф}∈{Ф,{{Ф}}} (2) {Ф}?{Ф,{{Ф}}} (3) Ф∈{{Ф}} (4) Ф?{Ф} (5) {a,b}∈{a,b,{a},{b}} 4. 设A∩B=A∩C，A∩B=A∩C，则B( )C。 5. 设,, A B C是论述域U的任意子集，证明下列各式： (a) () A B A ； -=Φ (b) ()()() ； A B C A B A C -=-- 6.证明:() -⊕= ； A B B A B
7.某班有50名学生，第一次考试中26人成绩为优，第二次考试中21人成绩为优，已知两 次考试中都不为优的共17人。问两次考试中都为优的有多少人？ 8.试证明集合等式：A? (B?C)=(A?B) ? (A?C)． 二元关系部分： 1 请描述得到传递闭包的算法 2举出集合A上的既是等价关系又是偏序关系的一个例子。( ) 3 集合A上的等价关系的三个性质是什么？( ) 4 集合A上的偏序关系的三个性质是什么？( ) 5 设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝求(1)R R (2) R-1 。
6 设Ａ＝｛1，2，3，4，5，6｝，Ｒ是A 上的整除关系，求R 。 7 设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B 的关系Ｒ＝｛〈x,y 〉|x=2y ｝，求(1)R (2) R-1 。 8 集合A={1,2,…,10}上的关系R={
离散数学(命题逻辑)课后总结
离散数学（课件上习题） 第一章 例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 是等边三角形当且仅当它是等角三角形。