自考 离散数学 02324 课后答案：[4]1.5章节

1.将下面公式化成与之等值并且仅含{|,∨，∧}中的联结词的公式。

a) |(P←→(Q→(P∨R)))；

b) ((P∨Q)∧R)→(P∨R)；

c) (P∧Q)∨R；

d) (P→(Q→R))。

(答案及点评)

a)解:

   |(P←→(Q→(P∨R)))

<=>|(P←→(|Q∨(P∨R)) 〔等值公式〕

<=>(|P←→(|Q∨(P∨R))

<=>(|P∧(|Q∨(P∨R))∨(P∧|(|Q∨(P∨R)) 〔等值公式〕

b)解:

   ((P∨Q)∧R)→(P∨R)

<=>|((P∨Q)∧R)∨(P∨R)

c)不用转换

d)解:

   (P→(Q→R))

<=>|P∨(Q→R)

<=>|P∨(|Q∨R)

<=>|P∨|Q∨R

2.将下面公式化成与之等值，并且仅含{ |∧}中联结词的公式。

a) P∧Q∧|R；

b) (P←→Q)∨R；

c) P∧(Q∨R)；

(答案及点评)

a) 解:此题不用化。

b) 解：

   (P←→Q)∨R

<=>(P∧Q)∨(|P∧|Q)∨R 〔等值公式〕

<=>|(|(P∧Q)∧|(|P∧|Q))∨R 〔德摩根律〕

<=>|(|(P∧Q)∧|(|P∧|Q)∧|R) 〔德摩根律〕

c) 解：P∧(Q∨R)<=>P∧|(|Q∧|R) 〔德摩根律〕

3.求|(P∨Q)←→(P∧Q)的析取范式。

解：析取范式就是在各个子公式中只含{|，∧}联结词，而各子公式之间只以“∨”联结的命题公式。

   |(P∨Q)←→(P∧Q)

<=>(|P∧|Q)←→(P∧Q)〔德摩根律〕

<=>((|P∧|Q)∧(P∧Q))∨(|(|P∧|Q)∧|(P∧Q))〔等值公式〕

<=>F(假)∨(|(|P∧|Q)∧|(P∧Q))〔交换律、结合律、否定律〕

<=>|(|P∧|Q)∧|(P∧Q)〔同一律〕

<=>(P∨Q)∧(|P∨|Q)

<=>(P∧(|P∨|Q)∨(Q∧(|P∨|Q)

<=>(P∧|Q)∨(|P∧Q)

4.求下列公式的主析取范式、主合取范式，并判断各式类型。

a) (|P→Q)→(|Q∨P)；

b) |(P→Q)∧Q∧R；

c) (|P∨|Q)→(P←→|Q)；

d) P∨(|P→(Q∨(|Q→K)))；

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

答案：

a)

主析取范式：

   (|P→Q)→(|Q∨P)

<=>(P∨Q)→(|Q∨P)<=>|(P∨Q)∨(|Q∨P)<=>(|P∧|Q)∨((|Q∧1)∨((P∧1))<=>(|P∧|Q)∨((|Q∧(P∨|P))∨((P∧(Q∨|Q)) <=>(|P∧|Q)∨(|Q∧P)∨(|Q∧|P)∨(P∧Q)∨(P∧|Q) <=>(|P∧|Q)∨(P∧|Q)∨(P∧Q) <=>m00∨m10∨m11 

<=>Σ0，2，3

主合取范式：

   (|P→Q)→(|Q∨P)

<=>(P∨Q)→(|Q∨P)

<=>|(P∨Q)∨(|Q∨P)

<=>(|P∧|Q)∨(|Q∨P)

<=>(|P∨(|Q∨P))∧(|Q∨(|Q∨P))

<=>1∧(|Q∨(|Q∨P))

<=>(|Q∨(|Q∨P))

<=>|Q∨P

<=>P∨|Q

<=>M01

<=>Π1

可以看出，主析取范式，和主合取范式是互补的关系，求出其中一个，可以推出另一个。

此式是可满足式；

b)

主析取范式：

   |(P→Q)∧Q∧R

<=>|(|P∨Q)∧Q∧R

<=>(P∧|Q)∧Q∧R<=>P∧(|Q∧Q)∧R<=>F(永假)可见，此公式为永假式，它的主析取范式不存在。反之其主合取范式就包含全部大项：M000∧M001∧M010∧ 

M011∧M100∧M101∧M110∧M111 =Π0，1，2，3，4，5，6，7

c) 

主析取范式：

   (|P∨|Q)→(P←→|Q)

<=>|(|P∨|Q)∨(P←→|Q)

<=>(P∧Q)∨((P∧|Q)∨(|P∧Q))

<=>(P∧Q)∨(P∧|Q)∨(|P∧Q)

<=>m11∨m10∨m01

<=>Σ1,2,3

主合取范式为Π0<=>M00<=>P∨Q

如果用推导的方式如下：

   (|P∨|Q)→(P←→|Q)

<=>|(|P∨|Q)∨(P←→|Q)

<=>(P∧Q)∨((P∧|Q)∨(|P∧Q))

<=>((P∧Q)∨(P∧|Q))∨(|P∧Q)

<=>(P∧(Q∨|Q))∨(|P∧Q)

<=>(P∧T)∨(|P∧Q)

<=>P∨(|P∧Q)

<=>(P∨|P)∧(P∨Q)

<=>T∧(P∨Q)

<=>P∨Q

此式是可满足式；

d)

主合取范式：

   P∨(|P→(Q∨(|Q→K)))

<=>P∨(P∨(Q∨(|Q→K)))

<=>P∨P∨(Q∨(Q∨K))

<=>P∨P∨Q∨Q∨K

<=>P∨Q∨K

<=>M000

<=>Π0

主析取范式为:Σ1,2,3,4,5,6,7

<=>m001∨m010∨m011∨m100∨m110∨m101∨m111

<=>(|P∧|Q∧K)∨(|P∧Q∧|K)∨(|P∧Q∧K)∨(P∧|Q∧|K)∨(P∧Q∧|K)∨(P∧|Q∧K)∨(P∧Q∧K)

此式是可满足式

e)

主析取范式为:

   (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)∧T)∨((|P∧|R)∧T))∨(P∧Q∧R)

<=>(((|P∧|Q)∧(R∨|R))∨((|P∧|R)∧(Q∨|Q)))∨(P∧Q∧R)

<=>(((|P∧|Q∧R)∨(|P∧|Q∧|R))∨((|P∧|R∧Q)∨(|P∧|R∧|Q)))∨(P∧Q∧R)

<=>(|P∧|Q∧R)∨(|P∧|Q∧|R)∨(|P∧Q∧|R)∨(|P∧|Q∧|R)∨(P∧Q∧R)

<=>m001∨m000∨m010∨m000∨m111

<=>m000∨m001∨m010∨m111

<=>Σ0,1,2,7

主合取范式：

   (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∨(P∧(Q∧R)))∧((|Q∨|R)∨(P∧(Q∧R)))

<=>((|P∨P)∧(|P∨(Q∧R)))∧((|Q∨|R)∨P)∧((|Q∨|R)∨(Q∧R))

<=>(|P∨(Q∧R))∧(|Q∨|R∨P)∧((|Q∨|R∨Q)∧(|Q∨|R∨R))

<=>((|P∨Q)∧(|P∨R))∧(|Q∨|R∨P)∧(T∧T)

<=>((|P∨Q)∨(R∧|R))∧((|P∨R)∨(Q∧|Q))(|Q∨|R∨P)

<=>(|P∨Q∨R)∧(|P∨Q∨|R)∧(|P∨Q∨R)∧(|P∨|Q∨R)∧(P∨|Q∨|R)

<=>M100∧M101∧M100∧M110∧M011

<=>Π3,4,5,6

此式是可满足式

5.使用将公式化为主范式的方法证明下式是等价式。

a) (A→B)∧(A→C)<=>(A→(B∧C)；

b) (A→B)→(A∧B)<=>(A∨B)∧(B→A)；

c) P∨(P→(P∨Q))<=>|P∨|Q∨(P∧Q)。

a)证明如下：

设P：(A→B)∧(A→C)

<=>(|A∨B)∧(|A∨C)

<=>((|A∨B∨(|C∧C))∧((|A∨C)∨(|B∧B)<=>(|A∨B∨C)∧(|A∨B∨|C)∧(|A∨|B∨C)∧(|A∨B∨C)<=>M100∧M101∧M110=Π4,5,6

再设Q：(A→(B∧C)

<=>|A∨(B∧C)

<=>(|A∨B)∧(|A∨C)

<=>(|A∨B∨C)∧(|A∨B∨|C)∧(|A∨B∨C)∧(|A∨|B∨C)<=>M100∧M101∧M110=Π4,5,6

可见 P<=>Q 原等价式成立。

b) 证明如下：

设P：(A→B)→(A∧B)

<=>(|A∨B)→(A∧B)

<=>|(|A∨B)∨(A∧B)

<=>(A∧|B)∨(A∨B)

<=>m10∨m11 =Σ2，3再设Q： (A∨B)∧(B→A)

<=>(A∨B)∧(|B∨A)

<=>(A∨B)∧(A∨|B)

<=>M00∧M01

<=>m10∨m11 = Σ2，3

因此P<=>Q，等价式成立

c) 解：等价式左边<=>P∨(|P∨(P∨Q)

<=>T

<=>Σ0，1，2，3

等价式右边<=>(|P∨|Q)∨(P∧Q)

<=>|(P∧Q)∨(P∧Q)

<=>T

<=>Σ0，1，2，3两边都为永真式，因此都可化为包含全部4个小项的主析取范式。二者是等价的。

6.判断(P→(Q→R))与(Q→(P→R))是否等值? 

(答案及点评)解：

设A: (P→(Q→R))

<=>P→(|Q∨R)

<=>|P∨(|Q∨R)

<=>M110

再设B：(Q→(P→R)

<=>Q→(|P∨R)

<=>|Q∨(|P∨R)

<=>M110

因此可以断定，A<=>B，二者等值

自考需要坚持，为自己加油！