离散数学答案章陈志奎.docx
- 文档编号:12319609
- 上传时间:2023-06-05
- 格式:DOCX
- 页数:60
- 大小:174.26KB
离散数学答案章陈志奎.docx
《离散数学答案章陈志奎.docx》由会员分享,可在线阅读,更多相关《离散数学答案章陈志奎.docx(60页珍藏版)》请在冰点文库上搜索。
离散数学答案章陈志奎
第1章命题逻辑
P7习题
1.给出下列命题的否定命题:
(1)大连的每条街道都临海。
否命题:
不是大连的每条街道都临海。
(2)每一个素数都是奇数。
否命题:
并非每一个素数都是奇数。
2.对下述命题用中文写出语句:
(1)(PR)Q
如果非P与R,那么Q。
(2)QR
Q并且R。
Q的逆
3.给出命题PQ,我们把QP、PQ、QP分别称为命题P
命题、反命题、逆反命题。
(1)如果天不下雨,我将去公园。
解:
逆命题:
如果我去公园,则天不下雨;反命题:
如果天下雨,则我不去公园;逆反命题:
如果我不去公园,则天下雨了。
(2)仅当你去我才逗留。
解:
(此题注意:
p仅当q翻译成pq)逆命题:
如果你去,那么我逗留。
反命题:
如果我不逗留,那么你没去。
逆反命题:
如果你没去,那么我不逗留。
(3)如果n是大于2的正整数,那么方程xnynzn无整数解。
解:
逆命题:
如果方程xnynzn无整数解,那么n是大于2的正整数。
反命题:
如果n不是大于2的正整数,那么方程xnynzn有整数解。
逆反命题:
如果方程xnynzn有整数解,那么n不是大于2的正整数
(4)如果我不获得更多的帮助,那么我不能完成这项任务。
解:
逆命题:
如果我不完成任务,那么我不获得更多的帮助。
反命题:
如果我获得了更多的帮助,那么我能完成任务。
逆反命题:
如果我能完成任务,那么我获得了更多的帮助。
4.给P和Q
指派真值T,
给R和
S指派真值F,求出下列命题的真值。
(1)((P
Q
R)
((Q
P)(RS)))
=((T
T
F)
((T
T)(FF)))
=T
(F
T)
=T
F
=T
2)Q
(P
Q)
P
=T
(T
T)
T
=T
T
T
=T
T
=T
3)(P
(Q
(R
P)))
(Q
S)
=(T
(T
(F
T)))
(T
F)
=(T
(T
F))
T
=T
T
=T
4)(P
R)
(Q
S)
=(T
F)
(T
F)
=F
(F
F)
=F
5.构成下来公式的真值表:
(1)Q(PQ)P
P
Q
F
F
F
T
F
T
T
F
T
F
F
T
T
T
T
T
2)(PQR)(PQ)(PR)
P
Q
R
F
F
F
T
F
F
F
F
T
T
F
F
F
T
F
T
F
F
F
T
T
F
T
F
T
F
F
F
T
F
T
F
T
F
T
F
T
T
F
F
T
F
T
T
T
F
T
F
3)(PQQP)PR
P
Q
R
F
F
F
T
F
F
F
F
T
T
F
F
F
T
F
F
F
T
F
T
T
F
F
T
T
F
F
F
T
T
T
F
T
F
F
T
T
T
F
T
T
T
T
T
T
T
F
F
4)(PPQR)QR
P
Q
R
F
F
F
T
T
F
F
T
F
F
F
T
F
T
T
F
T
T
F
F
T
F
F
T
T
T
F
T
F
F
T
T
F
F
T
T
T
T
F
F
6.使用真值表证明:
如果PQ为T,那么PQ和QP都是T,反之亦然
证明:
P
Q
F
F
T
T
T
F
T
F
T
F
T
F
F
F
T
T
T
T
T
T
由上表可知:
当PQ为T时,PQ和QP都是T;PQ和QP为T时,
PQ为T。
故命题得证。
7.使用真值表证明:
对于P和Q的所有值,PQ与PQ有同样的真值。
P
Q
F
F
T
T
F
T
T
T
T
F
F
F
T
T
T
T
8.一个有两个运算对象的逻辑运算符,如果颠倒其运算对象的次序,产生一逻辑等价命题,则称此逻辑运算符是可交换的。
1)确定所给出的逻辑运算符哪些是可交换的:
2)用真值表证明你的判断。
解:
(1),,是可交换的
2)真值表如下:
P
Q
F
F
F
F
F
F
T
T
T
T
F
T
F
F
T
T
T
F
F
F
T
F
F
F
T
T
F
T
F
F
T
T
T
T
T
T
T
T
T
T
9.设是具有两个运算对象的逻辑运算符,如果(xy)z和x(yz)逻辑等价,那么运算符是可结合的。
(1)确定逻辑运算符,,,哪些是可结合的?
(2)用真值表证明你的判断。
解:
(1),,是可结合的。
2)真值表如下:
P
Q
R
F
F
F
F
F
F
T
F
F
T
F
T
T
T
F
T
F
F
T
F
T
F
T
T
F
T
T
F
T
F
F
F
T
T
T
T
F
T
F
T
T
F
T
T
F
F
T
F
F
T
T
T
T
T
T
T
P
Q
R
F
F
F
F
F
T
T
F
F
T
F
T
T
T
F
T
F
F
T
T
T
F
T
T
F
T
T
F
T
F
F
F
T
T
T
T
F
T
F
T
T
F
T
T
F
F
T
F
F
T
T
T
T
T
T
T
10.令P表示命题“苹果是添的”,Q表示命题“苹果是红的”,R表示命题“我买苹果”试将下列命题符号化:
(1)如果苹果甜而红,那么我买苹果。
(2)苹果不是甜的。
(3)我没买苹果,因为苹果不红也不甜。
解:
(1)PQR
2)P
P15习题
1.指出下面命题公式哪些是重言式、永假式或可满足式。
解:
(1)重言式
(2)永假式
(3)重言式
(4)重言式
(5)重言式
(6)重言式
=(PQ)(QP)T
(7)重言式
=(PQ)(PQ)T
(8)重言式
=((PQ)(PR))(PQPR)
=(PQPR)(PQPR)
=T
(9)重言式
=FQT
(10)可满足式
=(PQ)QPQQ,当Q为真时公式为真,Q为假时公式为假。
故为可满
足式。
(11)重言式
(12)重言式
(13)可满足式
(PQP)(PQ)的真值表如下:
P
Q
F
F
T
T
T
F
T
T
F
F
T
F
F
F
T
T
T
T
T
T
14)可满足式
=(PQRS)(PRQS)
=((PR)(QS))((PR)(QS))
公式为真;
当Q或S有一个为真时公式为真;当Q和S均为假时,若P和R真值相同时,真值不同时,公式为假。
故公式是可满足式。
2.写出与下面给出的公式等价并且仅含有联接词与的最简公式。
(1)(P(Q(RP)))
2)((PQ)
R)
(PR)
3)PQ
R
4)P(Q
R
P)
5)P(Q
P)
3.写出与下面的公式等价并且仅含联结词和的最简公式
1)(PQ)P
2)
(P
(QQ))
PQ
3)
P
Q(R
P)
4.使用常用恒等式证明下列各式,并给出下列各式的对偶式。
(1)(
P
Q)(
P
Q)
P
证明:
对偶式:
(P
Q)
(
P
Q)
P
(2)(P
Q)
(PQ
)(
P
Q)
(PQ)
证明:
对偶式:
(P
Q)(P
Q)
(
P
Q)(P
(3)Q
((
PQ)
P)
T
证明:
对偶式:
Q((PQ)P)F5.试证明下列合式公式是永真式。
(1)((PQ)P)T
证明:
(2)((PQ)P)F
证明:
(3)
(Q
P)
(P
Q)
P
证明:
(4)
(P
P)
(P
P)
F
证明:
6.证
明下列
蕴含式。
(1)
P
QP
Q
证明:
(2)
P
(Q
R)
(P
Q)
(P
R)
证明:
(3)
P
Q
PP
Q
证明:
(4)
(P
Q)
Q
PQ
证明:
(5)
(P
P
Q)
(P
P
R)
Q
R
证明:
(6)
(Q
P
P)
(R
P
P)
R
Q
证明:
7.对一个重言式使用代入规则后仍为一个重言式,对一个可满足式和一个矛盾式,使用代入规则后,结果如何?
对重言式、可满足式和矛盾式,使用替换规则后,结果如何?
解:
对于代入规则:
(1)如果是可满足式,使用代入规则后可能是重言式、可满足式或矛盾式。
如:
可满足式
PQ,将Q分别替换为P,R分别得到重言式PP和可满足式PR,对于可满足式
PQ,将Q替换为P得到矛盾式PP。
(2)如果是矛盾式,使用代入规则后仍然是矛盾式。
设P是矛盾式,则P是重言式。
而
对于重言式使用代入规则后仍为重言式,即P是重言式,故P是矛盾式。
对于替换规则:
由于替换规则是一种对子公式逻辑上等价的替换,故对于重言式、可满足式和矛盾式使用替换规则后其真值不变。
8.求出下列各式的代入实例。
(1)(((P
Q)
P)
P);用P
Q代P,用((P
Q)P)代Q
解:
((((P
Q)
((P
Q)P))
(PQ))(P
Q))
解:
((QP)(PQ))
P21习题
1.求下列各式的主合取范式。
(1)(PQR)
(PQ
R)
(P
Q
R)
((P(Q
R))(P
(Q
R)))
(P
QR)
((PP)
(QR))
(P
Q
R)
解:
(QR)(
PQ
R)
(PQ)
(QR)
(P
R)
(Q
R)
(PQ
R)(P
Q
R)(PQ
R)(PQR)(PQR)
(1,2,4,5,6)
(2)(PQ)(
PQ)(P
Q)
(3)(PQ)(
PQR)
2.求下列公式的主析取范式和主合取范式:
(1)(PQ)
(P
Q)
合取范式:
析取范式:
(1,2,3)
(2)P
(P(Q
(
Q
R)))
合取范式:
析取范式:
(1,2,3)
(3)(P
(QR))
(
P
(QR))
合取范式:
(P
(QR))
(P
(
QR))
(PQ)(PR)(PQ)(PR)
(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)
(1,2,3,4,5,6)析取范式:
(0,7)
(4)(P
QS)(PQR)
析取范式:
合取范式:
(0,1,2,3,4,5,8,10,12,13,14,15)
P25习题
1.试用真值表法证明:
AE不是AB,B(CD),C(AE)和AE的有效结
论。
解:
构造真值表如下:
ABCDE
00000
1
1
1
0
0
00001
1
1
0
1
0
00010
1
1
1
0
0
00011
1
1
0
1
0
00100
1
1
0
0
0
00101
1
1
1
1
0
00110
1
0
0
0
0
00111
1
0
1
1
0
01000
0
0
1
0
0
01001
0
0
0
1
0
01010
0
0
1
0
0
01011
0
0
0
1
0
01100
0
0
0
0
0
01101
0
0
1
1
0
01110
0
1
0
0
0
01111
0
1
1
1
0
10000
0
1
0
1
0
10001
0
1
0
1
1
10010
0
1
0
1
0
10011
0
1
0
1
1
10100
0
1
1
1
0
10101
0
1
1
1
1
10110
0
0
1
1
0
10111
0
0
1
1
1
11000
1
0
0
1
0
11001
1
0
0
1
1
11010
1
0
0
1
0
11011
1
0
0
1
1
11100
1
0
1
1
0
11101
1
0
1
1
1
11110
1
1
1
1
0
11111
1
1
1
1
1
第6,31行前提取值均为1时,结论为0。
故命题得证。
2.H1,H2和H3是前提。
在下列情况下,试确定结论C是否有效(可以使用真值表法证明。
)
1)H1:
PQ
证明:
真值表如下:
PQ
00
1
1
01
1
1
10
0
0
11
1
1
第1,2,4行当前提取值为1时,结论都为1。
故结论C是有效的
2)H1:
PQ
证明:
(4)H1:
P
Q
证明:
{1}
(1)
P
P规则(附加前提)
{2}
(2)
P
Q
P规则
{1,2}
(3)
Q
T规则,
(1),
(2),I10
{4}
(4)
Q
R
P规则
{1,2,4}(5)
R
T规则,(3),(4),I10
{1,2,4}(6)
PR
CP规则,
(1),(5)
3.不构成真值表证明:
A
C不是A
(B
C)、B(AC)、C(AB)和B
的有效结论。
证明:
(1)
B
P
规则
(2)
B
(A
C)
P规则
(3)
A
C
T规则,
(1)
(2)
(4)
A
(B
C)
P规则
(5)
AC
T规则,
(1)(4)
(6)
(AC)
(A
C)
T规则(5)
(7)
(AC)
T规则(3)
(8)
AC
T规则(6)(7)
(9)
(AC)
T规则(8)
因此,(A
C)是题目的有效结论,
A
C不是。
4.使用推理的方法证明:
L
M是P
Q
R和(QR)
(LM)的有效结论。
证明:
{1}
(1)
P
QR
P规则
{1}
(2)
R
T规则,(
1),
I2
{1}
(3)
Q
R
T规则,(
2),
I4
{1}
(4)
Q
R
T规则,(
3),
E27
{1}
(5)
Q
T规则,(
1),
I2
{1}
(6)
R
Q
T规则,(
5),
I4
{1}
(7)
R
Q
T规则,(
6),
E27
{1}
(8)
Q
R
T规则,(
4),
(7),
{9}
(9)
(Q
R)(LM)
P规则
{1,9}
(10)
L
M
T规则,(
8),
(9),
5.不构成真值表证明下列命题公式不能同时全为真。
(1)PQ,
QR,
RS,
P
S,S
证明:
{1}
(1)
S
P规则
{2}
(2)
P
S
P规则
{1,2}
(3)
P
T规则,(
1),
(2),
{4}
(4)
P
Q
P规则
{1,2,4}(
5)
Q
T规则,(3),
(4)
,I10
I10
I11
{6}
(6)
Q
R
P规则
{1,2,4,6}
(7)
R
T规则,(5),(6),I10
{8}
(8)
R
S
P规则
(1,2,4,6,8)
(9)
S
T规则,(7),(8),I9
推出结论与前提矛盾,因此命题公式不能同时为真。
(2)RM
,RS,
M,S
证明:
{1}
(1)
M
P规则
{2}
(2)
RM
P规则
{1,2}
(3)
R
T规则,
(1),
(2),I9
{4}
(4)
RS
P规则
{1,2,4}
(5)
S
T规则,(3),(4),I9
推出的结论与命题公式S矛盾,因此命题公式不能同时为真。
6.
H1,H2和H3是前提,根据推理规则断定,在下列情况下C是否是有效结论。
即P、Q的值任意。
因此C不是有效结论。
7.证明下列结论的有效性。
1)(PQ),QR,R
证明:
(1)
(2)
R
Q
R
(3)
Q
(4)
(P
Q)
(5)
P
Q
(6)
P
(2)
(PQ)
R
,
RS,
证明:
(1)
S
(2)
R
S
(3)
R
(4)
(P
Q)
R
(5)
(P
Q)
(6)
P
Q
由RS得R为真,再由(PQ)
P规则
P规则
T规则,
(1),
(2),I9
P规则
T规则,(4),E11
T规则,(3),(5),I9
SPQ
P规则
P规则
T规则
(1)
(2)
P规则
T规则(3)(4)
T规则(5)
3)(PQ)R,RS,QTP
R得(PQ)真假任意,故无法推出P一定为真的结论
(题目有问题)
8.导出下列结论(如果需要,就是用规则CP)
(1)
PQ,
Q
R,R
S
PS
证明:
(1)
P
P规则(假设前提)
(2)
P
Q
P规则
(3)
Q
T规则
(1)
(2)
(4)
Q
R
P规则
(5)
R
T规则(3)(4)
(6)
R
S
P规则
(7)
S
T规则(5)(6)
(8)
P
S
CP规则
(1)(7)
(2)
PQ
P
(P
Q)
证明:
(1)
P
P规则(假设前提)
(2)
P
Q
P规则
(3)
Q
T规则
(1)
(2)
(4)
P
Q
T规则
(1)(3)
(5)
P
(PQ)
CP规则
(1)
(4)
(3)
(PQ)
R
(P
Q)
R
证明:
(1)
P
Q
P规则(假设前提)
(2)
P
T规则
(1)
(3)
Q
T规则
(1)
(4)
P
Q
T规则
(2)(
3)
(5)
(P
Q)
R
P规则
(6)
R
T规则(4)(
5)
(7)
(P
Q)
R
CP规则
(1)
(6)
9.证明下列各式的有效性(如果需要,
就使用间接证明法)。
(1)
(R
Q),R
S,S
Q,P
QP
证明:
(1)
P
P规则(假设前提)
(2)
P
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 答案 章陈志奎