自考 离散数学 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∨R2.将下面公式化成与之等值，并且仅含{|∧}中联结词的公式。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，7c)主析取范式： (|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，二者等值自考需要坚持，为自己加油！