(完整版)离散数学屈婉玲版第一章部分习题汇总

千里之行，始于足下。第2页/共2页精品文档推荐(完整版)离散数学[屈婉玲版]第一章部分习题汇总第一章习题

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)2008年10月1日天气晴好.

是命题,简单命题.p:2008年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:蓝群和黄XXX能够调配成绿XXX.真值:1

1.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

真值为：0

1.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→?q

1.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．7推断下列命题公式的类型。（1）p→(p∨q∨r)

由真值表可知，该命题公式为重言式。

由真值知命题公式的类型是：重言式（3

(4)(p→q)→(﹁q→﹁p)

解:

其真值表为:

由真值表观看,此命题为重言式.(5)(﹁p→q)→(q→﹁p)

解:

由真值表观看,此命题为非重言式的可满脚式.

（7）（p∨?p）→((q∧?q)∧?r)

结论：此命题为矛盾式

1.7(8)

由此能够懂，上式为非重言式的可满脚式.(9)((ｐ→ｑ)∧(ｑ→ｒ))→(ｐ→ｒ)

解:

（10）（（p∨q）→r）?s

结论：此命题为非重言式可满脚式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）蕴含等值式

??（?（p∧q））∧?p德·摩根律

?p∧q∧?p双重否定律

?p∧?p∧q交换律

?0∧q矛盾律

?0零律

即原式为矛盾式.

(2)((p→q)∧(q→p))?(p?q)

解：((p→q)∧(q→p))?(p?q)

?(p?q)?(p?q)

?((p?q)→(p?q))∧((p?q)→(p?q))

?(P?q)→(p?q)

??(p?q)∨(p?q))

?1

即((p→q)∧(q→p))?(p?q)是重言式。

(3)(?p→q)→(q→?p).

解：(?p→q)→(q→?p)

??((p∨q))∨(?q∨?p)

?(?p∧?q)∨(?q∨?p)

?(?p∨(?p∧?q))∧(?q∨(?q∨?p))

?((?p∨?p)∨?q)∧((?q∨?q)∨?p]

?(?p∨?q)∧(?p∨?q)

?(?p∨?q)

或(?p→q)→(q→?p)

??((p∨q))∨(?q∨?p)

?(?p∧?q)∨(?q∨?p)

?（(?p∧?q)∨?q）∨?p结合律

??p∨?q汲取律

结论：该公式为可满脚式。

1.12(1)求下面命题公式的主析取范式、主合取范式、成真赋值、成假赋值。

(p∨(q∧r))→（p∧q∧r）

?←(p∨(q∧r))∨(p∧q∧r)

?(?p∧(?q∨?r))∨(p∧q∧r)

?(?p∧?q)∨(?p∧?r)∨(p∧q∧r)

?((?p∧?q)∧(r∨?r))∨((?p∧?r)∧(q∨?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∧?r)∨(p∧q∧r)

?((?p∧?q∧?r)∨(?p∧?q∧r)∨(?p∧q∧?r)∨(p∧q∧r)

?m0∨m1∨m2∨m7

?∑(0,1,2,7)

故其主析取范式为

(p∨(q∧r))→（p∧q∧r）?∑(0,1,2,7)

由最小项定义可懂原命题的成真赋值为

(0,0,0)(0,1,0)(0,0,1)(1,1,1)

成假赋值为(0,1,1)(1,0,0)(1,0,1)(1,1,0)

由主析取范式和主合取范式的关系即可懂主合取范式为

(p∨(q∧r))→（p∧q∧r）?∏(3,4,5,6)

（3）?（p→q）∧q∧r

解：?（p→q）∧q∧r

??（?p∨q）∧q∧r

?p∧?q∧q∧r

?0

既?（p→q）∧q∧r是矛盾式。?（p→q）∧q∧r的主合取范式为M0∧M1∧M2∧M3∧M4∧M5∧M6∧M7，成假赋值为：000，001，010，011，100，101，111．

13.经过求主析取范式推断下列各组命题公式是否等值。∨∨∧（1）①p→(q→r);②q→(p→r).

解：p→(q→r)?﹁p∨(q→r)

?﹁p∨(﹁q∨r)

?﹁p∨﹁q∨r

?(﹁p∧(q∨﹁q)∧(r∨﹁r))∨((p∨﹁p)∧﹁q∧(r∨﹁r))∨((p∨﹁p)∧(q∨﹁q)∧r)

?(﹁p∧q∧r)∨(﹁p∧q∧﹁r)∨(﹁p∧﹁q∧r)∨(﹁p∧﹁q∧﹁r)∨(p∧﹁q∧r)∨(p∧﹁q∧﹁r)∨(﹁p∧q∧r)

?∑(0,1,2,3,4,5,7)

q→(p→r)?﹁q∨(﹁p∨r)

?﹁p∨﹁q∨r

?∑(0,1,2,3,4,5,7)

因此两式等值。

（2）①p↑q

?←(p∧q)

?(p∧(q∨←q))∨(q∧(p∨←p))

?(p∧q)∨(←p∧←q)∨(←q∧p)∨(←p∧←q)

?(←p∧q)∨(←p∧←q)∨(p∧←q)

?m1∨m0∨m2

?∑(0,1,2)

(p∧←q)处原为(←q∧p)，别是极小项

②令A=p↑q

B=←(p∧q)

C=(←p∧q)∨(←p∧←q)∨(p∧←q)

D=p↓q

则B*=←(p∨q)?p↓q=D

且A?B?C

因此D?A*?C*

C*=(←p∨q)∧(←p∨←q)∧(p∨←q)

?∏（0，1，2）?∑(3)

因此①!?②

1.15某勘探队有3名队员，有一天取得一块矿样，3人推断如下：

甲讲：这别是铁，也别是铜；

乙讲：这别是铁，是锡；

丙讲：这别是锡，是铁；

经实验室鉴定后发觉，其中一人两个推断都正确，一具人判对一半，另一具人全错了。依照以上事情推断矿样的种类。

解：p：是铁q：是铜r：是锡

由题意可得共有6种事情：

1)甲全对，乙对一半，丙全错：(﹁p∧﹁q)∧((﹁p∧﹁r)∨(p