离散数学(屈婉玲版)部分习题.doc

第一章习题1.1&1.2 判断下列语句与否为命题,若是命题请指出是简朴命题还是复合命题.并将命题符号化,并讨论它们的真值.(1) √2是无理数.是命题,简朴命题.p:√2是无理数.真值:1(2) 5能被2整除. 是命题,简朴命题.p:5能被2整除.真值:0(3) 目前在开会吗?不是命题.(4) x+5>0.不是命题.(5) 这朵花真好看呀! 不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.p«q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p«q真值:0 (8) 10月1日天气晴好. 是命题,简朴命题.p:10月1日天气晴好.真值唯一. (9) 太阳系以外的星球上有生物. 是命题,简朴命题.p:太阳系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命题,简朴命题.P:小李在宿舍里.真值唯一. (11) 全体起立! 不是命题. (12) 4是2的倍数或是3的倍数. 是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p∨q真值:1 (13) 4是偶数且是奇数. 是命题,复合命题.P:4是偶数.q:4是奇数.p∧q真值:0 (14) 李明与王华是同窗. 是命题,简朴命题.p: 李明与王华是同窗.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简朴命题.p: 蓝色和黄色可以调配成绿色.真值:11.3 判断下列各命题的真值.(1)若 2+2=4,则 3+3=6.(2)若 2+2=4,则 3+3≠6.(3)若 2+2≠4,则 3+3=6.(4)若 2+2≠4,则 3+3≠6.(5)2+2=4当且仅当3+3=6.(6)2+2=4当且仅当3+3≠6.(7)2+2≠4当且仅当3+3=6.(8)2+2≠4当且仅当3+3≠6.答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题.(1)p→q,真值为1.(2)p→┐q,真值为0.(3)┐p→q,真值为1.(4)┐p→┐q,真值为1.(5)p«q,真值为1.(6)p«┐q,真值为0.(7)┐p«q,真值为0.(8)┐p«┐q,真值为1.1．4将下列命题符号化，并讨论其真值。

（1）如果今天是1号，则明天是2号 p:今天是1号 q:明天是2号 符号化为：p®q 真值为：1 （2）如果今天是1号，则明天是3号 p:今天是1号 q:明天是3号 符号化为：p®q 真值为：01.5将下列命题符号化1）2是偶数又是素数2）小王不仅聪颖并且用功3）虽然天气很冷，老王还是来了4）她一边吃饭，一边看电视5）如果天下雨，她就乘公共汽车上班6）只有天下雨，她才乘公共汽车上班7）除非天下雨，否则她不乘公共汽车上班意思为：如果她乘公共汽车上班，则天下雨或如果不是天下雨，那么她就不乘公共汽车上班)（8）不经一事，不长一智答案：（1）设p：2是偶数，q：2是素数符号化为：p∧q （2）设p：小王聪颖，q：小王用功符号化为：p∧q （3）设p：天气很冷，q：老王来了符号化为：p∧q （4）设p：她吃饭,q：她看电视符号化为：p∧q （5）设p：天下雨，q：她乘公共汽车符号化为：p→q （6）设p：天下雨，q：她乘公共汽上班符号化为：q→p （7）设p：天下雨，q：她乘公共汽车上班。

符号化为：q→p或Øq→Øp（8）设p：经一事，q：长一智符号化为：Øp→Øq1.6设p,q的真值为0；r,s的真值为1，求下列各命题公式的真值1） p∨(q∧r)（2） (p↔r)∧(¬p∨s)（3） (p∧(q∨r))→(p∨q)∧(r∧s)（4） ¬(p∨(q→(r∧¬p)) → (r∨¬s) 解：（1） p∨(q∧r)pqrq∧rp∨(q∧r) 00100(2) (p↔r)∧(¬p∨s) pqrsp«r¬p¬p∨s(p«r)∧(¬p∨s)00110110(3)(p∧(q∨r))→(p∨q)∧(r∧s)pqrsq∨rp∧(q∨r)p∨qr∧s(p∨q)∧(r∧s)(p∧(q∨r))→(p∨q)∧(r∧s)0011100101 (4) ¬(p∨(q→(r∧¬p)) → (r∨¬s)pqrs¬pr∧¬pq→(r∧¬p)(p∨(q→(r∧¬p))(r∨¬s)¬(p∨(q→(r∧¬p)) → (r∨¬s)00111111111．7 判断下列命题公式的类型1）p®(pÚqÚr) 解：pqrpÚqpÚqÚrp®(pÚqÚr)000001001011010111011111100111101111110111111111由真值表可知，该命题公式为重言式。

2）（p → ┑p）→ ┑ p p┑pp → ┑p（p → ┑p）→ ┑p01111001由真值知命题公式的类型是：重言式（3）┐(q→p)∧pp→p┐（q→p）┐(q→p)∧p00100010101010011100此命题公式是矛盾式 (4)(p→q) →(﹁q→﹁p) 解:其真值表为:pq﹁p﹁qp→q﹁q→﹁p(p→q)→(﹁q→﹁p)0011111011011110010011100111由真值表观测,此命题为重言式. (5)( ﹁p→q) →(q→﹁p) 解:其真值表为:pq﹁p﹁p→→﹁p(﹁p→q)→(q→﹁p)001011011111100111110100 由真值表观测,此命题为非重言式的可满足式.（7）（p∨p）→((q∧q) ∧r)解：pqrp∨pq∧qr(q∧q) ∧r（p∨p）→((q∧q) ∧r)00010100001100000101010001110000100101001011000011010101111000结论：此命题为矛盾式1.7(8) (p «q)→﹁(p∨q).p q(p«q)(p∨q)﹁(p∨q)(p «q)→﹁(p∨q)0 010110 101011 001011 11100由此可以懂得，上式为非重言式的可满足式.(9) ((ｐ→ｑ)∧(ｑ→ｒ))→(ｐ→ｒ) 解:pｑｒｐ→ｑｑ→ｒ（ｐ→ｑ）∧（ｑ→ｒ）ｐ→ｒA0001111100111111010100110111111110001001101010111101000111111111该命题为永真式（10）（（p∨q）→r）s解：pqrsp∨q（p∨q）→r（p∨q）→r）s0000010000101100100100011011010010101011000110110011111111111111110110110110011001011001100101011010111111000101 结论：此命题为非重言式可满足式1.8 用等值演算法证明下列等值式（1）（p∧q）∨(p∧﹁q) p证明：（p∧q）∨(p∧﹁q) （分派律）p∧(q∨﹁q) （排中律）p∧1 (同一律)p （3）Ø（p « q）Û ( ( p Ú q ) Ù Ø ( p Ù q ) ) 证明：Ø（p « q） Û Ø ( ( p ® q ) Ù (q ® p ) ) Û Ø ( (Ø p Ú q ) Ù (Ø q Ú p ) ) Û Ø (Ø p Ú q ) Ú Ø ( Øq Ú p ) Û ( p Ù Ø q ) Ú ( q Ù Ø p ) Û ( ( p Ù Ø q ) Ú q ) Ù ( (p Ù Ø q ) Ú Ø p ) Û ( ( p Ú q ) Ù ( Ø q Ú q ) ) Ù ( ( p Ú Ø p ) Ù ( Ø q Ú Ø p) )Û (( p Ú q ) Ù1) Ù (1 Ù ( Ø q Ú Ø p) )Û ( p Ú q ) Ù ( Ø q Ú Ø p) Û ( p Ú q ) Ù Ø ( p Ù q ) 1.9 用等值演算法判断下列公式的类型。

（1）Ø（（pÙq）®p）.解：（1）Ø（（pÙq）®p）ÛØ（Ø（pÙq）Úp） 蕴含等值式ÛØ。