离散数学 数理逻辑 课后答案VIP

千里之行，始于足下。第2页/共2页精品文档推荐离散数学数理逻辑课后答案第一章命题逻辑基本概念

4.将下列命题符号化，并指出真值：

（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；

（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；

（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；

（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；

（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.

5.将下列命题符号化，并指出真值：

（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；

（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；

（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；

（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；

（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；

6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一具苹果，q：小丽从筐里拿一具梨；

（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.

7.因为p与q别能并且为真.

8.p:2<1，q:3<2

（1）p→q，

（2）p→┐q，

（3）┐q→p，

（4）┐q→p，

（5）┐q→p，

（6）p→q，

13.设p:今天是星期一，q:改日是星期二，r:改日是星期三：

（1）p→q，真值为1（不可能浮现前件为真，后件为假的事情）；

（2）q→p，真值为1（也不可能浮现前件为真，后件为假的事情）；

（3）pq，真值为1；

（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.

16.设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r)?0∨(0∧1)?0

（2）（p?r）∧(﹁q∨s)?（0?1）∧(1∨1)?0∧1?0.

（3）（?p∧?q∧r）?(p∧q∧﹁r)?（1∧1∧1）?(0∧0∧0)?0

(4)（?r∧s）→(p∧?q)?（0∧1）→(1∧0)?0→0?1

17．推断下面一段论述是否为真：“π是无理数。同时，假如3是无理数，则2也是无理数。另外6能被2整除，6才干被4整除。”

答：p:π是无理数1

q:3是无理数0

r:2是无理数1

s:6能被2整除1

t:6能被4整除0

命题符号化为：p∧(q→r)∧(t→s)的真值为1，因此这一段的论述为真。

19．用真值表推断下列公式的类型：

（4）(p→q)→(?q→?p)

（5）(p∧r)?(?p∧?q)

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

答：（4）

pqp→q?q?p?q→?p(p→q)→(?q→?p)

0011111

0110111

1001001

1110011

因此公式类型为永真式//最终一列全为1

（5）公式类型为可满脚式（办法如上例）//最终一列至少有一具1

（6）公式类型为永真式（办法如上例）//

第二章命题逻辑等值演算

3.用等值演算法推断下列公式的类型，对别是重言式的可满脚式，再用真值表法求出成真赋值.

(1)?(p∧q→q)

(2)(p→(p∨q))∨(p→r)

(3)(p∨q)→(p∧r)

答：

(1)?(p∧q→q)??(?(p∧q)∨q)?(p∧q)∧?q?0

(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1

因此公式类型为永真式

(3)Pqrp∨qp∧r（p∨q）→(p∧r)

000001

001001

010100

011100

100100101111110100111111

因此公式类型为可满脚式4.用等值演算法证明下面等值式：(2)(p→q)∧(p→r)?(p→(q∧r))

(4)(p∧?q)∨(?p∧q)?(p∨q)∧?(p∧q)证明（2）(p→q)∧(p→r)

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

（4）(p∧?q)∨(?p∧q)?(p∨(?p∧q))∧(?q∨(?p∧q)

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

5.求下列公式的主析取范式与主合取范式，并求成真赋值

(1)(?p→q)→(?q∨p)(2)?(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：

（1）主析取范式

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

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

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

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

?320mmm∨∨

主合取范式：

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

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

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

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

?1∧(p∨?q)

?(p∨?q)?M

1

(2)主合取范式为：

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

?(p∧?q)∧q∧r?0

因此该式为矛盾式.

主合取范式为∏(0,1,2,3,4,5,6,7)

矛盾式的主析取范式为0

(3)主合取范式为：

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

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

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

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

?1∧1

?1

因此该式为永真式.

永真式的主合取范式为1

主析取范式为∑(0,1,2,3,4,5,6,7)

7.(1)：∨∨∨∨?∧∧；

(2)：∨∨∨?∧∧∧；

8.(1)：1?∨∨∨,重言式；

(2)：∨?∨∨∨∨∨∨；

(3)：∧∧∧∧∧∧∧?0，矛盾式.

11.(1)：∨∨?∧∧∧∧；

(2)：∨∨∨∨∨∨∨?1；

(3)：0?∧∧∧.

12.A?∧∧∧∧?∨∨.

第三章命题逻辑的推理理论

6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次算是推断*是否为重言式，若*是重言式，推理就正确，否则推理就别正确，这个地方别思考简单语句之间的内在联系

(1)、(3)、(6)推理正确，其余的均别正确，下面以(1)、(2)为例，证明(1)推理正确，

(2)推理别正确

(1)设p:今天是星期一，q:改日是星期三，推理的形式结构为

(p→q)∧p→q(记作*1)

在本推理中，从p与q的内在联系能够懂，p与q的内在联系能够懂，p与q不会并且为真，但在证明时，别思考这一点，而只思考*1是否为重言式.

能够用多种办法（如真值法、等值演算法、主析取式）证明*1为重言式，特殊是，别难看出，当取A为p,B为q时，*1为假言推理定律，即

(p→q)∧p→q?q

(2)设p:今天是星期一，q:改日是星期三，推理的形式结构为

(p→q)∧p→q(记作*2)

能够用多种办法证明*2别是重言式，比如，等值演算法、主析取范式（主和取范式法也能够）等

(p→q)∧q→p

?(┐p∨q)∧q→p

?q→p

?┐p∨┐q

??∨∨

从而可知，*2别是重言式，故推理别正确，注意，尽管这个地方的p与q并且为真或并且为假，但别思考内在联系时，*2别是重言式，就以为推理别正确.

9.设p:a是奇数，q:a能被2整除，r:a：是偶数

推理的形式结构为

(p→q┐)∧(r→q)→(r→┐p)(记为*)

能够用多种办法证明*为重言式，下面用等值演算法证明：

(p→┐q)∧(r→q)→(r→┐p)

?(┐p∨┐q)∨(q∨┐r)→(┐q∨┐r)(使用了交换律)

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

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

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

?1

10.设p:a,b两数之积为负数，q:a,b两数种恰有一具负数，r：a，b基本上负数.

推理的形式结构为

(p→q)∧┐p→(┐q∧┐r)

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

?┐p→(┐q∧┐r)(使用了汲取律)

?p∨(┐q∧┐r)

?∨∨∨

由于主析取范式中只含有5个W极小项，故推理别正确.

14.在自然推理系统P中构造下面推理的证明：

(2)前提：p→q,?(q∧r),r

结论：?p

(4)前提：q→p,q?s,s?t,t∧r

结论：p∧q

(1)证明

①p→(q→r)前提引入

②P前提引入

③q→r①②假言推理

④q前提引入

⑤r③④假言推理

⑥r∨s前提引入

（2）证明：

①?(q∧r)前提引入

②?q∨?r①置换

③q→?r②蕴含等值式

④r前提引入

⑤?q③④拒取式

⑥p→q前提引入

⑦￢p⑤⑥拒取式

（3）证明：

①p→q前提引入

②┐q∨q①置换

③(┐p∨q)∧(┐p∨p)②置换

④┐p∨(q∧p③置换

⑤p→(p∨q)④置换

（4）证明：

①t∧r前提引入

②t①化简律

③q?s前提引入

④s?t前提引入

⑤q?t③④等价三段论

⑥（q→t）∧(t→q)⑤置换

⑦（q→t）⑥化简

⑧q②⑥假言推理

⑨q→p前提引入

⑩p⑧⑨假言推理

(11)p∧q⑧⑩合取

15.在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p→(q→r),s→p,q

结论：s→r

(1)证明

①s附加前提引入

②s→p前提引入

③p①②假言推理

④p→(q→r)前提引入

⑤q→r③④假言推理

⑥q前提引入

⑦r⑤⑥假言推理

（2）证明：

①p附加前提引入

②p∨q①附加

③(p∨q)→(r∧s)前提引入

④r∧s②③假言推理

⑤s④化简

⑥s∨t⑤附加

⑦(s∨t)→u前提引入

⑧u⑥⑦拒取式

16.在自然推理系统P中用归谬法证明下面各推理：

(1)前提：p→?q,?r∨q,r∧?s

结论：?p

证明：

①p结论的否定引入

②p→﹁q前提引入

③﹁q①②假言推理

④￢r∨q前提引入

⑤￢r④化简律

⑥r∧￢s前提引入

⑦r⑥化简律

⑧r∧﹁r⑤⑦合取

由于最终一步r∧﹁r是矛盾式,因此推理正确.（2）证明：

①┐(r∨s)结论否定引入

②┐r∨┐s①置换

③┐r②化简

④┐s②化简

⑤p→r前提引入

⑥┐p③⑤拒取式

⑦q→s前提引入

⑧┐q④⑦拒取式

⑨┐p∧┐q⑥⑧合取

⑩┐(p∨q)⑨置换

⑾p∨q前提引入

┐(p∨q)∧(p∨q)⑩⑾合取

17．设p：A到过受害者房间，q:A在11点往常离开，r：A犯谋杀罪，s：看门人看见过A。

前提：(p∧┐q)→r,p,q→s,┐s

结论：r

证明：

①q→s前提引入

②┐s前提引入

③┐q①②拒取式

④p前提引入

⑤p∧┐q③④合取

⑥（p∧┐q）→r前提引入

⑦r⑤⑥假言推理

18．（1）设p：今天是星期六，q：我们要到颐和园玩，s：颐和园游人太多。

前提：p→(p∨r),s→┐q,p,s

结论：r

证明：

①s→┐q前提引入

②s前提引入

③┐q①②假言推理

④p前提引入

⑤p→(q∨r)前提引入

⑥q∨r④⑤假言推理

⑦r③⑥析取三段论

（2）设p:小王是理科学生，q：小王数学成绩好，r：小王是文科学生。

前提：p→q,┐r→p,┐q

结论：r

证明：

①p→q前提引入

②┐q前提引入

③┐p①②拒取式

④┐r→p前提引入

⑤r③④拒取式

第四章(一阶)谓词逻辑基本概念

3.在一阶逻辑中将下面将下面命题符号化,并分不讨论个体域限制为(a),(b)条件时命题的真值:

(1)关于任意x,均有2=(x+)(x).

(2)存在x,使得x+5=9.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：

F(x):

2=(x+

)(x

).

G(x):x+5=9.

(1)在两个个体域中都解释为)(xxF?，在（a）中为假命题，在(b)中为真命题。(2)在两个个体域中都解释为)(xxG?，在（a）(b)中均为真命题。

4.(1)┐x(F(x)∧┐G(x))?x(F(x)→G(x)),其中,F(x)：x是有理数,G(x)：x能表示成分数；

(2)┐x(F(x)→G(x))?x(F(x)∧┐G(x)),其中,F(x)：x在北京卖菜,G(x)：x是外地人；

(3)x(F(x)→G(x)),其中,F(x)：x是乌鸦,G(x)：x是黑XXX的；(4)xF(x)∧G(x)),其中,F(x)：x是人,G(x)：x天天锻炼躯体。因为本题中没有指明个体域,因而使用全总个体域。

5.(1)xy(F(x)∧G(y)→H(x,y)),其中,F(x)：x是火车,G(y)：y是轮船,H(x,y)：x比y快；

(2)xy(F(x)∧G(y)→H(x,y)),其中,F(x)：x是火车,G(y)：y是汽车,H(x,y)：x比y快；

(3)┐x(F(x)∧y(G(y)→H(x,y)))?x(F(x)→y(G(y)∧┐H(x,y))),其

中,F(x)：x是汽车,G(y)：y是火车,H(x,y)：x比y快；

(4)┐x(F(x)→y(G(y)→H(x,y)))?xy(F(x)∧G(y)∧┐H(x,y))),其中,F(x)：x

是汽车,G(y)：y是火车,H(x,y)：x比y慢。6.各命题符号化形式如下：(1)xy(x．y=0)；(2)xy(x．y=0)；(3)xy(y=x+1)

(4)xy(x．y=y．x)(5)xy(x．y=x+y)(6)xy(x+y＜0)

9.(1)对任意数的实数x和y,若x＜y,则x≠y；(2)对任意数的实数x和y,若x–y=0,则x＜y；(3)对任意数的实数x和y,若x＜y,则x–y≠0；(4)对任意数的实数x和y,若x–y＜0,则x=y.其中,(1)(3)真值为1(2)与(4)真值为0.

11.(1)、(4)为永真式,(2)、(6)为永假式,(3)、(5)为可满脚式。这个地方仅对(3)、(4)、(5)给出证明。

(3)取解释I为：个体域为自然数集合N,F(x,y)：x≤y,在下,xyF(x,y)为真,而

xyF(x,y)也为真(只需取x=0即可),于是(3)中公式为真,取解释为：个体域仍为自然数集合N,而F(x,y)：x=y。此刻,xyF(x,y)为真(取y为x即可),可是xyF(x,y)为假,于是(3)中公式在下为假,这讲明(3)中公式为可满脚式。

(4)设I为任意一具解释,若在I下,蕴涵式前件xyF(x,y)为假,则

xyF(x,y)→yxF(x,y)为真,若前件xyF(x,y)为真,必存在I的个体域D1中的个体常

项x0,使yF(x0,y)为真,同时关于任意y∈,F(x0,y)为真,由于有x0∈,F(x0,y)为真,

因此xF(x,y)为真,又其中y是任意个体变项,因此yxF(x,y)为真,由于I的任意性,因此(4)中公式为永真式(事实上,次永真式可用第五章的构造证明法证明之)。

(5)取解释为：个体域为自然数集合,F(x,y)：x=y在下,(5)中公式为真,而将F(x,y)改为F(x,y)：x＜y,(5)中公式就为假了,因此它为可满脚式。

13．（1）取解释为：个体域为自然数集合N，F（x）：x为奇数，G（x）：x为偶数，在下，x（F（x）∨G（x））为真命题。

取解释为：