第一章部分课后习题参考答案
16 设p、q的真值为0;r、s的真值为1,求下列各命题公式的真值。
(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
所以公式类型为永真式//最后一列全为1
(5)公式类型为可满足式(方法如上例)//最后一列至少有一个1
(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所以公式类型为永真式
(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)
?320m m m ∨∨
?∑(0,2,3)
主合取范式:
(?p →q)→(?q ∨p)
??(p ∨q)∨(?q ∨p)
?(?p ∧?q)∨(?q ∨p)
?(?p ∨(?q ∨p))∧(?q ∨(?q ∨p))
?1∧(p ∨?q)
?(p ∨?q) ? M 1
?∏(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 前提引入
⑤?q ③④拒取式
⑥p→q 前提引入
⑦¬p ⑤⑥拒取式
证明(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 前提引入
③﹁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)在两个个体域中都解释为)(x xF ?,在(a )中为假命题,在(b)中为真命题。
(2)在两个个体域中都解释为)(x xG ?,在(a )(b)中均为真命题。
4. 在一阶逻辑中将下列命题符号化:
(1) 没有不能表示成分数的有理数.
(2) 在北京卖菜的人不全是外地人.
解:
(1)F(x): x 能表示成分数
H(x): x 是有理数
命题符号化为: ))()((x H x F x ∧???
(2)F(x): x 是北京卖菜的人
H(x): x 是外地人
命题符号化为: ))()((x H x F x →??
5. 在一阶逻辑将下列命题符号化:
(1) 火车都比轮船快.
(3) 不存在比所有火车都快的汽车.
解:
(1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快
命题符号化为: )),())()(((y x H y G x F y x →∧??
(2) (1)F(x): x 是火车; G(x): x 是汽车; H(x,y): x 比y 快
命题符号化为: ))),()(()((y x H x F x y G y →?∧??
9.给定解释I 如下:
(a) 个体域D 为实数集合R.
(b) D 中特定元素=0.
(c) 特定函数(x,y)=x y,x,y D ∈.
(d) 特定谓词(x,y):x=y,(x,y):x ∈. 说明下列公式在I下的含义,并指出各公式的真值: (1))) G x y ? y → x? ? ) ( , , ( x (y F (2))) f x y F a ? x→ y ? , ) ( , ), ( x (y ( G 答:(1) 对于任意两个实数x,y,如果x (2) 对于任意两个实数x,y,如果x-y=0, 那么x 10. 给定解释I如下: (a)个体域D=N(N为自然数集合). (b) D中特定元素=2. (c) D上函数=x+y,(x,y)=xy. (d) D上谓词(x,y):x=y. 说明下列各式在I下的含义,并讨论其真值. (1)xF(g(x,a),x) (2)x y(F(f(x,a),y)→F(f(y,a),x) 答:(1) 对于任意自然数x, 都有2x=x, 真值0. (2) 对于任意两个自然数x,y,使得如果x+2=y, 那么y+2=x. 真值0. 11. 判断下列各式的类型: (1) (3) yF(x,y). 解:(1)因为1 ? → q →p p p为永真式; q p ? ( ) ) (? ∨ ∨ ? 所以为永真式; (3)取解释I个体域为全体实数 F(x,y):x+y=5 所以,前件为任意实数x存在实数y使x+y=5,前件真; 后件为存在实数x对任意实数y都有x+y=5,后件假,] 此时为假命题 再取解释I个体域为自然数N, F(x,y)::x+y=5 所以,前件为任意自然数x存在自然数y使x+y=5,前件假。此时为假命题。 此公式为非永真式的可满足式。 13. 给定下列各公式一个成真的解释,一个成假的解释。 (1) (F(x) (2) x(F(x)G(x)H(x)) 解:(1)个体域:本班同学 F(x):x 会吃饭, G(x):x 会睡觉.成真解释 F(x):x 是泰安人,G(x):x 是济南人.(2)成假解释 (2)个体域:泰山学院的学生 F(x):x 出生在山东,G(x):x 出生在北京,H(x):x 出生在江苏,成假解释. F(x):x 会吃饭,G(x):x 会睡觉,H(x):x 会呼吸. 成真解释. 第五章部分课后习题参考答案 5.给定解释I如下: (a)个体域D={3,4}; (b))(x f 为3)4(,4)3(==f f (c)1)3,4()4,3(,0)4,4()3,3(),(====F F F F y x F 为. 试求下列公式在I下的真值. (1)),(y x yF x ?? (3))))(),((),((y f x f F y x F y x →?? 解:(1) ))4,()3,((),(x F x F x y x yF x ∨???? ? ))4,4()3,4(())4,3()3,3((F F F F ∨∧∨ ?1)01()10(?∨∧∨ (2) )))(),((),((y f x f F y x F y x →?? ))))4(),(()4,(()))3(),(()3,(((f x f F x F f x f F x F x →∧→?? )))3),(()4,(())4),(()3,(((x f F x F x f F x F x →∧→?? )))3),3(()4,3(())4),3(()3,3(((f F F f F F →∧→? )))3),4(()4,4(())4),4(()3,4(((f F F f F F →∧→∧ )))3,4()4,3(())4,4(0((F F F →∧→?)))3,3(0())4,3(1((F F →∧→∧ )11()00(→∧→?)00()11(→∧→∧1? 12.求下列各式的前束范式。 (1)),()(y x yG x xF ?→? (5))),()((),(2121211x x G x x H x x F x ??→→? (本题课本上有错误) 解:(1) ),()(y x yG x xF ?→?),()(y t yG x xF ?→??)),()((y t G x F y x →??? (5) )),()((),(2121211x x G x x H x x F x ??→→? )),()((),(2323211x x G x x H x x F x ??→→?? )),()((),(2332411x x G x H x x x F x ?→?→?? ))),()((),((2334121x x G x H x x F x x ?→→??? 15.在自然数推理系统F 中,构造下面推理的证明: (1) 前提: ))())()((()(y R y G y F y x xF →∨?→?,)(x xF ? 结论: ?xR(x) (2) 前提: ?x(F(x)→(G(a)∧R(x))), xF(x) 结论:x(F(x)∧R(x)) 证明(1) ①)(x xF ? 前提引入 ②F(c) ①EI ③))())()((()(y R y G y F y x xF →∨?→? 前提引入 ④))())()(((y R y G y F y →∨? ①③假言推理 ⑤(F(c)∨G(c))→R(c)) ④UI ⑥F(c)∨G(c) ②附加 ⑦R(c) ⑤⑥假言推理 ⑧?xR(x) ⑦EG (2) ①?xF(x) 前提引入 ②F(c) ①EI ③?x(F(x)→(G(a)∧R(x))) 前提引入 ④F(c)→(G(a)∧R(c)) ③UI ⑤G(a)∧R(c) ②④假言推理 ⑥R(c) ⑤化简 ⑦F(c)∧R(c) ②⑥合取引入 ⑧ x(F(x)∧R(x))