离散数学习题解答_屈婉玲耿素云高等教育出版社(第一部分)(2)

q

r

0001111

0110011

1010101

1101

1

11

1011101

1110011

由真值表得：（1）的成假赋值是011（2）的成假赋值是010,110

（3）的成假赋值是100,101

22.已知公式解：∵

是矛盾式，求公式是矛盾式∴

成真和成假赋值.

也是矛盾式。

由此可得：该式无成真赋值。而成假赋值为：000,001,010,011,100,101,110,111

23.已知公式解：∵

是重言式,求公式是重言式，∴

的成真和成假赋值.

也是重言式。

由此可得：该式无成假赋值。而成真赋值为：000,001,010,011,100,101,110,111

24.已知

的类型.

解：∵

是重言式，试判断公式及

是重言式，而要使该式为重言式，其成真赋值只有

11，∴都是重言式。

25.已知

的类型.

解：∵

是矛盾式，试判断公式及

是矛盾式，而要使该式为矛盾式，其成假赋值

只有00，∴都是重言式。

26.已知是重言式，是矛盾式，试判断

及

解：

是矛盾式。是重言式。

的类型.

27.设A、B都是含命题变量项p1,p2,…,pn的公式,证明:重言式.

解：A0011

B0

101

是重言式当且仅当A和B都是

0001

是重言式。

由真值表可得，当且仅当A和

B都是重言式时，

28.设A、B都是含命题变量项p1,p2,…,pn的公式,已知矛盾式的结论吗?为什么?解：A0011

同样由真值表可得，

B0101

是矛盾式,能得出A和B都是

0001

的成假赋值有00,01,10.所以无法得到

A和B都是矛盾式。

29.设A、B都是含命题变量项p1,p2,…,pn的公式,证明:是矛盾式.解：A0011

B0101

是矛盾式当且仅当A和B都

0111

由真值表可得，当且仅当A和B

都是矛盾式时，是矛盾式。

30.设A、B都是含命题变量项p1,p2,…,pn

的公式,已知重言式的结论吗?

解：A0011

由真值表可得

B0101

是重言式,能得出A和B都是

0111

的成真赋值有01,10，11.所以无法得到A和B都是重言式。

习题二

1.设公式A=p→q,B=p∧¬q，用真值表验证公式A和B适合德摩根律：

¬(A∨B) ¬A∧¬B

0011

0101

A

1101

B

0010

¬(A∨B)

1000

¬A∧¬B

1000

2.公式A和B同题（1），用真值表验证公式A和B适合蕴涵等值式.

0011

成真赋值.

0101

A

1101

A→B ¬A∨B

B

0010

A→B

0010

¬A∨B

0010

3．用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出

（1）¬(p∧q→q)答：原式=¬(¬(p∧q)∨q)

=¬(¬p∨¬q∨q)

=0

是矛盾式.

4.用等值演算法证明下面等值式.（1）p （p∧q）∨（p∧¬q）答：右式=p∧（q∨¬q）=p∧1=p（2）((p→q)∧(p→r)) (p→(q∧r))

答：右式=¬p∨(q∧r)=(¬p∨q)∧(¬p∨r)=(p→q)∧(p→r))=左式（3）¬(p q) (p∨q)∧¬(p∧q)答：左式=¬(¬p∨q)∨¬(p∨¬q)

=(p∨(¬p∧q))∧(¬q∨(¬p∧q))=(p∨q)∧¬(p∧q)

（4）(p∧¬q)∨(¬p∧q) (p∨q)∧¬(p∧q)答：左式=(p∨(¬p∧q))∧(¬q∨(¬p∧q))

=(p∨q)∧¬(p∧q)

5.求下列公式的主析取范式，并求成真赋值：（1）(¬p→q)→(¬q∨p)答：

(¬p→q)→(¬q∨p)=(p∨q)→(¬q∨p)=¬(p∨q)∨(¬q∨p)=(¬p∧¬q)∨(¬q∧(p∨¬p))∨(p∧(q∨¬q)=(p∧q)∨(p∨¬p)∨(¬p∧¬q)=m0∨m2∨m3

成真赋值为00,10,11.（2）¬(p→q)∧q∧r

答：¬(p→q)∧q∧r=¬(¬p∨q)∧q∧r=p∧¬q∧q∧=0所以为矛盾式。

（3）(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)∨(¬p∧¬r)∨(p∨q∨r)=(¬p∧¬q∧(r∨¬r)∨(¬p∧(q∨¬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)∨(¬p∧q∧r)=m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7

所以是重言式，真值为000,001,010,011,100,101,110,111.

6.求下列公式的主析取范式，并求成真赋值：（1）¬(q→¬p)∧¬p

答：¬(q→¬p)∧¬p=¬(¬q∨¬p)∧¬p=q∧p∧¬p=0，是矛盾式，所有赋值均为成真赋值。

（2）(p∧q)∨(¬p∨r)

答：(p∧q)∨(¬p∨r)=(p∨¬p∨r)∧(q∨¬p∨r)=(¬p∨q∨r)=M4，成假赋值为100.

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

答：(p→(p∨q))∨r=(¬p∨(p∨q))∨r=(¬p∨p∨q∨r=1，所以为重言式。所有赋值均为成真赋值。

7.求下列公式的主析取范式，再用主析取范式求主合取范式：（1）(p∧q)∨r

答：(p∧q)∨r=(p∧q∧(r∨¬r))∨((p∨¬p)∧(q∨¬q)∧r)

=(p∧q∧(r∨¬r))∨((p∨¬p)∧(q∨¬q)∧r)

=(p∧q∧r)∨(p∧q∧¬r)∨(p∧¬q∧r)∨(¬p∧q∧r)∨(¬p∧¬q∧r)=m1∨m3∨m5∨m6∨m7=M0∧M2∧M4

（2）(p→q)∧(q→r)答：

(p→q)∧(q→r)=(¬p∨q)∧(¬q∨r)=(¬p∧¬q)∨(¬p∧r)∨(q∧¬q)∨(q∧r)=(¬p∧¬q∧(r∨¬r))∨(¬p∧(q∨¬q)∧r)∨((p∨¬p)∧q∧r)=(¬p∧¬q∧r)∨(¬p∧¬q∧¬r)∨(¬p∧q∧r)∨(p∧q∧r)=m0∨m1∨m3∨m7=M2∨M4∨M5∨M6

8.求下列公式的主合取范式，再用主合取范式求主析取范式：

（1）(p∧q)→q

答：(p∧q)→q=¬(p∧q)∨q=¬p∨¬q∨q=1=m0∨m1∨m2∨m3

为重言式。

（2）(p q)→r

答：(p q)→r=¬((p∧q)∨(¬p∧¬q))∨r=(¬(p∧q)∧¬(¬p∧¬q))∨r

=((¬p∨¬q)∧(p∨q))∨r=(¬p∨¬q∨r)∧(p∨q∨r)=M0∧M6=m1∨m2∨m3∨m4∨m5∨m7

（3）¬(r→p)∧p∧q

答：¬(r→p)∧p∧q=r∧¬p∧p∧q

=M0∧M1∧M2∧M3∧M4∧M5∧M6∧M7=0

因此为矛盾式.

9.用真值表求下面的公式的主析取范式.（1）(p∨q)∨(¬p∧r)答：公式的真值表如下：

r

(p∨q)∨(¬p∧r)

01111111

00001111

00110011

01010101

11110000

00111111

01010000

其成真赋值为001,010,011,100,101,110,111，所以其主析取范式为

m1∨m2∨m3∨m4∨m5∨m6∨m7

…… 此处隐藏：2776字，全部文档内容请下载后查看。喜欢就下载吧 ……