离散数学第1章习题答案.docx
- 文档编号:14549379
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:42
- 大小:34.46KB
离散数学第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)
所以
(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))
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 习题 答案