离散数学第四版课后标准答案
巡山小妖精
789次浏览
2021年01月28日 19:44
最佳经验
本文由作者推荐
高考寄语或鼓励的话-光阴荏苒的意思
离散数学第四版
课后答案
第
1
章
习题解答
1
．
1
除（
3
）
，
（
4
）
，
（
5
）
，
（
11
）外全是命题，其中，
（
1
）
，
（
2
）
，
（
8
）
，
（
9
）
，
（
10）
，
（
14
）
，
（
15
）是简单命题 ，
（
6
）
，
（
7
）
，
（
12
）
，
（
13
）是复合命题。
分析
首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。
本题中，
（
3
）为疑问句，
（5
）为感叹句，
（
11
）为祈使句，它们都不是陈述句，
所以它们都不是命题。
其次，
4
）这个句子是陈述句，但它表示的
判断结果是不确定。又因为（
1
）
，
（
2
）
，
（
8
）
，
（
9
）
，
（
10
）
，
（
14
）
，
（
15
）都是简单的陈述句，因而作为命题，它 们
都是简单命题。
（
6
）和（
7
）各为由联结词“当且仅当”联结起来的复合命题，
（
12
）是由联结词“或”联结的复合命 题，而（
13
）是由联结词“且”联结起来
的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许
多表述法，例如，
“虽然……，但是……”
、
“不仅……，而且……”
、
“一面……，
一面……”
、
“……和……”
、
“ ……与……”等。但要注意，有时“和”或“与”
联结的是主语，构成简单命题。例如，
（
14
）
、
（
15
）中的“与”与“和”是联结
的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或
“与”出现的命题时，要根据命题所陈述的含义加以区分。
1
．
2
（
1
）
p:
2
是无理数，
p
为真命题。
（
2
）
p:5
能被
2整除，
p
为假命题。
< br>（
6
）
p
→
q
。其中，
p:2
是素 数，
q
：三角形有三条边。由于
p
与
q
都是真
命题，因而
p
→
q
为假命题。
（
7
）
p
→
q
， 其中，
p
：雪是黑色的，
q
：太阳从东方升起。由于
p
为假 命
题，
q
为真命题，因而
p
→
q
为假命题。
（
8
）
p:2000
年
10
月
1
日天气晴好，今日（
1999
年
2
月
13
日）我们还不
知道
p
的真假，但
p
的真值是确定的（客观存 在的）
，只是现在不知道而已。
（
9
）
p
：太阳系外的星球上的生物。它的真值情况而定，是确定的。< br>
1
（
10
）
p
：小李在宿舍里
. p
的真值则具体情况而定，是确定的。
（
12
）
p
∨
q
，其中，
p:4
是偶数，
q:4
是奇数。由于
q
是假命题，所以，
q
为假命题，
p
∨
q
为真命题。
（
13
）
p
∨
q
，其中，
p:4
是偶数，
q:4
是奇数，由于
q
是假命题， 所以，
p
∨
q
为假命题。
（
14
）
p
：李明与王华是同学，真值由具体情况而定（是确定的）
。
（
15
）
p
：蓝色和黄色可以调配成绿色。这是真命题。
分析
命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不
能马上知道，但它们的真值不会变化，是客观存在的。
1
．
3
令
p:2+2=4,q:3+3=6,
则以下命题分别符号化为
（
1
）
p
→
q
（
2
）
p
→
¬
q
（
3
）
¬
p
→
q
（
4
）
¬
p
→
¬
q
（
5
）
p↔q
（
6
）
p↔¬q
（
7
）
¬
p
→
q
（
8
）
¬
p↔¬q
以上命题中，
（
1
）
，
（
3
）
，
（
4
）
，
（
5
）
，
（
8
）为真命题，其余均为假命题。
分析
本题要求读者记住p
→
q
及
p↔q
的真值情况。
p
→
q
为假当且仅当
p
为 真
,q
为假
,
而
p↔q
为真当且仅当
p
与
q
真值相同
.
由于
p
与
q
都是真命题，< br>
在
4
个蕴含式中，只 有（
2
）
p
→
r
，其中，
p
同（
1
）
，
r
：明天为
3
号。
在这里，当
p
为真时，
r
一定为假 ，
p
→
r
为假，当
p
为假时，无论
r
为真
还是为假，
p
→
r
为真。
2
1
．
5
（
1
）
p
∧
q
，其中，
p
：2
是偶数，
q
：
2
是素数。此命题为真命题。
（
2
）
p
∧
q
，其中，
p
：小王聪明，
q
：小王用功
（
3
）
p
∧
q
，其中，
p
：天气冷，
q
：老王来了
（
4
）
p
∧
q
，其中，
p
：他吃饭，
q
：他看电视
（
5
）
p
∧
q
， 其中，
p
：天下大雨，
q
：他乘公共汽车上班
（
6
）
p
→
q
， 其中，
p
，
q
的含义同（
5
）
（
7
）
p
→
q
，其中，
p
，
q
的含义同（
5
）
（
8
）
¬
p ↔¬q
，其中，
p
：经一事，
q
：长一智
分析
1
°在前4
个复合命题中，都使用了合取联结词，都符号化为合取式，
这正说明合取联结词在使用时是很灵活的。在符号化时，应该注意，不要将联结
词部分放入简单命题中。例如，在（
2
） 中，不能这样写简单命题：
p
：小王不但
聪明，
q
：小王而且用功。在（
4
）中不能这样写：p
：他一边吃饭，
q
：他一边
看电视。
2
°
后
4
个复合命题中，都使用了蕴含联结词，符号化为蕴含式，在这里，
关键问题是要分清蕴含式的前件和后件。
p
→
q
所表达的基本逻辑关系为，
p
是
q
的充公条件，或者说
q
是
p
的必要
条件，这种逻辑关系在叙述上也是很灵活的。例如，
“因为< br>p
，所以
q
”
，
“只要
p
，
就
q
”
“
p
仅当
q
”
“只有
q
才
p
”
“除非
q
，否则
¬
p
”
“没有
q
，就没有
p
”等都表
达了
q
是
p
的必要条件，因而都符号化为
p
→
q
或¬
p↔¬q
的蕴含式。
在（
5
）中，
q
是
p
的必要条件，因而符号化为< br>p
→
q
，而在（
6
）
（
7
）中，< br>
p
成了
q
的 必要条件，因而符号化为
q
→
p
。
在（
8
）中，虽然没有出现联结词，但因两个命题的因果关系可知，应该符
号化为蕴含式。
1
．
6
（
1
）
，
（
2
）的真值为
0
，
（
3
）
，
（
4
）的真值为
1
。
分析
1
°
（
1
）中公式含
3
个命题变项，因而它应该有
23=8
个赋值：
000
，
3
001
，…，
111
题中指派
p, q
为
0, r
为
1
，于是就是考查
001
是该公式
p
∧
(q
∧
r)
的成真赋值，
还是成假赋值，易知
001
是它的 成假赋值。
2
°
在公式
（
2
）
，
（
3
）
，
（
4
）
中均含
4
个命题就项，
因而共有
24=1 6
个赋值：
0000
，
0001
，
…，
1111< br>。现在考查
0011
是它的成假赋值。
1.7
（
1
）
，（
2
）
，
（
4
）
，
（
9）均为重言式，
（
3
）
，
（
7
）为矛盾式，< br>（
5
）
，
（
6
）
，
（
8< br>）
，
（
10
）
为非重言式的可满足式。
一般说来，可用真值表法、等值演算法、主析取范式（主合 取范式）法等判断公式的类
型。
（
1
）对（
1
）采用两种方法判断它是重言式。
真值表法
表
1.2
给出了（
1
）中公式的真值表，由于 真值表的最后一列全为
1
，所以，
（
1
）为重言
式。
p
∨
q
∨
r
p
→
(p
∨
q
∨
r)
p
q
r
0
0
0
0
1
0
0
1
1
1
0
1
0
1
1
0
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
1
1
等值演算法
p
→
(p
∨
q
∨
r)
⇔
¬
p
∨
(p
∨
p
∨
r)
（蕴含等值式）
⇔
(¬
p
∨
p)
∨
p
∨
r
（结合律）
⇔
1
∨
q
∨
r
（排中律）
⇔
1
（零律）
4
由最后一步可知，
（
1
）为重言式。
（
2
）用等值演算法判（
2
）为重言式。
(p
→
¬
p)
→
¬
p
⇔
(¬
p
∨
¬
)
→
¬
p
（蕴含等值式）
⇔
¬
p
∨
¬
p
（等幂律）
⇔
p
∨
¬
p
（蕴含等值式）
⇔
1
（排中律）
（
3
）用等值演算法判（
3
）为矛盾式
¬
(p
→
q)
∧
q
⇔
¬
(p¬
∨
q)
∧
q
（蕴含等值式）
⇔
p
∨
¬
q
∧
q
（德·摩根律）
⇔
p
∨
(¬
q
∧
q)
（结合律）
⇔
p
∧
0
（矛盾律）
⇔
0
（零律）
由最后一步可知，
（
3
）为矛盾式。
（
5
）用两种方法判（
5
）为非重言式的可满足式。
真值表法
p
q
¬
p
¬
p
→
q
q
→
¬
p
(¬
p
→
q)
→
(q
→
¬
p)0
1
0
1
1
1
1
1
1
0
0
1
1
1
1
1
0
1
0
0
0
1
0
1
由表
1.3
可知（
5
）为非重言式的可满足式。
主析取范式法
(¬
p
→
q)
→
(q
→
¬
p)
⇔
(p
∨
q)
→
(¬
q∨
¬
p)
5
⇔
¬
(p
∨
q)
∨
(¬
q
∨
¬
p)
⇔
(¬
p
∨
¬
q)
∨
¬
q
∨
¬
p
⇔
¬
p
∨
¬
q
⇔
(¬
p
∧
1)
∨
(1
∧¬
q)
⇔
(¬
p
∧
(¬
q
∨
q)
∨
((¬
p
∨
p)
∧
¬
q)
⇔
(¬
p
∧
¬
q)
∨
(¬
p
∨
q)
∨
(¬
p
∧
¬
q)
∨
(p
∨
¬
q)
⇔
(¬
p
∧
¬
q)
∨
(¬
p
∨
q )
∨
(¬
p
∧
¬
q)
⇔
m0
∨
m1
∨
m2.
在（
3
）的主析取范式中不含全部（4
个）极小项，所以（
3
）为非重言式的可满足式，
请读者在以上演算每 一步的后面，填上所用基本的等值式。
其余各式的类型，请读者自己验证。
分析
1
真值表法判断公式的类别是万能。公式
A为重言式当且仅当
A
的
o
真值表的最后一旬全为
1
；
A
为矛盾式当且仅当
A
的真值表的最后一列全为
0
；
A
为非重言
式的可满足式当且仅当
A
的真值表最后一列至少有一 个
1
，又至少有一个
0
。真值表法不易
出错，但当命题变项较多时， 真值表的行数较多。
2o
用等值演算法判断重言式与矛盾式比较方例，
A
为重言式当且仅当
A
与
1
等值；
A
为矛盾式当且仅当
A
与
0
等值，当
A
为非重言式的可满足式时，经过等值演算可将
A
化
简，然后用观察法找到一个成真赋值，再找到一个成假赋值，就可判断
A
为非重言式的可满足式了。例如，对（
6
）用等值演算判断它的类型。
(p
∧
¬
p)↔q
⇔
0↔q
（矛盾律）
⇔
(p
→
q)
∧
(q
→
0)
（等价等值式）
⇔
(¬
0
∨
q)
∧
(¬
q∨
0)
（蕴含等值式）
⇔
(1
∨
q)
∧
¬
q
（同一律）
⇔
1
∧
¬
q
（零律）
6
⇔
¬
q
（同一律）
到最后一步已将公式化得很简单。由此可知，
无论
p
取
0
或
1
值，
只要
q
取
0
值，
原公< br>式取值为
1
，即
00
或
10
都为原公式的成真赋值， 而
01
，
11
为成假赋值，于是公式为非重
言式的可满足式。
用主析取范式判断公式的类型也是万能的。
A
为重言式当且仅当
A
的主析取范式含
2n
（
n< br>为
A
中所含命题变项的个数）个极小项；
A
为矛盾式当且仅当
A
的主析取范式中不含
任何极小项，
记它的主析取范式为
0
；
A
为非重言式的可满足式当且仅当
A
的主析取范式中
含极小项，但不是完全 的。
当命题变项较多时，用主析取范式法判公式的类型，运算量是很大的。
用主合取范式判断公式的类型也是万能的。
A
为重言 式当且仅当
A
的主合取范式中不
含任何极大项，此时记
A
的主合取范 式为
1
；
A
为矛盾式当且仅当
A
的主合取范式含
2 n
个
极大项（
n
为
A
中含的命题变项的个数）
；< br>A
为非重言式的可满足式当且仅当
A
的主析取范
式中含含极大项，但不 是全部的。
1.8
（
1
）从左边开始演算
(p
∧
q)
∨
(p
∧
¬
q)
⇔
p
∧
(q
∨
¬
q)
（分配律）
⇔
p
∧
1
（排中律）
⇔
p.
（同一律）
（
2
）从右边开始演算
p
→
(q
∧
r)
⇔
¬
p
∨
(q
∧
r)
（蕴含等值式）
⇔
(¬
p
∨
q)
∧
(¬
p
∨
r)
（分配律）
⇔
(p
→
q)
∧
(p
→
r).
（蕴含等值式）
（
3
）从左边开始演算
¬(p↔q)
7
⇔
((p
→
q)
∧
(q
→
p))
⇔
¬
((¬
p
∨
q)
∨
(¬< br>p
∨
q))
⇔
¬
((¬
p
∧< br>q)
∨
(¬
p
∧
)
∨
(q
∧
¬
q)
∨
(p
∧
q))
⇔
¬
((¬p
∧
¬
q)
∨
(p
∧
q))
⇔
(p
∨
q)
∧
¬
(p
∧
q).
请读者填上每步所用的基本等值式。本题也可以从右边开始演算
(p
∨
q)
∧
¬
(p
∧
q)
⇔
¬
¬
((p
∨
q)
∧
¬
(p< br>∧
q)
⇔
¬
(¬
(p
∨
q)< br>∨
¬
¬
(p
∧
q))
⇔
¬((¬
p
∨
¬
q)
∨
(p
∧
q))
⇔
¬
((¬
p
∧
q)
∧
(¬< br>p
∨
q)
∧
(¬
q
∨
p)
∧
(¬
q
∨
q))
⇔
¬
(1
∧
p
∨
q)
∧
(¬
q
∨
p)
∧
1
⇔
¬
((p
→
q)
∧
(q
→
p) )
⇔
¬(p↔q).
读者填上每步所用的基本的等值式。
1.9
（
1
）
¬
((p
∧
q)
→
p)
⇔
¬
(¬
(p
∧
q)
∨
p
（蕴含等值式）
⇔
¬
(¬
(p∧
q)
∨
p)
（德·摩根律）
⇔
p
∧
q
∧
¬
p
（结合律、交换律）
⇔
(p
∧
¬
p)
∧
q
（矛盾式）
⇔
0.
（零律）
8
由最后一步可知该公式为矛盾式。
< br>（
2
）
((p
→
q)
∧
(q
→p))
→
(p↔q)
⇔
¬
(¬
(p
∧
q)
∨
p)
（蕴含等值式）
由于较高层次等价号两边的公式相同，因而此公式无成假赋值，所以，它为重言式。
（
3
）
(¬
p
→
q)
→
(q
→
¬
p)
⇔
(p
∨
q)
→
(¬
q∨
¬
p)
（蕴含等值式）
⇔
¬
(p
∨
q)
∨
(¬
q
∨
¬
p)
（蕴含等值式）
⇔
(¬
p
∧
q)
∨
¬
q
∨
¬p
（德·摩根律）
⇔
¬
q
∨
¬
p
（吸收律）
⇔
¬
p
∨
¬
q.
（交换律）
< br>由最后一步容易观察到，
11
为该公式成假赋值，因而它不是重言式，又
00< br>，
01
，
10
为
成真赋值，因而它不是矛盾式，它是非重言式 的可满足式。
1.10
题中给出的
F
，
G
，
H
，
R
都是
2
元真值函数。
给出的
5
个联结词集都是全功能集，
可以用 观察法或等值演算法寻找与真值函数等值的公式。
首先寻找在各联结词集中与
F
等值的公式。
（
1
）设
A=¬
(p
→< br>q)
，易知
A
是
{¬
,
→
}
中公式 且与
F
等值，即
F
⇔
A.
（
2
）设
B=p
∧
¬
q，易知
B
是
{¬
,
∧
}
中公式且与
F
等值，即
F
⇔
B.
（
3
）设
C=¬
(¬
p
∨
q)
， 易知
C
是
{¬
,
∧
}
中公式，且
F
⇔
C.
（
4
）设
D=(p
↑
(q
↑
q))
↑
(p
↑
(q
↑
q))
，易知
D
为
{
↑
}
中公式，且
F
⇔
D.
（
5
）设
E=(p
↓
p)
↓
q
，易知
E
为
{
↓
}
中公式，且
F
⇔
E.
分析
1°
只要找到一个联结词集中与
F
等值的公式，
经过等值演算就可以找出其他联
结词集中与
F
等值的公式。例如，已知
A= ¬
(p
→
q)
是
{¬
,
→
}
公式 ，且
F
⇔
A
。进行以下演算，
就可以找到
F
等值的 其他联结词集中的公式。对
A
进行等值演算，消去联结词→，用
¬
，
∧取代，得
9
A=¬
(p
→
q)
⇔
¬
(¬
p
∨
q)
⇔
p
∧
¬
q
记为
B.
则
B
为
{¬
,
∧
}
中公式，且
F
⇔
B
。再对
A
进行等值演算，消去 →，用
¬
，∧取代，得
A=¬
(p
→
q)
⇔
¬
(¬
p
∨
q)
记为
C.
则
C
为
{¬
,
∧
}
中公式，且
F
⇔
C
。再对
B
进行演算 ，消去
¬
，→，用↑取代，在演算中，
注意，对于任意的公式
A
，有
¬
A
⇔
¬
(A
∧
A)
⇔
A
↑
A.
B=p
∧
¬
q
⇔
p
∧
(q
↑
q)
⇔
¬
¬
(p
∧
(q
↑
q))
⇔
¬
(p
↑
(q
↑
q))
⇔
(p
↑
(q
↑
q))< br>↑
(p
↑
(q
↑
q)
记为
D.
则
D
为
{
↑
}
中公式，且
F
⇔
D.
再对
C
进行演算，消去
¬
,
∨
,
用↓取代，在演算中注意，
对于任意的公式
A
¬
A
⇔
¬
( A
∨
A)
⇔
A
↓
A.
C=¬
(¬
p
∨
q)
⇔
¬
p
↓
q
⇔
(p
↓
p)
↓
q
记为
E.
则
E
为
{
↓
}
中公式，且
F
⇔
E.
2
°
开始找一个与某真值函数等值的公式的方法，除观察法外，就是根据
10
该真值函数的真值表，求它的主析取范式， 而后进行等值演算即可。例如，由
G
的真值表
可知
G
的主析取范式为
m1
∨
m3
，于是
G
⇔
m1
∨
m3
⇔
(¬
p
∧
q)
∨
(p
∧
q)
⇔
(¬
p
∨
p)
∧
q
⇔
q.
由于公式
q
不带联结词，所以，它应该为任何联结词集中的合式公式。
3
°
在各联结词集中找到的与某真值函数等值的公式并不唯一。例如，取
A=¬
q
→
q.
({¬
,
→
}
中公式
)
B=q
∧
q.
({¬
,
∧
}
中公式
)
C=q
∨
q.
({¬
,
∨
}
中公式
)
D=(q
↑
q)
↑
(q
↑
q).
({
↑
}
中公式
)
E=(q
↓
q)
↓
(q
↓
q).
({
↓
}
中公式
)
则
G
⇔
A
⇔
B
⇔
C
⇔
D
⇔
E,
对于同一个真值函数
G
，找 到与它等值的形式各异的公式。
对于
H
和
R
，请读者自己去完成。
1.11
（
1
）对
C
是否为矛盾式进行讨论。
当
C
不是矛盾式时，
A
∨
C
⇔
B
∨
C
，则一定有
A
⇔
B
， 这是因为，此时，
A
∨
C
⇔
A,B
∨
C
⇔
B
，所以，有
A
⇔
A
∨
C
⇔
B
∨
⇔
B
必有
A
⇔
B
而当
C
不是矛盾式时，
A
∨
C
⇔
B
∨
C
，不一定有
A
⇔
B
，举反例如下：
设
A,B,C
均为含命题变项
p,q
的公式，
A
，
B
，
C
及
A
∨
C,B
∨
C
的真 值表如表
1.4
所示，
从表
1.4
可看出，
A
∨< br>C
⇔
B
∨
C
，但
A
⇔
B
。
表
1.4
11
p
q
A
B
C
A
VC
BVC
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
1
1
1
1
1
1
0
1
1
1
1
(2)
对
C
是否为重言式进行讨论
:
若
C
为重言式
,
则
A
∧
C⇔
A,C
⇔
B,
于是
A
⇔
A
∧
C
⇔
B
∧
C
⇔
B.
因而有
A
⇔
B
当
C
不是重言式时
,
请读者举反例说明
, A
∧
C
⇔
B
∧
C
时
,
不一定有
A
⇔
B.
(3)
若
¬
A
⇔
¬
B,
则
A< br>⇔
B.
证明如下
:
A
⇔
¬
¬
A
(
双重否定律
)
⇔
¬
¬
B
(¬
A
⇔
¬
B)
⇔
B
(
双重否定律
)
所以
A
⇔
B
1.12 (1)
设
(1)
中公式为
A.
A
⇔
(p
∨
(q
∧
r))
→
(p
∧
q
∧
r)
A
⇔
¬
(p
∨
(q
∧
r))
∨
(p
∧
q
∧
r)
A
⇔
¬
p
∧
( ¬
q
∧
¬
r)
∨
(p
∧
q
∧r)
A
⇔
(¬
p
∧
¬
q)
∨
(¬
q
∧
¬
r)< br>∨
(p
∧
q
∧
r)
A
⇔
(¬
p
∧
¬
q
∧
(¬
r
∧
r))
∨
(¬
p
∧
q
∧
r)
∧
¬
r)
∨
(p
∧
q∧
r)
∨
(¬
p
∧
q
∧
¬
r)
∨
(p
∧
q∧
r)
A
⇔
m0
∨
m1
∨
m7
12
于是
,
公式
A
的主析取范式为
m0
∨
m1
∨
m2
∨m7
易知
,A
的主合取范式为
M3
∨
M4
∨
M5
∨
M6A
的成真赋值为
000, 001, 010, 111A
的成假赋值为
011,100,101,110(2)
设
(2)
中公式为
B
B
⇔
(¬
p
→
q)
→
(¬q
∧
p)
⇔
(¬
¬
p
∨
q)
→
(¬
q
∧
p)
⇔
(p
∨
q)
→
(¬
q
∧
p)
⇔
¬
(p
∨
q)
∨
(¬
q∧
p)
⇔
(¬
p
∨
¬
q)
∨
¬
q
∧
p
⇔
¬
q
∧
p
(
吸收律
)
⇔
((¬
p
∨
q )
∧
¬
)
∨
p
∧
(¬
q
∧
p)
⇔
(¬
p
∨
¬
q)
∨
p
∧
(p
∧
¬
q)
∨
(p
∧
q)
⇔
m0
∨
m2
∨
m3
所以
, B
的主析取范式为
m0
∨
m2
∨
m3.B
的主合取 范式为
M1
B
的成真赋值为
00,10,11.
B
的成假赋值为
01.
(3)
设
(3)
中公式为
C.
C
⇔
¬
(p
→
q)
∧
q
∧
r
⇔
(p
∧
¬
q)
∧
q
∧
r]
13
⇔
p
∧
(¬
q
∧
q)
∧
r
⇔
p
∧
0
∧
r
⇔
0.
所以
,C
的主析取范式为
0.
C
的主合取范式为
M0
∧
M1
∧
M2
∧
M3
C
的成假赋值为
00,01,10,11
C
无成真赋值
,C
为矛盾式
.
分析
1°
设公式
A
中含
n(n
≥
1)
个命题变项
,
且
A
的主析取范式中含
l(0
≤
l
≤
2n)
个极
小项
,
则
A
的主合邓范式中含
2n−l
个极 大项
,
而且极大项的角标分别为
0
到
2n−1
这
2 n
个十
进制数中未在
A
的主析取范式的极小项角标中出现过的十进制数
.
在
(1)
中
, n=3,A
的主析取范式中含
4
个极小项
,
所以
,A
的主合取范式中必含
23−4=4
个极
大项
,
它们的角标为
0
到
7
中未在主析取范式的极小项角标中出现过的
3,4,5,6. 这样
,
只要知
道
A
的主析取范式
,
它的主合邓 范式自然也就知道了
,
在
(2),(3)
中情况类似
.
2
°
A
的主析取范式 中极小项角标的二进制表示即为
A
的成真赋值
.
在
(1)
中
,
由于主析取
范式中的极小项角标分别为
0,1,2,7,
它们的二进制表示分别为
000,001,010,111,
所以
,A
的成
真赋值为以上各值
.
类似地
,A
的主合取范式中所含 极大项角标的二进制表示
,
即为
A
的成假
赋值
.
1.13 (1)
首先求
p
→
(q
→
r)
的主析取范式
.
p
→
(q
→
r)
⇔
¬
p
∨
(¬
q
∨
r)
⇔
¬
p
∨
¬
q
∨
r).
由于演算过程较长
,
可以分别先求出由< br>¬
p,¬
q,r
派生的极小项
.
注意
,
本公 式中含
3
个命题
变项
,
所以
,
极小项长度为
3.
14
¬
p
⇔
¬
p
∧
( ¬
q
∨
q)
∧
(¬
r
∨
r)
⇔
(¬
p
∧
¬
q
∧
r)
∨
(¬
p
∧
¬
q
∧r)
∨
(¬
p
∧
q
∧
¬
r)
∨
(¬
p
∧
¬q
∧
r)
⇔
m0
∨
m1
∨
m2
∨
m3
¬
p
⇔
(¬
p
∨
p)
∧
¬
q
∧
(¬
r
∨
r)
⇔
(¬
p
∧
¬
q
∧
¬
r)
∨
(¬
p
∧
¬q
∧
r)
∨
( ¬
p
∧
¬
q
∧
¬
r)
∨
(p∧
¬
q
∧
r)
⇔
m0
∨
m1
∨
m4
∨
m5
r
⇔
(¬
p
∨
p)
∧
(¬
q
∨
q)
∧
r
⇔
(¬
p
∧
¬
q
∧
r)
∨
(¬
p
∧
¬
q
∧
r)
⇔
(p
∧
¬
q
∧
r)
∨
(p
∧
q
∧
r)
⇔
m1
∨
m31
∨
m5
∨
m7
p
→
(q
→
r)
⇔
m0
∨
m1
∨
m2
∨
m3
∨
m4
∨
m5
∨
m7
类似地
,
可求出
q
→
(p
→
r)
主的析取范式也为上式
,
由于公式的主析取范式的唯一性
,
可知
,
(p
→
(q
→
r))
⇔
(q
→
(p
→
r)).
(2)
①
p
↑
q
⇔
¬
(p
∧
q)
⇔
¬
p
∨
¬
q
⇔
(¬
p
∧
(¬
q
∨
q))
∨
((¬
p
∨
p)
∧
¬
q)
⇔
(¬
p
∧
¬
q)
∨
(¬
p
∧
q))
∨
((¬
p
∨
¬
p)
∨
(p
∧
¬
q)
⇔
(¬
p
∧
¬
q)
∨
(¬
p
∧
q)
∨
(p
∨
¬
p)
15
⇔
m0
∨
m1
∨
m2.
②
p
↓
q
⇔
¬
(p
∧
q)
⇔
¬
p
∨
¬
q
⇔
m0.
由于< br>p
↑
q
与
p
↓
q
的主析取范式不同
.
因而它们不等值
,
即
p
↑
q
⇔
p
↓
q.
1.14
设
p:A
输入
;
设
q:B
输入
;
设
r:C
输入
;
由题的条件
,
容易写出
FA,FB,FC
的真值表
,
见表
1.5
所示
.
由真值表分别写出它们的主析
范邓范 式
,
而后
,
将它们都化成与之等值的
{
↓
}
中的公式即可
.
表
1.5
p
q
r
F
F
F
A
B
C
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
1
0
1
0
1
0
0
1
0
0
1
0
1
1
0
0
1
1
0
1
0
0
1
1
1
1
0
0
FA
⇔
(p
∧
¬
q
∧
¬
r)
∨
(p
∧
¬< br>q
∧
r))
∨
(p
∧
q
∧
¬
r)
∨
(p
∧
q
∧
r)
⇔
(p
∧
¬
q)
∧
(¬
r
∨
r)
∨
(p
∧
q)
∧
(¬
r
∨
r)
⇔
(p
∧
¬
q)
∨
(p
∧
q)
⇔
p
16
⇔
¬
¬
(p
∧
q)
⇔
¬
(p
↓
q)
⇔
¬
(p
↓
q)
⇔
(p
↓
q)
↓
(p
↓
p)
FB
⇔
(¬
p
∧
q
∧
¬
r)∨
(¬
p
∧
q
∧
r)
⇔
(¬
p
∧
q)
∧
(¬
r
∨
r)
⇔
(¬
p
∧
q)
⇔
¬
¬
(¬
p
∧
q)
⇔
¬
(p
∧
¬
q)
⇔
p
↓
¬
q)
⇔
p
↓
(q
↓
q).
FC
⇔
(¬
p
∧
¬
p
∧
r)
⇔
¬
(p
∨
q)
∧
r
⇔
(p
↓
q)
∧
r
⇔
¬
¬
((p
↓
q)
∧
r
⇔
¬
(¬
(p
↓
q)
∨
¬
r
⇔
¬
(p
↓
q)
↓
¬
r
⇔
((p
↓
q)
↓
(p
↓
q) )
↓
(r
↓
r)
分析
在 将公式化成
{
↑
}
或
{
↓
}
中公式时,
应分以下几步
:(1)
先将公式化成全功能集
{¬
,
∧
,
∨
}
中的公式
.
(2)
使用
¬
A
⇔
¬
(A
∧
A)
⇔
A
↑
A,
17
或
¬
A
⇔
¬
( A
∨
A)
⇔
A
↓
A.
使用双重否定律
A
∧
B
⇔
¬
¬
(A
∧
B)
⇔
¬
(A
↑
B)
⇔
(A
↑
B)
↑
(A
↑
B)
或
A
∨
B
⇔
¬
¬
(A
∨
B)
⇔
¬
(A
↓
B)
⇔
(A
↓
B)
↓
(A
↓
B)< br>使用德·摩根律
A
∧
B
⇔
¬
¬
(A
∧
B)
⇔
¬
(¬
A
∨
¬
B)
⇔
¬
A
↓
¬
B
⇔
(A
↓
A)
↓
(B
↓
B)
或
A
∨
B
⇔
¬
¬
(A
∨
B)
⇔
¬
(¬
A
∧
¬
B)
⇔
¬
A
↑
¬
B
⇔
(A
↑
A)
↑
(B
↑
B)1
．
15
设
p
：矿样为铁；
q
：矿样为铜；
r
：矿样为锡
.
设
F1
⇔
(
甲全对
)
∧(
乙对一半
)
∧
(
丙全错
)
，
⇔
(¬
p
∧
¬
q)
∧
((¬< br>p
∧
¬
r)
∨
(p
∧
r))
∧(¬
p
∧
r)
⇔
(¬
p
∧
¬
q
∧
¬
p
∧
¬
r
∧
¬
p
∧
r)
∨
(¬
p
∧
¬
q
∧< br>p
∧
r
∧
¬
p
∧
r)
⇔
0
∨
0
⇔
0.
F2
⇔(
甲全对
)
∧
(
乙全错
)
∧
(
丙对一半
)
⇔
(¬
p
∧
¬
q)∧
(p
∧
¬
r)
∧
((p
∧
r)∨
(¬
p
∧
¬
r)
18
⇔
(¬p
∧
¬
q
∧
p
∧
¬
r
∧p
∧
r)
∨
( ¬
p
∧
¬
q
∧
p
∧
r
∧
¬
p
∧
¬
r)
⇔
0
∨
0
⇔
0
F3
⇔
(
甲对一半
)
∧
(
乙全对
)
∧
(
丙全错
)
⇔
((¬
p
∧
q)
∨
(p
∧
¬
q))
∧
(¬
p
∧
r)
∨
(¬
p
∧
¬
r)
⇔
(¬
p
∧
q
∧
¬
p
∧
r
∧
¬
p
∧
r
∨
(p
∧
¬q
∧
¬
p
∧
r
∧
¬
p
∧r)
⇔
(¬
p
∧
q
∧
r)
∨
0
⇔
¬
p
∧
q
∧
r.
F4
⇔
(
甲对一半
)
∧< br>(
乙全错
)
∧
(
丙全对
)
⇔
((¬
p
∧
q)
∨
(p
∧
¬
q))
∧< br>(p
∧
¬
r)
∧
(p
∧
¬
r)
⇔
(¬
p
∧
q¬
∧
¬
r
∧
p
∧
¬
r
∨
(p
∧
¬
q
∧
p
∧
¬
r
∧
p
∧
¬
r)
⇔
0
∨
(p
∧
¬
q
∧
¬
r)
⇔
p
∧
¬
q
∧
¬
r.
F5
⇔
(
甲会错
)
∧(
乙对一半
)
∧
(
丙全对
)
⇔
(p
∧
q)
∧
((¬< br>p
∧
¬
r)
∨
(p
∧
r))
∧(p
∧
¬
r)
⇔
(p
∧
q
∧
¬
p
∧
¬
r
∧
p
∧
¬
r
∨
(p
∧
q
∧
p
∧
r
∧
p< br>∧
¬
r)
⇔
0
∨
0
⇔
0.
F6
⇔(
甲全错
)
∧
(
乙全对
)
∧
(
丙对一半
)
⇔
(p
∧
q)
∧
((¬
p
∧
r)
∧
((p∧
r)
∨
(¬
p
∧
¬
r)
19
⇔
(p
∧
q
∧
¬
p
∧
r
∧p
∧
r
∨
(p
∧
q
∧
¬
p
∧
r
∧
¬
p
∧
¬
r)
⇔
0
∨
0
⇔
0.
设
F
⇔
(
一人全对)
∧
(
一人对一半
)
∧
(
一人全错
)
则
F
为真命题，并且
F
⇔
F1
∨
F2
∨
F3
∨
F4
∨
F5
∨
F6
⇔
(¬
p
∧
q
∧
r)
∨
(p
∧
¬
q
∧
¬r)
⇔
1.
但，矿样不 可能既是铜又是锡，于是
q,r
中必有假命题，所以
¬
p
∧
q
∧
r
⇔
0,
因而必有
p
∧
¬
q
∧
¬
r
⇔
1.
于是，必有
P
为真，
q
与
r
为假，即矿样为铁。
1.16
令
p
：今天是
1
号；
q
：明天是
5
号
.
由于本题给出的推理都比较简单，因而可以直接判断推理的形式结构是否为重言式。
（
1
）推理的形式结构为
(p
→
q)
∧
p
→
q.
可以用多种方法判断上公式为重言式，其实，本推理满足假言推理定律，即
(p
→
q)
∧
p
⇒
q.
所以，推理正确。
（
2
）推理的形式结构为
(p
→
q)
∧
p
→
q.
可以用多种方法证明上公式不是重言式，
其实，当
p
为假（即今天不是
1
号）
，
q
为真
（明天真是
5
号）
，也即
01
是上面公式的成假赋值，所以 ，推理的
20
形式结构不是重方式，故，推理不正确。
（
3
）推理的形式结构为
(p
→
q)
∧
¬
p
→
¬
q.
可以用多种方法证明上面公式为重言式，其实，它满足拒取式推理定律，即
(p
→
q)
∧
¬
p
⇒
¬
q.
所以，推理正确。
（
4
）推理的形式结构为
(p
→
q)
∧
¬
p
→
¬
q.
可以用多种方法证明上公式不是重言式，
01
为上公式的成假赋值，
所以，
推理不正确。
分析
对于前提与结论都比较简单的推理，最好直接 判推理的形式结构是否为重言式，
来判断推理是否正确，若能观察出一个成假赋值，立刻可知，推理不正 确。
1
．
17
(1)
证明
①
¬
q
∨
r
前提引入
②
¬
r
前提引入
③
¬
q
①②析取三段论
④
¬
(p
∧
¬
q)
前提引入
⑤
¬
p
∨
q
④置换
⑥
¬
p
②⑤析取三段论
（
2
）
证明
①
p
→
(q
→
s)
前提引入
②
q
→
(q
→
s)
①置换
③
q
前提引入
④
p
→
s
②③假言推理
⑤
p
∨
¬
r
前提引入
21
⑥
r
→
p
⑤置换
⑦
r
→
s
④⑥假言三段论
（
3
）
证明
①
p
附加前提引入②
p
→
q
③
q
①②假言推理
④
p
∧
q
①③合取
或者
证明
①
p
→
q
前提引入②
¬
p
∨
q
③
(¬
p
∨
p)
∧
(¬
p
∨q)
②置换
前提引入
①置换
④
¬
p
∨
(p
∧
q)
③置换
⑤
p
→
(p
∧
q)
④置换
（
4
）
证明
①
前提引入②
(s
→
t)
∧
(t
→
s)
①置换
③
②化简
④
t
∧
r
前提引入
⑤
t
⑥
s
③⑤假言推理⑦
前提引入
⑧
(q
→
s)
∧
(s
→
q)
⑦置换
⑨
s↔q
⑧化简
⑩
q
⑥⑨似言推理
⑪
q↔ p
前提引入
22
⑫
p
⑩
⑪
假言推理
⑬
r
④化简
⑭
p
∧
q
∧
s
∧
r
⑥⑩
⑪⑫
合取
分析
由于
(A1
∧
A2
∧L
∧
Ak)
→
(C
→
B)
⇔
¬
(A1
∧
A2
∧L
∧
Ak)
∨
(¬
C
∨
B)
⇔
¬
(A1
∧
A2∧
L
∧
Ak
∧
C)
∨
B
⇔
A1
∧
A2
∧
L
∧
Ak
∧
C
→
B
所以
,
当推理的结论也为蕴含式时
,
可以将结论的前件作 为推理的前提
,
称为附加前提
,
并
称使用附加前提的证明方法为附加 前提证明法
.(3)
中第一个证明
,
即为附加前提证明法
.
1.18
设
p
：他是理科生
q
：他是文科生
r
：他学好数学
前提
p
→
r,¬
q
→
p,¬
r
结论
q
通过对前提和结论的观察，知道推理是正确的，下面用构造证明法给以证明。
证明
①
p
→
r
前提引入
¬
r
前提引入
③
¬
p
①②拒取式
④
¬
q
→
p
前提引入
⑤
¬
¬
q
③④拒邓式
⑥
q
⑤置理
1
．
19
本题可以用多种方法求解，根据要求回答问题，解本题 最好的方法是真值表示
或主析取范式法。这里采用主析取范式的主析取范式（过程略）
23
p
∨
(q
∧
¬
r)
⇔
m2
∨
m4
∨
m5
∨
m6
∨
m7
所以，成真赋值为
010
，
100
，
101，
110
，
111
，由④给也，成假赋值为
000
，< br>001
，
011
，
由③给出，公式是非重言式的可满足式，由③给出。
1
．
20
答案
A
：③；
B
：④；
C
：②
分析
解本题的方法不限于求主析取范式或主合取范式，也可以利用真值表法。
方法
1
：
求主析取范式
¬
(p
∧
q)
→
r
⇔
(p
∧
q)
∨
r
⇔
(p
∧
q)
∧
(r
∨
¬
r)
∨
(p
∨
¬
p)
∧
(q
∨
¬
q)
∧
r
⇔
m1
∨
m3
∨
m5
∨m6
∨
m7
从上式可知 ，
¬
(p
∧
q)
→
r
的主析取范式中含
5
个极小项。
极小项角码的二进制表示为成
真赋值，因而成真赋值为
001，
011
，
101
，
110
，
111
。由成真赋值立即可知成假赋值为
000
，
010
，
100
，成假赋值的十进制的十进表示为极大 项的角码，因而极大项为
M0,M2,M4
，
故有
3
个极大项。
方法
2
：求主合取范式，分析类似主析取范式法。
方法
3
：真值表法
由真值表，
求出成真赋值，
将成真赋值转化成十进制 数做为极小项的角码，
这样就求出
了全部极小项，也容易求出极大项。
1
．
21
答案
A
：③；
B
：⑤；
C
：⑥
分析
可用构造证明法解此题。
（
1
）
①
¬
q
∨
r
前提引入
②
¬
r
前提引入
③
¬
q
①②析取三段论
24
④
¬
(p
∧
¬
q)
前提引入
⑤
¬
p
∨
q
④置换
⑥
¬
p
③⑤析取三段论
至此可知
¬
p
是（
1
）的逻辑结论。
（
2
）
①
¬
r
∨
s
前提引入
②
¬
s
前提引入
③
¬
r
①②析取三段论
④
(p
∧
q)
→
r
前提引入
⑤
¬
(p
∧
q)
④置换
⑥
¬
p
∨
¬
q
⑤置换
至此可知
¬
p
∨
¬
q
是（
2
）的国逻辑结论。
（
3
）
①
¬
p
∨
q
前提引入
②
p
→
q
①置换前提引入
③
¬
q
∨
r
前提引入
④
q
→
r
③置换
⑤
p
→
r
②④假言推理
⑥
r
→
s
前提引入
⑦
p
→
s
⑤⑥假言推理
至此可知
p
→
s
是（
3
）的逻辑结论。
1
．
22
答案
A
：④
分析
在本题中，设
A
，
B
，
C
分别表示
3
个开 关状态的命题变项，开关的扳键向上
时，对应命题变项的真值为
1
，否则为
0
，由真值表易知。
F
⇔
(¬
A
∧
¬
B
∧
C)
∨
(¬
A
∧
B
∧
¬
C)
∨
(A
∧
¬
B
∧
¬
C)
∨
(A
∧
B
∧
C)
25
⇔
¬
A
∧
((¬< br>B
∧
C)
∨
(B
∧
¬
C))
< br>∨
A
∧
((¬
B
∧
¬
C)
∨
(B
∧
C))
⇔
(¬
A
∧
(B∨
C))
∨
(A
∧
(¬
B
∨
C)∧
(B
∨
¬
C))
⇔
(¬
A
∧
(B
∨
C))
∨
(A
∧
¬
((B
∧¬
C)
∨
(¬
B
∧
C))
⇔
(¬A
∧
(B
∨
C))
∨
(A
∧
¬
(B
∨
C))
⇔
A
∨
B
∨
C
26
第
2
章
习题解答
2.1
本题没有给出个体域
,
因而使用全
总个体域
.
(1)
令
F(x):x
是鸟
G(x):x
会飞翔
.
命题符号化为
∀
x(F(x)
→
G(x)).
(2)
令
F(x):x
为人
.
G(x):x
爱吃糖
命题符号化为
¬
∀
x(F(x)
→
G(x))
或者
∃
x(F(x)
∧
¬
G(x))
(3)
令
F(x):x
为人
.
G(x):x
爱看小说
.
命题符号化为
∃
x(F(x)
∧
G(x)).
(4) F(x):x
为人
.
G(x):x
爱看电视
.
命题符号化为
¬
∃
x(F(x)
∧
¬
G(x)).
分析
1
°如果没指出要求什么 样的个体域，
就使用全总个休域，
使用全总个体域时，
往
往要使用特性谓词。
（
1
）
-
（
4
）中的
F(x)
都 是特性谓词。
2
°
初学者经常犯的错误是，将类似于（
1
）中的命题符号化为
27
∀
x(F(x)
∧
G(x))
即用合取联结词取代蕴含联结词，这是万万不可的。将（
1
）中 命题叙述得更透彻些，
是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。
”因而符 号化应该使用联结
词→而不能使用∧。若使用∧，使（
1
）中命题变成了“宇宙间的一 切事物都是鸟并且都会
飞翔。
”这显然改变了原命题的意义。
3
°
（
2
）与（
4
）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证
明（
2）
，
（
4
）中两公式各为等值的。
2.2 (1)d (a),(b),(c)
中均符号化为
∀
xF(x)
其中
F(x):(x+1)2=x2+2x+1,
此命题在
(a),(b),(c)
中均为 真命题。
（
2
）
在
(a),(b),(c)
中均符号化为
∃
xG(x)
其中
G(x):x+2=0
，此命题在（
a
）中为假命题，在
(b)(c)
中均为真命题。
（
3
）在
(a),(b),(c)
中均符号化为
∃
xH(x)
其中
H(x):5x=1.
此命题在
(a),(b)< br>中均为假命题，在
(c)
中为真命题。
分析
1
°命题的真值与个体域有关。
2
°
有的命题在不同个体域中，符号化的形式不同，考虑命题
“人都呼吸”
。
在个体域为人类集合时，应符号化为
∀
xF(x)
这里，
F(x):x
呼吸，没有引入特性谓词。
在个体域为全总个体域时，应符号化为
∀
x(F(x)
→
G(x))
这里，
F(x):x
为人，且
F (x)
为特性谓词。
G(x):x
呼吸。
28
2
．
3
因题目中未给出个体域，因而应采用全总个体域。
（
1
）
令 ：
F(x):x
是大学生，
G(x):x
是文科生，
H(x):x< br>是理科生，命题符号化为
∀
x(F(x)
→
(G(x)
∨
H(x))
（
2
）令
F(x):x
是人，
G(y):y
是化，
H(x):x
喜欢，命题符
号化为
∃
x(F( x)
∧
∀
y(G(y)
→
H(x,y)))
（
3
）令
F(x):x
是人，G(x):x
犯错误，命题符号化为
¬
∃
x(F(x)
∧
¬
G(x)),
或另一种等值的形式为
∀
x(F(x)
→
G(x)
（
4
）令
F(x):x
在北京工作，
G(x):x
是北京人，命题符号化为
¬
∀
x(F(x)
→
G(x)),
或
∃
x(F(x)
∧
¬
G(x)),
（
5
）令
F(x):x
是金属，< br>G(y):y
是液体，
H(x,y):x
溶解在
y
中，命题符 号化为
∀
x(F(x)→
∃
y(G(y)
∧
H(x,y))).
（
6
）令
F(x):x
与
y
是对顶角，
H(x,y):x
与
y
相等，命题符号化为
∀
x
∀
y(F(x,y)
→
H(x,y)).
分析
（
2
）
，
（
5
）
，
（
6
）中要使用
2
无谓词，用它们来描述事物之间的关系。
2.4
1
）对所有的
x
，存在着
y
，使得
x
⋅
y=0
，在
(a),(b)
中为真命题 ，在
(c),(d)
中为假命
题。
（
2
）存在着
x
对所有的
y
，都有
x,
⋅
y=0
，在
(a),(b)
中为 真命题，在
(c),(d)
中为假命
题。
29
（
3
）
对所有
x
，
存在着
y
，使得
x⋅
y=1
，在
(a),(b)(c)
中均为假命题，
而在
(d)
中为真命题。
（< br>4
）存在着
x
，对所有的
y
，都有
x
⋅y=1
，在
(a),(b)(c)(d)
中都是假命题。
（
5
）对所有的
x
，存 在着
y
，使得
x
⋅
y=x
在
(a),(b)(c) (d)
中都是真命题。
（< br>6
）存在
x
，对所有的
y
，都有
x
⋅
y=x
，在
(a),(b)
中为真命题，在
(c)(d)
中为假命 题。
（
7
）对于所 有的
x
和
y
，存在着
z
，使得
x−y=z
，在
(a),(b)
中为真命题，在
(c)(d)
中为假
命题。
2.5
1
）取解释
I1
为：个体域
D=R
（实数集合）
，
F(x):x
为有理数，
G(x):x
能表示成分
数，在
I1
下，
∀
x(F(x)
→
G(x))
的含义为
“
对于叙何实数
x
而言，若x
为有理数，则
x
能表示成分数”
，简言之为“有理数都能表
示 成分数。
”在此蕴含式中，当前件
F(x)
为真时，后件
G(x)
也 为真，不会出现前件为真，后
件为假的情况，所以在
I1
下，
∀
x( F(x)
→
G(x))
为真命题。
在在
I1
下，
∀
x(F(x)
∧G(x))
的含义为
“对于任何实数
x,x
既为有理数，又能表示成分数。
”
取
x=
2
，则
F( 2)
∧
g( 2)
显然为假，所以，在
I1
下，
∀
x(F(x)
∧
G(x))
为假命题
.
(2)
取解释
I2
为
:
个体域
D=N(
自然数集合
), F(x):x
为奇数
, G(x):x< br>为偶数
,
在
I2
下
,
∃
x(F(x)
∧
G(x))
的含义为
“存在自然数
x,x
发既为奇数，又为偶数。
”
取
x=2
，则
F(2)
为假，于是
F(2)
→
G(2)
为真，这表明
∃
x(F(x )
→
G(x)
为真命题。
分析
本题说明
∀
x(F(x)
→
G(x))
⇔∀
x(F(x)
∧
G(x)),
30
∃
x(F(x)
∧
G (x))
⇔∃
x(F(x)
→
G(x)),
这里，
A
⇔
B
表示
A
与B
不等值，以后遇到
⇔
，含义相同。
在一阶逻辑中，将命题符号化时，当引入特性谓词（如题中的
F(x))
之后，全称量词
∀
后往往使用联结词→而不使用∧，而存在量词
∃
后 往往使用∧，而不使用→，如果用错了，
会将真命题变成假命题，或者将假命题变成真命题。
2
．
6
在解释
R
下各式分别化为
（
1
）
∀
x(−x<0);
（
2
）
∀
x
∀
y(x−y
≥
x);
（
3
）
∀
x
∀
y
∀
z(x
(x−z
（
4
）
∀
x
∃
y(x
易知，在解释
R
下，
（
1
）
，
（
2
）为假；
，
（
3< br>）
（
4
）为真。
2
．
7
给定解释
I
为：个体域
D=N
（自然数集合）
，
F(x):x
为奇数，
G(x):x
为偶 数。
（
1
）在解释
I
下，公式被解释为
“如果所有的自然数不是奇数就是偶数，
则所有自然数全为奇 数，
或所有自然数全为偶
数。
”因为蕴含式的前件为真，后件为假，所以真值为假。< br>
（
2
）在
I
下，公式解释为
“如果存在着自然数为奇数，
并且存在着自然为偶数，
则存在着自然数既是奇数，
又是
偶数。
”
由于蕴含式的前件为真，后件为假，后以真值为假。
分析
本题说明全称量词对析取不满足分配律，存在量词对合取不满足分配律。
2.8
令
A=
∀
x< br>∀
y(F(x)
∧
G(y)
→
L(x,y)),
在< br>A
中，无自由出现的个体变项，所以
A
为闭
式。
给定解释
I1
：个体域
D=N
（整数集合）
，
F(x):x
为正数，
G(x):x
为负数，
L(x,y):x>y
，
在
I1
下，
A
的含义为
31
“对于任意的整数
x
和
y
，如果< br>x
为正整数，
y
为负整数，则
x>y
。
”
这是真命题。
设解释
I2
：个体域
D=R
（R
整数集合）
，
F(x):x
为有理数，
G(y):y
为无理数，
L(x,y):x
≤
y
，在
I2
下，
A
的含义为
“对于任意的实数
x
和
y
，如果
x
为有理数，
y
为元理数， 则
x
≥
y
。
”
这是假命题。
分析
闭式在任何解释下不是真就是假，
不可能给出解释
I,
使得闭式 在
I
下真值不确
定，这一点是闭式的一个重要特征。而非封闭的公式就没有这个特征。
2.9
取
A1= L(f(x,y),g(x,y))
和
A2=
∀
x(f(x,y),x)，则
A1
和
A2
都是非土产的公式，在
A1
中，
x, y
都是自由出现的，在
A2
中，
y
是自出现的。
取
解
释
I
为
，
个
体
域
D=N
（
N
为
自
然
数
集
合
）
，
f(x,y, )=x+y,g(x,y)=x
⋅
yL(x,y)
为
x=y
。在
I
下，
A1
为
x+y=x
⋅
y
为假 ，所以在
I
下，
A1
真值不确定，即在
I
下
A2< br>的真值也是命题。
在
I
下，
A2
为
∀
x(x+y=x),
当
y=0时，它为真；
y
≠
0
时为假，在
I
下
A2的真值也不确
定。
分析
非闭式与
闭式的显著区别是，前者可能在某些解 释下，真值不确定，而后者对
于任何解释真值都确定，即不是真就是假。
当然非闭式也可以是逻辑有效式（如
F(x)
→F(x)
）
，也可能为矛盾式（如
F(x)
∧
¬
F(x ))
，
也可能不存在其值不确定的解释。
2
．
10
（
1
）
¬
∀
xA(x)
⇔< br>¬
(A(a)
∧
A(b)
∧
A(c))
（消去量词等值式）
⇔
¬
A(a)
∨
¬
A(b)
∨
¬
A(c)
（德·摩根律）
⇔∃
x¬
A(x)
（消去量词等值式）
（
2
）
¬
∃
xA(x)
⇔
¬
(A(a)
∨
A(b )
∨
A(c))
（消去量词等值式）
32
⇔
¬
A(a)
∧¬
A(b)
∧
¬
A(c)
（德·摩根律）
⇔∃
x¬
A(x)
（消去量词等值式）
2
．
11
（
1
）
令
F(x):x
为人。
G(x):x
长着绿色头发。
本命题直接符号化验为
¬
∃
x(F(x)
∧
G(x))]
而
¬
∃
x(F(x)
∧
G(x))
⇔∀
x¬
(F(x)
∧
G(x))
（量词否定等值式）
⇔∀
x(¬
F(x)
∨
¬
G(x))
（德·摩根律）
⇔∀
x(F(x)
→
¬
G(x))
（蕴含等值式）
最后一步得到的公式满足要求（使用全称量词）
，将它翻译成自然语言，即为
“所有的人都不长绿色头发”
。
可见得
“没有人长着绿色头发。
”与“所有人都不长绿色头发。
”
是同一命题的两种不同
的叙述方法。
（
2
）令
F(x):x
是北京人
G(x):x
去过香山。
命题直接符号化为
∃
x(F(x)
∧
¬
G(x))]
而
∃
x(F(x)
∧
¬
G(x))
⇔
¬
¬
∃
x(F(x)
∧
¬
G(x))
（双重否定律）
⇔
¬
∀
x¬
(F(x)
∧
¬
G(x))
（理词否定等值式）
⇔
¬
∀
x(¬
F(x)
∨
G(x))
（德·摩根律）
⇔
¬
∀
x(F(x)
→
G(x))
（蕴含等值式）
33
最后得到的公式满足要求（只含全称量词）
，将它翻译成自然语言，即为
“并不是北京人都去过香山。
”
可见，
“有的北京人没过过香山。”与“并不是北京人都去过香山。
”是同一命题不同的
叙述方法。
2.12
（
1
）
∀
xF(x)
→
∃
yG(y)
⇔
(F(a)
∧
F(b)
∧
F(c)
→
(G(b)
∨
G(c)).
（
2
）
∀
xF(x)
∧
∃
yG(y)
⇔∀
xF(x)
∧
∃
yG(y)
（量词辖域收缩扩张等值式）
⇔
(F(a)
∧
F(b)
∧
F(c))
∧
(G(a)
∨
G(b)
∨
(c)).
（
3
）
∃
x
∀
yH(x,y)
⇔∃
x(H(x,a)
∧
H(x,b)
∧
H(x,c)
⇔
(H(a,a)
∧
H(a,b)
∧
H(x,c)
∨
(H(b,a)
∧
H(b,b)
∧
H(b,c)
∨
(H(c,a)
∧
H(c,b)
∧
H(c,c)
分析
在有穷个体 域内消去量词时，应将量词的辖域尽量缩小，例如，在（
2
）中，首
先将量词辖域缩小 了
（因为
∃
yG(y)
中不含
x
，所以，可以缩小）
。否则，
演算是相当麻烦的。
见下面的演算：
∀
x(F(x)
∧
∃
yG(y)
⇔
(F(a)
∧
∃
yG (y))
∧
(F(b)
∧
∃
yG(y))
∧
F(c )
∧
∃
yG(y))
⇔
(F(a)
∧
(G(a)
∨
G(b)
∨
G(c )
∧
(F(b)
∧
(G(a)
∨
G(c))
∧
(F(c)
∧
(G(a)∨
G(b)
∨
G(c))
⇔
(F(a)
∧
(F(b)
∧
(G(a)
∨
G(b)
∨
(c)).
显然这个演算比原来的喾算麻烦多了。
34
2.13
在
I
下
（
1
）
∀
x(F(x)
∧
G(x))
⇔
(F(−2)
∧
G(−2))
∧
(F(3)
∧< br>G(3))
∧
F(6)
∧
G(6))
⇔
(1
∧
0)
∧
(1
∧
0)
∧
(0
∧
1)
⇔
0,
所以，
∀
x(F(x)
∧
G(x)
在
I
下为假。
（
2
）
∀
x(R(x)
→
F(x))
∨
G(5)
⇔
((R(−2)
→
F(−2))
∧
(R(3)
→
F(3))
∧
(R(6)
→
F(6)))
∨
0⇔
((1
→
1)
∧
(1
→
1)
⇔0,
所以，此公式在
I
下也是假命题。
（
3
）
∃
x(F(x)
∨
G(x))
⇔∃
xF(x)
∨
∃
xG(x)
（量词分配等值式）
⇔
(F−( 2)
∨
F(3)
∨
F(6))
∨
(G−( 2)
∨
G(3)
∨
G(3)
⇔
(1
∨
1
∨
0)
∨
(0
∨
0
∨
1)⇔
1,
所以，此公式在
I
下为真
2
．
14
（
1
）
¬
∃
xF(x)
→
∀
yG(x,y)
⇔∀
x¬
F(x)
→
∀
yG(x,y)
（量词否定等值式）
⇔∀
z¬
F(z)
→
∀
yG(x,y)
（约束变项换名规则）
⇔∃
z
∀
y(¬
F(z)
→
G(x,y)
（量词辖域收
缩扩张等值 式）
⇔∃
z
∀
y(F(z)
∨
G(x,y)
（
2
）
¬
(
∀
xF(x,y)
∨
∃
yG(x,y))
⇔∃
x¬
F(x,y)
∧
∀
y¬
G(x,y)
35
⇔∃
z1¬
F(z1,y)
∧
∀< br>z2¬
G(x,z2)
⇔∃< br>z1
∀
z2(¬
F(z1,y)
∧
¬
G(x,z2)
在以上演算中分别使用了德·摩根律、量词否定等值式、约束变项换名规则等。
分析
公式的前束范式是不唯 一的。
（
1
）中最后两步都是前束范式，其实
∀
y
∃
z(F(z)
∨
G(x,y))
也是（
1
）中公式的前束范式。
2
．
15
（
1
）
∀
xF(x)
∨
∃
yG(x,y)
⇔∀
xF(x)
∨
∃
yG(z,y)
⇔∀
x
∃
y(F(x)
∨
G(z,y))
（
2
）
∃
x(F(x)
∧
∀
yG(x,y ,z))
→
∃
zH(x,y,z)
⇔∃
x(F(x)
∧
∀
yG(x,y,u))
→
∃
zH(v,
ϖ
,z)
⇔∃
x
∀
y(F(x)
∧
G(x,y,u))< br>→
∃
zH(v
ϖ
,
,z)
⇔∀
x
∃
y(F(x)
∧
G(x,y,u))
→
H(v
ϖ
,
,z)
在以上演算中分别使用了自由变项换名规则和量词辖域收缩扩张等值式。
2.16
（
1
）②错。使用< br>UI
，
UG
，
EI
，
EG
规则应对前束范式 ，而①中公式下不是前束
范式，所以，不能使用
UI
规则。
（
2
）
。①中公式为
∀
xA(x)
，这时，
A(x)=F(x)
∨
G(x)
，因而 使用
UI
规则时，应得
A(a)
（或
A(y)
）
， 故应有
F(a)
∨
G(a),
而不可能为
F(a)
∨
G(b).
（
3
）
②错。
应对
A(c)=F(c)
→
G(c)
使用
EG规则，
其中
c
为特定的使
A
为真的个体常项，
而不能为 个体变项。
（
4
） ②错。①中公式含个体变项
x
，不能使用
EG
规则。
（
5
）②错。①公式含两个个体常项，不能使用
EG
规则。
36
（
6
）⑤错。对①使用
EI
规则得
F (c)
∧
G(c)
，此
c
应使
F(c)
∧
G(c)
为真，此
c
不一定使
H(c)
∧
R(c)
为真。
分析
由于⑤的错误，可能由真前提，推出假结论。反例如下：
设个体域为自然数集合
N.F(x):x
为偶数，
G( x):x
为素数，
H(x):x
能被
3
整除，
R (x):x
能
被
4
整数，显然此时，
∃
x(F(x)
∧
G(x))
与< br>∃
x(H(x)
∧
R(x))
均为真，但
∃
x(F(x)
∧
G(x))
为假。 其实在（
6
）中，③应为
F(2)
∧
G(2)
，它是真命题 ，
而
H(2)
∧
R(2)
为假命题。对
∃
x(H( x)
∧
R(x))
使用
EI
规则，得
H(12 )
∧
R(12)
才为真。所以，
对两个公式使用
EI
规则使 用同一个个体常项是会犯错误的。
2.17
（
1
）证明
①
∃
xF(x)
→
∀
y((F(y)
∨
G(y) )
→
R(y)
前提引入
②
∃
xF(x)
前提引入
③
∀
y((F(y)
∨
G(y))
→
R(y))
①②
假言推理
④
F(c)
②
EI
⑤
F(c)
∨
G(c)
④附加
⑥
F(c)
∨
G(c))
→
R(c)
③
UI
⑦
R(c)
⑤⑥假言推理
⑧
∃
xR(x)
⑦
EG
（
2
）证明：
①
∃
xF(x)
②
F(c)
37
③
∀
x(F(x)
→
(G(y)
∧
R(x)))
③
UI
⑤
G(y)
∧
R(c)
⑤
化
简
⑦
F(c)
∧
R(c)
⑦
EG
2
．
18
令
F(x):x
是大熊猎。
G(x):x
产在中国。
a:
欢欢
前提：
∀
x(F(x)
→
(G(x)),F(a)
结论：
G(a)
证明：
①
∀
x(F(x)
→
G(x))
前提引入③
F(a)
→
G(a)
④
G(a)
G(x):x
为实数。
H(x):x
为整数。
前提引入
①
EI
前
提
引
入
④
F(c)
→
(G(y)
∧
R(c))
②
④
假
言
推
理
⑥
R(c)
②
⑥
合
取
⑧
∃
x(F(x)
∧
R (x))
前
提
引
入
②
F(a)
①
UI
②③假言推理
2
．
19
令
F(x):x
为有理数。
前提：
∀
x(F(x)
→
G(x)),
∃
xF(x)
∧
H(x)) .
结论：
∃
x(G(x)
∧
H(x)).
证明：
①
∃
xF(x)
→
∀
y((F(y)
∨
G(y))
→
R(y)
前提引入
38
②
∃
xF(x)
③
∀
y((F(y)
∨
G(y))
→
R(y))
④
F(c)
⑤
F(c)
∨
G(c)
⑥
F(c)
∨
G(c))
→
R(c)
⑦
R(c)
⑧
∃
xR(x)
（
2
）证明：
①
∃
xF(x)
∧
H(x)
②
F(c)
∧
H(c)
③
∀
x(F(x)
→
G(x)
④
F(c)
→
G(c)
⑤
F(c)
⑥
G(c)
⑦
H(c)
⑧
G(c)
∧
H(c)
⑨
∃
x(G(x)
∧
H(x))
前提引入
①②
假言推理
②
EI
④附加
③
UI
⑤⑥假言推理
⑦
EG
前提引入
①
EI
前提引入
③
UI
②化简
④⑤假言推理
②化简
⑥与⑦合取
⑧
EG
分析
在以上证明中，不能如下进行。
①
∃
x(F(x)
∧
H(x)
前提引入
②
∀
x(F(x)
→
G(x))
前提引入
③
F(c)
→
G(c)
②
UI
④
F(c)
∧
H(c)
①
EI
至此，可能犯了错误，在③中取
c=
2,
则
F( 2)
→
G( 2)
为真，但
39
E(
2)
∧
H(
2)为假，就是说，由
UI
规则得到的
c
不一定满足
EI
规 则，但反之为真，这一点
务必注意。
2.20
答案
A
：③；
B
：②
分析
（
7
）式为非闭式，在个体域为整数集
Z
时，
∀
x(x·
y=x)
的真值不能确定，当
y=1
时为真，当
y
≠
1
时为假，所以，它不是命题，其余各式都是命题。
（
5
）虽然不是闭式，但
它为真。
2
．
21
答案
A
：②；
B
：④，⑤，⑨
C
：⑦；
D
：⑧
分析
注意约束变项和自由变项改名规则 的使用。
供选答案中，
（
1
）
的前束范式只有一
个，就是② 。而②的前束范式有
3
个，当然它们都是等值的。
（
3
）的前束范式 有
2
个，就
是⑦和⑧。注意，在（
3
）式中，
∀
x
的辖域为
(F(x,y)
→
∀
yG(x,y))
，这就决定了它们的前束
范式为
< br>∀
x
∀
y(F(x,z)
→
G(x,y))
，
（将自由出现的
y
改名为
z
）
但由于
∀
y
∀
x(F(x,z)
→
G(x,y))
⇔∀
x
∀
y(F(x,z)
→
G(x,y))
所以，⑧也是（
3
）的前束范式。
2
．
22
答案
A
：⑤。
分析
（
1
）
，
（
4
）正确；可以构造证明。
（
1
）证明：
①
∃
yF(y)
前提引入
②
F(c)
①
EI
③
∀
x(F(x)
→
G(x)
前提引入
④
F(c)
→
G(c)
③
UI
⑤
F(c)
②④假言推理
⑥
∃
yG(y)
⑤
EG
40
注意应先使用
EI
规则。
（
4
）证明：
①
∀
x(F(x)
→
H(x))
前提引入
②
F(y)
→
H(y)
①
UI
③
¬
H(y)
前提引入
④
¬
F(y)
②③拒取式
⑤
∀
x(¬
F(x)
④
UG
(2),(3)
推理不正确
,
只要举出反例即可
.
在自然数集合中
,
令
F(x):x
是偶数
,
G( x):x
是素数
,
则
∃
x(F(x)
∧
G(x))
为真命题
,
而
∀
yF(y)
为假命题
,
所 以
,
∃
x(F(x)
∧
G(x))
→
∀
yF(y)
不是逻辑有效蕴含式
,
这说明
(2)
是推理不 正确
,
读
者可举反例说明
(3)
中推理也不正确
.
2.23
答案
A:
②
B:
①
C:
⑦
D:
⑤
41
第
3
章
习题解答
3.1
A
：③；
B
：④；
C
：⑤；
D
：⑦；
E
：⑧
3.2
A
：③；
B
：①；
C
：⑤；
D
：⑥；
E
：⑦
3.3
A
：①；
B
：③；
C
：⑧；
D
：⑤；
E
：⑩
分析
对于给定的集合或集合 公式，
比如说是
A
和
B
，
判别
B
是否被< br>A
包含，
可以有下
述方法：
1°
若
A
和
B
是通过列元 素的方式给出的，那么依次检查
B
中的每个元素是否在
A
中
出现，如 果都在
A
中出现，则
B
⊆
A,
否则不是。例如，
3 .3
题给的答案中有
{{1
，
2}}
和
{1}
，< br>谁是
S={
∅
,{1},{1,2}}
的子集呢
?
前 一个集合的元素是
{1,2},
要
S
中出现
,
但后一个集合 的元素
是
1,
不在
S
中出现
,
因此
,{{ 1,2}}
⊆
S.
2
°
若
A
和
B
是通过用谓词概括元素性 质的主试给出的
,B
中元素的性质为
P,A
中元素
的性质为
Q,
那么
,
“
如果
P
则
Q”
意味着
B
⊆
A,
“
只有
P
才
Q”
意味着
A
⊆
B,
“
除去
P
都不
Q”
意味着
A
⊆
B,
“
P
且仅
P
则
Q
”意味着
A=B.
例如，
3.1
题（
1
）是“如果
P
则
Q
”的形式，其中“计算机专业二年级学生”是性质
P
，
“学《离散数学》课”是性质；题（
2
）是“
P
且仅
P
则
Q
”的形式，此外
“
如果
P
就非
Q”
则意味着
AIB=
∅
。
例如，
3.1
题（
3
）和
3.2
题（
3
）都是这种形式。
3°
通过集合运算差别
B
⊆
A,
如果
A UB=A
，
BIA=B
，
B−A=
∅
三个等式中有任何一个 成立，
则有
B
⊆
A.
。
4°
通过文氏图观察，如果代表
B
的区域落 在代表
A
的区域内部，则
B
⊆
A.
。
42
这后两种方法将在后面的解答中给出实例。
3.4
A
：②；
B
：④；
C
：⑦；
D
：⑥；
E
：⑧
3.5
A
：②；
B
：④；
C
：⑤；
D
：⑥；
E
：⑨
3.6
A
：①；
B
：⑨；
C
：④；
D
：⑦；
E
：⑧
3.7
A
：④；
B
：⑨；
C
：①；
D
：⑧；
E
：①
分析
设只买1
本、
2
本及
3
本书的学生集合分别为
S1,S2和
S3
，它们之间两两不交，
由题意可知，
|S3|=20,
|S2US3|=55.
又知
|S2IS3|=
∅
,
所以
,
|S2|=|S2US3|−|S3|=55−20=35.
然后列出下面的方程
:
|S1|+2|S2|+3|S3|=140
求得
|S1|=10.
因此
,
没有买书的人数是
75-(10+35+20)=10.
3.8
(1)
和
(4)
为真
,
其余为假
.
分析
这里可以应用集合运算 的方法来差别集合之间的包含或相等关系
.
如题
(3)
中的条
件S−T=
∅
意味着
, S
⊆
T,
这时不一定有
S=T
成立
.
而对于题
(4),
由条件
~SUT=E
可推出
SI(~SUT)=SIE
⇒
(SI~S)U(SIT)=S
⇒∅
U(SIT)=S
⇒
SIT =S.
这是
S
⊆
T
的充公必要条件
,
从而结论为真
.
对于假命题都可以找到反例
,
如题
(2)
中令
S ={1,2},T=z{1},M={2}
即可
;
而对于题
(5),
只要
S
≠
∅
即可
.
3.9 (2),(3)
和
(4)
为真
,
其余为假
.
3.10 (1) A={0,1,2}.
(2) A={1,2,3,4,5}
43
(3) A={−1}
< br>(4)A={<0,0>,<0,1><1,0>,<0,2>,<1,1>,<2,0>,<0,3>,
<1,2>,<2,1>,<3,0><0,4 >,<1,3>,<2,3>,<2,2>,<3,1>,<4,0>}
3.11
(1) a=c
或
c=b
(2)
任何
a,b
(3) b=c=d
(4) a=b=c
(5) a=c=
∅
且
b={
∅
}.
3.12
(1),(2)
和
(6)
都是
B
⊂
A,
而
(3),(4),(5)
是
A= B.
分析
对于 用谓词给定的集合先尽量用列元素的方法表示
,
然后进行集合之间包含关系
的判别.
如果有的集合不能列元素
,
也要先对谓词表示尽可能化简
.
如 题
(3)
中的
A
可化简为
{x|x
∈
N
∧
x>2};
题
(5)
中的
A
和B
都可以化简为
{1−, 2};
题
(6)
中的
A={x|x
∈
N
∧
−
2
≤
x
≤
2},B={1,1}.
2
而对于题
(4),
不难看出
A=B=R,
是实数集合
.
3.13
(1) AUB={{a,b},c,d},
AIB={c}.
A−B={
{a,b}},
A
⊕
B={{a,b}},d}.
(2) AUB={{a{b}},c,{c},{a,b},{b}}.
AIB={{a,b},c},
A−B={{a,{b}},{c}},
A
⊕
B={{a{b},{c},{b}}.
(3) AUB=N,AIB={2},A−B={0,1}
A
⊕
B=N−{2}
(4)
观察到
B
⊂
A,
故
44
AUB=A,AIB=B,A
⊕
B=A−B={x|x
∈
R−Z
∧
x<1}.
(5)
观察到
AIB=
∅
,
故
AUB=Z−{0,1}
AIB=
∅
A−B=A
A
⊕
B=N−{0,1}
3.14
(1) P(A)={
∅
,{
∅
}}.
(2) P(A)={
∅
,{{1}},{1},{{1},1}}.
(3) P(A)={
∅
,{
∅
},{{1}},{{2}},{{1,2}},
∅
{ {2}},
∅
{ {2}},{
∅
,{1,2}},
{{1},{2}},{{1},{1,2}},{{2},{1,2 }},{{2},{1,2}},{
∅
,{1},{2}}
{
∅
,{1},{2}},{
∅
{1},{1 ,2}},
∅
{
,{2},{1,2}},{{1},{2}{1,2}},
{
∅
,{1},{2},{1,2}}}.
(4) P(A)={
∅
,{{1}},{{1,2}},{{1}},{{1,2}}
(5) P(A)={
∅
,{−1},{ 1},{2},{−1,1},{−1,2}{1,2}{−1,1,2}.
分析
在做集合运算前先要化简集合,
然后再根据题目要求进行计算
.
这里的化简指的是
元素
,谓词表示和集合公式三种化简
.
元素的化简——相同的元素只保留一个，去掉所有冗余的元素。
谓词表示的化简——去掉冗余的谓词，这在前边的题解中已经用到。
集合公工的化简——利用简单的集合公式代替相等的复杂公式。
这种化简常涉及到集合
间包含或相等关系的判别。
例如，题（
4
）中的
A={{1,1},{2,1}, {1,2,1}}
化简后得
A={{1},{1,2}}
，而题（
5
）中的
A={x|x
∈
R
∧
x3−2x2−x+2=0}
化简为
A={−1,1,2}
。
3
．
15
45
3
．
16
（
1
）
，
（
2
）
，
（
3
）和（
6
）为真。
（
4
）和（
5
）不为真。
分析
如果给出的是集合恒等式，
可以用两种方法验证。
一是分别对等式两边的集合画
出文氏图，
然后检查两个图中的阴影区域是否一致。
二是 利用集合恒等式的代入不断对等式
两边的集合公式进行化简或者变形，
直到两边相等或者一边是 另一边的子集为止。
例如，
题
（
1
）中的等式左边经恒等变形后可得 到等式右边，即
(AUB)−C=(AUB)I~C
=(AI~C)U(BI~C)=(A−C)U(B−C)
类似地，对题（
2
）和（
3
）中的等式分别有
A−B(B−C)=AI~(BI~C)
=AI(~BUC)=(AI~B)U(AIC)
=(A−B)UAIC)
A−(BUC)=(A−B)I(A−C)
=(A−B)I(AI~C)=((A−B)IA)I~C
=(A−B)I~C=(A−B)−C
但对于等式（
4
）
，左边经变形后得
(AUBUC)−(AUB)=((AUB)−(AUB))U(C−(AUB))
=
∅
U(C−(AUB))=C−(AUB).
易见，
C−(AUB)
⊆
C,
但不 一定有
C−(AUB)=C.
如令
A=B=C={1}.
时，等式（
4
）不为真。
类假地，等式（
5
）的左边经化简后得
(A−C)−B
，而
(A−C)−B
不一定恒等于
A-C
。
3
．
17
（
1
）不为真。
（
2
）
，
（
3
）和（
4）都为真。对于题（
1
）举反例如下：令
A={1},
A={1},B={1,4},C={2},D={2,3},
则
A
⊂
B
且
C
⊂
B
，但
AIC =BID
，与结论矛盾。
46
分析
（2
）由于
C
⊆
D
⇔
~D
⊆
~C,又由
A
⊆
B
可得
AIC~D
⊆
BI~C,即
A−D
⊆
B−C
成立。
（
3
）由于
AU(B−A)=AUB
，故有
B=AU(B−A)
⇔
B=AUB
⇔
A
⊆
B
。
这里用到
A
⊆
B
的充要条件为
B=AUB
或
B=AIB
或
A−B=
∅
.
（
4
）易见，当
A=B
成立时，必有
A-B=B-A
。反之，由
A-B=B-A
得
(A−B)IB=(B−A)IB
化简后得
B−A=
∅
，即
B
⊆
A
，同理，可证出
A
⊆
B
，从而得到
A=B< br>。
3
．
18
由
|P(B)|=64
可知
|B|=6
。又由
|P(AUB )|=256
知
|AUB|=8
，代入包含排斥原理得
8=3+6−|AIB|,
从而有
|AIB|=1,|A−B|=2,|A
⊕
B|=2+5=7.
3
．
19
令
S={x|x
∈
N
∧
1
≤
x
≤
1000 000}.
A={x|x
∈
S
∧
x
是完全平方数
}
，
B={x|x
∈
S
∧
x
是完全立方数
}
，
从而有
|S|=1000000,|A|=1000,|B|=100,|AIB|=10
代入包含排斥原理 得
.
|AIB|=|S|−(|A|+|B|)+|AIB|
=1000000−(1000+100)+10
=998910
47
第
4
章
习题解答
4
．
1
A
：⑤；
B
：③；
C
：①；
D
：⑧；
E
：⑩
4
．
2
A
：②；
B
：③；
C
：⑤；
D
：⑩；
E
：⑦
4
．
3
A
：②；
B
：⑦；
C
：⑤；
D
：⑧；
E
：④
分析
题
4.1-4.3
都涉及到关系的表示。先根据题意将关系 表示成集合表达式，然后再
进行相应的计算或解答，例如，题
4.1
中的
Is ={<1,1>,<2,2>},
Es ={<1,1>,<1,2>,<2,1>,<2,2>}
Is ={<1,1>,<1,2>,<2,2>};
而题
4.2
中的
R={<1,1>,<1,4>,<2,1>,<3,4>,<4,1>}.
为得到题
4.3
中的
R
须求解方程
x+3y=12
，最终得到
R={<3,3>,<6,2>,<9,1>}.
求
RoR
有三种方法，即集合表达式、关系矩阵和关系图的主法。下面由题
4.2
的关系
分别加以说明。
1
°集合表达式法
将
domR,domRUran,ranR
的元素列出来，如图
4.3
所示。然后检查
R
的每个有序对，若
∈
R
，< br>则从
domR
中的
x
到
ranR
中的
y画一个箭头。
若
danR
中的
x
经过
2
步有向 路径
到达
ranR
中的
y
，则
∈
RoR
。由图
4.3
可知
RoR={<1,1>,<1,4><4,1>,<4,4>,<2,1>,<2,4>,< 3,1>}.
如果求
FoG
，则将对应于
G
中的有序对的箭头画在左边，而将对应于
F
中的有序对的箭头画在右边。对应的三个集合分别为
domG
,ranUdomF,ranF
， 然后，同样地寻找
domG
到
ranF
的
2
步长的有向路径 即可。
2
°
矩阵方法
若
M是
R
的关系矩阵，则
RoR
的关系矩阵就是
M
·
M
，也可记作
M
，在计算
2
48
乘积时的相加不是普通加法，而是逻辑加，即
0+0=0
，
0+1=1+0=1+1=1
，根据已知条件得
⎡
1
0
0
1
⎤
⎡
1
0
0
1
⎤
⎡
1
0
0
1
⎤
⎢
1
0
0
0
⎥
⎢
1
0
0
0
⎥
⎢
1
0
0
1
⎥
2
⎢
⎥
⎢
⎥
⎢
⎥
M
=
⎢
⎥
⋅
⎢
⎥
=
⎢
⎥
⎢
0
0
0
1
⎥
⎢
0
0
0
1
⎥
⎢
1
0
0
0
⎥
⎣
1
0
0
0
⎦
⎣
1
0
0
0
⎦
⎣
1
0
0
1
⎦
M2
中含有
7
个1
，说明
RoR
中含有
7
个有序对。
图
4.3
图
4.4
3
°关系图方法
n
'
'
设
G
是
R
的关系图。
为求
R
的关系图
G
，
无将
G
的结点复制到
G
中，
然后依次检查
G
的每个结点。如果结点
x
到
y
有一条
n
步长的路径，就在
G'
中从
x
到
y
加一条有向边。
当所有的结点检查完毕，就得到图
G'
。以题
4.2
为例。图
4.4
（
1
）表示
R
的关系图
G
。依次
检查结点
1
，
2
，
3
，
4
。从
1
出发，沿环走
2
步仍回到
1
，所以，
G'
中有过
1
的环。从
1
出发，
经
<1,1>
和
<1,4>
，
2
步可达
4
，所以，
'
中有从
1
到
4
的边。结点
1
检查完毕。 类似地检查
其他
3
个结点，
2
G
步长的路径还有
2
→
1
→
1
，
2
→
1
→
4
，
3
→
4
→
1
，
4
→
1
→
1
，
4
→
1
→
4
。将这些路径
'
2
对应的边也加到
G
中，最终得到
R
的关系图。这个图给在图
4.4(2).
4
．
4
A
：④；
B
：⑧；
C
：⑨；
D
：⑤；
E
：⑩
分析
根据表
4.1
中关系图的特征来判定
R1,R2,L R5
的性质，如表
4.2
所示。
表
4.2