下载文档原格式
离散数学总复习资料一、鸽笼原理与容斥原理1．求证边长为1的正方形中放9个点，由这些点构成的三角形中，必有一个三角形面积小于18。
证：把该正方形均分成四个相同的小正方形，则由鸽笼原理知，必有一个小正方形内存在三个点，且这三个点构成的三角形面积小于18。
# 2．对一列21n +个不同整数，任意排列，证明一定存在长为1n +的上升子序列或下降子序列。
证：设此序列为：2121,,,,,k n a a a a +，从k a 开始上升子序列最长的长度为k x ，下降子序列最长的长度为k y ，每一个k a 2(1,2,,1)k n =+都对应了(,)k k x y 。
若不存在长为1n +的上升子序列或下降子序列，那么,k k x n y n ≤≤，形如(,)k k x y 的不同点对至多有2n 个，而k a 有21n +个，则由鸽笼原理知，必有,i j a a 2(11)i j n ≤<≤+同时对应(,)i i x y =(,)j j x y ，由于i j a a ≠，若i j a a <，则i x 至少比j x 大1，若i j a a >，则i y 至少比j y 大1，这均与(,)i i x y =(,)j j x y 矛盾。
故原命题成立。
#3．求}100,,2,1{ 中不被3、4、5整除的个数。
解： 设A 表示}100,,2,1{ 中被3整除的数的集合，B 表示}100,,2,1{ 中被4整除的数的集合，C 表示}100,,2,1{ 中被5整除的数的集合，则20,25,33===C B A6,5,8=⋂=⋂=⋂A C C B B A ， 1=⋂⋂C B A ，进而有C B A A C C B B A C B A C B A ⋂⋂+⋂-⋂-⋂-++=⋃⋃601658202533=+---++= 故有4060100=-=⋃⋃-=⋃⋃C B A U C B A即}100,,2,1{ 中不被3、4、5整除的个数为40。
命题逻辑练习题《离散数学》命题逻辑部分练习题⼀、选择题1．下列句⼦中，（）是命题。
A ．2是常数。
B ．这朵花多好看呀！C ．请把门关上！D ．下午有会吗？2．令p : 今天下雪了，q :路滑，r :他迟到了。
则命题“下雪路滑，他迟到了” 可符号化为（）。
A. p q r ∧→ B. p q r ∨→ C. p q r ∧∧ D. p q r ∨?3．令:p 今天下雪了，:q 路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。
A. p q ∧? B. p q ∧ C. p q ∨?D. p q →?4．设()P x :x 是鸟，()Q x :x 会飞，命题“有的鸟不会飞”可符号化为（）。
A. ()(()())x P x Q x ??→B. ()(()x P x ??∧())Q xC. ()(()())x P x Q x ??→D. ()(()x P x ??∧())Q x 5.设()F x :x 是⼈，()G x :x 犯错误，命题“没有不犯错误的⼈”符号化为（）。
A ．(()())x F x G x ?∧B ． (()())x F x G x ??→?C ．(()())x F x G x ??∧D ． (()())x F x G x ??∧? 6.下列命题公式不是永真式的是（）。
A. ()p q p →→B. ()p q p →→C. ()p q p ?∨→D. ()p q p →∨ 7．下列式⼦为⽭盾式的是（）。
A ．()p p q ∨∧B ．p p ∨?C ．p p ∧?D ． ()p q p q ?∨??∧? 8．命题：“所有马都⽐某些⽜跑得快” 的符号化公式为( )。
假设：H(x )：x 是马；C(x )：x 是⽜；F(x,y )：x 跑得⽐y 快。
A. ()(()()(()(,)))x H x y C y F x y ?∧?∧B. ()(()()(()(,)))x H x y C y F x y ?→?→C. ()(()()(()(,)))x H x y C y F x y ?→?∧D. ()()(()(()(,)))y x H x C y F x y ??→→⼆、计算题（仅给出部分题⽬的解题思路，未给出答案⾃⼰完成）1. 已知命题公式()()p q p r ?→→∧（1）构造真值表（2）求出公式的主析取范式（2）()()p q p r ?→→∧0157()()()()p q r p q r p q r p q r m m m m ??∧?∧?∨∧∧?∨∧?∧∨∧∧?∨∨∨2.已知命题公式()()p q p r ∨→?∨（1）构造真值表；（2）⽤等值演算法求公式的主析取范式。
页眉内容《离散数学》试题及答案一、选择或填空（数理逻辑部分）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），（5），（6）4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。
答：x,y, x,z5、判断下列语句是不是命题。
若是，给出命题的真值。
( )(1)北京是中华人民共和国的首都。
(2) 陕西师大是一座工厂。
(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。
(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。
答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。
(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）PP⌝P→⌝↔（4）QQ→⌝（2）QP⌝→（3）Q8、设个体域为整数集，则下列公式的意义是( )。
(1) ∀x∃y(x+y=0) (2) ∃y∀x(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值：(1) ∀x∃y (xy=y) ( ) (2) ∃x∀y(x+y=y) ( )(3) ∃x∀y(x+y=x) ( ) (4) ∀x∃y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。
离散数学命题逻辑练习题⼀、选择题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 PB ,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 8B 3C 5D 07. 如果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 AB B AC B C ∨?∨ C A C B C ∧?∧D C A C B →?→10. 下⾯4个推理定律中，不正确的是 ( )A ()A AB ?∧ B ()A B A B ∨∧??C ()A B A B →∧?D ()A B B A →∧11. 下列命题公式是等价公式的为（）．A ．?P??Q ?P?QB ．A?(?B?A) ??A?(A?B)C ．Q ?(P?Q )??Q ?(P?Q )D ．?A?(A?B) ?B12. 命题公式)(Q P →?的主析取范式是（）．A ．Q P ?∧B ．Q P ∧?C ．Q P ∨?D ．Q P ?∨13．下列表述成⽴的为（）．A ．?P ??Q ?P ?QB ．?B ?A ? A ?BC ．P ? Q ?QD ．?A ? (A ?B ) ?B14. ⼀个公式在等价意义下，下⾯哪个写法是唯⼀的（）。
离散数学期末复习题2012-6-161.“太阳系以外的星球上有生命。
”是命题。
（ T ）2．ρ（A⋃B）=ρ（A）⋃ρ（B）（ F ）ρ（A∩B）=ρ（A）∩ρ（B）（ T ）3．一个命题的合取范式不是唯一的。
（ T ）4．等价式⌝（∃x）A（x）⇔（∀x）⌝A（x）成立。
( T )5．（∀x）（P（x）∨Q（x））∧ R（x）是命题。
（ F ）8．对于一个谓词公式，指定不同的个体域，则其真值不一定相同.T9. 若命题公式A的主析取范式包含全部的极小项，则A为永真式T10．命题“他在教室看书或在宿舍看书。
”可以符号化为P∨ S。
F11．当个体域S=｛a,b,c｝消去公式(∀x) P(x)∨(∃x)Q(x)中量词为(P(a)∨Q(a)) ∧ (P(b)) ∨Q(b)) ∧ (P(c)∨Q(c)) F12. 设P、Q是两个命题，当且仅当P、Q的真值均相同时，P↔Q的值为T. T13. 命题公式(P∧(P→ Q)) → Q是永真式. T14．命题联结词集｛∨、∧｝是极小功能完备的联结词集. F15．(A ≠Φ) ∧ (B ≠Φ) ⇒ (A ⋂ B ≠Φ ) F16. （P ↔ Q）→┐（ P ∨Q）是矛盾式。
F17. ∃xA(x) ∨∃x B(x) ⇒∃x ( A(x) ∨ B(x)) T19. 若关系R不具有对称性则R一定具有反对称性 F22. 设A、B、C是任意集合，且C-B = C-A，则A=B 。
F23. 设A、B和C为任意集合，且A∪B=A∪C，则B=C. F24．若R和S是X上具有对称性的关系，则R º S也具有对称性。
F25．若R和S是X上的具有对称性的关系，则R ∩S具有对称性。
T26．∃xA(x)∨∃x B(x)⇒∃x ( A(x) ∨ B(x)) （F ）27．（P ↔ Q）→┐（ P ∨Q）是可满足式。
（ F）28．｛｝=｛φ｝（ F ）二、填空题1．已知B={ {a，b}，c}，则B的幂集ρ（B）= { B ,Φ,{{a，b}}，{c} }2．已知A={1，2，3，4，5，6，7}，B={2，4，6，8，10}，则A-B= {1,3,5,7,} ,A + B= {1,3,5,7, 8,10} 。
![[试题]离散数学复习题（请参考课件）](https://img.taocdn.com/s1/m/f28571b7294ac850ad02de80d4d8d15abe230009.png)
离散数学Part1_数理逻辑部分1．将下列命题符号化。
P48（1）豆沙包是由面粉和红小豆做成的.（2）苹果树和梨树都是落叶乔木.（3）王小红或李大明是物理组成员.（4）王小红或李大明中的一人是物理组成员.（5）由于交通阻塞，他迟到了.（6）如果交通不阻塞，他就不会迟到.（7）他没迟到，所以交通没阻塞.（8）除非交通阻塞，否则他不会迟到.（9）他迟到当且仅当交通阻塞.分清复合命题与简单命题分清相容或与排斥或分清必要与充分条件及必要充分条件答案：（1）是简单命题（2）是合取式（3）是析取式（相容或）（4）是析取式（排斥或）请分别写出（1）—（4）的符号化形式设p: 交通阻塞，q: 他迟到（5）p→q, （6）⌝p→⌝q或q→p（7）⌝q→⌝p或p→q, （8）q→p或⌝p→⌝q（9）p↔q或⌝p↔⌝q可见（5）与（7），（6）与（8）相同（等值）3．用真值表判断下面公式的类型P51（1）p r (q p)（2）((p q) ( q p)) r（3）(p q) (p r)按层次写真值表，由最后一列判类型答案：（1）为矛盾式，（2）为重言式，（3）为可满足式例用等值演算法判断下列公式的类型P59（1）q (p q)（2）(p q) ( q p)（3）((p q) (p q)) r)解（1）q (p q)q ( p q) （蕴涵等值式）q (p q) （德摩根律）p (q q) （交换律，结合律）p 0 （矛盾律）0 （零律）由最后一步可知，（1）为矛盾式.（2）(p q) ( q p)( p q) (q p) （蕴涵等值式）( p q) ( p q) （交换律）1由最后一步可知，（2）为重言式.问：最后一步为什么等值于1？说明：（2）的演算步骤可长可短，以上演算最省.（3）((p q) (p q)) r)(p (q q)) r（分配律）p 1 r（排中律）p r（同一律）由最后一步可知，（3）不是矛盾式，也不是重言式，它是可满足式，其实101, 111是成真赋值，000, 010等是成假赋值.总结：从此例可看出A为矛盾式当且仅当A 0A为重言式当且仅当A 1例求公式A=(p q) r的主析取范式与主合取范式. P71（1）求主析取范式(p q) r(p q) r（析取范式）①(p q)(p q) ( r r)(p q r) (p q r)m6 m7②r( p p) ( q q) r( p q r) ( p q r) (p q r) (p q r)m1 m3 m5 m7 ③②, ③代入①并排序，得(p q) r m1 m3 m5 m6 m7 （主析取范式）（2）求A的主合取范式(p q) r(p r) (q r) （合取范式）①p rp (q q) r(p q r) (p q r)M0 M2 ②q r(p p) q r(p q r) ( p q r)M0 M4 ③②, ③代入①并排序，得(p q) r M0 M2 M4 （主合取范式1．设A与B均为含n个命题变项的公式，判断下列命题是否为真？P85（1）A B当且仅当A与B有相同的主析取范式（2）若A为重言式，则A的主合取范式为0（3）若A为矛盾式，则A的主析取范式为1（4）任何公式都能等值地化成{ , }中的公式（5）任何公式都能等值地化成{ , , }中的公式（1）为真，这是显然的（2）为假. 注意, 任何公式与它的主范式是等值的，显然重言式不能与0等值。
《离散数学》复习题及答案《离散数学》试题及答案⼀、选择或填空（数理逻辑部分）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），（5），（6）4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，⾃由变元是( )，约束变元是( )。
答：x,y, x,z5、判断下列语句是不是命题。
若是，给出命题的真值。
( )(1)北京是中华⼈民共和国的⾸都。
(2) 陕西师⼤是⼀座⼯⼚。
(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三⾓形有4条边。
(5) 前进！ (6) 给我⼀杯⽔吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在⼀些⼈是⼤学⽣”的否定是( )，⽽命题“所有的⼈都是要死的”的否定是( )。
答：所有⼈都不是⼤学⽣，有些⼈不会死7、设P：我⽣病，Q：我去学校，则下列命题可符号化为( )。
(1) 只有在⽣病时，我才不去学校 (2) 若我⽣病，则我不去学校(3) 当且仅当我⽣病时，我才不去学校(4) 若我不⽣病，则我⼀定去学校答：（1）PP?P→（4）QQ→→（3）Q8、设个体域为整数集，则下列公式的意义是( )。
(1) ?x?y(x+y=0) (2) ?y?x(x+y=0)答：（1）对任⼀整数x存在整数 y满⾜x+y=0（2）存在整数y对任⼀整数x满⾜x+y=0 9、设全体域D是正整数集合，确定下列命题的真值：(1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( )(3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)∨Q(x))在哪个个体域中为真?( )(1) ⾃然数(2) 实数 (3) 复数(4) (1)--(3)均成⽴答：（1）11、命题“2是偶数或-3是负数”的否定是（）。
离散数学1.将下面程序语言进行化简If A then if B then X else Y else if B then X else Y2.在自然推理系统P中构造下面推理的证明：前提：,,p q r q rs ⌝∨∨⌝→ 结论：p s →.3设一阶逻辑公式((,)(()()))G x yP x y zQ z R x =∃⌝∃→∃→试将G 化成与其等价的前束范式。
4.判断下面推理是否正确，并证明你的结论。
如果小王今天家里有事，则他不会来开会。
如果小张今天看到小王，则小王今天来开会了。
小张今天看到小王。
所以小王今天家里没事。
5、构造下面推理的证明前提： ))()(()),()()((x R x F x x H x G x F x ∧∃∧→∀结论: ))()()((x G x R x F x ∧∧∃6用等值演算法和真值表法判断公式)())()((Q P P Q Q P A ↔↔→∧→=的类型。
7分别用真值表法和公式法求(P →(Q ∨R ))∧(⌝P ∨(Q ↔R ))的主析取范式，并写出其相应的成真赋值和成假赋值。
8用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。
因此有些学生很有风度。
9、设A ＝{∅，1，{1}}，B ＝{0，{0}}，求P (A )、P (B )－{0}、P (B )⊕B 。
10、设X ＝{1，2，3，4}，R 是X 上的二元关系，R ＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)画出R 的关系图。
(2)写出R 的关系矩阵。
(3)说明R 是否是自反、反自反、对称、传递的。
11、集合X={<1,2>, <3,4>, <5,6>,… }，R={<<x 1,y 1>,<x 2,y 2>>|x 1+y 2 = x 2+y 1} 。
离散数学命题逻辑练习题及答案本文档包含了一些离散数学中的命题逻辑练习题及其详细答案。
在离散数学中，命题逻辑是一种符号逻辑系统，它研究命题的形式和逻辑推理的规则。
这些练习题旨在帮助读者巩固对命题逻辑基本概念的理解，并锻炼逻辑推理能力。
练习题1.写出下列命题的否定形式：a)如果今天下雨，我就不出门。
b)数学和计算机科学是紧密相关的学科。
c)所有猫都有尾巴。
d)如果一个数是偶数，它肯定可以被2整除。
2.判断以下陈述是否为命题，并给出理由：a)蓝色是我最喜欢的颜色。
b)2加2等于4。
c)这是一个错误的陈述。
d)如果明天下雨，我就会带伞。
3.使用真值表判断以下复合命题的真值：a)P ∧ (¬Q ∨ R)b)(P ∧ Q) ∨ (¬R ∧ S)c)(P → Q) ∧ (R → S)d)(P ∨ Q) ∧ (¬P ∨ Q)4.使用推理规则化简以下逻辑表达式：a)~((P ∧ Q) ∨ R)b)~(P ∨ (Q ∧ R))c)(~P ∧ Q) ∨ ((~P ∨ Q) ∧ R)d)(P → Q) ∨ (¬Q → ¬P)答案a)今天下雨而且我不出门。
b)数学和计算机科学不是紧密相关的学科。
c)存在不具备尾巴的猫。
d)存在一个偶数，它不能被2整除。
a)不是命题。
因为它表达了个人偏好，无法判断真假。
b)是命题。
因为它可以明确地判断为真。
c)不是命题。
因为它没有明确的真值。
d)是命题。
因为它可以根据明天的天气情况来判断真假。
P Q R¬Q ∨ R P ∧ (¬Q ∨ R)T T T T TT T F F FT F T T TT F F T TF T T T FF T F T FF F T T FF F F T FP Q R P ∧ Q¬R ∧ S(P ∧ Q) ∨ (¬R ∧ S) T T T T F TT T F T F TT F T F T TT F F F T TF T T F F FF T F F F FF F T F F FF F F F F FP Q R P → Q R → S(P → Q) ∧ (R → S) T T T T T TT T F T F FT F T F T FT F F F T FF T T T T TF T F T F TF F T T T TF F F T T TP Q(P ∨ Q)¬P ∨ Q(P ∨ Q) ∧ (¬P ∨ Q) T T T T TT F T F FF T T T TF F F F F~((P ∧ Q) ∨ R)= ~(P ∧ Q) ∧ ~R~(P ∨ (Q ∧ R))= ~P ∧ ~(Q ∧ R)= ~P ∧ (~Q ∨ ~R)(~P ∧ Q) ∨ ((~P ∨ Q) ∧ R)= (~P ∨ ~P) ∧ (Q ∨ Q) ∧ (Q ∨ R) ∧ (~P ∨ R) = ~P ∧ Q ∨ R(P → Q) ∨ (¬Q → ¬P)= (~P ∨ Q) ∨ (Q ∨ ¬P)= (~P ∨ Q) ∨ (¬P ∨ Q)= T以上是一些离散数学命题逻辑的练习题及答案。
