离散数学第1章习题答案.docx
《离散数学第1章习题答案.docx》由会员分享，可在线阅读，更多相关《离散数学第1章习题答案.docx（42页珍藏版）》请在冰点文库上搜索。
离散数学第1章习题答案
#include
#include
#defineMAX_STACK_SIZE100typedefintElemType;
typedefstruct
{
ElemTypedata[MAX_STACK_SIZE];
inttop;
}Stack;
voidlnitStack（Stack*S）
{
S->top=-1;
}
intPush（Stack*S,ElemTypex）
{
if（S->top==MAX_STACK_SIZE-1
）
{
printf（"\nStackisfull!
"）;
return0;
}
S->top++;
S->data[S->top]=x;
return1;
}
intEmpty（Stack*S）
{
return（S->top==-1）;
}
intPop（Stack*S,ElemType*x）
{
if（Empty（S））
{
printf（"\nStackisfree!
"）;
return0;
}
*x=S->data[S->top];
S_>top__;
return1;
}
voidconversion（intN）
{
inte;
Stack*S=（Stack*）malloc（sizeof（Stack））;
InitStack（S）;while（N）
{
Push（S,N%2）;
"}
while（!
Empty（S））
{
Pop（S,&e）;
printf（"%d",e）;
}
}
voidmain（）
{intn;
printf（"请输入待转换的值n:
\n"）;
scanf（"%d",&n）;
conversion（n）;
1.判断下列语句是否是命题，为什么？
若是命题，判断是简单命题还是复合命题？
（1）离散数学是计算机专业的一门必修课。
（2）李梅能歌善舞。
（3）这朵花真美丽！
（4）3+2>6。
（5）只要我有时间，我就来看你。
（6）x=5o
（7）尽管他有病，但他仍坚持工作。
（8）太阳系外有宇宙人。
（9）小王和小张是同桌。
（10）不存在最大的素数。
解在上述10个句子中，（3）是感叹句，因此它不是命题。
（6）虽然是陈述句，但它没有确定的值,
（9）、
因此它也不是命题。
其余语句都是可判断真假的陈述句，所以都是命题。
其中：
（1）、（4）、（8）、
是简单命题，、
（2）、（5）、（7）、（10）是复合命题。
2.判断下列各式是否是命题公式，为什么？
（1）（P（PVQ）。
（2）（pQ（QP）））。
（3）（（PQ）（QP））o
（4）（QRAS。
（5）（PVQRSo
（6）（（R（QRi（PQ）。
解
（1）是命题公式。
（2）不是命题公式，因为括号不配对。
（3）是命题公式。
（5）不是命题公式，因为QR没有意义。
⑹不是命题公式，因为R（QR）（PQ没有意义。
3•将下列命题符号化：
（1）我们不能既划船又跑步。
（2）我去新华书店，仅当我有时间。
（3）如果天下雨，我就不去新华书店。
（4）除非天不下雨，我将去新华书店。
（5）张明或王平都可以做这件事。
（6）“2或4是素数，这是不对的”是不对的。
（7）只有休息好，才能工作好。
（8）只要努力学习，成绩就会好的。
（9）大雁北回，春天来了。
（10）小张是山东人或河北人。
（1）符号化为（PAQ，其中，P：
我们划船，Q:
我们跑步。
符号化为
QR,其中，R：
我有时间，Q：
我去新华书店。
符号化为
PQ,其中，P：
天下雨，Q我去新华书店。
符号化为
PQ其中,
P：
天下雨，Q我去新华书店。
符号化为
PAQ,其中,
P：
张明可以做这件事，Q王平可以做这件事。
符号化为
（PVQ）,
“2或4是素数，这是不对的”是不对的，其中,
P:
2是素数,
素数，。
（8）
（9）
符号化为
符号化为
符号化为
（10）符号化为P
P,其中,
Q其中,
Q,其中,
Q其中,
P：
P：
P：
休息好，Q工作好。
努力学习，Q：
成绩就会好的。
大雁北回，Q:
春天来了。
P：
小张是山东人，Q小张是河北人。
（1）
（PVQ。
⑵
PA（QVF）。
⑶
（PVQ（PA
Q。
⑷
P（QP）。
解
（1）
P
Q
PVQ
（PVQ
0
0
1
0
0
1
0
1
1
0
1
0
1
1
1
0
4.构造下列命题公式的真值表，并据此说明哪些是其成真赋值，哪些是其成假赋值?
由真值表可知，公式（PVQ）的成真赋值为：
01,成假赋值为00、10、11。
⑵
PQR
QVR
PA（QVF）
000
0
0
001
1
0
010
1
0
011
1
0
100
0
0
101
1
1
110
1
1
111
1
1
由真值表可知，公式PA（QVR）的成真赋值为：
101、110、111,成假赋值为000、001、010、011、
100。
⑶
PQ
（PVQ
PAQ
（PVC）（PAQ
00
1
1
1
01
0
0
1
10
0
0
1
11
0
0
1
由真值表可知，公式（PVQ）（PAQ的成真赋值为：
00、01、10、11,没有成假赋值。
01。
由真值表可知，公式
⑷
PQ
QP
P（QP）
00
1
1
01
0
0
10
1
1
11
1
1
P（QP）的成真赋值为：
00、10、11,成假赋值为:
5.分别用真值表法和公式法判断下列命题公式的类型:
（1）（
PVQ）
（PAQ）。
（2）（
PAQ）
（PVQ）。
（3）（
PVQ）
A（QVR）A（RVPVQ）。
（4）（
PAQF）（PARAQ。
（5）（
QP）A
（PAQ）。
（6）（
PQ
（PQ）。
（7）（
PAQ）A
（PVQ）。
解
（1）真值
1表法：
PQ
PVQ
PAQ
（PVQ（PA0
00
0
0
1
01
1
0
0
10
1
0
0
11
1
1
1
由真值表可知，公式（PVQ（PAQ）为可满足式。
公式法：
因为（PVQ）（PAQ（PVQV（PAQ（PAQV（PAQ，所以，公式（PVQ（PA
（2）真值表法:
P
Q
PAQ
PVQ
（PAQ（PVQ
0
0
0
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
1
由真值表可知，公式（PAQ（PVQ）为重言式。
公式法：
因为（PAQ（PVQ（PAQ）V（PVQPVQVPVQT,所以，公式（PAQ（PVQ
为重言式。
（3）真值表法：
PQR
PVQ
QR
RVPVQ
（PVQA（QVF）A（RVPVQ
000
1
1
1
0
001
1
0
1
0
010
1
1
1
0
011
1
1
1
0
100
0
1
1
0
101
0
0
1
0
110
1
1
0
0
111
1
1
1
0
由真值表可知，公式（PVQA（QVF）A（RVPVQ为矛盾式。
公式法：
因为（PVQA（QVF）A（RVPVQ（PVQAQAFA（FAPAQF,所以，公
式（PVQA（QVF）A（RVPVQ为矛盾式。
（4）真值表法：
PQR
PAQR
PARAQ
（PAQF）（PARAQ
000
1
0
0
001
1
0
0
010
1
0
0
011
1
0
0
100
1
0
0
101
1
0
0
110
0
1
1
111
1
0
0
由真值表可知，公式（PAQ&（PAFAQ为可满足式。
公式法：
因为（PAQF）（PAFAQ（（PAQVRV（PAFAQ
（PAQAF）V（PAFAQ（PACAF）
所以，公式（PAQF）（PAFQ为可满足式。
（5）真值表法：
P
Q
QP
PAQ
（QP）A（PAQ
0
0
1
0
0
0
1
0
1
0
1
0
1
0
0
1
1
1
0
0
由真值表可知，公式（QP）A（PAQ为可矛盾式。
公式法：
因为（QP）A（PAQ（QVP）A（PAQ（QAP）A（PAQF,所以，公式为可矛
（6）真值表法:
PQ
PQ
（PQ
（PQ（PQ
00
0
0
1
01
1
1
1
10
1
1
1
11
0
0
1
由真值表可知，公式
（
PQ
（P
Q）为永真式。
公式法：
因为（P
Q）
（PQ
（（
PQA（Q
P））
（（PAQ）V（PAQ））
（（
PVQ）A（
PV
Q））（（pv
Q）A（PVQ））T
所以，公式（PQ（PQ为永真式。
（7）真值表法：
P
Q
PAQ
PVQ
（PAQA（PVQ
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
1
1
0
由真值表可知，公式（PAQA（PVQ为矛盾式。
公式法：
因为（PAQ）A（PVQ（PAQ）A（PAQF,所以，公式（PAQA（PVQ为矛盾式。
6.分别用真值表法和公式法证明下列各等价式：
（1）（PVQAPPAQ
（2）（PVQV（PAQP。
（3）（PAQVPPVQ
（4）P（QAF）（PQA（PR）。
（5）（PQA（RQ（PVR）Q。
（6）（PAQAAC）A（APVQVC）（AA（PQ）C。
⑺（PQPQ
（8）（PC）PQ
证明
（1）真值表法：
P
Q
PVQ
（PVQAP
PAQ
0
0
0
0
0
0
1
1
1
1
1
0
1
0
0
1
1
1
0
0
由真值表可知，（PVQ）APPAQ
公式法：
（PVQAP（PAP）V（QAP）PAQ
（2）真值表法：
P
Q
PAQ
（PVQV（PAQ
P
0
0
1
1
1
0
1
1
1
1
1
0
0
0
0
1
1
0
0
0
由真值表可知，（PVQ）V（PQ
P。
公式法：
（PVQ）V（PAQ）（PAQ）V（PAQPA（QVQ）P。
（3）真值表法：
P
Q
PAQ
（PAQVP
PVQ
0
0
0
1
1
0
1
0
1
1
1
0
0
0
0
1
1
1
1
1
由真值表可知，（PAQ）VP
PVQ
公式法：
（PAQVP（PV
P）A（QV
P）
PVQ
（4）真值表法：
PQR
|PQ
PR
（PQ）A（PR
P（QAR）
000
1
1
1
1
001
1
1
1
1
010
1
1
1
1
011
1
1
1
1
100
0
0
0
0
101
0
1
0
0
110
1
0
0
0
111
1
1
1
1
由真值表可知，P（QAR）（PQA（PR）。
公式法：
P（QAF）PV（QAF）（
PVQ）A（PVR）（PQ）
A（PR）。
（5）真值表法：
PQR
PQ
RQ
（PQ）A（RQ
（PVRQ
000
1
1
1
1
001
1
0
0
0
010
1
1
1
1
011
1
1
1
1
100
0
1
0
0
101
0
0
0
0
110
1
1
1
1
111
1
1
1
1
由真值表可知，（PQA（RQ）（PVR）Q）。
公式法：
（PQA（RQ）（PVQ）A（RVQ）（PARVQ
（PVRVQ（PVR）Q。
（6）真值表法：
PQAC
PQ
（PACAAC）A（APVQVC）
（AA（PQ））C
0000
1
1
1
0001
1
1
1
0010
1
0
0
0011
1
1
1
0100
0
1
1
0101
0
1
1
0110
0
1
1
0111
0
1
1
1000
0
1
1
1001
0
1
1
1010
0
1
1
1011
0
1
1
1100
1
1
1
1101
1
1
1
1110
1
0
0
1111
1
1
1
由真值表可知，（PAQAAC）A（APVQVC）（AA（PQ）G
公式法：
（PAQAAC）A（APVQVC（PVQVAVCA（AVPVQVC）
（PVQVAVC）A（AVPVQVC）
（（PVQVA）A（
AVPVQ））VC
（（PAQAAV（AA
PAQ）VC
（AA（（PAQV（
PAQ）））VC
（AA（PQ））VC
（AA（PQ））Co
（7）真值表法:
由真值表可知,
公式法：
（PQ
（8）真值表法:
由真值表可知,
公式法：
（PQ
PQ
PQ
（PQ
PQ
00
1
0
0
01
1
0
0
10
1
0
0
11
0
1
1
PQ
AQ）
（PVQ））
PQ
PQ
PQ
（PQ:
PQ
00
1
0
0
01
0
1
1
10
0
1
1
11
0
1
1
（PQ
（
（PQPQ
（（PVQ）
（PAQ）PQ
（1）
若AVC
BVC,则
A
B。
⑵
若AAC
BAC,则
A
B。
⑶
若A
B,则A
B。
⑷
若AC
BC,则
A
B。
若AC
BC,则
A
Bo
解
（1）不正
确。
例如，
设有
一赋值
:
A=T,
B=F,C=T,贝UAVCBVC,
但AB不成立。
⑵
不正确。
1
例如，设有「
赋值
宜：
A=T,B=1
-,C=F,则AAcBaC,但A
B不成立。
⑶
正确。
因:
为AB（
A
E）A（B
A（AVB）A（BVA（B
A）A（AB）
7.设ABC为任意的三个命题公式,
试问下面的结论是否正确?
AB,
所以，若AB,则ABo
（4）不正确。
例如，设有一赋值:
A=T,
B=F,C=T,则ACBC,
B不成立。
⑸正确。
因为，若ACB
C与BC等值。
当AC与BC都为真时，A和C等值且B
和C等值，从而A和B等值，此时AB;当AC与BC都为假时，A和C不等值且B和C也不等值，从而A和B等值，此时ABo
总之有，若ACBC,则ABo
8.试给出下列命题公式的对偶式：
（1）（PAQ）VR。
（2）TV（PAQo
（3）（PVQ）AFo
（4）（PAQA（PVQo
解
（1）对偶式为（PVQ）ARo
（2）对偶式为FA（PVQ）o
（3）对偶式为（PAQ）VTo
⑷对偶式为（PVQV（PAQ）o
9.分别用真值表法、分析法和公式法证明下列蕴涵式：
（1）（PQP。
（2）（PQ）QPVQ
（3）PQP（PAQ）o
（4）（PQ）A（QF）（PR）o
证明
（1）真值表法：
PQ
PQ
（PQ
P
00
1
0
0
01
1
0
0
10
0
1
1
11
1
0
1
由真值表可知，（PQ）P。
分析法：
若（PQ）为真，则PQ为假，从而P为真，而Q为假°故（PQPo
公式法：
因为（PQ）P（PVQVPT,所以（PQPo
（2）真值表法：
P
Q
PQ
（PQQ
PVQ
0
0
1
0
0
0
1
1
1
1
1
0
0
1
1
1
1
1
1
1
由真值表可知，（PQQPVQ
分析法：
若PVQ为假，都P和Q为假，于是PQ为真，从而（PQ）Q为假。
故（PQ）QPVQ
公式法：
因为（（PQQ）（PVQ（（PVQVQ）V（PVQ
（（PVQ）AQ）V（PVQ）
（PAQ）V（QAQ）V（PVQ）
（PVQ）V（PVQ
所以，（PQQPVQ
（3）真值表法：
PQ
PAQ
PQ
P（PAQ）
00
0
1
1
01
0
1
1
10
0
0
0
11
1
1
1
由真值表可知，PQP（PAQ。
分析法：
若P（PAQ为假，则P为真且PAQ为假，于是P为真且Q为假，从而PQ为假。
故PQP（PAQo
公式法：
因为（PQ）（P（PAQ）
（PVQ）V（
PV（PAQ
（PA
Q）V（
PV（PAQ）
（PA
Q）V（
PVQ
（PA
Q）V
（PAQ）
T
所以，PQP（PAQo
（4）真值表法：
PQR
PQ
QR
（PQA（QF）
PR
000
1
1
1
1
001
1
1
1
1
010
1
0
0
1
011
1
1
1
1
100
0
1
0
0
101
0
1
0
1
110
1
0
0
0
111
1
1
1
1
由真值表可知，（PQA（QR）（PF）o
分析法：
若PR为假，则P为真而R为假。
当Q为真时，QR为假；当Q为假时，PQ为假。
从而不管Q取什么值，都有（PQA（QR）为假。
故（PQA（QF）（PR）。
公式法：
因为（（PC）A（QR））（PF）（（PVQ»A（QVF））V（PVF）
（PAQ）V（QARVPVR
（PAQ）V（（QVPVRA（RVPVR）
（PAQ）V（QVPVR）
（PVQVPVRA（QVQVPVR）
T
所以，（PQA（Q&（PRo
10.将下列命题公式化成与之等价的仅含联结词或的公式：
（1）PA（QF）o
（2）（P（QAR））VPo
PAQ
（PQ）
（PQ
（PQ
PVQ
（PA
QP
Q（
P
（PVP）
PP
PVQ
（PQ
（PQ）
（PQ）
PAQ
PQ
（PP）
（QQ
所以
（1）PA（Q
F）PA（
QVR）
P
（PaP）
pP
Pa（（Q
（
PP）（QQ）
Q））（RR）
PA（Q
R）
PA（（QQ）
（P（（（QQ）
PA（QVR
QQ））（RR
QQ））（RR）））（P（（（QQ）（QQ）
（RR）））
PA（（Q）P
（（Q）PR）
（2）（P
PA（（QQ）PR）（（QQ）PR）
（PP）（（（（QQPR（（QQ）P电（（（QQ）PR（（Q
（QAR））VP（PV（QAR））VP
QPR）））
（（PP）V（（QR）
（QR）））VP
（（PP）V（（QR）
（QR）））VP
（（（PP）（PP））
（（（（QR）（QR）））（（（QR）
（QR）））））vp
（（（（（pP）（pP））（（（（QR）
（QR）））（（（QR）（QR））））））（（（（pP）
（P
P））（（（（
QR）（QR））
升级会员 