离散数学习题与解答

第一章 集合、关系与函数 习题答案

1、用列举法表示下列集合。

（1）{x|x是小于20的正偶数}={2，4，6，8，10，12，14，16，18}

2

（2）{x|x是整数，x＜80}={0，±1，±2，±3，±4，±5，±6，±7，±8} （3）{x|x=3k，k是小于10的素数}={6,9,15,21}

（4）{x|x是能整除30的正整数}={1，2，3，5，6，10，15，30}

（5）{x|x是小于30的素数}={2，3，5，7，11，13，17，19，23，29}

2、用特征法表示下列集合。

（1）{1，3，5，…，99}={x|x是正奇数，x≤99}

2

（2）{1，4，9，16，25}={x|x=k,k是正整数，k≤5}

（3）{5，10，15，…，100}={x|x=5k,k是正整数，k≤20}

?1（4）{1，3，2，5，3，7，4}={x|x=k2，k是正整数，k≤7} 2223、设A，B，C是集合，确定下列命题是否正确，并说明理由。 （1）如果A∈B,B?C,则A?C。

? 。 解：不正确。例如，A={a}，B={{a},b}，C={{a},b }。易见A∈B,B?C但A C（2）如果A∈B,B?C,则A∈C。

解：正确。因为B?C，所以B中元素都属于C，而A∈B，所以A∈C。 （3）如果A?B,B∈C,则A∈C。

解：不正确。例如，A={a}，B={a,b}，C={{a,b}}。易见A?B,B∈C但A?C。 （4）如果A?B,B∈C,则A?C。

? 。 解：不正确。例如，A={a}，B={a,b}，C={{a,b}}。易见A?B,B∈C但A C

4、确定下列命题是否正确。

（1）??? 正确。 （2）?∈? 错误。 （3）??{?} 正确。 （4）?∈{?} 正确。

5、设A，B，C是集合。

（1）如果A?B,B?C,是否必有A?C？

解：不一定。例如，A={a}，B={b},C={{a}}。易见A?B,B?C,但A∈C。 （2）如果A∈B,B?C,是否必有A?C？

解：不一定。例如，A={a}，B={{a}},C={{a}}。易见A∈B,B?C,但A∈C。 （3）如果A?B,B?C,是否必有A?C？

解：不一定。例如，A={a}，B={a,b},C={{a}}。易见A?B,B?C,但A∈C。

6、求下列集合的幂集。 （1）{1，2，3，4，5} 解：P({1，2，3，4，5})

={?,{1},{2},{3},{4},{5},{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5},{1,2,3}, {1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5},{1,2,3,4},{1,2,3,5}, {1,2,4,5},{1,3,4,5},{2,3,4,5},{1，2，3，4，5} } （2）{a，b，{a,b}}

解：P({a，b，{a,b}})={?,{a},{b},{{a,b}},{a,b},{a,{a,b}},{b,{a,b}},{ a，b，{a,b}}} （3）? 解：P(?)={?}

（4）{?} 解：P({?})={?,{?}}

（5）{?,{?}} 解：P({?,{?}})={?,{?},{{?}},{?,{?}}}

第1页 /共 44页

7、设A={a},求P(P(A))。 解：P(A)={?，{a}}，

P(P(A))={ ?，{?}，{{a}}，{?，{a}}}

8、设Z+是正整数集，A，B，C是Z+

的子集，且：

A={i|i2

＜50}={1，2，3，4，5，6，7}

B={i|i能整除30}={1，2，3，5，6，10，15，30} C={1,3,5,7} 求下列集合。

（1）A∪C={1，2，3，4，5，6，7}

（2）A∪(B∩C)={1，2，3，4，5，6，7} （3）C-(A∩B)={7}

（4）(B∩C)-(A∪B)={1,3,5}-{1，2，3，4，5，6，7, 10，15，30}={}= ? （5）A⊕C=(A-C)∪(C-A)={2,4,6}∪{}={2,4,6}

9、给定正整数集Z+

的子集： A={x|x＜12} B={x|x≤8}

C={x|x=2k,k∈Z+

}

D={x|x=3k,k∈Z+

}

试用A，B，C，D的运算表示下列集合。

（1）{2，4，6，8}=B∩C （2）{1，3，5，7}=B-C （3）{3，6，9}=A∩D （4）{10}=A∩C-B

（5）{x|x是大于12的奇数}=C-A

10、证明下列各等式。 （1）A∩(B?A)= ?

证：A∩(B?A)=A∩(B∩A)= (A∩A)∩B= ?∩B= ? （2）A∪(B-A)=A∪B

证：A∪(B-A)= A∪(B∩A)=(A∪B)∩(A∪A)=(A∪B)∩E=A∪B （3）A∩(A-B)= A-B

证：A∩(A-B)= A∩A∩B= A∩B= A-B （4）(A∩B)∪(A-B)=A

证：(A∩B)∪(A-B)= (A∩B)∪(A∩B)=A∩(B∪B)=A∩E=A （5）(A∩B)-C = (A-C)∩(B-C)

证：(A∩B)-C= A∩B∩C=A∩B∩C∩C= (A∩C)∩(B∩C)=(A-C)∩(B-C) （6）(A-B)-C = (A-C)-B

第2页 /共 44页

证：(A-B)-C=A∩B∩C= (A∩C)∩B=(A-C)-B （7）(A-B)-C = (A-C)-(B-C)

证：(A-C)-(B-C)=(A∩C)∩B?C=(A∩C)∩B?C =(A∩C)∩(B∪C)=(A∩C)∩(B∪C) =(A∩C∩B) (A∩C∩C)= (A∩B∩C)∪? = (A∩B)∩C=(A-B)-C （8）(A∪B) -C = (A-C)∪(B-C)

证：(A-C)∪(B-C)=(A∩C)∪(B∩C)=(A∪B)∩C=(A∪B) -C （9）(A-B)∪(A-C)∪(A∩B∩C) = A

证：(A-B)∪(A-C)∪(A∩B∩C) = (A∩B)∪(A∩C)∪(A∩B∩C) =(A∩(B∪C))∪(A∩(B∩C)) =(A∩(B?C))∪(A∩(B∩C)) =A∩((B?C))∪(B∩C))= A∩E=A 11、12、14、15答案见教材62-64页。 13、证明下列等式。 （1）A∪(A⊕B)=A∪B

证：A∪(A⊕B)= A∪(A-B)∪(B-A)=A∪(A∩B)∪(B∩A)=A∪(B∩A)(吸收律) =（A∪B）∩（A∪A）=（A∪B）∩E= A∪B

（2）(A∪B)⊕(A∩B)=A⊕B

证：(A∪B)⊕(A∩B)= ((A∪B)-(A∩B))∪((A∩B)- (A∪B)) =（(A∪B)∩A?B）∪((A∩B)∩A?B)) =（(A∪B)∩(A∪B)∪((A∩B)∩(A∩B))

=(((A∪B)∩A)∪((A∪B)∩B))∪((A∩A)∩(B∩B)) =(((A∩A)∪(B∩A))∪((A∩B)∪(B∩B)))∪(?∩?) =((?∪(B∩A))∪((A∩B)∪?))∪? =(B∩A)∪(A∩B)=(B-A)∪(A-B)= A⊕B （3）(A∪B)⊕(A-B)=B

证：(A∪B)⊕(A-B)= ((A∪B)-(A∩B))∪((A∩B)- (A∪B))

第3页 /共 44页

=((A∪B)∩A?B)∪((A∩B)∩A?B) =((A∪B)∩(A∪B))∪((A∩B)∩(A∩B)) =((A∩A)∪B)∪((A∩A)∩(B∩B)) =(?∪B)∪(?∩B)=B∪?=B （4）(A∩B)⊕(A-B)=A

证：(A∩B)⊕(A-B)= ((A∩B)-(A∩B))∪((A∩B)- (A∩B)) =((A∩B)∩A?B)∪((A∩B)∩A?B) =((A∩B)∩(A∪B))∪((A∩B)∩(A∪B)) =(A∩(B∩(A∪B)))∪(A∩(B∩(A∪B))) =(A∩B)∪(A∩B)(吸收律) =A∩(B∪B)=A∩E=A

（5）(A∩B)⊕(A∪B)⊕(A-B)=B-A

证：(A∩B)⊕(A∪B)⊕(A-B)=(((A∩B)-(A∪B))∪((A∪B)-(A∩B)))⊕(A-B) =(((A∩B)∩(A∩B))∪((A∪B)∩(A∪B)))⊕(A-B)

=(((A∩A)∩(B∩B))∪(((A∪B)∩A)∪((A∪B)∩B)))⊕(A-B) =((?∩?)∪(((A∩A)∪(B∩A))∪((A∩B)∪(B∩B))))⊕(A-B) =(?∪((?∪(B∩A))∪((A∩B)∪?)))⊕(A-B)

=((B∩A)∪(A∩B))⊕(A-B)= ((B∩A)∪(A∩B))⊕(A∩B) = (((B∩A)∪(A∩B))-(A∩B))∪((A∩B)-((B∩A)∪(A∩B))) = (((B∩A)∪(A∩B))∩(A∪B))∪((A∩B)∩(B?A)?(A?B))

= (((B∩A)∩(A∪B))∪((A∩B)∩(A∪B)))∪((A∩B)∩((B∪A)∩(A∪B))) = ((B∩(A∩(A∪B)))∪(A∩(B∩(A∪B))))∪(A∩(B∩(B∪A))∩(A∪B)) = (B∩A)∪(A∩B∩(A∪B))∪(A∩B∩(A∪B)) = (B∩A)∪(A∩B∩(A∪B))

= (B∩A)∪(A∩((B∩A)∪(B∩B)))

第4页 /共 44页

= (B∩A)∪((A∩A)∩B)= (B∩A)∪?= (B∩A)=B-A （6）((A⊕B)∩(A⊕C))-A=(B∩C)-A

证：((A⊕B)∩(A⊕C))-A=（（(A∩B)∪(B∩A)）∩((A∩C)∪(C∩A))）∩A =（（(A∩B)∪B）∩（(A∩B)∪A)）∩(((A∩C)∪C)∩((A∩C)∪A))）∩A =(A∪B)∩(B∪B)∩(A∪A)∩(B∪A)∩(A∪C)∩(C∪C)∩(A∪A)∩(C∪A)∩A =(A∪B)∩E∩E∩(B∪A)∩(A∪C)∩E∩E∩(C∪A)∩A =(A∪B)∩(B∪A)∩(A∪C)∩(C∪A)∩A =(A∪B)∩(B∪A)∩A∩(A∪C)

=(A∪B)∩(A∪C)∩A=(A∪(B∩C)) ∩A=(A∩A)∪((B∩C) ∩A) =?∪((B∩C) ∩A)=(B∩C) ∩A=(B∩C)-A （7）((A⊕B)∪(A⊕C))-A=(B∪C)-A

证：((A⊕B)∪(A⊕C))-A=（（(A∩B)∪(B∩A)）∪((A∩C)∪(C∩A))）∩A =（((A∩B)∪(A∩C))∪((B∩A)∪(C∩A))）∩A =（(A∩(B∪C))∪((B∪C)∩A)）∩A =（A∩(B∪C)∩A)∪((B∪C)∩A∩A） =（(A∩A)∩(B∪C))∪((B∪C)∩A） =?∪((B∪C)∩A）=(B∪C)∩A=(B∪C)-A （8）((A⊕B)∩(A⊕C))-(B∪C)= A-(B∪C)

证：((A⊕B)∩(A⊕C))-(B∪C)=（（(A∩B)∪(B∩A)）∩((A∩C)∪(C∩A))）∩B?C =（（(A∩B)∪B）∩（(A∩B)∪A)）∩(((A∩C)∪C)∩((A∩C)∪A))）∩B?C =(A∪B)∩(B∪B)∩(A∪A)∩(B∪A)∩(A∪C)∩(C∪C)∩(A∪A)∩(C∪A)∩B?C =(A∪B)∩E∩E∩(B∪A)∩(A∪C)∩E∩E∩(C∪A)∩B?C =(A∪B)∩(B∪A)∩(A∪C)∩(C∪A)∩(B∩C) =(A∪B)∩((B∪A)∩B)∩(A∪C)∩((C∪A)∩C)

=((A∪B)∩B)∩((A∪C)∩C)=((A∩B)∪(B∩B))∩( (A∩C)∪(C∩C))

第5页 /共 44页

证：列出┐(┐P∨┐Q)∨┐(┐P∨Q)和P的真值表： P Q ┐P ┐Q 0 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0 ┐P∨┐Q 1 1 1 0 ┐(┐P∨┐Q) 0 0 0 1 ┐(┐P∨Q) 0 0 1 0 ┐(┐P∨┐Q)∨┐(┐P∨Q) 0 0 1 1

（6）(P→Q)∧(Q→R) ? (┐P∧┐Q)∨(┐P∧R)∨(Q∧R)

证：列出(P→Q)∧(Q→R)和(┐P∧┐Q)∨(┐P∧R)∨(Q∧R)的真值表： P Q R P→Q Q→R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 P Q R ┐P 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 ┐Q 1 1 0 0 1 1 0 0 ┐P∧┐Q 1 1 0 0 0 0 0 0 ┐P∧R 0 1 0 1 0 0 0 0 Q∧R 0 0 0 1 0 0 0 1 (┐P∧┐Q)∨(┐P∧R)∨(Q∧R) 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 (P→Q)∧(Q→R) 1 1 0 1 0 0 0 1

10、证明下列等价式。

（1）(P∧Q)∨(P∧┐Q) ? P

证：(P∧Q)∨(P∧┐Q) ? P∧(Q∨┐Q) ? P∧1? P

（2）Q→(P∨(P∧Q)) ? ┐Q∨P

证：Q→(P∨(P∧Q)) ? Q→P (吸收律)? ┐Q∨P

（3）P→(P→Q) ? P→Q

证：P→(P→Q) ? ┐P∨(┐P∨Q) ? ┐P∨Q(等幂律) ? P→Q

（4）(A∧┐B)→C ? A→(B∨C)

证：(A∧┐B)→C ? ┐(A∧┐B) ∨C ? (┐A∨B) ∨C ? ┐A∨(B∨C)? A→(B∨C)

（5）(P→Q)∨(P→R) ? P→(Q∨R)

证：(P→Q)∨(P→R) ? (┐P∨Q)∨(┐P∨R) ? ┐P∨(Q∨R) ? P→(Q∨R)

（6）┐(P?(Q→(R∨P))) ? ┐P∧┐(Q∧┐R)

第26页 /共 44页

证：┐(P?(Q→(R∨P))) ? ┐(P?(┐Q∨R∨P)) ? ┐((P→(┐Q∨R∨P))∧((┐Q∨R∨P)→P)) ? ┐((┐P∨┐Q∨R∨P)∧(┐(┐Q∨R∨P)∨P)) ? ┐(1∧((Q∧┐R∧┐P)∨P))

? ┐((Q∧┐R∧┐P)∨P) ? ┐((Q∧┐R)∨P)∧(┐P∨P)) ? ┐((Q∧┐R)∨P)∧1) ? ┐((Q∧┐R)∨P) ? ┐(Q∧┐R) ∧┐P ? ┐P∧┐(Q∧┐R)

（7）(P→R)∧(Q→R) ? (P∨Q)→R

证：(P→R)∧(Q→R) ? (┐P∨R)∧(┐Q∨R) ? (┐P∧┐Q)∨R ? ┐(P∨Q)∨R ? (P∨Q)→R （8）（9）（10）（12）答案见教材105-106页。 （11）A→(B→C) ? (A→C)∨(B→C)

证：A→(B→C) ? ┐A∨(┐B∨C) ? ┐A∨┐B∨C∨C ? (┐A∨C)∨(┐B∨C) ? (A→C)∨(B→C)

11、证明下列命题公式为永真式。 （1）(P∧Q→P)∧(P∨┐P)

证：(P∧Q→P)∧(P∨┐P) ? (┐(P∧Q) ∨P)∧1 ? ┐(P∧Q) ∨P ? (┐P∨┐Q) ∨P ? ┐P∨P∨┐Q ? 1∨┐Q ? 1

（2）P→(P∨Q)

证：P→(P∨Q) ? ┐P∨(P∨Q) ? (┐P∨P)∨Q ? 1∨Q ? 1

（3）┐P→(P→Q)

证：┐P→(P→Q) ? P∨(┐P∨Q) ? (P∨┐P)∨Q ? 1∨Q ? 1

（4）(P→(P∨Q))∧(┐P→(P→Q))

证：(P→(P∨Q))∧(┐P→(P→Q)) ? (┐P∨(P∨Q))∧(P∨(┐P∨Q)) ? ((┐P∨P)∨Q)∧((P∨┐P)∨Q)? (1∨Q)∧(1∨Q) ? 1∧1 ? 1

（5）(P∧(P→Q))→Q

证：(P∧(P→Q))→Q ? ┐(P∧(┐P∨Q)) ∨Q

? (┐P∨┐(┐P∨Q))∨Q ? (┐P∨(P∧┐Q))∨Q ? ((┐P∨P)∧(┐P∨┐Q))∨Q

? (1∧(┐P∨┐Q))∨Q ? (┐P∨┐Q)∨Q ? ┐P∨(┐Q∨Q) ? ┐P∨1 ? 1

（6）((P→Q)∧(Q→R))→(P→R)

证：((P→Q)∧(Q→R))→(P→R) ? ┐((┐P∨Q)∧(┐Q∨R))∨(┐P∨R) ? (┐(┐P∨Q)∨┐(┐Q∨R))∨(┐P∨R) ? ((P∧┐Q)∨(Q∧┐R))∨┐P∨R ? ((P∧┐Q)∨┐P)∨((Q∧┐R))∨R)

? ((P∨┐P)∧(┐Q∨┐P))∨((Q∨R)∧(┐R∨R)) ? (1∧(┐Q∨┐P))∨((Q∨R)∧1) ? (┐Q∨┐P)∨(Q∨R)

? (┐Q∨Q)∨┐P∨R? 1∨┐P∨R ? 1

第27页 /共 44页

12、利用真值表证明：

（1）析取运算满足结合律。

证：列出(P∨Q)∨R和P∨(Q∨R)的真值表： P Q R P∨Q (P∨Q)∨R Q∨R P∨(Q∨R) 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 由表可知(P∨Q)∨R ? P∨(Q∨R)，即析取运算满足结合律。

（2）合取运算满足结合律。

证：列出(P∧Q)∧R和P∧(Q∧R)的真值表： P Q R P∧Q (P∧Q)∧R Q∧R P∧(Q∧R) 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 由表可知(P∧Q)∧R ? P∧(Q∧R)，即合取运算满足结合律。

（3）合取对析取满足分配律。

证：列出P∧(Q∨R)和(P∧Q)∨(P∧R)的真值表： P Q R Q∨R P∧(Q∨R) P∧Q P∧R (P∧Q)∨(P∧R) 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 由表可知P∧(Q∨R)? (P∧Q)∨(P∧R)，即合取对析取满足分配律。

（4）析取对合取满足分配律。

证：列出P∨(Q∧R)和(P∨Q)∧(P∨R)的真值表： P Q R Q∧R P∨(Q∧R) P∨Q P∨R (P∨Q)∧(P∨R) 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0

第28页 /共 44页

0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 由表可知P∨(Q∧R)? (P∨Q)∧(P∨R)，即析取对合取满足分配律。

（5） 摩根律。

证：①列出┐(P∧Q)和┐P∨┐Q的真值表： P Q R P∧Q ┐(P∧Q) ┐P ┐Q ┐P∨┐Q 0 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 由表可知┐(P∧Q)? ┐P∨┐Q。 ②列出┐(P∨Q)和┐P∧┐Q的真值表： P Q R P∨Q ┐(P∨Q) ┐P ┐Q ┐P∧┐Q 0 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 由表可知┐(P∨Q)? ┐P∧┐Q。 由①②可知运算满足摩根律。

13、利用真值表证明下列永真蕴含式。 （1）┐P ? P→Q

证：列出┐P → P→Q的真值表： P Q P→Q ┐P ┐P → P→Q 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 1 （2）┐Q∧(P→Q)? ┐P

证：列出┐Q∧(P→Q) → ┐P的真值表： P Q ┐Q P→Q ┐Q∧(P→Q) ┐P ┐Q∧(P→Q) → ┐P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1

第29页 /共 44页

（3）┐P∧(P∨Q)? Q

证：列出┐P∧(P∨Q) → Q的真值表： P Q 0 0 0 1 1 0 1 1 ┐P 1 1 0 0 P∨Q 0 1 1 1 ┐P∧(P∨Q) 0 1 0 0 ┐P∧(P∨Q) → Q 1 1 1 1 （4）(P∨Q)∧(P→R)∧(Q→R)? R

证：列出(P∨Q)∧(P→R)∧(Q→R)→R的真值表： P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R P∨Q P→R 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 Q→R 1 1 0 1 1 1 0 1 (P∨Q)∧(P→R)∧(Q→R) 0 0 0 1 0 1 0 1 (P∨Q)∧(P→R)∧(Q→R)→R 1 1 1 1 1 1 1 1 14、利用常用永真蕴含式证明： （1）(P∨Q)∧(P→R)∧(Q→S) ? R∨S

证：(P∨Q)∧(P→R)∧(Q→S) ? ((┐P→Q) ∧(Q→S))∧(P→R) ? (┐P→S)∧(P→R) ? (P∨S)∧(┐P∨R) ? ((P∨S)∧┐P)∨((P∨S)∧R)

? ((P∧┐P)∨(┐P∧S))∨((P∨S)∧R) ? 0∨(┐P∧S)∨((P∨S)∧R)

? (┐P∧S)∨((P∨S)∧R)(简化律) ? S∨((P∨S)∧R) ? S∨R ? R∨S

（2）(P→Q)∧(┐Q∨R)∧┐R∧┐(┐P∧S) ? ┐S

证：(P→Q)∧(┐Q∨R)∧┐R∧┐(┐P∧S) ? (P→Q)∧((┐Q∨R)∧┐R)∧(P∨┐S) ? (P→Q)∧┐Q∧(P∨┐S) ? ┐P∧(P∨┐S) ? ┐S （3）（4）答案见教材106-107页。

（5）(┐(P→Q)→┐(R∨S))∧((Q→P) ∨┐R)∧R ? P ? Q 证：(┐(P→Q)→┐(R∨S))∧((Q→P) ∨┐R)∧R ? ((P→Q) ∨┐(R∨S))∧((Q→P) ∨┐R)∧(R∧R) ? (((R∨S)→(P→Q))∧R) ∧((R→(Q→P))∧R) ? (((R∨S)→(P→Q))∧(R∨S))∧((R→(Q→P))∧R) ? (P→Q)∧(Q→P) ? P ? Q

15、利用直接证明方法证明下列各永真蕴含式。 （1）┐D，┐C∨D，A∧B→C ? ┐A∨┐B 证：

① ┐D P ② ┐C∨D P ③ ┐C T①②

第30页 /共 44页

④ A∧B→C P ⑤ ┐(A∧B) T③④ ⑥ ┐A∨┐B E⑤

（2）A→（┐B∨C），D∨E，(D∨E)→A ? B→C 证：

① (D∨E)→A P ② D∨E P ③ A T①② ④ A→（┐B∨C） P ⑤ ┐B∨C T③④ ⑥ B→C E⑤

（3）A→B，B→C，A∨┐D，┐C ? ┐D 证：

① A→B P ② B→C P ③ A→C T①② ④ ┐C P ⑤ ┐A T③④ ⑥ A∨┐D P ⑦ ┐D T⑤⑥

（4）A→(B→C)，┐D∨A，B ? D→C 证：

① ┐D∨A P ② D→A E① ③ A→(B→C) P ④ D→(B→C) T②③ ⑤ ┐D∨┐B∨C E④ ⑥ B→(D→C) E⑤ ⑦ B P ⑧ D→C T⑥⑦ （5）M?Q，M→S，S→┐R ? R→Q 证：

① M→S P ② S→┐R P ③ M→┐R T①② ④ ┐M∨┐R E③ ⑤

R→┐M E④

⑥ M?Q P ⑦ (┐M∨┐Q)∧(M∨Q) E⑥ ⑧ M∨Q T⑦ ⑨ ┐M→Q E⑧ ⑩

R→Q T⑤⑨

第31页 /共 44页

（6）┐(P→Q)→┐(R∨S)，(Q→P) ∨┐R，R ? P?Q 证：

① (Q→P) ∨┐R P ② R→(Q→P) E① ③ R P ④ Q→P T②③ ⑤ ┐(P→Q)→┐(R∨S) P ⑥ (P→Q)∨┐(R∨S) E⑤ ⑦ (R∨S)→(P→Q) E⑥ ⑧ R∨S T③ ⑨ P→Q T⑦⑧ ⑩ (P→Q)∧(Q→P) E④⑨ ? P?Q E⑩

（7）P?Q，S→┐Q，S∨R，┐R ? ┐P 证：

① ┐R P ② S∨R P ③ S T①② ④ S→┐Q P ⑤ ┐Q T③④ ⑥ P?Q P ⑦ (P→Q)∧(Q→P) E⑥ ⑧ P→Q T⑦ ⑨ ┐P T⑤⑧

（8）P∨Q，P→R，Q→S，┐S ? R 证：

① ┐S P ② Q→S P ③ ┐Q T①② ④ P∨Q P ⑤ P T③④ ⑥ P→R P ⑦ R T⑤⑥

16、用间接证明法证明下列各式。

（1）P→Q，┐Q∨R，┐(┐P∧S)，┐R ? ┐S 证：

① ┐(┐S) P(附加前提) ② ┐(┐P∧S) P ③ P∨┐S E② ④ P T①③ ⑤ P→Q P ⑥ Q T④⑤ ⑦ ┐Q∨R P ⑧ R T⑥⑦

第32页 /共 44页

⑨ ┐R P ⑩ R∧┐R ? 0 E⑧⑨

（2）(A→B)∧(C→D)∧(B→E)∧(D→F)∧┐(E∧F)∧(A→C) ? ┐A 证：

① ┐(┐A) P(附加前提) ② A→B P ③ B T①② ④ B→E P ⑤ E T③④ ⑥ ┐(E∧F) P ⑦ ┐E∨┐F E⑥ ⑧ ┐F T⑤⑦ ⑨ D→F P ⑩ ┐D T⑧⑨ ? C→D P

? ┐C T○10○11 ? A→C P ? C T①○13 ? ┐C∧C ? 0 E○12○14

（3）P→Q，S→┐Q，S∨R，┐R ? ┐P 证：

① ┐(┐P) P(附加前提) ② P→Q P ③ Q T①② ④ S→┐Q P ⑤ ┐S T③④ ⑥ S∨R P ⑦ R T⑤⑥ ⑧ ┐R P

⑨ R∧┐R ? 0 E⑦⑧

（4）┐P→Q，P→┐R，Q→S，┐S ? ┐R 证：

① ┐(┐R) P(附加前提) ② P→┐R P ③ ┐P T①② ④ ┐P→Q P ⑤ Q T③④ ⑥ Q→S P ⑦ S T⑤⑥ ⑧ ┐S P

⑨ S∧┐S ? 0 T⑦⑧

第33页 /共 44页

17、用CP规则证明下列各式。

（1）A→（┐B∨C），D∨E，（D∨E）→A ? B→C 证：

① D∨E P ② (D∨E)→A P ③ A T①② ④ A→(┐B∨C) P ⑤ ┐B∨C T③④

⑥ B P(附加前提) ⑦ ┐(┐B) E⑥ ⑧ C T⑤⑦ ⑨ B→C CP规则

（2）A，B→（A→C），（C∧D）→E，┐F→（D∧┐E）? B→F 证：

① B P(附加前提) ② B→（A→C） P ③ A→C T①② ④ A P ⑤ C T③④ ⑥ (C∧D)→E P ⑦ ┐(C∧D)∨E E⑥ ⑧ ┐C∨┐D∨E E⑦ ⑨ C→(┐D∨E) E⑧ ⑩ ┐D∨E T⑤⑨ ? ┐(D∧┐E) E⑩ ? ┐F→（D∧┐E） P

? F T○11○12 ? B→F CP规则

（3）A→(B→C)，┐D∨A，B ? D→C 证：

① D P(附加前提) ② ┐D∨A P ③ D→A E② ④ A T①③ ⑤ A→(B→C) P ⑥ B→C T④⑤ ⑦ B P ⑧ C T⑥⑦ ⑨ D→C CP规则

（4）┐D，┐C∨D，（A∧B）→C ? A→┐B 证：

① ┐D P ② ┐C∨D P

第34页 /共 44页

③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ┐C T①② (A∧B)→C P ┐(A∧B) T③④ ┐A∨┐B E⑤

A P(附加前提) ┐B T⑥⑦ A→┐B CP规则

18、对于下列一组前提，请给出它们的有效结论，并进行证明。

（1）如果我努力学习，那么我能通过考试；如果我通过考试，那么我去看电影；但我没去看电影。 证：令 P：我努力学习，Q：我通过考试，R：我去看电影。

前提：P→Q，Q→R，┐R 有效结论：┐P 即需证：（P→Q）∧（Q→R）∧┐R ?┐P ① P→Q P ② Q→R P ③ P→R T①② ④ ┐R P ⑤ ┐P T③④

┐P是有效结论，即我没努力学习是有效结论。

（2）今晚我去剧场看戏或者去夜大上课；如果我去剧场看戏，那么我很高兴；如果我去夜大上课，那么我要吃

个面包；但我没吃面包。

证：令 P：我去剧场看戏，Q：我去夜大上课，R：我高兴，S：我吃面包。

前提：P∨Q，P→R，Q→S，┐S 有效结论：R 即需证：（P∨Q）∧（P→R）∧（Q→S）∧┐S ?R ① Q→S P ② ┐S P ③ ┐Q T①② ④ P∨Q P ⑤ P T③④ ⑥ P→R P

⑦ R T⑤⑥

R是有效结论，即我高兴是有效结论。

19、分析下列事实：“早饭我吃面包或蛋糕；如果我吃面包，那么我还要喝牛奶；如果我吃蛋糕，那么我还要喝

咖啡；但我没有喝咖啡，所以早饭我吃面包和牛奶。”请写出前提和有效结论，并证明之。 证：令 P：早饭我吃面包，Q：早饭我吃蛋糕，R：我喝牛奶，S：我喝咖啡。

前提：P∨Q，P→R，Q→S，┐S 结论：P∧R 即需证：（P∨Q）∧（P→R）∧（Q→S）∧┐S ? P∧R ① Q→S P ② ┐S P ③ ┐Q T①② ④ P∨Q P ⑤ P T③④

第35页 /共 44页

⑥ P→R P ⑦ R T⑤⑥ ⑧ P∧R T⑤⑦

20、分析下列事实：“如果我考上大学，那么我去杭州旅游；如果我去杭州旅游，那么我要买新衣服；如果我要

买新衣服，那么我就去银行取钱。但我没去银行取钱，所以我没考上大学”。写出前提和结论，并证明结论是有效结论。

证：令 P：我考上大学，Q：我去杭州旅游，R：我买新衣服，S：我去银行取钱。

前提：P→Q，Q→R，R→S，┐S 结论：┐P 即需证：（P→Q）∧（Q→R）∧（R→S）∧┐S ? ┐P ① P→Q P ② Q→R P ③ P→R T①② ④ R→S P ⑤ P→S T③④ ⑥ ┐S P ⑦ ┐P T⑤⑥ 21、答案见教材107页。

22、下列推理中，哪些结论是有效结论。

（1）如果我参加长跑比赛，那么我很疲劳；但我不疲劳，所以我没有参加长跑比赛。 解：令 P：我参加长跑比赛，Q：我疲劳。 前提：P→Q，┐Q 结论：┐P

因为（P→Q）∧┐Q ? ┐P

所以┐P是有效结论，即我没有参加长跑比赛是有效结论。

（2）如果你上课用心听讲，那么你考试及格；你上课不用心听讲，所以你考试不及格。解：令 P：你上课用心听讲，Q：你考试及格。 前提：P→Q，┐P 结论：┐Q 因为 P Q P→Q ┐P ┐Q （P→Q）∧┐P （P→Q）∧┐P → ┐Q 0 0 1 1 1 1 1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 1 （P→Q）∧┐P → ┐Q?1即（P→Q）∧┐P?┐Q 所以┐Q不是有效结论，即你考试不及格不是有效结论。

23、求下列命题公式的析取范式。 （1）（P→Q）? ┐R

解:（P→Q）? ┐R ?（┐P∨Q）? ┐R

?(（┐P∨Q）→ ┐R）∧(┐R→（┐P∨Q）） ?(┐（┐P∨Q）∨ ┐R）∧(R∨（┐P∨Q）） ?(（P∧┐Q）∨ ┐R）∧(┐P∨Q∨R）

?(（P∧┐Q）∧(┐P∨Q∨R）)∨ (┐R∧(┐P∨Q∨R）)

第36页 /共 44页

?(P∧┐Q∧┐P)∨(P∧┐Q∧Q)∨(P∧┐Q∧R)∨(┐R∧┐P)∨(┐R∧Q)∨(┐R∧R) ?0∨0∨(P∧┐Q∧R)∨(┐P∧┐R)∨(Q∧┐R)∨0 ?(P∧┐Q∧R)∨(┐P∧┐R)∨(Q∧┐R)

（2） P →（Q?R）

解: P →（Q?R）? ┐P ∨（Q?R）? ┐P ∨(（Q→R）∧（R→Q）) ? ┐P ∨(（┐Q∨R）∧（┐R∨Q）)

? ┐P ∨((（┐Q∨R）∧┐R) ∨（（┐Q∨R）∧Q）)

? ┐P ∨((┐Q∧┐R)∨(R∧┐R)）∨（（┐Q∧Q）∨(R∧Q）) ? ┐P ∨(┐Q∧┐R)∨0∨0∨(R∧Q） ? ┐P ∨(┐Q∧┐R)∨(Q∧R）

（3）（┐P∨Q）→R

解:（┐P∨Q）→R ? ┐（┐P∨Q）∨R ? （P∧┐Q）∨R

（4）（P?Q）→（R∧P）

解:（P?Q）→（R∧P）? ┐(P?Q）∨（R∧P）? ┐((P→Q) ∧(Q→P)）∨（R∧P）? ┐((┐P∨Q) ∧(┐Q∨P)）∨（R∧P） ? (┐(┐P∨Q) ∨┐(┐Q∨P)）∨（R∧P） ? ( (P∧┐Q) ∨ (Q∧┐P)）∨（R∧P） ? (P∧┐Q)∨(┐P∧Q)∨（P∧R）

（5）（P→Q）? R

解:（P→Q）? R ? ((P→Q）→ R) ∧(R→(P→Q）) ? (┐(P→Q）∨ R) ∧(┐R∨(P→Q）) ? (┐(┐P∨Q）∨ R) ∧(┐R∨(┐P∨Q）) ? ( (P∧┐Q）∨ R) ∧(┐P∨Q∨┐R)

? ((P∧┐Q）∧(┐P∨Q∨┐R))∨ (R∧(┐P∨Q∨┐R))

? (P∧┐Q∧┐P）∨(P∧┐Q∧Q)∨ (P∧┐Q∧┐R)∨(R∧┐P)∨(R∧Q)∨(R∧┐R) ? 0∨0∨ (P∧┐Q∧┐R)∨(┐P∧R)∨(Q∧R)∨0 ? (P∧┐Q∧┐R)∨(┐P∧R)∨(Q∧R)

24、求下列命题公式的主析取范式。 （1）（P→Q）∨（P→R）

解:（P→Q）∨（P→R）?（┐P∨Q）∨（┐P∨R） ? ┐P∨Q∨R

? m0□□∨m□1□∨m□□1

?(m000∨m001∨m010∨m011)∨(m010∨m011∨m110∨m111)∨(m001∨m011∨m101∨m111) ? m000∨m001∨m010∨m011∨m101∨m110∨m111

?(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R) ∨(┐P∧Q∧┐R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R)

（2）（P→R）∧（Q→R）

解:（P→R）∧（Q→R）?（┐P∨R）∧（┐Q∨R） ? (┐P∧┐Q) ∨ R

? m00□∨m□□1 ? (m000∨m001)∨(m001∨m011∨m101∨m111)

第37页 /共 44页

? m000∨m001∨m011∨m101∨m111

?(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧R) ∨(P∧Q∧R)

（3） P∧（Q?R）

解: P∧（Q?R）? P∧（Q→R）∧（R→Q）? P∧（┐Q∨R）∧（Q∨┐R） ?((P∧┐Q)∨(P∧R）)∧（Q∨┐R）

?((P∧┐Q) ∧（Q∨┐R）) ∨((P∧R）∧（Q∨┐R）)

?(P∧┐Q∧Q) ∨(P∧┐Q∧┐R) ∨(P∧R∧Q）∨(P∧R∧┐R） ?(P∧0) ∨(P∧┐Q∧┐R) ∨(P∧Q∧R）∨(P∧0） ? 0∨(P∧┐Q∧┐R) ∨(P∧Q∧R）∨0 ?(P∧┐Q∧┐R) ∨(P∧Q∧R）

（4） ┐(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∨（P∧Q）)) ∧(┐P∨┐Q∨(┐P∧┐Q）) ?(Q∨P) ∧(┐Q∨(┐P∨(┐P∧┐Q）))

?(Q∨P) ∧(┐Q∨┐P) ?((Q∨P) ∧┐Q) ∨((Q∨P) ∧┐P) ?((Q∧┐Q)∨(P∧┐Q))∨((Q∧┐P)∨(P∧┐P)) ?(0∨(P∧┐Q) )∨((Q∧┐P)∨0) ?(P∧┐Q) ∨(┐P∧Q)

（5） ┐(P→Q）∨（Q?R）

解: ┐(P→Q）∨（Q?R）? ┐(┐P∨Q）∨((Q→R）∧(R→Q)) ? (P∧┐Q）∨((┐Q∨R）∧(┐R∨Q))

? (P∧┐Q）∨(((┐Q∨R）∧┐R)∨((┐Q∨R）∧Q))

? (P∧┐Q）∨((┐Q∧┐R)∨(R∧┐R）)∨((┐Q∧Q)∨(R∧Q)) ? (P∧┐Q）∨((┐Q∧┐R)∨0)∨(0∨(R∧Q)) ? (P∧┐Q）∨(┐Q∧┐R)∨(Q∧R)

? m10□∨m□00∨m□11 ?(m100∨m101)∨(m000∨m100)∨(m011∨m111) ? m000∨m011∨m100∨m101∨m111

?(┐P∧┐Q∧┐R)∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R) ∨(P∧┐Q∧R) ∨(P∧Q∧R)

25、利用真值表求下列命题公式的主析取范式。 （1）（P→Q）? R P Q R P→Q （P→Q）? R 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 主析取范式?m001∨m011∨m100∨m111

?(┐P∧┐Q∧R)∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R) ∨(P∧Q∧R)

第38页 /共 44页

（2） ┐(P→Q）∨(Q→R) P Q R P→Q ┐(P→Q） Q→R ┐(P→Q）∨(Q→R) 0 0 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1 0 1 1 主析取范式?m000∨m001∨m011∨m100∨m101∨m111

?(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R) ∨(P∧┐Q∧R) ∨(P∧Q∧R)

（3） P∧Q∧(Q ? R) P Q R P∧Q Q ? R P∧Q∧(Q ? R) 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 主析取范式?m111 ? P∧Q∧R

（4） (P→Q) ∨(┐R→S) P Q R S P→Q ┐R ┐R→S (P→Q）∨ (┐R→S) 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 1 0 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 主析取范式?m0000∨m0001∨m0010∨m0011∨m0100∨m0101∨m0110∨m0111

∨m1001∨m1010∨m1011∨m1100∨m1101∨m1110∨m1111

第39页 /共 44页

? (┐P∧┐Q∧┐R∧┐S)∨(┐P∧┐Q∧┐R∧ S) ∨(┐P∧┐Q∧ R∧┐S) ∨(┐P∧┐Q∧R∧S)∨(┐P∧Q∧┐R∧┐S)∨(┐P∧Q∧┐R∧S)

∨(┐P∧Q∧R∧┐S) ∨(┐P∧Q∧R∧S)∨(P∧┐Q∧┐R∧S) ∨(P∧┐Q∧R∧┐S) ∨(P∧┐Q∧R∧S) ∨(P∧Q∧┐R∧┐S) ∨(P∧Q∧┐R∧S)∨(P∧Q∧R∧┐S) ∨(P∧Q∧R∧S)

（5） ┐P∧(Q?R) P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 ┐P 1 1 1 1 0 0 0 0 Q?R 1 0 0 1 1 0 0 1 ┐P∧(Q?R) 1 0 0 1 0 0 0 0 主析取范式?m000∨m011? (┐P∧┐Q∧┐R) ∨(┐P∧Q∧R)

26、求下列命题公式的合取范式。 （1）（┐P→Q）→R

解:（┐P→Q）→R ? (P∨Q）→R ? ┐(P∨Q）∨R ? (┐P∧┐Q）∨R ? (┐P∨R)∧(┐Q∨R)

（2）（P→┐Q）?R

解:（P→┐Q）?R ?（┐P∨┐Q）?R ?（（┐P∨┐Q）→R）∧（ R→（┐P∨┐Q）） ?（┐（┐P∨┐Q）∨R）∧（┐R∨（┐P∨┐Q）） ?（（P∧Q）∨R）∧（┐P∨┐Q∨┐R） ?（P∨R）∧（Q∨R）∧（┐P∨┐R∨┐Q）

（3） ┐P?(Q→R)

解: ┐P?(Q→R)? ┐P?(┐Q∨R) ? （┐P→(┐Q∨R)）∧ （(┐Q∨R)→┐P） ?（P∨(┐Q∨R)）∧（┐(┐Q∨R) ∨┐P） ?（P∨┐Q∨R）∧（ (Q∧┐R) ∨┐P） ?（P∨┐Q∨R）∧(┐P∨Q)∧（┐P∨┐R)

（4）（┐P→Q）?R

解:（┐P→Q）?R ?（P∨Q）?R ?（（P∨Q）→R）∧（R→（P∨Q）） ?（┐（P∨Q）∨R）∧（┐R∨（P∨Q）） ?（（┐P∧┐Q）∨R）∧（P∨Q∨┐R） ?（┐P∨R）∧（┐Q∨R）∧（P∨Q∨┐R）

（5） P∧(Q?R)

解: P∧(Q?R) ? P∧(Q→R)∧(R→Q) ? P∧(┐Q∨R)∧(Q∨┐R)

27、求下列命题公式的主合取范式。 （1）（P→Q）∧(R→Q)

解：（P→Q）∧(R→Q) ?（┐P∨Q）∧(Q∨┐R) ? M10□∧M□01? M100∧M101∧M001∧M101

? M001∧M100∧M101?（P∨Q∨┐R）∧（┐P∨Q∨R）∧（┐P∨Q∨┐R）

第40页 /共 44页

（2） ┐P∧(┐Q?R)

解：┐P∧(┐Q?R)? ┐P∧(┐Q→R)∧(R→┐Q) ? ┐P∧(Q∨R)∧(┐Q∨┐R)

? M1□□∧M□00∧M□11? (M100∧M101∧M110∧M111)∧(M000∧M100)∧(M011∧M111) ? M000∧M011∧M100∧M101∧M110∧M111

?（P∨Q∨R）∧（P∨┐Q∨┐R）∧（┐P∨Q∨R）

∧（┐P∨Q∨┐R）∧（┐P∨┐Q∨R）∧（┐P∨┐Q∨┐R）

（3）（P?Q）∧(Q?R)

解:（P?Q）∧(Q?R)?（P→Q）∧（Q→P）∧(Q→R) ∧(R→Q) ?（┐P∨Q）∧（P∨┐Q）∧(┐Q∨R) ∧(Q∨┐R)

? M10□∧M01□∧M□10∧M□01? (M100∧M101)∧(M010∧M011)∧(M010∧M110)∧(M001∧M101) ? M001∧M010∧M011∧M100∧M101∧M110

?（P∨Q∨┐R）∧（P∨┐Q∨R）∧（P∨┐Q∨┐R）

∧（┐P∨Q∨R）∧（┐P∨Q∨┐R）∧（┐P∨┐Q∨R）

（4）（P→Q）∧(Q?R)

解:（P→Q）∧(Q?R) ?（┐P∨Q）∧(Q→R)∧(R→Q) ?（┐P∨Q）∧(┐Q∨R)∧(Q∨┐R)

? M10□∧M□10∧M□01?(M100∧M101)∧(M010∧M110)∧(M001∧M101) ? M001∧M010∧M100∧M101∧M110

?（P∨Q∨┐R）∧（P∨┐Q∨R）∧（┐P∨Q∨R）

∧（┐P∨Q∨┐R）∧（┐P∨┐Q∨R）

（5） ┐P∨(Q→R)

解: ┐P∨(Q→R) ?┐P∨(┐Q∨R)

? M1□□∧M□10?(M100∧M101∧M110∧M111)∧(M010∧M110) ? M010∧M100∧M101∧M110∧M111

?（P∨┐Q∨R）∧（┐P∨Q∨R）∧（┐P∨Q∨┐R）

∧（┐P∨┐Q∨R）∧（┐P∨┐Q∨┐R）

28、利用真值表求下列命题公式的主合取范式。 （1）（P?Q）∧(R→Q) P Q R P?Q R→Q （P?Q）∧(R→Q) 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 主合取范式?M001∧M 010∧M 011∧M 100∧M 101

?(P∨Q∨┐R)∧(P∨┐Q∨R)∧(P∨┐Q∨┐R)∧(┐P∨Q∨R) ∧(┐P∨Q∨┐R)

（2）（┐P→Q）∧(Q?R)

第41页 /共 44页

P Q R ┐P ┐P→Q Q?R （┐P→Q）∧(Q?R) 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 1 主合取范式? M000∧M001∧M 010∧M 101∧M 110

?(P∨Q∨R)∧(P∨Q∨┐R)∧(P∨┐Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R)

（3） P∨(┐Q?R) P Q R ┐Q ┐Q?R P∨(┐Q?R) 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 主合取范式? M000∧M011?(P∨Q∨R)∧(P∨┐Q∨┐R)

（4）（┐P→Q）→R P Q R ┐P ┐P→Q （┐P→Q）→R 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 1 1 0 1 1 主合取范式? M010∧M100∧M110?(P∨┐Q∨R)∧(┐P∨Q∨R) ∧(┐P∨┐Q∨R)

（5） P∧(┐Q?R) P Q R ┐Q ┐Q?R P∧(┐Q?R) 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0

第42页 /共 44页

主合取范式? M000∧M001∧M010∧M011∧M100∧M111

?(P∨Q∨R)∧(P∨Q∨┐R) ∧(P∨┐Q∨R)∧(P∨┐Q∨┐R) ∧(┐P∨Q∨R) ∧(┐P∨┐Q∨┐R)

29、利用真值表求下列命题公式的主析取范式和主合取范式。 （1）（P→Q）? R P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 P→Q 1 1 1 1 0 0 1 1 （P→Q）? R 0 1 0 1 1 0 0 1 主析取范式?m001∨m011∨m100∨m111

?(┐P∧┐Q∧R)∨(┐P∧Q∧R)∨(P∧┐Q∧┐R)∨(P∧Q∧R)

主合取范式?M000∧M 010∧M 101∧M 110

?(P∨Q∨R)∧(P∨┐Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R)

（2）┐(P→Q）∨ (Q ? R) P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 P→Q 1 1 1 1 0 0 1 1 ┐(P→Q） 0 0 0 0 1 1 0 0 Q ? R 1 0 0 1 1 0 0 1 ┐(P→Q）∨ (Q ? R) 1 0 0 1 1 1 0 1 主析取范式?m000∨m011∨m100∨m101∨m111

?(┐P∧┐Q∧┐R)∨(┐P∧Q∧R)∨(P∧┐Q∧┐R)∨(P∧┐Q∧R) ∨(P∧Q∧R)

主合取范式?M001∧M 010∧M 110

?(P∨Q∨┐R)∧(P∨┐Q∨R)∧(┐P∨┐Q∨R)

（3）P∧(Q ? R) P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 Q ? R 1 0 0 1 1 0 0 1 P∧(Q ? R) 0 0 0 0 1 0 0 1 主析取范式?m100∨m111?(P∧┐Q∧┐R)∨(P∧Q∧R) 主合取范式?M000∧M 001∧M 010∧M011∧M101∧M110

第43页 /共 44页

?(P∨Q∨R)∧(P∨Q∨┐R)∧(P∨┐Q∨R)∧(P∨┐Q∨┐R) ∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R)

（4） (P→Q）∨ (┐R→S) P Q R S P→Q ┐R ┐R→S (P→Q）∨ (┐R→S) 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 1 0 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 主析取范式?m0000∨m0001∨m0010∨m0011∨m0100∨m0101∨m0110∨m0111

∨m1001∨m1010∨m1011∨m1100∨m1101∨m1110∨m1111

? (┐P∧┐Q∧┐R∧┐S)∨(┐P∧┐Q∧┐R∧ S) ∨(┐P∧┐Q∧ R∧┐S) ∨(┐P∧┐Q∧R∧S)∨(┐P∧Q∧┐R∧┐S)∨(┐P∧Q∧┐R∧S) ∨(┐P∧Q∧R∧┐S) ∨(┐P∧Q∧R∧S)∨(P∧┐Q∧┐R∧S) ∨(P∧┐Q∧R∧┐S) ∨(P∧┐Q∧R∧S) ∨(P∧Q∧┐R∧┐S) ∨(P∧Q∧┐R∧S)∨(P∧Q∧R∧┐S) ∨(P∧Q∧R∧S)

主合取范式?M1000?(┐P∨Q∨R∨S)

第44页 /共 44页

本文来源：https://www.bwwdw.com/article/7b55.html