学会生存作文-有意栽花花不开

2021年1月28日发(作者：哥斯达)

离散数学课后习题答案

(
左孝凌版
)
1-1
，
1-2
解：

a)

是命题，真值为
T
。

b)

不是命题。

c)

是命题，真值要根据具体情况确定。

d)

不是命题。

e)

是命题，真值为
T
。

f)

是命题，真值为
T
。

g)

是命题，真值为
F
。

h)

不是命题。

i)

不是命题。

（
2
）

解
：

原子命题：我爱北京天安门。

复合命题：如果不是练健美操，我就出外旅游拉。

（
3
）

解
：

a)

(┓P ∧R)→Q

b)

Q
→
R
c)

┓
P

d)

P
→┓
Q

（
4
）

解
：

a)
设
Q:
我将去参加舞会。
R:
我有时间。
P:
天下雨。

Q

(R
∧┓
P):
我将去参加舞会当且仅当我有时间和 天不下雨。
b)
设
R:
我在看电视。
Q:
我在吃苹果。
dintin@
1


R
∧
Q:
我在看电视边吃苹果。

c)
设
Q:
一个数是奇数。
R:
一个数不能被
2
除。

（
Q
→
R
）∧
(R
→
Q):
一个数是奇数 ，则它不能被
2
整除并且一个数不能被
2
整除，
则它是奇数。

(5)
解：

a)

设
P
：王强身 体很好。
Q
：王强成绩很好。
P
∧
Q
b)

设
P
：小李看书。
Q
：小李听音乐。
P
∧
Q
c)

设
P
：气候很好。
Q
：气候很热。
P
∨
Q
d)

设
P
：
a
和
b
是偶数。
Q
：
a+b
是偶数。
P
→
Q
e)

设
P
：四边形
ABCD
是平行四边形。
Q
：四边形
ABCD
的对边平行。
P

Q
f)

设
P
：语法错误。
Q
：程序错误。
R
：停机。
（
P
∨
Q
）→
R
(6)
解：

a)

P:
天气炎热。
Q:
正在下雨。
P
∧
Q
b)

P:
天气炎热。
R:
湿度较低。
P
∧
R
c)

R:
天正在下雨。
S:
湿度很高。
R
∨
S
d)

A:
刘英上山。
B:
李进上山。
A
∧
B
e)

M:
老王是革新者。
N:
小李是革新者。
M
∨
N
f)

L:
你看电影。
M:
我看电影。

┓
L
→┓
M
g)

P:
我不看电视。
Q:
我不外出。
R:
我在睡觉。
P
∧
Q
∧
R
h)

P:
控制台打字机作输入设备。
Q:
控制台打字机作输出设备。P∧Q


1-3
（
1
）解：

dintin@
2

a)

不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）

b)

是合式公式

c)

不是合式公式（括弧不配对）

d)

不是合式公式（
R
和
S
之间缺少联结词）

e)

是合式公式。


（
2
）解：





a
）

A
是合式公式，
(A∨B)是合式公式，(A→(A∨B))

是合式公式。
这个过程可以简
记为：

A
；(A∨B)；(A→(A∨B))

同理可记

b
）
A
；┓A ；(┓A∧B) ；((┓A∧B)∧A)

c
）

A
；┓A ；
B
；(┓A→B) ；(B→A) ；((┓A→B)→(B→A))

d
）
A
；
B
；(A→B) ；(B→A) ；((A→B)∨(B→A))

（
3
）解：

a
）((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C))

b
）((B→A)∨(A→B))。

（
4
）解：


a)
是由
c)
式进行代换得到，在
c)
中用
Q
代换
P, (P→P)代换
Q.
d)
是由
a)
式进行代换得到，在
a)
中用

P→(Q→P)代换
Q.
e)
是由
b)
式进行代换得到，用
R
代换
P, S
代换
Q, Q
代换
R, P
代换
S.

（
5
）解：

a) P:
你没有给我写信。
R:
信在途中丢失了。
P Q
∨

b) P:
张三不去。
Q:
李四不去。
R:
他就去。

(P∧Q)→R

dintin@
3

c) P:
我们能划船。
Q:
我们能跑步。

┓(P∧Q)

d) P:
你来了。
Q:
他唱歌。
R:
你伴奏。

P→(Q

R)

（
6
）解：

P:
它占据空间。
Q:
它有质量。
R:
它不断变化。
S:
它是物质。

这个人起初主张：(P∧Q∧R)

S
后来主张：(P∧Q

S)∧(S→R)

这个人开头主张与后来主 张的不同点在于：
后来认为有
P∧Q
必同时有
R
，
开头时没
有这样的主张。

（
7
）解：

a) P:
上午下雨。
Q:
我去看电影。
R:
我在家里读书。
S:
我在家里看报。
(┓P→Q)∧(P→(R∨S))

b) P:
我今天进城。
Q:
天下雨。┓Q→P

c) P:
你走了。
Q:
我留下。Q→P


1-4


（
4
）解：
a)
P Q R

T T T

T T F

T F T

T F F

F T T

F T F

dintin@
Q∧R

T

F

F

F

T

F

P∧(Q∧R)

T

F

F

F

F

F

P∧Q

T

T

F

F

F

F

(P∧Q)∧R

T

F

F

F

F

F

4

F F T

F F F

F

F

F

F

F

F

F

F

所以，P∧(Q∧R)



(P∧Q)∧R

b)

Q∨R

Ｔ

Ｔ

Ｔ

Ｆ

Ｔ

Ｔ

Ｔ

Ｆ


P∨(Q∨R)

Ｔ

Ｔ

Ｔ

Ｔ

Ｔ

Ｔ

Ｔ

Ｆ



P∨Q




Ｔ




Ｔ




Ｔ




Ｔ




Ｔ




Ｔ




Ｆ




Ｆ


(P∨Q)∨R




Ｔ




Ｔ




Ｔ




Ｔ




Ｔ




Ｔ




Ｔ




Ｆ

P Q R

T T T

T T F

T F T

T F F

F T T

F T F

F F T

F F
F

所以，P∨(Q∨R)



(P∨Q)∨R


ｃ）

Ｐ

Ｑ

Ｑ∨
Ｐ∧
（Ｑ∨
Ｐ∧
Ｐ∧
（Ｐ∧Ｑ）
∨
（Ｐ
Ｒ

Ｒ

Ｒ）

Ｑ

Ｒ

∧Ｒ）

dintin@
5

Ｔ

Ｔ

Ｔ

Ｔ

Ｔ

Ｆ

Ｔ

Ｆ

Ｔ

Ｔ

Ｔ

Ｔ

Ｔ

Ｔ

Ｆ

Ｆ

Ｆ

Ｆ

Ｆ

Ｔ

Ｔ

Ｆ

Ｆ

Ｆ

Ｆ

Ｆ

Ｆ

Ｔ

Ｆ

Ｔ

Ｆ

Ｆ

Ｆ

Ｆ

Ｆ

Ｔ

Ｔ

Ｔ

Ｆ

Ｆ

Ｆ

Ｆ

Ｆ

Ｔ

Ｆ

Ｔ

Ｆ

Ｆ

Ｆ

Ｔ

Ｔ

Ｔ

Ｔ

Ｆ

Ｔ

Ｔ

Ｆ

Ｆ

Ｆ

Ｔ

Ｆ

Ｆ

Ｆ

Ｆ

所以，P∧(Q∨R)



(P∧Q)∨(P∧R)


ｄ）

P Q

T T

T F

F T

F F

dintin@
┓P

F

F

T

T

┓Q

F

T

F

T

┓P∨┓Q

F

T

T

T

┓(P∧Q)

F

T

T

T

┓P∧┓Q

F

F

F

T

┓(P∨Q)

F

F

F

T

6

所以，┓(P∧Q)


┓P∨┓Q, ┓(P∨Q)


┓P∧┓Q

（
5
）解：如表，对问好所填的地方，可得 公式
F
1
～
F
6
，可表达为

Q

T

T

F

F

T

T

F

F

R

T

F

T

F

T

F

T

F

F1

T

F

T

F

T

T

T

F

F2

F

F

F

T

F

F

F

T

F3

T

T

F

F

F

F

T

F

F4

T

F

T

T

T

F

T

T

F5

F

F

T


T

T

T

T

T

F6

F

F

F

F

F

F

F

T

P

T

T

T

T

F

F

F

F

F1:(Q→P)→R

F2:(P∧┓Q∧┓R)∨(┓P∧┓Q∧┓R)

F3:(P←→Q)∧(Q∨R)

F4:(┓P∨┓Q∨R)∧(P∨┓Q∨R)

F5:(┓P∨┓Q∨R)∧(┓P∨┓Q∨┓R)

F6:┓(P∨Q∨R)

(6)
Q

1

2

T

F

F

3

4

5

F

F

T

6

T

F

T

7

F

T

T

8

T

T

T

9

F

F

F

10

T

F

F

11

F

T

F

12

T

T

F

13

F

F

T

14

T

F

T

15

F

T

T

16

T

T

T



F

F

T

F

F

F

F

T

T

F

T

F



dintin@
7


T

F

F

F

F

F

F

F

F

T

T

T

T

T

T

T

T

解：由上表可得有关公式为

1.F 2.┓(P∨Q) 3.┓(Q→P) 4.┓P


5.┓(P→Q) 6.┓Q 7.┓(P

Q) 8.┓(P∧Q)


9.P∧Q 10.P

Q 11.Q 12.P→Q


13.P 14.Q→P 15.P∨Q 16.T

(7)
证明：

a)

A
→
(B
→
A)


┐
A
∨
(
┐
B
∨
A)

A
∨
(
┐
A
∨┐
B)

A
∨
(A
→┐
B)

┐
A
→
(A
→┐
B)
b)

┐
(A

B)

┐
((A
∧
B )
∨
(
┐
A
∧┐
B))

┐
((A
∧
B)
∨┐
(A
∨
B))

(A
∨B)∧┐(A∧B)

或

┐
(A

B)

┐
((A
→
B )
∧(
B
→
A))

┐
((
┐
A
∨B)∧(┐
B
∨
A))

┐
((
┐ A∧┐
B)
∨
(
┐A∧
A)
∨
(B
∧┐< br>B)
∨
(B
∧
A))

┐
((
┐ A∧┐
B)
∨
(B
∧
A))

┐
(
┐
(A
∨
B))
∨(A∧B)


(A
∨B)∧┐(A∧B)

c)

┐
(A
→
B)


┐(┐A∨
B)

A
∧┐
B
d)

┐
(A
< br>B)

┐
((A
→
B)
∧(
B
→< br>A))

┐
((
┐
A
∨B)∧(┐
B∨
A))
dintin@
8


(A
∧ ┐
B)
∨
(
┐
A
∧
B)
e)

(((A
∧
B
∧
C)
→
D)
∧
( C
→
(A
∨
B
∨
D)))

(
┐
(A
∧
B
∧
C)
∨
D)
∧
(
┐
C
∨
(A
∨
B
∨
D))

(
┐
(A
∧
B
∧
C)
∨
D)∧
(
┐
(
┐
A
∧┐
B
∧
C)
∨
D)

(
┐
(A
∧
B
∧< br>C)
∧┐
(
┐
A
∧┐
B
∧
C))< br>∨
D

((A
∧
B
∧
C)
∨< br>(
┐
A
∧┐
B
∧
C))
→
D

(((A
∧
B)
∨
(
┐
A
∧ ┐
B))
∧
C)
→
D

((C
∧
(A

B))
→
D)
f)

A
→
(B
∨
C)


┐
A
∨
(B
∨
C)

(
┐
A
∨
B)
∨
C

┐
(A
∧┐
B)
∨
C


(A
∧┐
B)
→
C
g)

(A
→
D)
∧
(B
→
D)

(
┐
A
∨
D)
∧
(
┐
B
∨
D)

(
┐
A
∧┐
B)
∨
D


┐
(A
∨
B)
∨
D

(A
∨
B)
→
D
h)

( (A
∧
B)
→
C)
∧
(B
→
(D
∨
C))

(
┐
(A
∧
B)
∨
C)
∧
(
┐
B
∨
(D
∨
C))

(
┐
(A
∧
B)
∧
(
┐B
∨
D))
∨
C

(
┐
(A
∧
B)
∧┐
(
┐
D
∧
B))
∨
C
< br>┐
((A
∧
B)
∨
(
┐
D
∧
B))
∨
C

((A
∨┐
D)
∧
B)
→
C

(B
∧
(D
→
A))
→
C
dintin@
9

（
8
）解：

a)

((A
→
B)

(
┐
B
→┐
A))
∧
C

((
┐
A
∨
B)

(B
∨┐
A))
∧
C

((
┐
A
∨
B)

(
┐
A
∨
B))
∧
C

T
∧
C

C
b)

A
∨
(
┐
A
∨
(B
∧┐
B))

(A
∨┐
A)
∨
(B
∧┐
B)

T
∨
F

T
c)

(A< br>∧
B
∧
C)
∨
(
┐
A
∧
B
∧
C)

(A
∨┐
A)
∧
(B
∧
C)

T
∧
(B
∧
C)

B
∧
C
（
9
）解：
1
）设< br>C
为
T
，
A
为
T
，
B
为< br>F
，则满足
A
∨
C

B
∨
C
，但
A

B
不成立。
2
）设
C
为< br>F
，
A
为
T
，
B
为
F
，则 满足
A
∧
C

B
∧
C
，但
A
B
不成立。

3
）由题意知┐
A
和┐B
的真值相同，所以
A
和
B
的真值也相同。


习题
1-5
（
1
）

证
明：

a)

(P
∧
(P
→
Q))
→
Q

(P
∧
(
┐
P
∨
Q))
→Q

(P
∧┐
P)
∨
(P
∧
Q)< br>→
Q

(P
∧
Q)
→
Q

┐
(P
∧
Q)
∨
Q

┐
P
∨┐
Q
∨
Q

┐
P
∨
T
dintin@

10


T
b)

┐
P
→
(P
→
Q)


P
∨
(
┐
P
∨
Q)

(P
∨┐
P)
∨
Q

T
∨
Q

T

c)

((P
→
Q)
∧
(Q
→
R))
→
(P< br>→
R)

因为
(P
→
Q)
∧
(Q< br>→
R)

(P
→
R)
所以
(P
→
Q)
∧
(Q
→
R)
为重言式。

d)

((a∧b)∨(b∧c) ∨(c∧a))

(a∨b)∧(b∨c)∧(c∨a)

因为((a∧b)∨(b∧c)∨(c∧a))


((a∨c)∧b)∨(c∧a)


((a∨c)∨(c∧a))∧(b∨(c∧a))


(a∨c)∧(b∨c)∧(b∨a)

所以((a∧b)∨(b∧c) ∨(c∧a))

(
a∨b)∧(b∨c)∧(c∨a)
（
2
）

证
明：

a)(P
→
Q)

P
→
(P
∧
Q)
解法
1
：

设
P
→
Q
为
T
（
1
）若
P
为
T
，则
Q
为
T
，所以
P
∧
Q
为
T
，故
P
→
(P
∧
Q)为
T
（
2
）若
P
为
F
，则
Q
为
F
，所以
P
∧
Q
为
F
，P
→
(P
∧
Q)
为
T
命题得证

解法
2
：

dintin@
为重言式。


11

设
P
→
(P
∧
Q)< br>为
F
，
则
P
为
T
，
(P
∧
Q)
为
F
，
故必有
P
为
T
，Q
为
F
，
所以
P
→
Q
为
F< br>。

解法
3
：

(P
→
Q)
→
(P
→
(P
∧
Q))

┐
(
┐
P
∨
Q)
∨
(
┐
P
∨
(P
∧
Q))

┐
(
┐
P
∨
Q )
∨
((
┐
P
∨
P)
∧
(
┐P
∨
Q))

T
所以
(P
→
Q)

P
→
(P
∧
Q)
b)(P
→
Q)
→
Q

P
∨
Q
设
P
∨
Q
为
F
，则
P
为
F
，且
Q
为
F
，

故
P
→
Q
为
T
，
(P
→
Q)
→
Q
为< br>F
，

所以
(P
→
Q)
→
Q

P
∨
Q
。

c)(Q
→
(P
∧┐
P))
→
(R
→
(R
→
(P
∧┐P)))

R
→
Q
设
R
→
Q
为
F
，则
R
为
T
，且
Q
为
F< br>，又
P
∧┐
P
为
F
所以
Q
→(P
∧┐
P)
为
T
，
R
→
(P
∧┐
P)
为
F
所以
R
→
(R
→
(P
∧┐
P))
为
F
，所以
(Q
→
(P
∧┐
P))
→
(R
→
(R
→
(P
∧┐
P)))
为
F
即
(Q
→
(P
∧┐< br>P))
→
(R
→
(R
→
(P
∧┐
P )))

R
→
Q
成立。

（
3
）

解
：

a)

P
→
Q
表示命题“如果
8
是偶数，那么糖果是甜的”
。
b)

a)
的逆换式
Q
→
P
表示命 题“如果糖果是甜的，那么
8
是偶数”
。

c)

a)
的反换式┐
P
→┐
Q
表示命题“如果
8
不是偶 数，那么糖果不是甜的”
。

d)

a)
的逆反式┐
Q
→┐
P
表示命题“如果糖果不是甜的，那么
8
不是偶数”
。

（
4
）

解
：

a)

如果天下雨，我不去。

dintin@
12

设
P
：天下雨。
Q
：我不去。P→Q

逆换式
Q→P
表示命题
:
如果我不去，则天下雨。

逆反式┐Q→┐P
表示命题
:
如果我去，则天不下雨

b)

仅当你走我将留下。

设
S
：你走了。
R
：我将留下。R→S

逆换式
S→R
表示命题：如果你走了则我将留下。

逆反式┐S→┐R
表示命题：如果你不走，则我不留下。

c)

如果我不能获得更多帮助，我不能完成个任务。

设
E
：我不能获得 更多帮助。
H
：我不能完成这个任务。E→H

逆换式
H→E
表示命题：我不能完成这个任务，则我不能获得更多帮助。
逆反式┐H→┐E
表示命题：我完 成这个任务，则我能获得更多帮助

（
5
）

试
证 明
P

Q
，
Q
逻辑蕴含
P
。

证明：解法
1
：

本题要求证明
(P

Q)
∧
Q

P,

设
(P

Q)
∧
Q
为
T，则
(P

Q)
为
T
，
Q
为
T
，故由

的定义，必有
P
为
T
。
所以< br>(P

Q)
∧
Q

P
解法
2
：

由体题可知，即证
((P

Q )
∧
Q)→P
是永真式。


((P

Q)
∧
Q)→P


(((P
∧
Q)
∨
(┐P
∧
┐Q))
∧
Q)→P



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



(((┐P
∨
┐Q)
∧
(P
∨
Q))
∨
┐Q)
∨
P


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

dintin@


13



((┐Q
∨
┐P)
∧
T)
∨
P

┐Q
∨
┐P
∨
P

┐Q
∨
T


T
（
6
）

解
：

P
：我学习
Q
：我数学不及格
R
：我热衷于玩扑克。
如果我学习，那么我数学不会不及格：

P→┐Q

如果我不热衷于玩扑克，那么我将学习: ┐R→P

但我数学不及格
: Q
因此我热衷于玩扑克。
R
即本题符号化为：(P→┐Q)∧(┐R→P)∧Q

R
证：

证法
1
：((P→┐Q)∧(┐R→P)∧Q)→R



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



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



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



┐Q∨P∨R∨┐P


T

所以，论证有效。

证法
2
：设(P→┐Q)∧(┐R→P)∧Q< br>为
T
，

则因
Q
为
T
，(P→┐Q)

为
T
，可得
P
为
F
，

由(┐R→P)为
T
，得到
R
为
T
。

故本题论证有效。

dintin@


14

（
7
）

解
：

P
：
6
是偶数
Q
：
7
被
2
除尽
R
：
5
是素数

如果
6
是偶数，则
7
被
2
除不尽

P→┐Q

或
5
不是素数，或
7
被
2
除尽

┐R∨Q

5
是素数
R
所以
6
是奇数

┐P

即本题符号化为：
（P→┐Q）∧（┐R∨Q）∧R

┐P

证：

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



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



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



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

(┐P∨Q) ∨(┐R∨┐Q)


T

所以，论证有效，但实际上他不符合实际意义。

证法
2
：(P→┐Q)∧(┐R∨Q)∧R
为
T
，

则有
R
为
T
，且┐R∨Q

为
T
，故
Q
为
T
，

再由
P→┐Q
为
T
，得到┐P
为
T
。

（
8
）

证
明：

a)

P

(
┐
P
→
Q)
设
P
为
T
，则┐
P
为
F
，故┐
P
→
Q
为
T
b)

┐
A
∧
B
∧
C

C
假定┐A
∧
B
∧
C
为
T
，则
C
为< br>T
。

dintin@

15

c)

C

A
∨
B
∨┐
B 因为
A
∨
B
∨┐
B
为永真，所以
C

A
∨
B
∨┐
B
成立。

d)

┐
(A
∧
B)

┐
A
∨┐
B
设┐
(A
∧
B)
为
T
，则
A
∧< br>B
为
F
。

若
A
为
T
，< br>B
为
F
，则┐
A
为
F
，┐
B
为
T
，故┐
A
∨┐
B
为
T
。

若
A
为
F
，
B
为
T
，则┐
A
为
T
，┐
B
为
F
，故┐
A
∨ ┐
B
为
T
。

若
A
为
F
，
B
为
F
，则┐
A
为
T
，┐
B< br>为
T
，故┐
A
∨┐
B
为
T
。

命题得证。

e)

┐
A
→
(B∨
C)
，
D
∨
E
，
(D
∨
E )
→┐
A

B
∨
C
设┐
A
→< br>(B
∨
C)
，
D
∨
E
，
(D
∨
E)
→┐
A
为
T
，

则
D< br>∨
E
为
T
，
(D
∨
E)
→┐
A
为
T
，所以┐
A
为
T
又┐
A
→
(B
∨
C)
为
T
，所以
B
∨
C
为
T
。命题得证。

f)

(A
∧B)
→
C
，┐
D
，┐
C
∨
D

┐
A
∨┐
B
设
(A
∧
B)
→
C
，┐
D
，┐
C
∨
D
为
T
，则┐
D
为
T
，┐
C
∨
D
为
T
，所以
C
为
F
又
(A
∧
B)
→
C
为
T
，所以
A
∧
B
为
F
，所以┐
A
∨┐
B
为
T
。命题得证。

（
9
）解：

a)

如果他有勇气，他将得胜。

P
：他有勇气
Q
：他将得胜

原命题：P→Q 逆反式：┐Q→┐P 表示：如果他失败了，说明他没勇气。
b)

仅当他不累他将得胜。

P
：他不累
Q
：他得胜

原命题：Q→P 逆反式：┐P→┐Q 表示：如果他累，他将失败。


dintin@

16

习题
1-6
(1)
解：

a)

(P
∧
Q)
∧┐
P

(P
∧┐
P)
∧
Q

┐
(T
∨
Q)
b)

(P
→
(Q
∨┐
R))
∧┐
P
∧
Q

(
┐
P
∨(Q
∨┐
R))
∧┐
P
∧
Q

(┐ P∧┓P∧Q)∨(Q∧┓P∧Q)∨(┓R∧┓P∧Q)

(┓P∧Q)∨(┓P∧Q)∨( ┓P∧┓R∧Q)


┓P∧Q


┐
(P
∨┐
Q)
c)

┐
P
∧┐
Q
∧
(
┐
R
→
P)

┐
P
∧┐
Q
∧
(R
∨
P)

(
┐
P
∧┐
Q
∧
R)
∨
(
┐
P
∧┐
Q
∧
P)

(
┐
P
∧┐
Q
∧
R)
∨
F

┐
P
∧┐
Q
∧
R

┐
(P
∨
Q
∨┐
R)
(2)
解：

a)
┐
P

P
↓
P
b)P
∨
Q

┐
(P
↓
Q)

(P
↓
Q)
↓
(P
↓
Q)
c)P
∧
Q

┐
P
↓┐
Q

(P
↓
P)
↓
(Q
↓
Q)
(3)
解：

P
→
(
┐
P
→
Q)

┐
P
∨
(P
∨
Q)

T
dintin@

17


┐
P
∨
P


(┐P↑┐P)↑(P↑P)


P
↑
(P
↑
P)

P
→
(
┐
P
→
Q)

┐
P
∨
(P
∨
Q)

T

┐
P
∨
P

┐
(
┐
P
↓
P)

┐
((P
↓
P)
↓
P)

( (P
↓
P)
↓
P)
↓
((P
↓
P)
↓
P)
(4)
解：

P
↑
Q

┐
(
┐
P
↓┐
Q)

┐((P
↓
P)
↓
(Q
↓
Q))

((P
↓
P)
↓
(Q
↓
Q))
↓
((P< br>↓
P)
↓
(Q
↓
Q))
(5)
证明：

┐
(B
↑
C)

┐
(
┐
B
∨┐
C)


┐
B
↓┐
C
┐
(B
↓
C)

┐
(
┐
B
∧┐
C)

┐
B
↑┐
C

dintin@
18

(6)
解：联结词“↑”和“↓”不满足结合律。举例如下：

a )
给出一组指派：
P
为
T
，
Q
为
F
，
R
为
F
，则
(P
↑
Q)
↑
R
为
T
，
P
↑
(Q
↑
R)
为
F


故
(P
↑
Q)
↑
R P
↑
(Q
↑
R).
b)
给出一组指派：
P
为
T
，
Q
为
F
，
R
为
F
，则
(P
↓
Q)
↓
R
为
T
，
P
↓
(Q
↓
R)
为
F


故
(P
↓
Q)
↓
R P
↓
(Q
↓
R).
(7)
证明：

设变 元
P
，
Q
，用连结词

,
┐作用于
P，
Q
得到：
P
，
Q
，┐
P
，┐
Q
，
P

Q
，
P

P
，
Q

Q
，
Q

P
。

但
P

Q

Q

P
，
P

P

Q

Q
，故实际有：

P
，
Q
，┐
P
，┐
Q
，
P

Q
，< br>P

P
（
T
）

（
A
）

用┐作用于（
A
）类，得到扩大的公式类（包括原公式类）
：
P
，
Q
，┐
P
，┐
Q
，┐（
P

Q
）
，
T
，
F
，
P

Q
（
B
）

用

作用于（
A
）类，得到：

P
Q
，
P

┐
P

F
，
P
┐
Q

┐（
P

Q
）
，< br>P

（
P

Q
）

Q
，< br>P

（
P

P
）

P
，< br>
Q

┐
P

┐（
P

Q
）
，
Q

┐
Q

F
，
Q

（
P

Q
）

P
，
Q

T

Q,
┐
P

┐
Q
P

Q
，┐
P

（
P
< br>Q
）

┐
Q
，┐
P

T

┐
P,
┐
Q

（
P

Q）

┐
P
，┐
Q

T

┐< br>Q,
（
P

Q
）

（
P

Q
）

P

Q.
因此，
（
A
）类使用运算后，仍在（
B
）类中。

对（
B
）类使用┐运算得：

┐
P
，┐
Q
，
P
，
Q
，
P

Q
，
F
，
T
，

┐（
P

Q
）
，

仍在（
B
）类中。

dintin@
19

对（
B
）类使用

运算得：

P

Q
，
P

┐
P

F
，
P

┐
Q

┐（
P

Q
）
，P

┐（
P

Q
）

┐
Q< br>，
P

T

P
，
P

F< br>
┐
P
，
P

（
P

Q< br>）

Q
，

Q

┐
P

┐（
P

Q
）
，
Q

┐
Q

F
，
Q

┐（
P

Q
）

┐
P
，
Q

T

Q,
Q

F

┐
Q
，
Q

（
P

Q
）

P
，

┐
P

┐
Q

P

Q
， ┐
P

┐（
P

Q
）

Q
，┐
P

T

┐
P,
┐
P

F

P,
┐
P

（
P

Q
）

┐
Q
，

┐
Q

┐（
P

Q
）

P
，┐
Q
< br>T

┐
Q,
┐
Q

T

┐
Q,
┐
Q

（
P

Q
）

┐
P
，

┐（
P

Q
）
T

┐（
P

Q
）
，┐（
P

Q
）

F

P

Q
，┐（
P

Q
）

（
P

Q）

F
T

F

F
，
T< br>
（
P

Q
）

P

Q
F

（
P

Q
）


┐（
P

Q
）

（
P

Q
）

（
P

Q
）

P

Q.
故由（
B
）类使用

运算后，结果仍在（
B
）中。

由上证明：用

,
┐两个连结词，反复作用在两 个变元的公式中，结果只能产生（
B
）
类中的公式，总共仅八个不同的公式，故
{

,
┐
}
不是功能完备的，更不能是最小联结
词组。< br>
已证
{

,
┐
}
不是最小联结词组，又因 为
P Q


┐（
P

Q
）
，故任何命题公式中的
∨

∨

∨

联结词，如仅用
{ ,
┐}
表达，则必可用
{

,
┐
}
表达，其逆亦真 。故
{ ,
┐
}
也必不是最小联结词组。

(8 )
证明
{
∨
}
，
{
∧
}
和
{
→
}
不是最小联结词组。

证明：若
{
∨}
，
{
∧
}
和
{
→
}
是最小 联结词，则


┐
P

（
P
∨
P
∨……）


┐
P

（
P
∧
P
∧……）

dintin@
20


┐
P

P< br>→
(P
→
(P
→……
)
对所有命题变元指派
T
，则等价式左边为
F
，右边为
T
，与等价表达式矛盾。

所以
{
∨
}
，
{
∧
}
c

和
{
→
}
不是最小联结词。

→

(9)
证明
{
┐
,
→
}
和
{
┐
, }
是最小联结词组。

证明：因为
{
┐
,
∨
}
为最小联结词组，且
P
∨
Q

┐P
→
Q
所以
{
┐
,
→
}
是 功能完备的联结词组，又
{
┐
},{
→
}
都不是功能完备的 联结词组。

所以
{
┐
,
→
}
是最小联结词组。

c

c

→

→

c

→

又因为
P
→
Q

┐
(P Q)
，
所以
{
┐
, }
是功能完备的联结词组，
又
{
┐
},{ }
不是功
c

→

能完备的联结词组，

所以
{
┐
, }
是最小联结词组。


习题
1-7
(1)
解：

P∧(P→Q)


P∧(┐P∨Q)



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

P∧(P→Q)



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



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

(2)
解：

a)

(┐P∧Q)→R


┐(┐P∧Q)∨R



P∨┐Q∨R

dintin@
21
< br>
(P∧Q)∨(P∧┐Q)∨(┐Q∧R)∨(┐
Q
∧┐
R
)∨(R∧P)∨(R∧┐P)

b)

P→((Q∧R)→
S)

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


┐P∨┐Q∨┐R∨S

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

c)

┐(P∨┐Q)∧(S→T)


(┐P∧Q)∧(┐S∨T)


(┐P∧Q∧┐S)∨(┐P∧Q∧
T)

d)

(P→Q)→R


┐(┐P∨Q)∨R


(P∧┐Q)∨R

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

e)

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


(┐P∨┐Q)∧(P∨Q)


(┐P∧P)∨(┐P∧Q)∨(┐Q∧P)∨(┐Q∧Q)



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

(3)
解：

a)

P∨(┐P∧Q∧R)

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


(P∨Q)∧(P∨R)

b)

┐(P→Q)∨(P∨Q)


┐(┐P∨Q)∨(P∨Q)

dintin@
22


(P∧┐Q)∨(P∨Q)


(P∨P∨Q)∧(┐Q∨P∨Q)

c)

┐(P→Q)


┐(┐P∨Q)



P∧┐Q


(P∨Q)∧(P∨┐Q)∧(┐Q∨┐P)

d)

(P→Q)→R


┐(┐P∨Q)∨R



(P∧┐Q)∨R



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

e)

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


(┐P∨P)∧(┐P∨┐Q)∧(Q∨P )∧(Q∨┐Q)

(┐P∨┐Q)∧(Q∨P)

(4)
解：

a)

(┐P∨┐Q)→(P

┐Q)


┐(┐P∨┐Q) ∨(P

┐Q)



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


1
，
2
，
3

P∨Q
=

0

b)

Q∧(P∨┐Q)


(P
∧
Q
)∨(Q∧┐Q)


P
∧
Q =

3


0
，
1
，
2

dintin@
23



(P∨Q)∧(P∨┐Q) ∧(┐P∨Q)

c)

P∨(┐P→(Q∨(┐Q→R))


P∨(P∨(Q∨(Q∨R))


P∨Q∨R=

0


1
，
2
，
3,4,5,6,7

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

d)

(P→(Q∧R) )∧(┐P→(┐Q∧┐R))



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



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



(P∧Q∧R) ∨(┐P∧┐Q∧┐R) =

0,7

1
，
2
，
3,4,5,6



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

e)

P→(P∧(Q→P)


┐P∨(P∧(┐Q∨P
)

(┐P∨P)∧(┐P∨┐Q∨P)


T∨(T∧┐Q)

T

0,1,2,3
= (┐P∧┐Q) ∨(┐P∧Q) ∨(P∧┐Q) ∨(P∧Q)

f)

(Q→P) ∧(┐P∧Q)



(┐Q∨P) ∧┐P∧Q



(┐Q∨P) ∧┐(P∨┐Q)

F


0,1
，
2
，
3
= (P∨Q) ∧(P∨┐Q) ∧(┐P∨Q) ∧(┐P∨┐Q)

dintin@
24

(5)
证明：

a)


(A→B) ∧(A→C)



(┐A∨B) ∧(┐A∨C)

A→(B∧C)


┐A∨(B∧C)



(┐A∨B) ∧(┐A∨C)

b)


(A→B) →(A∧B)


┐(┐A∨B) ∨(A∧B)



(A∧┐B) ∨(A∧B)


A∧(B∨┐B)


A∧T


A
(┐A→B) ∧(B→A)



(A∨B) ∧(┐B∨A)


A∨(B∧┐B)


A∨F


A
c)
A∧B∧(┐A∨┐B)



((A∧┐A)∨(A∧┐B))∧B


A∧B∧┐B

dintin@
25


F
┐A∧┐B∧(A∨B)



((┐A∧A)∨(┐A∧B))∧┐B


┐A∧┐B∧B


F
d)

A∨(A→(A∧B)


A∨┐A∨(A∧B)


T

┐A∨┐B∨(A∧B)


┐(A∧B) ∨(A∧B)


T

(6)
解：
A

R↑(Q∧┐( R↓P)),则
A*


R↓(Q∨┐(R↑P))

A

R↑(Q∧┐(R↓P))

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


┐R∨┐Q∨┐(R∨P)

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

A*

R↓(Q∨┐(R↑P))

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


┐R∧┐Q∧┐(R∧P)

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

(7)
解：设
A
：
A
去出差。
B
：
B
去出差。
C
：
C
去出差。
D
：
D
去出差。
若
A
去则
C
和
D
中要去一个。

A→(C
V
D)

dintin@
26


B
和
C
不能都去。

┐(B∧C
)

C
去则
D
要留下。

C→┐D

按题意应有：A→(C
V
D)
，┐(B∧C)， C→┐D
必须同时成立。

因为
C
V
D


(C∧┐D) ∨(D∧┐C)

故(A→(C
V
D))∧┐(B∧C) ∧(C→┐D)



(┐A∨(C∧┐D) ∨(D∧┐C)) ∧┐(B∧C) ∧(┐C∨┐D)



(┐A∨(C∧┐D) ∨(D∧┐C)) ∧(┐B∨┐C) ∧(┐C∨┐D)



(┐A∨(
C∧┐D
)
∨(
D∧┐C
)) ∧((┐B∧┐C) ∨(┐B∧┐D) ∨(┐C∧┐D) ∨┐C)



(┐A∧
┐B∧┐C
)
∨(┐A∧
┐B∧┐D
)
∨(┐A∧
┐C∧┐D
)
∨(┐A∧
┐C
)
∨(
┐B∧┐C
∧D) ∨(┐
C
∧D∧┐B∧┐D)

∨(┐C∧D∧
┐C∧┐D
)
∨(┐C∧D∧
┐C
) ∨(┐D∧C∧
┐B∧┐C
)
∨(┐D∧C∧
┐B∧┐D
)
∨(┐D∧C∧
┐C∧┐D
)
∨(┐D∧C∧
┐C
)
在上述的析取范式中，有些（画线的）不符合题意，舍弃，得

(┐A∧┐C) ∨(┐B∧┐C∧D) ∨（┐C∧D）∨(┐D∧C∧┐B)

故分派的方法为：B∧D,或

D∧A,或

C∧A。
< br>(8)
解：设
P
：
A
是第一。
Q
：
B
是第二。
R
：
C
是第二。
S
：
D
是第四。
E
：
A
是第二。


由题意得
(P
V
Q) ∧(R
V
S) ∧(E
V
S)


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



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


因为

(P∧┐Q∧┐R∧S)与(┐P∧Q∧R∧┐S)不合题意，所以原式可化为

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



(P∧┐Q∧R∧┐S∧E∧┐S) ∨(P∧┐Q∧R∧┐S∧┐E∧S)
dintin@
27

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



(P∧┐Q∧R∧┐S∧E) ∨(┐P∧Q∧┐R∧S∧┐E)
因
R
与
E
矛盾，故┐P∧Q∧┐R∧S∧┐E
为真，

即
A
不是第一，
B
是第二，
C
不是第二，
D
为第四，
A
不是第二。

于是得：

A
是第三

B
是第二

C
是第一

D
是第四。


习题
1-8
(1)
证明：

a)
┐
(P
∧┐
Q)，┐
Q
∨
R
，┐
R

┐
P
(1)
┐
RP
(2)
┐
Q
∨
R P
(3)
┐
Q (1)(2)T,I
(4)
┐
(P
∧┐
Q) P
(5)
┐
P
∨
Q (4)T,E
(6)
┐
P (3)(5)T,I
b)J
→
(M
∨
N)
，
(H
∨
G)
→
J
，
H
∨
G

M
∨
N
(1) (H
∨
G)
→
J P
(2) (H
∨
G) P
(3) J (1)(2)T,I
(4) J
→
(M
∨
N) P
(5) M
∨
N (3)(4)T,I
c)B
∧
C
，
( B

C)
→
(H
∨

G
∨
H
(1) B
∧
C P
dintin@
28
(2) B(1)T,I
(3) C (1)T,I
(4) B
∨┐
C(2)T,I
(5) C
∨┐
B (3)T,I
(6) C
→
B(4)T,E
(7) B
→
C (5)T,E
(8) B

C (6)(7)T,E
(9) (B

C)
→
(H
∨
G) P
(10) H
∨
G(8)(9)T,I
d)P
→
Q
，
(┐
Q
∨
R)
∧┐
R
，┐
(
┐
P
∧
(1) (
┐
Q
∨
R)
∧┐
R
(2)
┐
Q
∨
R (1)T,I
(3)
┐
R (1)T,I
(4)
┐
Q (2)(3)T,I
(5) P
→
Q P
(6)
┐
P (4)(5)T,I
(7)
┐
(
┐
P
∧┐
S) P
(8) P
∨┐
S (7)T,E
(9)
┐
S (6)(8)T,I
(2)
证明：

a)
┐
A
∨
B
，
C
→┐
B

A
→┐
C
(1)
┐
(A
→┐
C) P
(2) A (1)T,I
dintin@


┐
S
29

(3) C (1)T,I
(4)
┐
A
∨
B P
(5) B (2)(4)T,I
(6) C
→┐
B P
(7)
┐
B (3)(6)T,I
(8) B
∧┐
B
矛盾。
(5),(7)
b)A
→
(B
→
C)，
(C
∧
D)
→
E
，┐
F
→
(D
∧┐
(1)
┐
(A
→
(B
→
F)) P
(2) A (1)T,I
(3)
┐
(B
→
F) (1)T,I
(4) B (3)T,I
(5)
┐
F (3)T,
(6) A
→
(B
→
C) P
(7) B
→
C (2)(6)T,I
(8) C (4)(7)T,I
(9)
┐
F
→
(D
∧┐
E) P
(10) D
∧┐
E (5)(9)T,I
(11) D (10)T,I
(12) C
∧
D (8)(11)T,I
(13) (C
∧
D)
→
E P
(14) E (12)(13)T,I
(15)
┐
E (10)T,I
(16) E
∧┐
E
矛盾。
(14),(15)
dintin@

A
→
(B
→
F)
30

c )A
∨
B
→
C
∧
D
，
D
∨
E
→
F

A
→
F
(1)
┐
(A
→
F) P
(2) A (1)T,I
(3)
┐
F (1)T,I
(4) A
∨
B (2)T,I
(5) (A
∨
B)
→
C
∧
D P
(6) C
∧
D (4)(5)T,I
(7) C (6)T,I
(8) D (6)T,I
(9) D
∨
E (8)T,I
(10) D
∨
E
→
F P
(11) F(9)(10)T,I
(12) F
∧┐
F
矛盾。
(3),(11)
d)A
→
(B
∧
C)
，┐
B
∨
D
，
(E
→┐< br>F)
→┐
D
，
(1)
┐
(B
→
E) P
(2) B (1)T,I
(3)
┐
E (1)T,I
(4)
┐
B
∨
D P
(5) D (2)(4)T,I
(6) (E
→┐
F)
→┐
D P
(7)
┐
(E
→┐
F) (5)(6)T,I
(8) E (7)T,I
(9) E
∧┐
E
矛盾

dintin@
B
→
(A
∧┐

B
→
E
31

学会生存作文-有意栽花花不开

学会生存作文-有意栽花花不开

学会生存作文-有意栽花花不开

学会生存作文-有意栽花花不开

学会生存作文-有意栽花花不开

学会生存作文-有意栽花花不开

学会生存作文-有意栽花花不开

学会生存作文-有意栽花花不开