离散数学复习资料

1、精品离散数学习题与解答第一篇数理逻辑第一章命题逻辑1-1 （1 ）指出下列语句哪些是命题，哪些不是命题，如果是命题指出他的真值a) 离散数学是计算机科学系的一门必修棵b) 2吗？c) 明天我去看电影d) 请勿随地吐痰e) 不存在最大质数f) 如果我掌握了英语，法语，那么学习其他欧洲的语言就容易多了g) 9+512h) x3i) 月球上有水j) 我正在说假话解 a) 不是命题b) 是命题 ,真值视具体情况而定c) 不是命题d) 是命题 ,真值为 te) 是命题 ,真值为 tf) 是命题 ,真值为 fg) 不是命题感谢下载载精品h) 是命题 , 真值视具体情况而定i) 不是命题1-2(1) 用 P

2、 表示命题“天下雪”,(又表示命题“我将去镇上”,R 表示命题“我有时间” .以符号形式写出下列命题:(a) 如果天不下雪和我有时间 ,那么我将去镇上 .(b) 我将去镇上，仅当我有时间 .(c) 天不下雪(d) 天下雪 ,那么我不去镇上 解 a)( P R) Qb)Q Rc) P d)P Q1-2(2) 将下面这段陈述中所出现的原子命题符号化,并指出他们的真值,然后将这段陈述中的每一命题符号化2是有理数是不对的.2 是偶素数 .2 或 4 是素数 .如果 2 是素数则3 也是素数.2是素数当且仅当3 也是素数 . 解 : 陈述中出现5 个原子命题，将他们符号化为:P:2 是有理数其真值为 F

3、Q:2 是素数其真值为 TR:2 是偶数其真值为 TS:3 是素数其真值为 TU:4 是素数其真值为 F感谢下载载精品陈述中各命题符号化为: P;Q R;Q U;Q S;Q S 1- 2(3) 将下列命题符号化a) 如果 3+3=6, 则雪是白色的 .b) 如果 3+3 6,则雪是白色的c) 如果 3+3=6, 则雪不是白色的 .d) 如果 3+3 6,则雪不是白色的e) 王强身体很好，成绩也很好 .f) 四边形 ABCD 是平行四边形 ,仅当其对边平行 解 : 设 P:3+3=6Q: 雪是白色的R:王强成绩很好S:王强身体很好U: 四边形 ABCD 是平行四边形V: 四边形 ABCD 的对边

4、是平行的于是 :a) 可表示为 :PQb) 可表示为 : PQc) 可表示为 : P Qd) 可表示为： P Qe) 可表示为： S Rf) 可表示为 :U V1-3(1) 判别下列公式中哪些是合式公式,那些不是合式公式a) (Q RS)b) (P (R S)感谢下载载精品c) ( PQ) (Q P)d) (RS T)e) (P (Q R) (P Q) (PR)解:a) 不是合式公式 (若规定运算符优先级后也可以作为合式公式)b) 是合式公式c) 不是合式公式 ( 括号不配对 )d) 不是合式公式e) 是合式公式1-3(2) 对下列各式用指定的公式进行代换:a) (A B) B) A), 用（

5、 A C）代换 A ，用（ B C） A 代换 B。b)(A B) (B A),用 B 代换 A,A 代换 B. 解 :a)(A C) (B C) A) (B C) A) (A C)b)(B A) (A B)1-3(3) 用符号形式写出下列命题a) 假如上午不下雨 ,我去看电影 ;否则就在家里读书或看报 .b) 我今天进城 ,除非下雨 .c) 仅当你走 ,我将留下 . 解 a) 设 P:上午天下雨 .Q:我去看电影R:我在家读书S:我在家看报原命题可译为:( P Q) (P (R S)b) 设 :P:我今天进城Q: 天下雨感谢下载载精品原命题可译为:Q Pc) 设:P:你走Q:我留下原命题可译

6、为:Q P (4) 称 P Q 为条件命题P Q 的反换式Q P 为条件命题P Q 的逆换式 Q P 为条件命题 P Q 的逆反式试写出如下条件命题的反换式，逆换式，逆反式。（ a ）如果他有勇气，则他将得胜。（ b ）如果天下雨，我不去。 解 （ a）设 P：他有勇气，Q ：他将得胜原条件命题可译为：PQ反换式： P Q ，表示：如果他没有勇气，则他将不能获胜。逆换式： Q P，表示：如果他将得胜，则他有勇气。逆反式： Q P，表示：如果他不获胜，则他没有勇气。（ b ）设 P：天下雨， Q：我去原条件命题可译为： P Q反换式： PQ ，表示：如果如果天不下雨，则我去。逆换式： Q P，表

7、示：如果我不去，则天下雨。逆反式： Q P，表示：如果我去，则天不下雨。1-4 （ 1 ）试求下列各命题公式的真值表并解释其结果（ a ）（ P Q） （ Q P）；（ b ）（ P Q ） P；感谢下载载精品（ c）Q （ P Q ）；（ d ）（ P Q ）（ P Q ）；（ e ）（ PQ ） （ （ P Q ）；（ f ） （ P Q ） Q R 。 解 （ a ）从真值表1-1 中可看出：（ P Q） （ Q P）（ P Q ）(b) 从真值表 1-2 中可看出：（ P Q ） P 是永真式(c) 从真值表 1-3 中可看出： Q （ P Q）是永真式(d) 从真值表 1-4 中可看

8、出：（ P Q ）（ P Q ）是永真式(e) 从真值表 1-5 中可看出：（ P Q ） （ （ P Q ） P Q P Q （ P Q ）P QPQQP （ P Q） （QP）TTTTTTFFTFFTTFFFFTTT(f)从真值表1-6 中可看出： （ PQ ） Q R 是永真式感谢下载载精品表 1-1P QPQ（PQ） PTTTTTFFTFTFTFFFT表 1-2P QPQQ （ PQ ）TTTTTFTTFTTTFFFT表 1-3PQ PP Q PQ（ P Q ）（ PQ ）TTFTTTTFFFFTFTTTTTFFTTTT表 1-4感谢下载载精品PQ P QP Q（ PQ）（ P Q）（

9、 P Q ）TTFFTTTTFFTFFFFTTFTTTFFTTTTT表 1-5P QP （PQ） （PQ） （PQ）QRRQQTTTFFFFTTFFFFFTFTTTFFTFFTTFFFTTTFFFFTFTFFFFFTTFFFFFFTFFF表 1-61-4 （ 2 ）用真值表判断下列各组公式是否等价：（ a） P (Q R)与（ P Q ） R（ b ） （ P Q） R 与（ P Q） R解 由表 1-7 可知 P (Q R) （ P Q ） R而（ P Q） R （ P Q） R感谢下载载精品P Q RP (QR)（PQ）R（PQ） RTTTTTTTTFFFFTFTTTTTFFTTTFTTT

10、TTFTFTTFFFTTTTFFFTTF表 1-71-4 （ 3 ）试以真值表证明下列命题：（ a）合取运算的结合律（ b ）德摩根定律 解 （ a）如表 1-8 ，（P Q ） R（ b ）如表 1-9 ， （ P Q ） P Q （ PQ ） P QP Q RPQ （PQ）RQRP（QR）TTTTTTTTTFTFFFTFTFFFFTFFFFFFFTTFFTFFTFFFFFFFTFFFFFFFFFFF感谢下载载精品表 1-8P QP QPQ （PQ） PQ（PQ）TTFFFFFFTFFTTTFFFTTFTTFFFFTTTTTT表 1-92-4 （4 ）证明下列等价式：（ a） A（ B A）

11、 A （ A B）；(b) （ A B） C（ A C） （ B C）；(c) （ A B）（ A B） （ A B）；(d) （ A B） C） D） （ C（ A （ B D ）（ C （A B）D 证 （ a） A （ B A） A （ B A ）（ B A ） A（ AB） A A（ BA） A（ AB） A（A B）感谢下载载精品 A （ A B）（ b ）（ A C） （ B C）（ A C） （ B C）（ A B） C （ A B） C（ A B） C（ c） （ A B） （A B） （ B A ） （ A B） （ BA ） （ A B） （ B A ）（ A B） （B

12、A）（ d ）（ A B） C） D ） （ C（ A （B D ）（ （ A BC） D ） （ C （A B D ）（ ABCD）（ CABD）（ C D ） （ A B） （A B）（ CD） （AB） （BA）（ C D ） （ A B） （ B A ）（ C （ A B） （ B A ） D （C （ A B） （ B A） D （C （A B） （ B A ） D （C （A B） D（ C （ A B） D1-4 （ 5 ）判断下列命题公式的类型（永真；永假；非永真，也非永假）：（ a ）（ PQ ） P） Q ；感谢下载载精品（ b ） （ P (P Q) ） R；（ c）P

13、(P Q) P) Q). 解 （ a）（ P Q ） P） Q（ P Q ） P） Q （ P Q ） P） Q（ （ P Q ） P） Q（ P Q ） P） Q（ P P） （ Q P） Q（ Q P） Q T P T （ a）为永真式（ b ） （ P (P Q) ） R （ P P Q ） R（ P P Q） R F R F （ b ）为永假式（ c） P (P Q) P) Q) P ( (P Q) P) Q) P ( (PP ) (Q P) Q) P ( (F (Q P) Q)感谢下载载精品 P ( QP Q) P T P （ c ）为非永真式，也非永假式1-4.(6) 化简如下语句

14、： “情况并非如此：若他不来，则我不去”。 解 ：首先符号化上述语句。设 P：他来。 Q ：我去则原句： （ P Q ）然后化简上述命题公式 （ P Q） （ Q P） （Q P） （ Q P） Q P即：我去了，但他未来。1 4 （ 7 ）（a ）如果 A C B C，是否有A B？如果 A C B C，是否有A B？如果 A B，是否有A B？ 解 （ a）不能说必有A B，因为当 A C BC 时，有可能某种指派使C 为 T，但 A 、 B 的值并不相同（ b ）不能说必有 A B，因为当 A C B C 时，有可能某种指派感谢下载载精品使 C 为 F，但 A、B 的值并不相同（ c）结

15、论正确。因为（ A B）（ B A ），所以 B A 为永真式时， A B 也是永真式。 即 B A 时，必有 A B。同理 A B 时，B A 。所以 B A 时，必有 A B1 5 （ 1 ）试证下列各式为永真式：（ a）（ P （ P Q） ） Q；（ b ） P（ P Q ）；（ c）（ PQ ） （ Q R）（ P R）；（ d ）（ P Q ） （ Q R） （ R P）（ P Q） （ Q R） （ R P）解 （ a）（ P （ P Q ） ） Q（ P （ PQ） ） Q（ P P） （ PQ） Q（ P Q） Q （P Q） Q PQQ P T T（ b ） P（ PQ ）

16、 P（ PQ ） P PQ T Q感谢下载载精品 T（ c）当本条件命题的后件为F 时，必有 P：T；R：F 考察条件的前件 （ PQ ）（ Q R）。当 Q： F 时，因 PQ ：F；当 Q ：T 时，因 Q R：F。所以前件必为F。故（ PQ） （QR） PR因此（ P Q） （ Q R）（ P R）是永真式（ d ） （ P ） （ R） （ RP）（ （P R） （ RP）（ （ R P） （ P R） （ R P）（ R） （ P） （ P R）（ P ） （ R） （ R P）（ P ） （ R） （ RP）（ PQ ） （ Q R）（ R P）1-5 （ 2 ）不构造真值表证明下

17、列蕴涵式：（ a ）（ P Q） P（ PQ ） ;(b) （PQ） Q PQ；（ c）（Q （ P P）（ R（ R（ P P） R 证 （ a ）解法 1设 PQ 为 T，则（ 1）P 为 T，Q 为 T 因而 P（ PQ）为 T或（ 2）P 为 F则必有 P（ P Q）为 T所以（ a ）成立。解法 2设 P（ PQ ）为 F感谢下载载精品则P为T，为 F所以PQ为F所以（ a ）成立。解法 3（ PQ ）（ P（ P Q ） （ P Q ） （ P（ PQ ） （ P Q ） （ P P） （ PQ ） （ P Q ） （ PQ ） T所以（ a ）成立。(b) 设PQ为F，则P为F，

18、Q为F则 PQ 为 T，所以（ PQ） Q 为 F所以（ b ）成立。（ c）（ Q（ P P）（ R（ R（ P P） （ Q F） （ R （ R F） （ Q ） （ R R） （ Q） R Q R R所以（ Q （ P P）（ R（ R（ P P） R当然有（ Q （ P P）（ R（ R（ P P） R1-5（ 3）试证明P Q， Q 逻辑蕴含P。感谢下载载精品 证 本题要求证明：(P Q) 设 (P Q) 为，则为且(P Q) 为所以必为，因而蕴含式成立。（）逻辑推证下列各式：（ a） （ P）；（ b ） ；（ c） ；（ d ） （ ） ；（ e） （ ）， ，（ ） ；（ f

19、） （ ）， ， 。证（ a）若为，则 P 为，故 P必为。所以（ a ）成立。（ b ）若为，则 必为。故（ b ）成立。（ c）因为 。故 。（ d ）设 为，则为且为所以 为， （ ）为。故（d ）成立。（ e）设 （ ）， ，（ ） 均为则因 为及（ ） 为，而可得 为又因 （ ）为故得 为，故（ e ）成立。（ f）设（ ）， ， 均为，则为，由 为，可知为。再由（ ）为可得 为，感谢下载载精品因而必有 （ ）为，也即 为，故（ f ）成立。（）把下列各式用只含和 的等价式表达，并要尽可能简单：（ a）（ P ） P；（ b ）（ ） P；（ c） P （ ）。解（ a）（ P ）

20、P（ P P） （ ）（ b ）（ ） P （ ） （ P ）（ P ） （ P ） （ P ）（ P ） （ P ） （ P ）（ P ） （ P ）（ P ） （ ）（ P ） P （P ）（ c） P （ ） P （ ）感谢下载载精品（ P ） （ P ）（ P ） P （P ）（）对下列各式仅用“或非”（ ）表示：（ a） P；（ b ） P ；（ c）P ；解：（ a ） P （ P P） P P（ b ） P （ （ P ） （ P）（ P ） （ P）（ c） P （ P ） P （ P P） （ ）（）对下列各式仅用“与非”（ ）表示：（ a） P；（ b ） P ；（ c）P

21、 ；解：（ a ） P （ P P） P P（ b ） P （ P ） P （ P P） （ ）（ c） P （ （ P ） （ P ）（ P ） （ P）感谢下载载精品（）把P（ P Q ）分别表示成只含“”和只含“”的等价公式。解 P（ P Q ） P （ P Q ） Q P P（ P P） （P P） P （ P P）。P（ P Q ） P P（ P P） （ P P）（P P） P） （ P P） P）。（）把P表示成只含“” 的等价公式，把P 表示成只含“” 的等价公式。解 P （ P ）P （ P P） （ ）（ P P） （ ） （ P P） （ ）。P （ P ）P （ P P

22、） （ ）（ P P） （ ） （ P P） （ ）。（）证明， 和不是最小联结词组。证（反证法）若， ，均是最小联结词组，则否定（ ）命题连接词可分别仅用， ，表示，即P（ P ）P（ P ）P P（ P（ P ） ）感谢下载载精品但当时所有命题变元均指派时，各等价式的左端为而右端却为，故产生矛盾。故， 和均不是最小联结词组。c（）证明， ，是最小联结词组。证：因为 ， 是最小联结词组，且 。故 ，是功能完备的联结词组。又和都不是功能完备的，所以，是最小联结词组。ccc又因为（）故 ，也是功能完备的联结词组。但c不是功能完备的。因为若它是功能完备的，则否定（）命题联结词必有仅用表示，即：cc

23、cP（ ） ）c但当对命题变元指派时，上等价式的左端为，但右端为，矛盾。所以，也是最小联结词组。（）求公式（）的析取范式和合取范式。解析取范式： （）（ ）（ ） （ ）合取范式：感谢下载载精品 （）（ ）或 （）（ ）（ ） （ ）（） （ ） （ ）（）把下列各式化为析取范式（每项两个变元）：（ a）（ ）；（ b ）（ ）；（ c）（）；（ d ） （ ） （ ）；解：（ a ）（ ）（ ） （ ） （ ） （ ）（ ） （ ） （ ） （ ） （ ）（ ）（ b ）（ ） （ （ ） ） （ ） （ ） （ ） （ ）（ ） （ ） （ ） （ ） （ ）（ ） （） （ ）（ c）（

24、）（ ） （） （ ） （ （ ）感谢下载载精品（） （ ） （ ）（ d ） （ ） （ ）（ ） （ ）（ ） （ ） （ ） （ ）（）把下列各式化为合取范式：（ a） （ ）；（ b ） （） （ ）；（ c） （）；（ d ） （）；（ e） （ ） （ ）解：（ a ） （ ）（） （ ） （ ）（） （ ）（ b ） （） （ ） （ ） （ ）（ ） （ ）（ ） （ ）（ ） （ ）（ c） （） （ ） （ （ ） （ （ ）（ ） （ ） （ ） （ ）（ ） （ ） （ ）（ d ）（）（ ） 感谢下载载精品（） （） （ ）（ e ）（ ） （ ）（ ） ） （ ）

25、）（ ） （ ） （ ） （ ）（ ） （ ）（）求下列各式的主析取范式及主合取范式，并指出其中哪些是重言式：（ a）（ ）（）；（ b ） （ （ （ ）；（ c）（ ） （ （ ）；（ d ）（ （）；（ e）（） （ ）。解：（ a ）（ ）（） （ ） （）（） （ ） （ ）（主析取范式） ， （主合取范式）（ b ） （ （ （ ） （ （ （ ） （主合取范式） ，（ ） （ ） （ ） （感谢下载载精品 ） （ ） （ ） （ ）（主析取范式）（ c）（ ） （ （ ）（ （ ） （ （ ）（ （ ） ） （ （ ） （ ）（ ） （ ） （ ） （ ）（ ） （ ），（主析取

26、范式） ，（ ） （ ） （ ） （ ） （ ） （ ）（主合取范式）（ d ）（ （） （ （ ）（ ）（ ） （永真式， 主合取范式为空） ，（ ） （ ） （ ） （ ）（主析取范式）（ e ）（） （ ）（ ）（ ）（ ） （ ） （永假式，主析取范式为空） ，。，（ ） （ ） （ ） （ ）（）用主析取范式判断下列各题中的两个命题公式是否等价。（ a）（）（）与（）；感谢下载载精品（ b ）（）（ ）与（ ） （）；（ c）（）与（） 。解：（ a ）（） （）（ ） （ ） ，（ ），这两个公式的主析取范式相同，所以它们等价。（ b ）（）（ ） （ ） （ ）（ ） （ ）（ ） （）（ ） （ ）（ ）（ ） （ ） （ ）（ ） （ ） （ ） （ ） （ （ ）（ ） （ ）可见这两个公式的主析取范式相同，所以它们等价。（ c）（） ，（） ，可见这两个公式的主析取范式不相同，所以它们不等价。（）已知一命题公式（，）当且仅当其中的二个命题变元为真时，为真。试求。感谢下载载精品解：根据题意写出的真值表PQRTTTFTTFTTFTTTFFFFTTTFTFFFFTFFFFF表