1
第一章部分课后习题参考答案
16 设 p、q的真值为 0000；r、s的真值为 1111，求下列各命题
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
的真值。
（1）p∨(q∧r)⇔ 0∨(0∧1) ⇔ 0
（2）（p↔r）∧(﹁q∨s) ⇔（0↔1）∧(1∨1) ⇔ 0∧1⇔ 0.
（3）（¬ p∧¬q∧r）↔(p∧q∧﹁r) ⇔（1∧1∧1） ↔ (0∧0∧0)⇔ 0
(4)（¬ r∧s）→(p∧¬q) ⇔（0∧1）→(1∧0) ⇔ 0→0⇔ 1
17．判断下面一段论述是否为真：“π 是无理数。并且，如果 3是无理数，则 2 也是无理数。另外
6能被 2整除，6才能被 4整除。”
答：p: π 是无理数 1
q: 3是无理数 0
r: 2 是无理数 1
s: 6能被 2整除 1
t: 6能被 4整除 0
命题符号化为： p∧(q→r)∧(t→s)的真值为 1，所以这一段的论述为真。
19．用真值表判断下列公式的类型：
（4）(p→q) →(¬q→¬p)
（5）(p∧r) ↔ (¬p∧¬q)
（6）((p→q) ∧(q→r)) →(p→r)
答： （4）
p q p→q ¬q ¬p ¬q→¬p (p→q)→(¬q→¬p)
0 0 1 1 1 1 1
0 1 1 0 1 1 1
1 0 0 1 0 0 1
1 1 1 0 0 1 1
所以公式类型为永真式
（5）公式类型为可满足式（
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
如上例）
（6）公式类型为永真式（方法如上例）
第二章部分课后习题参考答案
3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.
(1) ¬ (p∧q→q)
(2)(p→(p∨q))∨(p→r)
(3)(p∨q)→(p∧r)
答：(2)（p→(p∨q)）∨(p→r)⇔ (¬p∨(p∨q))∨(¬p∨r)⇔ ¬ p∨p∨q∨r⇔ 1
所以公式类型为永真式
2
(3) P q r p∨q p∧r （p∨q）→(p∧r)
0 0 0 0 0 1
0 0 1 0 0 1
0 1 0 1 0 0
0 1 1 1 0 0
1 0 0 1 0 0
1 0 1 1 1 1
1 1 0 1 0 0
1 1 1 1 1 1
所以公式类型为可满足式
4.用等值演算法证明下面等值式：
(2)(p→q)∧(p→r)⇔ (p→(q∧r))
(4)(p∧¬q)∨(¬p∧q)⇔ (p∨q) ∧¬(p∧q)
证明（2）(p→q)∧(p→r)
⇔ (¬ p∨q)∧(¬ p∨r)
⇔ ¬ p∨(q∧r))
⇔ p→(q∧r)
（4）(p∧¬q)∨(¬ p∧q)⇔ (p∨(¬p∧q)) ∧(¬ q∨(¬p∧q)
⇔ (p∨¬ p)∧(p∨q)∧(¬ q∨¬ p) ∧(¬ q∨q)
⇔ 1∧(p∨q)∧¬(p∧q)∧1
⇔ (p∨q)∧¬(p∧q)
5.求下列公式的主析取范式与主合取范式，并求成真赋值
(1)(¬p→q)→(¬q∨p)
(2)¬ (p→q)∧q∧r
(3)(p∨(q∧r))→(p∨q∨r)
解：
（1）主析取范式
(¬p→q)→(¬q∨ p)
⇔ ¬ (p∨ q)∨ (¬q∨ p)
⇔ (¬ p∧ ¬ q)∨ (¬q∨ p)
⇔ (¬ p∧ ¬q)∨ (¬ q∧ p)∨ (¬q∧ ¬ p)∨ (p∧ q)∨ (p∧ ¬q)
⇔ (¬p∧ ¬ q)∨ (p∧ ¬q)∨ (p∧ q)
⇔
320 mmm ∨∨
⇔∑(0,2,3)
主合取范式：
(¬ p→q)→(¬ q∨ p)
⇔ ¬ (p∨ q)∨ (¬ q∨ p)
3
⇔ (¬ p∧ ¬q)∨ (¬ q∨ p)
⇔ (¬ p∨ (¬q∨ p))∧ (¬q∨ (¬ q∨ p))
⇔ 1∧ (p∨ ¬q)
⇔ (p∨ ¬q) ⇔ M1
⇔∏(1)
(2) 主合取范式为：
¬ (p→q)∧ q∧ r⇔ ¬(¬p∨ q)∧ q∧ r
⇔ (p∧ ¬q)∧ q∧ r⇔ 0
所以该式为矛盾式.
主合取范式为∏(0,1,2,3,4,5,6,7)
矛盾式的主析取范式为 0
(3)主合取范式为：
(p∨ (q∧ r))→(p∨ q∨ r)
⇔ ¬ (p∨ (q∧ r))→(p∨ q∨ r)
⇔ (¬p∧ (¬ q∨ ¬r))∨ (p∨ q∨ r)
⇔ (¬p∨ (p∨ q∨ r))∧ ((¬q∨ ¬r))∨ (p∨ q∨ r))
⇔ 1∧ 1
⇔ 1
所以该式为永真式.
永真式的主合取范式为 1
主析取范式为∑(0,1,2,3,4,5,6,7)
第三章部分课后习题参考答案
14. 在自然推理系统 P中构造下面推理的证明：
(2)前提：p→q,¬(q∧ r),r
结论：¬ p
(4)前提：q→ p,q↔ s,s↔ t,t∧ r
结论：p∧ q
证明：（2）
①¬(q∧ r) 前提引入
②¬q∨ ¬r ①置换
③q→¬r ②蕴含等值式
④r 前提引入
4
⑤¬q ③④拒取式
⑥p→q 前提引入
⑦￢p（3） ⑤⑥拒取式
证明（4）：
①t∧ r 前提引入
②t ①化简律
③q↔s 前提引入
④s↔t 前提引入
⑤q↔t ③④等价三段论
⑥（q→t）∧ (t→q) ⑤ 置换
⑦（q→t） ⑥化简
⑧q ②⑥ 假言推理
⑨q→p 前提引入
⑩p ⑧⑨假言推理
(11)p∧ q ⑧⑩合取
15 在自然推理系统 P中用附加前提法证明下面各推理：
(1)前提：p→(q→r),s→p,q
结论：s→r
证明
①s 附加前提引入
②s→p 前提引入
③p ①②假言推理
④p→ (q→ r) 前提引入
⑤q→r ③④假言推理
⑥q 前提引入
⑦r ⑤⑥假言推理
16 在自然推理系统 P中用归谬法证明下面各推理：
(1)前提：p→¬ q,¬ r∨ q,r∧ ¬ s
结论：¬ p
证明：
①p 结论的否定引入
②p→﹁q 前提引入
5
③﹁q ①②假言推理
④￢r∨ q 前提引入
⑤￢r ④化简律
⑥r∧￢s 前提引入
⑦r ⑥化简律
⑧r∧﹁r ⑤⑦ 合取
由于最后一步 r∧﹁r 是矛盾式,所以推理正确.
第四章部分课后习题参考答案
3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:
(1) 对于任意 x,均有 2=(x+ )(x ).
(2) 存在 x,使得 x+5=9.
其中(a)个体域为自然数集合.
(b)个体域为实数集合.
解：
F(x): 2=(x+ )(x ).
G(x): x+5=9.
(1)在两个个体域中都解释为 )(xxF∀ ，在（a）中为假命题，在(b)中为真命题。
(2)在两个个体域中都解释为 )(xxG∃ ，在（a）(b)中均为真命题。
4. 在一阶逻辑中将下列命题符号化:
(1) 没有不能表示成分数的有理数.
(2) 在北京卖菜的人不全是外地人.
解:
(1)F(x): x 能表示成分数
H(x): x 是有理数
命题符号化为: ))()(( xHxFx ∧¬¬∃
(2)F(x): x 是北京卖菜的人
H(x): x 是外地人
命题符号化为: ))()(( xHxFx →¬∀
5. 在一阶逻辑将下列命题符号化:
(1) 火车都比轮船快.
(3) 不存在比所有火车都快的汽车.
解:
(1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比 y 快
6
命题符号化为: )),())()((( yxHyGxFyx →∧∀∀
(2) (1)F(x): x 是火车; G(x): x 是汽车; H(x,y): x 比 y 快
命题符号化为: ))),()(()(( yxHxFxyGy →∀∧¬∃
9.给定解释 I如下:
(a) 个体域 D为实数集合 R.
(b) D 中特定元素 =0.
(c) 特定函数 (x,y)=x y,x,y
D∈ .
(d) 特定谓词 (x,y):x=y, (x,y):x
,<3,3>,<4,4>}
EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}
LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}
DA={<2,4>}
13.设 A={<1,2>,<2,4>,<3,3>}
B={<1,3>,<2,4>,<4,2>}
求 A∪B,A∩B, domA, domB, dom(A∪B), ranA, ranB, ran(A∩B ), fld(A-B).
11
解：A∪ B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}
A∩ B={<2,4>}
domA={1,2,3}
domB={1,2,4}
dom(A∨B)={1,2,3,4}
ranA={2,3,4}
ranB={2,3,4}
ran(A∩ B)={4}
A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3}
14.设 R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}
求 R �R, R-1, R↑ {0,1,}, R[{1,2}]
解：R � R={<0,2>,<0,3>,<1,3>}
RRRR-1-1-1-1,,,,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}
R↑ {0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}
R[{1,2}]=ran(R|{1,2})={2,3}
16．设 A={a,b,c,d}， 1R ， 2R 为 A上的关系，其中
1R =
{ }, , , , ,a a a b b d
{ }2 , , , , , , ,R a d b c b d c b=
求 2 31 2 2 1 1 2, , ,R R R R R R� � 。
解: R1 �R2={,,}
R2�R1={}
R12=R1 � R1={,,}
R22=R2 � R2={,,}
R23=R2 � R22={,,}
36．设 A={1，2，3，4}，在 A× A 上定义二元关系 R，
∀ ,∈A× A ，〈u,v> R ⇔ u + y = x + v.
(1)证明 R 是 A× A 上的等价关系.
(2)确定由 R 引起的对 A× A 的划分.
（1）证明：∵R ⇔ u+y=x-y
∴R⇔ u-v=x-y
∀ ∈A× A
12
∵u-v=u-v
∴R
∴R 是自反的
任意的,∈A×A
如果R ，那么 u-v=x-y
∴x-y=u-v ∴R
∴R是对称的
任意的,,∈A×A
若R,R
则 u-v=x-y,x-y=a-b
∴u-v=a-b ∴R
∴R 是传递的
∴R是 A×A 上的等价关系
(2) ∏={{<1,1>,<2,2>,<3,3>,<4,4>}, {<2,1>,<3,2>,<4,3>}, {<3,1>,<4,2>},
{<4,1>}, {<1,2>,<2,3>,<3,4>}, {<1,3>,<2,4>}, {<1,4>} }
41.设 A={1，2，3，4}，R为 A ×A 上的二元关系,,,, ∀〈a，b〉，〈c，d〉∈A ×A ,,,,
〈a，b〉R〈c，d〉⇔ a + b = c + d
(1) 证明 R为等价关系.
(2)求 R导出的划分.
(1)证明：∀ R
∴R 是自反的
任意的,∈A×A
设R，则 a+b=c+d
∴c+d=a+b ∴R
∴R 是对称的
任意的,,∈A×A
若R,R
则 a+b=c+d,c+d=x+y
∴a+b=x+y ∴R
∴R 是传递的
∴R是 A×A上的等价关系
13
(2) ∏ ={{<1,1>}, {<1,2>,<2,1>}, {<1,3>,<2,2>,<3,1>}, {<1,4>,<4,1>,<2,3>,<3,2>},
{<2,4>,<4,2>,<3,3>}, {<3,4>,<4,3>}, {<4,4>}}
43. 对于下列集合与整除关系画出哈斯图:
(1) {1,2,3,4,6,8,12,24}
(2) {1,2,3,4,5,6,7,8,9,10,11,12}
解:
1
2 3
4 6
8 12
24
1
2 3
4
5
6
7
8
910
11
12
(1) (2)
45.下图是两个偏序集的哈斯图.分别写出集合 A和偏序关系 R≺的集合表达式.
a
b c
d e f g
a
b
c
d
e
f
g
(a) (b)
解: (a)A={a,b,c,d,e,f,g}
R≺ ={,,,,,,,,,} AI∪
(b) A={a,b,c,d,e,f,g}
R≺ ={,,,,,,} AI∪
46.分别画出下列各偏序集的哈斯图,并找出 A的极大元`极小元`最大元和最小元.
(1)A={a,b,c,d,e}
R≺ ={,,,,,,}∪ IA.
(2)A={a,b,c,d,e}, R≺ ={}∪ IA.
解:
14
a
b c d
e
a b
c
d
e
(1) (2)
项目 (1) (2)
极大元: e a,b,d,e
极小元: a a,b,c,e
最大元: e 无
最小元: a 无
第八章部分课后习题参考答案
1．设 f :N→N,且
f (x)=
1
2
x
x
x
⎧
⎪
⎨
⎪⎩
，若 为奇数
若 为偶数
，
求 f (0), f ({0}), f (1), f ({1}), f ({0,2,4,6,…})，f ({4,6,8}), f -1({3,5,7}).
解：f (0)=0, f ({0})={0}, f (1)=1, f ({1})={1},
f ({0,2,4,6,…})=N，f ({4,6,8})={2,3,4}, f -1 ({3,5,7})={6,10,14}.
4. 判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的?
(1) f:N→N, f(x)=x2+2 不是满射，不是单射
(2) f:N→N,f(x)=(x)mod 3,x除以 3的余数 不是满射，不是单射
(3) f:N→N,f(x)=
1
0
x
x
⎧
⎨
⎩
，若 为奇数
，若 为偶数
不是满射，不是单射
(4) f:N→ {0,1},f(x)=
0
1
x
x
⎧
⎨
⎩
，若 为奇数
，若 为偶数
是满射，不是单射
(5) f:N-{0}→R,f(x)=lgx 不是满射，是单射
(6) f:R→R,f(x)=x2-2x-15 不是满射，不是单射
5. 设 X={a,b,c,d},Y={1,2,3},f={,,,}判断以下命题的真假:
(1)f是从 X 到 Y 的二元关系,但不是从 X到 Y的函数; 对
(2)f是从 X 到 Y 的函数,但不是满射,也不是单射的; 错
(3)f是从 X 到 Y 的满射,但不是单射; 错
15
(4)f是从 X 到 Y 的双射. 错
第十章部分课后习题参考答案
4．判断下列集合对所给的二元运算是否封闭：
（1） 整数集合 Z和普通的减法运算。
封闭,,,,不满足交换律和结合律，无零元和单位元
（2） 非零整数集合 普通的除法运算。不封闭
（3） 全体
nn× 实矩阵集合 （R）和矩阵加法及乘法运算，其中 n 2。
封闭 均满足交换律，结合律，乘法对加法满足分配律；
加法单位元是零矩阵，无零元；
乘法单位元是单位矩阵，零元是零矩阵；
（4）全体 nn× 实可逆矩阵集合关于矩阵加法及乘法运算，其中 n 2。不封闭
（5）正实数集合 和 运算，其中 运算定义为：
不封闭 因为 +∉−=−−×= R1111111�
（6）
n
关于普通的加法和乘法运算。
封闭，均满足交换律，结合律，乘法对加法满足分配律
加法单位元是 0000，无零元；
乘法无单位元（ 1>n ），零元是 0000； 1=n 单位元是 1111
（7）A = { },,, 21 naaa ⋯ n 运算定义如下：
封闭 不满足交换律，满足结合律，
（8）S = 关于普通的加法和乘法运算。
封闭 均满足交换律，结合律，乘法对加法满足分配律
（9）S = {0,1},S是关于普通的加法和乘法运算。
加法不封闭，乘法封闭；乘法满足交换律，结合律
（10）S = ,S 关于普通的加法和乘法运算。
加法不封闭，乘法封闭，乘法满足交换律，结合律
5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。
见上题
7．设 * 为 +
Z
上的二元运算 +∈∀ Zyx, ，
16
X * Y = min ( x，y ),即 x 和 y之中较小的数.
(1)求 4 * 6，7 * 3。
4,4,4,4, 3333
(2)* 在 +Z 上是否适合交换律，结合律，和幂等律？
满足交换律，结合律，和幂等律
(3)求*运算的单位元，零元及 +
Z
中所有可逆元素的逆元。
单位元无，零元 1111, 所有元素无逆元
8．
QQS ×= Q为有理数集，*为 S 上的二元运算， , S 有
<<<< aaaa，bbbb >****y>y>y> ==== b>b>b>
（1）*运算在 S上是否可交换，可结合？是否为幂等的？
不可交换：****=>=>=>= +y>+y>+y>≠ <<<< aaaa，bbbb >****y>y>y>
可结合：(*)*=*)*=*)*=*)*=*=*=*=*=>>>
*(*)=*(*)=*(*)=*(*)=*=*=*=*=>>>
(*)*=*)*=*)*=*)*=*(*)>*(*)>*(*)>*(*)
不是幂等的
（2）*运算是否有单位元，零元？ 如果有请指出，并求 S中所有可逆元素的逆元。
设是单位元， >>> SSSS ，*=>*=>*=>*= ****=>=>=>=
则========，解的=<1,0>=<1,0>=<1,0>=<1,0>，即为单位。
设是零元， >>> SSSS ，*=>*=>*=>*= ****=>=>=>=
则========，无解。即无零元。
>>> SSSS，设是它的逆元*=>*=>*=>*= ****=<1,0>>=<1,0>>=<1,0>>=<1,0>
==<1,0>=
