习题一
1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明.
答：此命题是简单命题，其真值为1. （2）5 是无理数.
答：此命题是简单命题，其真值为1. （3） 3是素数或4是素数.
答：是命题，但不是简单命题，其真值为1. （4） 2x+ <3
5 答：不是命题.
（5） 你去图书馆吗？答：不是命题. （6） 2与3是偶数.
答：是命题，但不是简单命题，其真值为0. （7） 刘红与魏新是同学.
答：此命题是简单命题，其真值还不知道. （8） 这朵玫瑰花多美丽呀！答：不是命题. （9） 吸烟请到吸烟室去！答：不是命题. （10） 圆的面积等于半径的平方乘以π. 答：此命题是简单命题，其真值为1. （11） 只有6是偶数，3才能是2的倍数. 答：是命题，但不是简单命题，其真值为0. （12） 8是偶数的充分必要条件是8能被3整除. 答：是命题，但不是简单命题，其真值为0. （13） 2008年元旦下大雪.
答：此命题是简单命题，其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:（1）p：中国有四大发明. （2）p:
是无理数.
（7）p:刘红与魏新是同学.
（10）p:圆的面积等于半径的平方乘以π. （13）p:2008年元旦下大雪.
3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. （1）5 是有理数.
答：否定式：5是无理数. p：5 是有理数.q：5 是无理数.其否定式q的真值 为 1.
（2） 25 不是无理数.
答：否定式： 25 是有理数. p： 25 不是无理数. q： 25 是有理数. 其否定式q的 真值为 1.
（3）2.5是自然数.
答：否定式：2.5不是自然数. p：2.5是自然数. q：2.5不是自然数. 其否定式q 的真值为 1.
（4）ln1是整数.
答：否定式：ln1不是整数. p：ln1是整数. q：ln1不是整数. 其否定式q的真值为 1. 4.将下列命题符号化，并指出真值. （1）2与5都是素数
答：p：2是素数，q：5 是素数，符号化为p q∧ ，其真值为 1. （2）不但π是无理数，而且自然对数的底e也是无理数.
答：p：π是无理数，q：自然对数的底e是无理数，符号化为p q∧ ，其真值为 1. （3）虽然2是最小的素数，但2不是最小的自然数.
答：p：2是最小的素数，q：2是最小的自然数，符号化为p q∧? ，其真值为 1. （4）3是偶素数.
答：p：3是素数，q：3是偶数，符号化为p q∧ ，其真值为0. （5）4既不是素数，也不是偶数.
答：p：4是素数，q：4是偶数，符号化为? ∧?p q，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数.
（4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数.
答: p：2是偶数，q：3是偶数，r:3是素数，s:4 是偶数, t:5是偶数 (1)符号化: p q∨ ，其真值为1. (2)符号化：p r∨ ，其真值为1. (3)符号化：r t∨ ，其真值为0. (4)符号化：? ∨?q s，其真值为1. (5)符号化：? ∨?r s，其真值为0. 6.将下列命题符号化.
（1）小丽只能从筐里拿一个苹果或一个梨.
答：p：小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨，符号化为: p q∨ . （2）这学期，刘晓月只能选学英语或日语中的一门外语课.
答：p：刘晓月选学英语，q：刘晓月选学日语，符号化为: (? ∧ ∨ ∧?p q)(p q) . 7.设p：王冬生于 1971 年，q：王冬生于 1972 年，说明命题“王冬生于 1971 年或 1972
年”既可以化答:列出两种符号化的真值表： p 0 0 1 1 q 0 1 0 1 0 1 1 0 0 1 1 1 根据真值表,可以判断出,只有当p与q同时为真时两种符号化的表示才会有不同的真值,但结合命题可以发现,p与q不可能同时为真,故上述命题有两种符号化方式. 8.将下列命题符号化,并指出真值. （1）只要（2）如果（3）只有（4）除非（5）除非（6）答:设p: （1） （2） （3） （4） （5） 0 0 0 1 , 就有 , 则 , 才有 , 才有 , 否则 仅当 , 则
:
； ； ； ； ； .
; 设 q: 符号化 , 则
:
.
真值 1
（6） 1 9.设p：俄罗斯位于南半球,q：亚洲人口最多,将下面命题用自然语言表述,并指出其真值： （1）（2）（3）（4）（5）（6）（7）
； ；； ； ； ； ； .
答:根据题意,p为假命题,q为真命题. （1） （2） （3） （4） （5） （6） （7） 自然语言 只要俄罗斯位于南半球,亚洲人口就最多 只要亚洲人口最多,俄罗斯就位于南半球 只要俄罗斯不位于南半球,亚洲人口就最多 只要俄罗斯位于南半球，亚洲人口就不是最多 只要亚洲人口不是最多，俄罗斯就位于南半球 只要俄罗斯不位于南半球，亚洲人口就不是最多 只要亚洲人口不是最多，俄罗斯就不位于南半球 真值 1 0 1 1 1 0 1 10．设p：9是3的倍数,q：英国与土耳其相邻,将下面命题用自然语言表述,并指出真值： （1）（2）（3）（4）
； ； ； .
答:根据题意,p为真命题,q为假命题. （1） （2） （3）
自然语言 9是3的倍数当且仅当英语与土耳其相邻 9是3的倍数当且仅当英语与土耳其不相邻 9不是3的倍数当且仅当英语与土耳其相邻 真值 0 1 1 （4） 9不是3的倍数当且仅当英语与土耳其不相邻 0 11．将下列命题符号化,并给出各命题的真值： （1）若2+2=4,则地球是静止不动的； （2）若2+2=4,则地球是运动不止的； （3）若地球上没有树木,则人类不能生存；
（4）若地球上没有水,则答: （1） （2） （3） （4） 命题1 p:2+2=4 p:2+2=4 p:地球上有树木 p:地球上有树木 是无理数.
命题2 q:地球是静止不动的 符号化 真值 0 1 q:地球是静止不动的 q:人类能生存 q:人类能生存 1 1 12.将下列命题符号化,并给出各命题的真值： （1）2+2=4当且仅当3+3=6； （2）2+2=4的充要条件是3+36； （3）2+24与3+3=6互为充要条件； （4）若2+24,则3+3 6,反之亦然. 答:设p:2+2=4,q:3+3=6. (1) (2) (3) (4) 13.将下列命题符号化,并讨论各命题的真值： （1）若今天是星期一,则明天是星期二； （2）只有今天是星期一,明天才是星期二；
1 0 0 符号化 真值 1
（3）今天是星期一当且仅当明天是星期二； （4）若今天是星期一,则明天是星期三.
答:设p:今天是星期一,q:明天是星期二,r:明天是星期三. (1) (2) (3) (4) 14.将下列命题符号化： （1） 刘晓月跑得快,跳得高； （2） 老王是山东人或者河北人； （3） 因为天气冷,所以我穿了羽绒服； （4） 王欢与李乐组成一个小组； （5） 李欣与李末是兄弟； （6） 王强与刘威都学过法语； （7） 他一面吃饭,一面听音乐； （8） 如果天下大雨,他就乘班车上班； （9） 只有天下大雨,他才乘班车上班； （10） 除非天下大雨,否则他不乘班车上班； （11） 下雪路滑,他迟到了； （12） 2与4都是素数,这是不对的； （13） “2或4是素数,这是不对的”是不对的. 答: (1) (2) (3) (4) (5) 命题1 p:刘晓月跑得快 p:老王是山东人 p:天气冷 p:王欢与李乐组成一个小组 p:李辛与李末是兄弟 命题2 q:刘晓月跳得高 q:老王是河北人 q:我穿羽绒服 - - 命题3 - - - - - 符号化 p:王欢与李乐组成一个小组 p:李辛与李末是兄弟 若p为真,则真值为0;若p为假,则真值为1 必然为1 不会出现前句为真,后句为假的情况 符号化 真值讨论 不会出现前句为真,后句为假的情况
(6) (7) (8) (9) (10) (11) (12) (13) p:王强学过法语 p:他吃饭 p:天下大雨 p:天下大雨 p:天下大雨 p:下雪 p:2是素数 p:2是素数 q:刘威学过法语 q:他听音乐 q:他乘车上班 q:他乘车上班 q:他乘车上班 q:路滑 q:4是素数 q:4是素数 - - - - - r:他迟到了 - - 15.设p：2+3=5. q：大熊猫产在中国.
r:太阳从西方升起. 求下列符合命题的真值： （1）
（2）
（3）（4）
解：p真值为1，q真值为1，r真值为0. （1）0，（2）0，（3）0，（4）1
16.当p,q的真值为0,r,s的真值为1时,求下列各命题公式的真值： （1）（2）（3）（4）
解：（1）0，（2）0，（3）0，（4）1
17.判断下面一段论述是否为真：“是无理数.并且,如果3是无理数,则 外,只有6能被2整除,6才能被4整除.” 解：p : 是无理数 q: 3 是无理数 r:
也是无理数.另
是无理数s: 6能被2整除t：6能被4整除
符号化为: ，该式为重言式，所以论述为真。
18.在什么情况下,下面一段论述是真的:“说小王不会唱歌或小李不会跳舞是正确的,而说如果小王会唱歌,小李就会跳舞是不正确的.” 解：p:小王会唱歌。q:小李会跳舞。
真值为1.
真值为0.可得，p真值为1，q真值为0.
所以，小王会唱歌，小李不会跳舞。 19.用真值表判断下列公式的类型: （1）（2） （3）（4）（5）（6）（7）
.
p
解：（1） p 0 0 0 0 1 q 0 0 1 1 0 r 0 1 0 1 0 1 1 1 1 1
1 1 1 此式为重言式 （2） p 0 0 1 1 此式为可满足式 （3） q 0 0 1 1 此式为矛盾式 （4） p 0 0 1 1 此式为重言式 （5） p 0 0 0 0 1 0 1 1 1 0 1 1 1 1 q （p0 1 0 1 1 0 1 1 r 0 1 0 1 0 0 0 0 q 0 1 0 1 1 1 1 1 q 0 0 1 1 0 r 0 1 0 1 0 0 0 1 1 1
1 1 1 此式为可满足式 （6） p 0 0 0 0 1 1 1 1 此式为重言式 （7） p 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 q 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 r 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 r 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 s 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1
此式为可满足式
20.求下列公式的成真赋值： （1）（2）（3）（4）p 0 0 1 1 q 0 1 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1
解：
由真值表得：（1）的成真赋值是01，10,11（2）的成真赋值是00，10,11 （3）的成真赋值是00，01,10 （4）的成真赋值是01，10,11
21.求下列各公式的成假赋值： （1）（2）（3）p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1
解：
由真值表得：（1）的成假赋值是011 （2）的成假赋值是010,110 （3）的成假赋值是100,101
22.已知公式解：∵
是矛盾式，求公式 是矛盾式 ∴
成真和成假赋值.
也是矛盾式。
由此可得：该式无成真赋值。而成假赋值为：000,001,010,011,100,101,110,111
23.已知公式解：∵
是重言式,求公式 是重言式，∴
的成真和成假赋值.
也是重言式。
由此可得：该式无成假赋值。而成真赋值为：000,001,010,011,100,101,110,111
24.已知
的类型.
解：∵
是重言式，试判断公式 及
是重言式，而要使该式为重言式，其成真赋值只有
11，∴25.已知
的类型.
解：∵
都是重言式。
是矛盾式，试判断公式
及
是矛盾式，而要使该式为矛盾式，其成假赋值
只有00，∴都是重言式。
26. 已 知 是 重 言 式 ，
及
是 矛 盾 式 ， 试 判 断
的类型.
是矛盾式。 是重言式。
解：
27.设A、B都是含命题变量项p1,p2,…,pn的公式,证明:重言式.
是重言式当且仅当A和B都是
解： A 0 0 1 1 B 0 1 0 1 0 0 0 1 是重言式。
由真值表可得，当且仅当A和B都是重言式时，
28. 设A、B都是含命题变量项p1,p2,…,pn的公式,已知矛盾式的结论吗?为什么? 解： A 0 0 1 1 同样由真值表可得，
B 是矛盾式,能得出A和B都是
0 1 0 1 0 0 0 1 的成假赋值有00,01,10.所以无法得到A和B都是矛盾式。
29. 设A、B都是含命题变量项p1,p2,…,pn的公式,证明:是矛盾式. 解： A 0 0 1 1 B 是矛盾式当且仅当A和B都
0 1 0 1 0 1 1 1 是矛盾式。
由真值表可得，当且仅当A和B都是矛盾式时，
30. 设A、B都是含命题变量项p1,p2,…,pn的公式,已知重言式的结论吗?
是重言式,能得出A和B都是
解： A 0 0 1 1 由真值表可得
B 0 1 0 1 0 1 1 1 的成真赋值有01,10，11.所以无法得到A和B都是重言式。
习 题 二
1.设公式A p q= → ,B p q= ∧? ，用真值表验证公式A和B适合德摩根律：
p 0 0 1 1 q 0 1 0 1 A 1 1 0 1 ? ∨ ?? ∧?(A B) B 0 0 1 0 A B ? ∨(A B) 1 0 0 0 ? ∧?A B 1 0 0 0 2.公式A和B同题（1），用真值表验证公式A和B适合蕴涵等值式. p 0 0 1 1 成真赋值.
q 0 1 0 1 A 1 1 0 1 A B→ ?? ∨A B B 0 0 1 0 A B→ 0 0 1 0 ? ∨A B 0 0 1 0 3．用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出（1）? ∧ →(p q q)
答：原式=?? ∧ ∨( (p q q)
=?? ∨? ∨( p q q) = 0 是矛盾式.
)
4.用等值演算法证明下面等值式.
（1）
p? ∧ ∨ ∧?（p q p q）（ ）答：
右式= p q q∧ ∨?（ ）= p∧1= p （2）
((p q→ ∧ → ? → ∧) (p r)) (p (q r))
答：右式= ? ∨ ∧p q r( )=(? ∨ ∧ ? ∨p q) ( p
r)= (p q p r→ ∧ →) ( )) =左式
（3）
? ? ? ∨ ∧? ∧(p q) (p q) (p q) 答：
左式= ?? ∨ ∨? ∨?( p q) (p q)
= (p∨ ? ∧ ∧ ? ∨ ? ∧( p q)) ( q ( p q)) = (p q∨ ∧? ∧) (p q)
（4）
(p q∧? ∨ ? ∧ ? ∨ ∧? ∧) ( p q) (p
q) (p q) 答：左式= (p∨ ? ∧ ∧ ? ∨ ? ∧( p q)) ( q ( p q))
= (p q∨ ∧? ∧) (p q)
5.求下列公式的主析取范式，并求成真赋值： 1） (?p→q) → (?q∨p) 答：
(? → → ? ∨ = ∨ → ? ∨ =? ∨ ∨ ? ∨p q) ( q p) (p q) ( q p) (p q) = (? ∧? ∨ ? ∧ ∨? ∨ ∧ ∨?p q) ( q p p( )) (p q q( )
= (p q∧ ∨ ∨? ∨ ? ∧? = ∨ ∨) (p p)
( p q m m m) 0
2
3
成真赋值为00,10,11.
2） ?(p→q) ∧q∧r 答：? → ∧ ∧ =?? ∨ ∧ ∧ = ∧? ∧ ∧=(p q q r) ( p q q r p q
q) 0
所以为矛盾式。 3） (p q r∨ ∧ → ∨ ∨(
)) (p q r)
( q p)
（
（（
答
(p q r∨ ∧ → ∨ ∨ =? ∨ ∧ ∨ ∨ ∨ = ? ∧? ∧ ∨ ∨ ∨( (p q r) ( p (q r)) (p q r) = (? ∧ ? ∨? ∨ ∨ ∨ = ? ∧? ∨ ? ∧? ∨ ∨ ∨p ( q r))
)) (p q r) ( p q)
(p q r) (p q r( ))( p r)
(p q r)
)
(
= (? ∧? ∧ ∨? ∨ ? ∧ ∨? ∧? ∨ ∧ ∨? ∧ ∨?p q r r( )( p q q( )) ∨ ∨? ∧ ∧ ∨? ∨((p p q r r)
(
) r) (p q q r r(
)
)
))((p p q q r∨? ∧ ∨? ∧) (
= (? ∧? ∧ ∨ ? ∧?p q r) ( p q r∧? ∨ ? ∧ ∧? ∨ ∧ ∧ ∨ ∧? ∧ ∨)( p q r) (p q r) (p q r) (p q r∧ ∧? ∨ ∧? ∧? ∨ ? ∧ ∧ = ∨ ∨ ∨ ∨ ∨ ∨ ∨) (p q r) ( p q r m m m m m m m m)
0
1
2
3
4
5
6
7 所以是重言式，真值为
000,001,010,011,100,101,110,111.
6.求下列公式的主析取范式，并求成真赋值： （1）
?(q→?p)∧?p 答：? →? ∧? =?? ∨? ∧? = ∧ ∧? =(q p) p ( q p) p q
p p 0，是矛盾式，所有赋值均为成真赋值。
（2）
(p∧q)∨ (?p∨r) 答：(p q∧ ∨ ? ∨ = ∨? ∨ ∧ ∨? ∨ = ? ∨ ∨ =) ( p
)
( p q r M)
4，成假赋值为
r) (p p r q p r) (
（3）
100.
(p→ (p∨q))∨r 答： (p→ ∨ ∨ = ? ∨ ∨ ∨ = ? ∨ ∨ ∨ =(p q r)) ( p p q
r( )) ( p p q r 1，所以为重言式。所
有赋值均为成真赋值。
7.求下列公式的主析取范式，再用主析取范式求主合取范式： （1） (p∧q)∨r 答：(p q r p q r r∧ ∨ = ∧ ∧ ∨? ∨) (
( ))
((p p q q r∨? ∧ ∨? ∧) ( ) )
)
)
= (p q r r∧ ∧ ∨? ∨( ))((p p q q r∨? ∧ ∨? ∧) (
= 0 ∧ 2 ∧ 4
= (p q r∧ ∧ ∨ ∧ ∧? ∨ ∧? ∧ ∨ ? ∧ ∧ ∨ ? ∧? ∧)(p q r) (p q r) ( p q r) ( p q r) =m m m m m M M M1 ∨ ∨ ∨ ∨3
5
6
7
（2） (p→q)∧ (q→r) 答：
(p q q r→ ∧ → = ? ∨ ∧ ? ∨ = ? ∧? ∨ ? ∧ ∨ ∧? ∨ ∧) q q q r) ( ) ( ) = (? ∧? ∧ ∨? ∨ ? ∧ ∨? ∧ ∨p q r r( )) =m m m m M M M M0∨ ∨ ∨13
（1）
( ) )
)( p q) ( q r) ( p q)
)
( p r
( p q q r( ((p p q r∨? ∧ ∧)
= (? ∧? ∧ ∨ ? ∧? ∧? ∨ ? ∧ ∧ ∨ ∧ ∧p q r) ( p q r) ( p q r) (p q r)
7
= 2 ∨ 4 ∨ 5 ∨ 6
8.求下列公式的主合取范式，再用主合取范式求主析取范式：
(p∧q) →q 答： (p q∧ → =? ∧ ∨ =? ∨? ∨ = = ∨ ∨ ∨) q
1
2
3
(p q q p q q) 1 m m m m0
为重言式。 （2）
(p q? →) r 答：(p q? → =? ∧ ∨ ? ∧? ∨ = ? ∧ ∧??
( p q r)) ( (p q) ( p q r))
(p q r)) ( p q r) (p q r M M) = 0
∧? ∨) r ((p q)
= ((? ∨? ∧ ∨ ∨ = ? ∨? ∨ ∧ ∨ ∨p q) =m m m m m m1 ∨ ∨ ∨ ∨ ∨2
（3）
7
∧ 6
3
4
5
? → ∧ ∧(r p p q) 答：? → ∧ ∧ = ∧? ∧ ∧(r p p q r p p q)
=M M M M M M M M0 ∧ ∧1
= 0
2
∧ 3 ∧ 4 ∧ 5 ∧ 6 ∧ 7
因此为矛盾式.
9.用真值表求下面的公式的主析取范式. （1） (p q∨ ∨ ? ∧) ( p r) 答：公式的真值表如下：
p q r ?p p q∨ ? ∧p r (p q∨ ∨ ? ∧) ( p r) 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 1 0 0 0 0
其成真赋值为 001,010,011,100,101,110,111，所以其主析取范式为
m m m m m m m1 ∨ ∨ ∨ ∨ ∨ ∨2
（2） (p q→ → ??)
下：
3 4 5 6
7
(p q) 答：公式的真值表如
?q 1 0 1 0 p q→ 1 1 0 1 p 0 0 1 1 q 0 1 0 1 p??q 0 1 1 0 (p q→ → ??) 0 1 1 0 (p q
(p q→ → ?? = ∧? ∨ ? ∨? ∧ ∨) (p q) (p q) (( p q) (p q))
= (? ∧ ∨ ∧?p q) (p q)
故其成真赋值为 001，010. 所以其主析取范式为m m1 ∨ 2 . 10.用真值表求下面公式的主合取范式. （1）
(p q r∧ ∨) 答：(p q r p
r q r∧ ∨ = ∨ ∧ ∨) ( ) ( )
=M M M0 ∧ 2 ∧ 4
（2）
(p q q r→ ∧ →) ( ) 答：
(p q q r→ ∧ → = ? ∨ ∧ ? ∨) ( ) ( p q) ( q r)
=M M M M2 ∧ 4 ∧ 5 ∧ 6
11.用真值表求下面公式的主析取范式和主合取范式. （1）(p
q r∨ ∧)
（2）p→ ∨ ∨(p q r) （3）?
→? ∧?(q p) p p q r (p q r∨ ∧) p→ ∨ ∨(p q r) ? →? ∧?(q p) p
0 0 0 0 1 0
0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 答：（1）由真值表可得成真赋值为 011,101,111，故主析取范式为m m m3 ∨ ∨57 ，主合
取范式为M M M M M0 ∧ ∧12 ∧ 4 ∧ 6
（2）由真值表可得无成假赋值，故主析取范式为
m m m m m m m m0 ∨ ∨ ∨ ∨ ∨ ∨ ∨1
2 3 4 5 6
7 ，主合取范式为 1.
（3）由真值表可得无成真赋值，故主析取范式为 0，主合取范式为 M
M M M0 ∧ ∧1
2
∧ 3.
12.已知公式A含 3 个命题变项pqr, , ，并且它的成真赋值为 000，011，110，求A的主合取范式和主析取范式.
答：由题意得，A的主主合取范式为M M M M M1 ∧ 2 ∧ 4 ∧ 5 ∧ 7 ，主析取范式
m m m0 ∨ ∨3 6 .
13. 已知公式A含 3 个命题变项pqr, , ，并且它的成真赋值为 000，011，110，求A的主合取范式和主析取范式. 答：由题意得，A的主主合取范式为M M M M2 ∧ 3 ∧ 6 ∧ 7 ，主析取范式
m m m m0 ∨ ∨ ∨1
5
7 .
14.已知公式A含n个命题变相p p1, 2,......, pn，并且无成假赋值，求A的主合取范式. 答：A的主合取范式为 1.. 15.用主析取范式判断下列公式是否等值： （1）
(p q r→ →) 与q→
→(p r) 答： (p q→ → = ∧? ∨) r p q r( )
=m m m m m1 ∨ ∨ ∨ ∨3 4
5
7
q→ → =? ∨? ∨(p r) p q r
=m m m m m m m0 ∨ ∨ ∨ ∨ ∨ ∨1
2
3
7 所以上述公式不等值.
（2）
? ∧(p q) 与? ∨(p q) 答：
? ∧ =? ∨?(p q)
p q
=m m m0 ∨ ∨1 2
? ∨ =? ∧?(p q) p q
=m0
16.用主合取范式判断下列公式是否等值. （1） p→ →(q r)与? ∧ ∨(p q r) 答：p→
→ =(q r M)
6
? ∧ ∨(p q r M)=
6
（2） p→ →(q r)与(p q→ →) r
答：p→ → =(q r M) 6
(p q→ →) r M M M= 0 ∧ 2 ∧ 6
17.将下列公式化成与之等值且仅含{?∧∨, ,
}中联结词的公式：
（1） ? → ? ∧(p q( (q r))) 答：? → ? ∧(p (q
(q r))) =?? ∨ ? ∧( p q( (q r)))
=p∧?? ∧((q r))
=p∧? ? ∨ ∧ ∧ ∨? ∧(( q q r( 4
5
)) (q (q r)))
（2） (p q∧ ∨?) r 答：(p q∧ ∨?) r，原式已满足题目要求.
（3） p? ?(q r) 答：p? ? = → ? ∧ ? →(q r)
(p (q r)) (( r) p)
= (? ∨ ? ∨ ∧ ∨?p (( q r q r)
()))∧ ? ? ∨ ∧ ∨? ∨( (( q r q r)
( )) p)
18.将下列公式化成与之等值且仅含{?∧, }中联结词的公式：（1）p q r∧? ∧? 答：此公式已经符合题目要求. （2） (p r q? ∧) 答：(p r q? ∧ =) ((p
r r p q→ ∧ →) ( ))∧
= ((? ∨ ∧ ? ∨p r)( r p q))∧
= ( (? ∧? ∧? ∧? ∧p r) (r p q))
（3） (p q r q→ ∧ ∨( )) 答： (p→ ∧ ∨
= ? ∨ ∧ ∨(q r q)) ( p q r( )) p
=? ∧? ∧ ∨(p (q r)) p
=? ∧? ∧ ∧?((p (q r))p)
将下列公式化成与之等值且仅含{?∨,
}中联结词的公式.
1）
(? ∨? ∧p q r) 答： (? ∨? ∧
=??? ∨? ∨?p q r) ( ( p q) r)
2）
(p→ ∧? ∧ ∧(q p q r)) 答： (p→
∧? ∧ ∧ =??? ∨?? ∨(q p q r)) ( ( p ( q p))∨? ∨?q r)
19.（（
（3）p q r∧ ∧? 答：p q r∧ ∧?
=?? ∨? ∨( p q r)
20．将下列公式化成与之等值且仅含{?，→}中联结词的公式：
（1） (p∧q)∨r（2）(p→?q)∧r（3）(p∧q) ?r 答： (p q r∧ ∨ ??? ∨?
∨ ?? →? ∨ ? →? →) ( p q r) (p q r) (p q r)
(2)(p→? ∧q r) 答： (p→? ∧ ??? →? ∨? ?? →? →?q r) ( (p
q) r) ((p q) r)
(3)(p q∧ ?) r 答：(p q∧ ? ? ?? ∨? → ∧ →?? ∨?) r
( ( p q) r r)
21．证明：
( ( p q))
????? ∨? → ∨? →?? ∨?( ( ( p q r) )
?? ? →? → →? →? →?(( (p
(r ( p q)))
(r (p q)))
q r) )
（1） (p↑q) ? (q↑p)，(p↓q) ? (q↓p).
（2） (p↑ (q↑r))? ((p↑q) ↑r)，(p↓ (q↓r))? ((p↓q) ↓r). 证明：(1)p q↑ ?? ∧ ?? ∧ ? ↑(p q)
(q p) q p； p q↓ ?? ∨ ?? ∨ ?
1,(p q r↑ ↑
↓(p q) (q p) q p (2)令p= 0,q= 0,r=1则 p q r↑ ↑ =( )
1,(p q r↓ ↓ =)
0.，可知
=) 0，p q r↓ ↓ =( )
(p q r↑ ↑ ?( ))((p q r p q r↑ ↑) ) (， ↓ ↓ ?()) (( p q r↓ ↓) ).
22.从表2.6中，找出与下列公式等值的真值函数： （1）p↑q
（2）p↓q
（3）(p∧?q)∨ (?p∧q) （4）?(p→q)
答： (1)F14(2);(2)F8(2) ;(3)F6(2) ;(4)F2(2) 23．设A、B、C为任意的命题公式，证明： （1）等值关系有自反性：A?A
（2）等值关系有对称性：若A?B,则B?A
（3）等值关系有传递性：若A?B且B?C，则A?C 答：(1)A A? ? → ∧ → ? →
?? ∨ ?(A A A A)
( ) A A A A 1
(2)B A? ? ? ∨ ∧ ? ∨ ? ? ∨ ∧ ? ∨ ? ?( B A)( A B) ( A B) ( B A) A B
(3)
若A B B C? 且 ? ? → ∧ → ∧ → ∧ →(A B B A B C C B) ( )
( ) (
? → ∧ → ∧ → ∧ → ? → ∧ →(A B B C C B B A)( )
( )
(
)
( )
? ?A C 即A C?
24．设A、B为任意的命题公式，证明：? ??A B当且仅当A B? 答：?
?? ? ∨? ∧ ∨? ? → ∧ → ? ?A B (A B B A) ( ) (A B B A)
(
)
A B. 因此? ??A B当且仅当A B? 。
25．设A、B、C为任意的命题公式，（1）若A∨C?B∨C，举例说明A?B不一定成立。（2）若A∧C?B∧C，举例说明A?B不一定成立。由（1）、（2）可知，联结词 ∨与∧不满足消去率。
答：(1)设A p B q= ∨1, = ∧0,C r= ∨1，则A C∨ = ? ∨ =1 B C 1
，但
A B=1, = 0，二者不等价。
（2）设A p B q= ∨1, = ∧0,C r= ∨0，则A C∧ = ? ∧ =0B C 0，但
A B=1, = 0，二者不等价。
26．在上题（25）中，若已知A∨C?B∨C，在什么条件下，A?B一定成立？又若已知A∧C?B∧C，在什么条件下，A?B一定成立？解：若C= 0;则A C B C∨ ? ∨ ，A
B? 一定成立。若C=1；则A C B C∧ ? ∧ ，A B? 一定成立。
27．某电路中有一个灯泡和三个开关A、B、C。已知在且仅在下述四种情况下灯亮：
)
(A C C A)
（1）C的扳键向上，A、B的扳键向下。（2）A的扳键向上，B、C的扳键向下。（3）B、 C的扳键向上，A的扳键向下。（4）A、B的扳键向上，C的扳键向下。设F为1表示灯亮，p、q、r分别表示A、B、C的扳键向上。 （a） 求F的主析取范式。
（b）在联结词完备集{?，∧}上构造F。（c）在联结词完备集{?，→，?}上构造F。
答：（a）由题意知，灯亮的情况如下：
F? ∧? ∧? ∨ ? ∧? ∧ ∨ ? ∧ ∧ ∨ ∧ ∧?(p q r)( p q r) ( p q r) (p q r) ?m m m m1 ∨ ∨ ∨3
4
6
（b） F? ∧? ∧? ∨ ? ∧? ∧ ∨ ? ∧ ∧ ∨ ∧ ∧?(p q r) ( p q r) ( p q r) (p
q r)
???? ∧ ∧? ∧?( ( p r) (p r))
（c） F?? ∧? ∧p q r
28.一个排队线路，输入为 A、B、C，其输出分别为
F
A 、
F
B 、
F
C .本线路中，在同一
时间只能有一个信号通过，若同时有两个或两个以上信号申请输出时，则按 A、B、C 的顺序
输出，写出FA 、FB 、 FC 在联结词完备集{? ∨， }中的表达式. 答：p：A输入，q：B输入，
r：C输入.有题意可得：
FA? ∧? ∧? ∨ ∧? ∧ ∨ ∧ ∧? ∨ ∧ ∧(p q r) (p q r) (p q r) (p q r) ? ∧? ∨ ∧ ?(p q) (p q) p
FB ? ? ∧ ∧? ∨ ? ∧ ∧ ?? ∧( p q r)( p q r) FC ?? ∧ ∧p q r
29.在某班班委成员的选举中，已知王小红、李强、丁金生 3 位同学被选进了班委会.
p q
该班的甲、乙、丙三名学生预言：甲说：王小红为班长，李强为生活委员.
乙说：丁金生为班长，王小红为生活委员. 丙说：李强为班长，王小红为学习委员.
班委会分工名单公布后发现，甲、乙、丙三人都恰好猜对了一半.问王小红、李强、丁金生各任何职（用等值等演求解）？
答：设p：王小红为班长，q：李强为生活委员 r：丁金生为班长，s：王小红为生活委
员 t：李强为班长，w：王小红为学习委员
由题意得，p、q有且只有一个为真，r、s有且只有一个为真，t、w有且只有一个 为真.
若p为真，则q为假，那么r为假，则s为真，这样p与s矛盾，因此这种假设行不通. 若p为假，则q为真，那么t为假，则w为真，则s为假，所以r为真，因此王小红、 李强、丁金生的职位分别是：学习委员、生活委员、班长.
30.某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件： （1）若赵去，钱也去. （2）李、周两人中必有一人去. （3）钱、孙两人中去且仅去一人. （4）孙、李两人同去或同不去. （5）若周去，则赵、钱也同去.
用等值演算法分析该公司如何选派他们出国？答：设p：派赵去，q：派钱去，r：派李去，
s：派孙去，t：派周去首先以条件（2）为基础，有三种情况：
1若周去，李不去，由条件（5）得则赵、钱同去，由条件（3）得那么孙不去，符合
5 个条件，即p q r s t∧ ∧? ∧? ∧ .
2若李去，周不去，由条件（4）得则孙去，从而由条件（3）得钱不去，而由条件（1）得赵也不去，即? ∧? ∧ ∧ ∧?p q r s t.
3若周、李都去，那么由条件（4）得则孙去，由条件（5）得赵、钱都去，这样孙和钱都去，与条件（3）矛盾，因此这种情况不存在.
习题三
1.从日常生活或数学中的各种推理中，构造两个满足附加律的推理定律，并将它们符号化。例如：“若2是偶数，则2是偶数或3是奇数”。令p:2是偶数，q:3是奇数，则该附加律符号为p?p∨q。 解：（1）“若3是素数，则3是素数或5是奇数”。令p：3是素数，q：5是奇数，则该附加律符号化为p? p∨q
（2）“若明天不下雨，则明天不下雨或明天下雪”。令p：明天下雨，q：明天下雪，则该附加律符号化为?p??p∨q。
2.从日常生活或数学的各种推理中，构造两个满足化简律的推理定律，并将它们符号化。例如：“我去过海南岛和新疆，所以我去过海南岛”。令p：我去过海南岛，q:我去过新疆，则该化简律符号化为p∧q?p。
解：（1）“6能被2和3整除，所以6能被2整除”。令p：6能被2整除，p：6能被2整除， q：6能被3整除，则该化简律符号化为p∧q?p。
（2）“小明会弹琴和跳舞，所以小明会弹琴”。令p：小明会弹琴，q：小明会跳舞，则该化简律符号化为p∧q?p。
3.随意构造三个满足假言推理定律的推理，并将它们符号化。例如：“如果2是素数，则雪是黑色的，2是素数，所以雪是黑色的”。令p:2是素数，q：雪是黑色的，该假言推理定律符号化为 (p→q)∧p?q。
解：（1）“如果小明会跳舞，则他会弹琴，小明会跳舞，所以他会弹琴”。 令p：小明会弹琴，q：小明会跳舞，该假言推理定律符号化为 (p→q)∧p?q。
（2） “如果3是奇数，则明天下雨，3是奇数，所以明天下雨”。令p：3是奇数，q：明天下雨，该假言推理定律符号化为 (p→q)∧p?q。
（3） “如果明天晴天，则小明去游泳，明天晴天，所以小明去游泳”。令p：明天晴天， q：小明去游泳，该假言推理定律符号化为 (p→q)∧p?q。
4.参照1,2,3题，请构造满足拒取式、析取三段论、假言三段论、等价三段论、构造性二难等推理定律的实例各一个，并将它们符号化。
解：（1）拒取式：“明天是周末，小明就休息，小明没有休息，所以明天不是周末”。令p：明天周末，q：小明休息。该拒取式定律符号化为(p→q)∧?q??p。
（2） 析取三段论：“小明会弹琴或跳舞，小明不会跳舞，所以小明会弹琴”。令p：
q
小明会弹琴，q：小明会跳舞，该析取三段式定律符号化为(p∨)∧?q? p。
（3） 假言三段论：“明天要是周末，小明明天休息，小明要是明天休息，他就会去游泳，所以，明天要是周末，小明就去游泳”。令p：明天是周末，q：小明明天休息，t：小明去游泳，该假言三段论定律符号化为(p→q)∧(q→t)? p→t。
（4） 等价三段论：“2是素数当且仅当3是奇数，3是奇数当且仅当4是偶数，所以2 是素数当且仅当4是偶数”。令p：2是素数，q：3是奇数，t：4是偶数，该等价三段论定
律符号化为
(p?q)∧(q?t)? p?t。
（5） 构造性二难：“明天是周一，小明就要上学，明天是周末，小明就要去游泳，明天是周末或者周一，所以小明去上学或者去游泳”。令p：明天是周一，q小明要上学，s：明天 是 周 末 ， t ： 小 明 要 去 游 泳 ， 该 构 造 性 二 难 定 律 符 号 化 为
(p→q)∧(s→t)∧(p∨s)? (q∨t)。
（6） 破坏性二难：“明天是周一，小明就要上学，明天是周末，小明就要去游泳，小明没有去上学或者小明没有去游泳，所以明天不是周一或者明天不是周末”。令p：明天是周一，q小明要上学，s：明天是周末，t：小明要去游泳，该构造性二难定律符号化为
(p→q)∧(s→t)∧(?q∨?t)? (?p∨?s)。
5.分别写出德摩定律、吸收律所产生的推理定律（每个等值式产生两条推理定律）。解：的摩定律1：?(A∨B)??A∧?B
产生的推理定律：（1）
?
(A∨B)??A∧?B （2）?A∧?B??(A∨B) 的摩定
?
律2：?(A∧B)??A∨?B 产生的推理定律：（1）
(A∧B)??A∨?B （2）
∨
?A∨?B??(A∧B) 吸收律1：A(A∧B)?A 产生的推理定律：（1）∧
A∨(A∧B)?A （2）A?A∨(A∧B) 吸收律2：A(A∨B)?A
产生的推理定律：（1）A
∧
(A∨B)?A （2）A?A(A∨B)
∧
6.判断下列推理是否正确。先将简单命题符号化，再写出前提、结论、推理的形式结构（以蕴涵式的形式给出）和判断过程（至少给出两种判断方法）： （1）若今天是星期一，则明天是星期三。今天是星期一，所以明天是星期三。 （2）若今天是星期一，则明天是星期二。明天是星期二，所以今天是星期一。 （3）若今天是星期一，则明天是星期三。明天不是星期三，所以今天不是星期一。 （4）若今天是星期一，则明天是星期二。今天不是星期一，所以明天不是星期二。 （5）若今天是星期一，则明天是星期二或星期三。
（6）今天是星期一当且仅当明天是星期三。今天不是星期一，所以明天不是星期三。
解：（1）设p：今天是星期一，q：明天是星期三，推理的形式结构为(p→判断该推理是否正确，即判断(p→
q
)∧p→q，
q
)∧p→q是否为重言式，不难看出，该式满足假言推理
定律，所以推理正确。
（2） 设p：今天是星期一，q：明天是星期二，推理的形式结构为(p→
q
)∧q→
p。
(p→q)∧q→p ? (?p∨q)∧q→p
等值演算法：
，可见该式不是重言式，所以推理不正确。
?q→p ? p∨?q
(p→q)∧q→p
? (?p∨q)∧q→ p
主析取范式法：?q→p
，从而可知不是重言式，故推理不正确。
? p∨?q
?M1 ?m0 ∨m2 ∨m3
（3） 设p：今天是星期一，q：明天是星期三，推理的形式结构为
(p→q)∧?q→?p，判断该推理是否正确，即判断(p→)∧?q→?p是否为重言式，
不难看出，该式满足拒取式定律，所以推理正确。
q
（4） 设p：今天是星期一，q：明天是星期二，推理的形式结构为
(p→q)∧?p→?q。
(p→q)∧?p→?q
? (?p∨q)∧?p→?q 等值演算法：? ((?p∧?p)∨(q∧?p)) →?q ，
可见该式不是重言式，所以推理不
??p→?q ? p∨?q
正确。
(p→q)∧?p→?q
? (?p∨q)∧?p→?q ? ((?p∧?p)∨(q∧?p)) →?q
主析取范式法：
，从而可知不是重言式，故推理不正确。
??p→?q
? p∨?q
?M1 ?m0 ∨m2 ∨m3
（5）设p：今天是星期一，q：明天是星期二，r：明天是星期三。推理的形式结构为
p→q∨r。 p→ (q∨r) ??p∨q∨r
?M4 ?m0 ∨m1 ∨m2 ∨m3 ∨m4 ∨m5 ∨m6 ∨m7 ，由此可知p→ (q∨s) 不为重言式，
故推理不正确。显然该式不是重言式，所以推理不正确。
（6）设p：今天是星期一，r：明天是星期三，推理的形式结构为 (p?r)∧?p→?r。
(p?r) ∧?p→?r
??((p→r) ∧ (r→p) ∧?p)∨?r ??(?p∨r)∨?(?r∨p)∨p∨?r
，由此可知不为重言式，故推理不正确。
? (p∧?r)∨ (?p∧r)∨p∨?r ?p∨ (?p∧r)∨?r?p ?m4 ∨m5 ∨m6 ∨m7
7.在下面各推理中没给出结论。请对于每个推理前提给出两个结论，使其中之一是有效的， 而另一个不是有效的： （1）前提：p→q，q→r （2）前提：(p∧q) →r，?r，q （3）前提：p→ (q→r) ，p，q
解：（1）结论1：p→r为有效的（假言三段论）结论2：p为无效的。
q
（2） 结论1：(p∧)是有效的（拒取式）结论2：p是无效
的 （3）
结论1： (q→r)是有效的（假言三段论）结论2：r是无
?
效的
8.在下面各推理中没给出结论，请对于每个推理前提给出两个结论，使其中之一是有效的，而另一个不是有效的。
（1）只有天气热，我才去游泳。我正在游泳，所以…… （2）只有天气热，我就去游泳。我没去游泳，所以……
（3）除非天气热并且我有时间，我才去游泳。天气不热或我没时间，所以…… 解： （1）设p：天气热，q：我去游泳前提：q→p,q
结论1：p，有效结论（假言推理）结论2：?p，无效结论 （2）设p：天气热，q：我去游泳。
前提：p→q,?q
结论1：?p，有效结论（拒取式）结论2：p，无效结论 （3）设p：天气热，q：我有时间，r：我去游泳。
前提：r→ (p∧q),?p∨?q
结论1：?r，有效结论（拒取式）结论2：r，无效结论。
9.用三种方法（真值表法，等值演算法，主析取范式法）证明下面推理是正确的：若a是奇数，则a不能被2整除。若a是偶数，则a能被2整除。因此，如果a是偶数，则 a不是奇数。
解：设p：a是奇数，q：a能被2整除，r：a是偶数。
∧→
推理的形式结构为(p→?q)(r→q)(r→?p)（*）。下面用三种方法证明该式为重 言式：
（1） 真值表法：
p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 (p→?q) ∧ (r→q) 0 1 0 0 0 1 1 1 (r→?p) 1 1 1 1 1 0 1 0 * 1 1 1 1 1 1 1 1 由真值表可知（*）为重言式，故推理是正确的。 （2） 等值演算法：
(p→?q)∧(r→q)→(r→?p)
? (?p∨?q)∧(?r∨q)→ (?r∨?p) ? (p∧q)∨(?q∧r)∨?p∨?r
? ((p∧q)∨?p)∨((?q∧r)∨?r)(交换律，结合律) ? (?p∨q)∨(?q∨?r) ??p∨(q∨?q)∨?r
? 1
（3） 构造证明法：
前提：
(p→?q),(r→q) (r→?p)
前提引入 ①置换 前提引入 ③②假言三段论
结论：
证明： ①p→?q ②q→?p ③r→q ④r→?p 主析取范式法
由方法2可以得知推理的形式结构（*）的主析取范式为
(*)?m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7，则（*）为重言式，推理正确。
10.用两种方法（真值表法，主析取范式法）证明下面推理不正确：
如果a,b两数之积是负数，则a,b之中恰有一个是负数。a,b两数之积不是负数，所以a,b 中无负数。真值表法： p q r A (q r∧? ∨ ? ∧)( q r) p→ ∧? ∨ ? ∧(q r)( q r) ? ∧?q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 推理不正确 主析取范式法：
(p→ ∧? ∨ ? ∧ ∨ ? ∧ ∧? → ? ∧?((q r)( q r)) ( q r)) p) ( q r) ? ? ∨ ∧? ∨ ? ∧ ∧? → ? ∧?( p q r( ) ( q r) ?? → ? ∧?p ( q r) ? ∨ ? ∧?p ( q r) ? ∨ ∨ ∨ ∨m m m m m0 4
5
6
7
0 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 p ( q r))
由于主析取范式只含有5个极小项，所以（3.8）不是重言式，推理不正确。 11.填充下面推理证明中没有写出的推理规则。 前提：?p∨q，?q∨r，r→s，p
结论：s 证明: ①p ②?p∨q ③q ④?q∨r ⑤r
前提引入 前提引入 析取三段论 前提引入 析取三段论 前提引入
⑥r→s ⑦s 假言推理
12.填充下面推理证明中没有写出的推理规则。 前提：p→ (q→r)，q→ (r→s) 结论：
(p∧q) →s
证明： ①p∧q ②p ③q
④p→ (q→r) ⑤q→r ⑥r
⑦q→ (r→s) ⑧r→s ⑨s
附加前提引入 化简规则 化简规则 前提引入 前提引入 ③⑤假言推理 前提引入 ③⑦假言推理 ⑥⑧假言推理
13.前提：?(p→q)∧q，p∨q，r→s 结论1：r 结论2：
s 结论3：r∨s
（1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。 （2）证明从此前提出发，推任何结论的推理都是正确的。 （1） 证明：结论1：
( (? → ∧ ∧ ∨ ∧ → →p q q) ) (p q r s) ( ) r
? ∧? ∧ ∧ ∨ ∧ → →(p q q) (p q r s) ( ) r ? ∧ ∨ ∧ → →0 (p q r s) ( ) r ? →0 r ?1
结论2：
( (? → ∧ ∧ ∨ ∧ → →p q q) ) (p q r s) ( ) s
? ∧? ∧ ∧ ∨ ∧ → →(p q q) (p q r s) ( ) s ? ∧ ∨ ∧ → →0 (p q r s) ( ) s ? →0 s ?1
结论3：
( (? → ∧ ∧ ∨ ∧ → → ∨p q q) ) (p q r s) ( ? ∧? ∧ ∧ ∨ ∧ → → ∨(p q q) (p q r s) ( ) r s
) r s
? ∧ ∨ ∧ → → ∨0 (p q r s) ( ) r s ? → ∨0 r s ?1
（2） 证明：设任何可能的结论为*,
则：
( (? → ∧ ∧ ∨ ∧ → →p q q) ) (p q r s) ? ∧? ∧ ∧ ∨ ∧ → →(p q q) (p q r s) () * ? ∧ ∨ ∧ → →0 (p q r s) ( ) *
? →0 * ?1
14.在自然系统p中构造下面推理的证明： （1）前提：p→ (q→r)，p，q 结论：r∨s （2）前提：p→q，?(q∧r)，r 结论：?p （3）前提：p→q 结论：p→ (p∧q) （4）前提：p→q，q→s，s→t，t∧r 结论：
p∧q
（5）前提：p→r，q→s，s→tt∧r 结论：r∧s （6）前提：?p∨r，?q∨sp∧q 结论：t→
(r∨s)
（1） 证明
（1） p→ →(q r) 前提引入
（2） p 前提引入 （3）q r→ （1）（2）假言推理 （4）q 前提引入 （5）r (3)(4)假言推理 （6）r s∨
（5）附加
( ) *
（2） 证明
（1）? ∧(q r) （2）? ∨?q r （3）r 前提引入
（1）置换
前提引入 （4）?q （5）p q→ （6）?p
（3） 证明
（1）p q→ （2）? ∨p q （3） (? ∨ ∧ ? ∨p q)
（4） ? ∨ ∧p q p( )
（5）p→ ∧(p q) （4） 证明
（1） (s t t s→ ∧ →) （2）t s→ （3）t r→ （4）t r∧ （5）t （6）s （7）q s?
（8） (q s s q→ ∧ →) （9）s q→ （10） q （11） q p→ （12） p
（13）
p q∧
（5） 证明
（1）p q∧
（2）p （3）q （4）p r→ （5）r （6）q s→ （7）s （8）r s∧
（6） 证明
（1）p q∧
（2）p （3）q
（2）（3）析取三段论
前提引入 （4）（5）拒取式 前提引入 （1）置换
( p p) （2）置换 （3）置换 （4）置换
( ) 前提引入
（1）置换 （2）换件 前提引入 （4）化简
（3）（5）假言推理前提引入
( ) （7）置换
（8）化简 （6）（9）假言推理 前提引入
（10）（11）假言推理 （10）（12）合取 前提引入 （1）化简 （1）化简 前提引入
（2）（4）假言推理 前提引入
（3）（6）假言推理 （5）（7）合取 前提引入 （1）化简 （1）化简
（4）? ∨p r （5）r （6）? ∨q s （7）s （8）r s∧
前提引入
（2）（4）析取三段论 前提引入
（3）（6）析取三段论
（5）（7）合取
（9）? ∨ ∧t r s( ) （8）附加
（9）置换 （10） t→ ∧(r s)
15.在自然推里系统p中用附加前提法证明下面各推理： （1）前提：p→ (q→r)，s→p，q 结论：s→r （2）前提：(p∨q) → (r∧s) ，(s∨t) →u 结论：
p→u
（1） 证明 （1）s
附加前提引入 前提引入
（1）（2）假言推理 前提引入
（3）（4）假言推理 前提引入
（5）（6）假言推理 附加前提引入 （1）附加
(r s) 前提引入
（2）s p→ （3）p （4）p→ →(q r) （5）q r→ （6）q （7）r （1）p （2）p q∨ （4）r s∧ （5）s （6）s t∨ （7） (s t∨ →) u （8）u
（2） 证明
（3） (p q∨ → ∧)
（2）（3）假言推理 （4）化简 （5）附加 前提引入
（6）（7）假言推理
16.在自然推理系统p中用归谬法证明下面推理： （1）前提：p→?q，?r∨qr∧?s 结论：?p （2）前提：p∨q，p→r，q→s 结论：r∨s
（1） 证明
（1）p （2）p→?q （3）?q （4）? ∨r q
结论否定引入 前提引入 （2）（1）假言推理 前提引入
（5）?r （6）r∧?s （7）r
（8）? ∧r r
（2） 证明
（1）? ∨(r s)
（3）（4）析取三段论
前提引入 （6）化简 （5）（7）合取 结论否定引入
(1)置换 （2）化简 （3）?r
（4）?s （2）化简
前提引入 （5）p r→
（3）（5）拒取式 （6）?p
前提引入 （7）q s→
（4）（7）拒取式 （8）?q
（9）置换 （9）? ∧?p q
前提引入 （10） q p∨
（11） ? ∨ ∧ ∨(p q)(p q) （10）（11）合取
（2）? ∧?r s
17.在自然系统p中构造下面推理的证明：只要A曾到过受害者房间并且11点前没离开，A
就犯了谋杀罪。A曾到过受害者房间，如果A在11点以前离开，看门人会看见他。看门人没有看见他，所以A犯了谋杀罪。 设 p:A到过受害者房间 q:A在11点前离开 r:A是谋杀嫌疑犯 s:看门人看见A
前提： (p q∧? →) rpq s s, , → ?, 结论：r
证明
（1） （2）
（3） （4） （5） （6）
q s→
?s
前提引入 前提引入 （2）（1）拒取式 前提引入 （3）（4）合取 前提引入
?q
p
p q∧?
(p q∧? →) r
（7） r （5）（6）假言推理 18.在自然系统p中构造下面各推理的证明：
(1)如果今天是星期六，我们就要去颐和园或圆明园玩。如果颐和园游人太多，我们就不去颐和园玩。今天是星期六，颐和园游人太多，所以我们去圆明园玩。
(2)如果小王是理科学生，则他的数学成绩一定很好。如果小王不是文科生，则他一定是理科生。小王的数学成绩不好，所以小王是文科学生。 (1)设
p:今天是星期六 q:我们到颐和园玩 r:我们到圆明园玩 s:颐和园游人太多
前提：p→ ∨(q r s), →?qps, , 结论：r 证明： （1） s→?q （2） （3） （4） （5） （6） （7） (2)设
p:小王是理科学生 q:小王数学成绩好 r:小王是文科学生 前提：p q r p q→ ? → ?, 结论：r 证明：
(1)p q→ (2)?q (3)?p (4)? →r p (5)r
,
s ?q
前提引入
前提引入 （1）（2）假言推理 前提引入 前提引入 （4）（5）假言推理 （3）（6）析取三段论
p
p→ ∨(q r)
q r∨ r
前提引入 前提引入 （1）（2）拒取式 前提引入
(3)(4)拒取式
习题四
1.将下列命题 0 元谓词符号化：
（1） 小王学习过英语和法语。
（2） 除非李建是东北人，否则他一定怕冷。 （3） 2 大于 3 仅当 2 大于 4. （4） 3 不是偶数。
（5） 2 或 3 是素数。
解（1）设一元谓词Fx( ) :小王学习过x。a：英语，b：法语。（1）中命题符号化为 0 元谓词的蕴含式：Fa Fb( )∧ ( )。
（2） 设一元谓词Fx( ) : x是东北人。Gx( ) ：x怕冷。a:李建。符号化为
?Fa( ) →Ga( ) 。
（3） 设二元谓词Gxy( , )：x大于y；a b c:2, :3, :4.符号化为：
Gab Gac( , ) → ( , ).
（4） 设一元谓词Fx( ) : x不是偶数。a：3。命题符号化为 0 元谓词的蕴含式：
Fa( )。
（5） 设一元谓词Fx( ) : x是素数。a：2，b：3. 符号化为
Fa Fb( )∨ ( ) 。
2.在一阶逻辑中将下面命题符号化，并分别讨论个体域限制为（a）,(b)条件时命题的真值： （1）凡有理数都能被 2 整除。
（2）有的有理数都能被 2 整除。其中（a）个体域为有理数集合。 （b）个体域为实数集合。
解: Fx x( ): 能被 2 整除；Gx x( ): 是整数。 （a)(1)?xFx( ),真值为 0，（2）?xFx( ) 真值为 1.
（b)（1）?xGx Fx( ( ) → ( )) 真值为 0，（2）?xGx Fx( ( )∧ ( ))，真值为 1.
3.在一阶逻辑中将下列命题符号化，并分别讨论个体域限制为（a）(b）条件时的命题的真值： (1)对任意的x，均有x2 ? = +2 (x 2)(x+ 2) 。 (2)存在x，使得x+ =5 9。 (a)个体域为自然数集合。 (b)个体域为实数集合。
解：设Fx x( ): 2 ? = +2(x 2)(x+ 2),Gx x( ): + =5 9
（a)(1)?xFx( ),真值为 0，（2）?xGx( )真值为 1. （b)(1) ?xFx( ),真值为 1，（2）?xGx( )真值为 1. 4.在一阶逻辑中将下列命题符号化： （1）没有不能表示成分数的有理数。 （2）在北京卖菜的人不全是外地人。
（3）乌鸦都是黑色的。（4）有的人天天锻炼身体。解：
(1) ??xFx( ( ) ∧?Gx( )) 或者?xFx Gx(( ) → ( )) ，其中Fx x( ): 是有理数，Gx x( ): 能表示 成分数
(2)??xFx Gx( ( )→ ( ))或?xFx(( ) ∧?Gx( ))，其中Fx x( ): 在北京卖菜，Gx x( ): 是外地人 (3)?xFx Gx(( ) → ( )) ，其中Fx x( ): 是乌鸦，Gx x( ): 是黑色的； (4) ?xFx Gx(( ) ∧ ( )) ，其中Fx x( ): 是人，Gx x( ): 天天锻炼身体。 5.在一阶逻辑中将下列命题符号化： (1)所有的火车都比轮船跑得快。 (2)有的火车比有的汽车快。 (3)不存在比所有火车都快的汽车。 (4)说凡是汽车就比火车慢是不对的。 解：
（1） ??x yFx Gy Hxy( ( )∧ ( ) → ( , ))，其中Fx x( ): 是火车，Gy y( ): 是轮船，Hxy x( , ): 比y快；
（2） ? ?xyFx Gy Hxy( ( )∧ ( )∧ ( , ))，其中Fx x( ): 是火车，Gy y( ): 是汽车，Hxy x( , ): 比y快；
（3） ??xGx( ( ) ∧?yFy( ( ) →Hxy( , )) ，其中 Fx x( ): 是火车，Gy y( ): 是汽车， Hxy x( , ): 比y快； （4） ??xGx(
( ) →?yFy( ( ) →Hxy( , )) ，其中Fx x( ): 是火车，Gy y( ): 是汽车，
Hxy x( , ): 比y慢；
6.在下列命题符号化，个体域为实数集合R，并指出各命题的真值：（1）对所有的x，都存在y，使得x y* = 0。
（2）存在着x，对所有y都有x y* = 0。 （3）对所有的x，都存在y，使得y x= +1。 （4）对所有的x和y，都有y x x y* = * 。 （5）对任意的x和y，都有y x x y* = + 。 （6）对任意的x，存在y，使得x y2 + <2 解：各命题符号化如下：
0。
（1） ? ?xyx y( * = 0) ， （2） ? ?x yx y( * = 0) ， （3） ? ? = +xyy x( 1)， （4） ? ?x yy x x y( * = * ) ，
（5） ? ?x yy x x y( * = + ) ，（6）? ?xyx y( 2 + <2
0)。
7.将下列各公式翻译成自然语言，个体域为整数集 Z, 并判断各命题的真假： (1)? ? ? ? =x yzx y
z( ) (2)? ?xyx y( * =1) (3) ? ? ? + =x y zx y z( )
解：
（1）对所有整数x和y，存在整数z，使得x y z? = ，为真命题。（2）对任意整数x，存在整数y，使得x y* =1，为假命题。
（3),存在整数x，使得对任意整数y与z，均有x y z+ = ，为假命题。
8.指出下列公式中的指导变元，量词的辖域，各个体变项的自由出现和约束出现： (1) ?xFx Gxy( ( ) → ( , )) (2) ?xFxy( , ) →?yGxy( , )
(3) ? ?xyFxy Gyz( ( , )∧ ( , ))∨?xHxyz( , , ) 解：
（1）指导变元为x，全称量词?的辖域为Fx Gxy( ) → ( , )。其中x是约束出现的，y是自
由出现的。
（2）蕴含式前件?xFxy( , )中，指导变元为x，全称量词?的辖域为Fxy( , )，其中x是约
束出现的，y是自由出现的。
（3）在? ?xyFxy Gyz( ( , )∧ ( , ))，指导变元为x和y，辖域为 (Fxy Gyz( , )∧ ( , ))，
其中x
和y约束出现的，而z是自由出现的。在?zHxyz( , , )中，指导变元为z，辖域为Hxyz( , , )，其中z约束出现的，而xy, 是自由出现的。 9.给定解释 I 如下： （a） 个体域
D
I为实数集合 R.
（b） DI中特定元素a= 0
（c） 特定函
数f xy x
yxy D( , ) = ? , , ∈ I
（d） 特定谓词Fxy x yGxy x yxy D( , ): = , ( , ): < , , ∈ I. 说明下列公式在 I 下的含义，并指出各公式的真值： (1).??x yGxy( ( , ) →?Fxy( , )) (2)? ?x yF f xy a Gxy(
( ( , ), ) → ( , ))
(3)? ?x yGxy(( , ) →?F f xy a( ( , ), )) (4)? ?x yGf xy a Fxy( ( ( , ), ) → ( , )) 解：
（1） ? ?x y x y(( < ) → ≠(x y)) ,即对任意的实数x和y，若x y< ，则x y≠ 。
（2） ? ?x y x y(( ? = 0) → (x y< )),即对任意的实数x和y，若x y? = 0，则x y< 。（3）? ?x y x
y(( < ) → ? ≠(x y 0)),即对任意的实数x和y，若x y< ，则x y? ≠ 0。
（4）? ?x y x y(( ? < 0) →(x y= )),即对任意的实数x和y，若x y? < 0，则x y= 。 其中（1）（3）真值为 1，（2）（4）真值为 0。 10.给定解释I如下： （a） 个体域D= N（N 为自然数集合） （b） D中特（c） D上函
（d） D上谓词Fxy x y( , ): = .
定元素数 f xy x
a=2.
ygxy x y( , ) = + ,
( , ) = * .
说明下列各式在 I 的含义，并讨论其真值： (1). ?xFgxa x( ( , ), )
(2) ? ?x yF f xa y( ( ( , ), ) →F f ya x( ( , ), )) . (3) ? ? ?x yzF f xy z( ( , ), ). (4) ?xF f xx gxx( ( , ), ( , )) . 解：各式在I下的解释为：
（1） ? =xx x( 2 )，即对任意的自然数x，有x x= 2 ；
（2） ? ?x y x(( + =2 y) →(y+ =2 x))，即对任意的自然数x和y，如果有x+ =2 y，则
有y+ =2 x。 （3） ? ? ? + =x yzx y z(
)，即对任意的自然数x和y，存在z，使x y z+ = ；
（4） ?x x x(2 = 2) ，即存在的自然数x，使 2x x= 2 。 其中（1）（2）真值为 0，（3）（4）真值为 1。 11.判断下列各式的类型：
(1). Fxy( , ) → ( (Gxy Fxy, )→ ( , ))
(2)?xFx( ( ) →Fx( )) →?yGy(( ) ∧?Gy( )) . (3)? ?xyFxy( , ) →? ?x yFxy( , ). (4) ? ?x yFxy( , ) →?
?xyFxy( , ).
(5)? ?x yFxy(( , ) →Fyz( , )) . (6) ??( xFx( ) →?yGy( )) ∧?yGy( ).
解：其中（1）（4）为永真式，（2）（6）为矛盾式，（3）（5）为可满足式，但不是永真式。 12.设I为一个任意的解释，在解释I下，下面哪些公式一定是命题？ (1). ?xFxy( , ) →?yGxy( , ).
(2) ?xFx Gx( ( ) → ( ))∧?yFy H y( ( )∧ ( ))..
(3) ? ?x yFxy( ( , ) →?yGxy( , )). (4) ?xFx Gx Hy(
( )∧ ( )∧ ( ))
（2）（3）一定是命题，因为他们是闭式。
13.给出下列各公式一个成真的解释，一个成假的解释。 (1). ?xFx Gx(( )∨ ( ))
(2) ?xFx Gx Hx( ( )∧ ( )∧ ( )) (3)
?xFx( ( ) ∧?yGy Hxy( ( ) ∧ ( , )))
解：(1).令x是全体正整数。
成真的情况是：Fx( )：x是偶数，Gx x( ): 是奇数。成假的情况是：Fx( )：
x是偶数，Gx x( ): 是素数。
(2).令x是全体正整数，。成真的情况是：Fx( )：x能被 2 整除，Gx x( ): 能被 3 整除，Hx
x( ): 能被 5 整除。则存在 30 能被，2，3，5 整除。成假的情况是：Fx( )：x是偶数，Gx x( ): 是素数，Hx x( ): 能被 5 整除。不存在一个数
既是偶数又是素数同时还能被 5 整除。
(1).令x是全体正整数，y是全体偶数。成真的情况是：Fx( )：x是奇数，Gy y( ): 能被 2 整除，Hxy x y( , ): 比 大。则对任意偶数y，都存在一个大于y的奇数。成假的情况是：
Fx( )：x是偶数，Gy y( ): 能被 2 整除，Hxy x y( , ): 比 小。则对偶数 2，
不存在一个小于 2的偶数。 14.证明下面的公式既不是永真式也不是矛盾式： (1). ?xFx(( ) →?yGy Hxy( ( ) ∧ ( , ))) (2) ? ?x yFx Gy(( )∧ ( ) →Hxy( , )))
解：(1),成真的情况是：Fx( )：x是正偶数，Gy y( ): 是非 1 的正整数，Hxy x( , ): 能被y 整除且x y≠ 。则对任意一个正偶数x，都存在 2，整除x。
矛盾的情况：Fx( )：x是偶数，Gy y( ): 是非 1 的正整数，Hxy x( , ): 能被y整除且 x
y≠ 。则对任意一个正数x（比如 3），不一定存在不等于x的整数，整除x。
(2).成真的情况：Fx( )：x能被 2 整除，Gy y( ): 能被 3 整除，Hxy xy( , ): * 能被 6 整除. 成假的情况是：Fx( )：x能被 2 整除，Gy y( ): 能被 4 整除，Hxy xy( , ): * 能被 6 整除. 15.（1）给出一个非闭式的永真式。
（2）给出一个非闭式的永假式。（3）给出一个非闭式的可满足式，但不是永真式。解：
（1） (Fx Gx Fx Gx( ) → ( ))∧ ( ) → ( )，它是重言式 (A B A B→ ∧ →) （2） ?(Fx( ) →Fx( ))，它是矛盾式? →(A A)的代换实例。 （3） ?xFxy(
的代换实例。
( , ) →Fyx( , ))
习题五
1. 设个体域D={a，b，c}，在D中消去公式?xFx( ( ) ∧?yGy( )) 的量词。甲、乙用了不同
的演算过程：甲的演算过程如下:
?xFx(( ) ∧?yGy( ))
??xFx Ga Gb Gc(
( ) ∧( ( ) ∨ ( ) ∨ ( )))
? (Fa Ga Gb Gc( )∧ (( )∨ ( )∨ ( ))) ∧(Fb Ga Gb Gc( ) ∧(( ) ∨ ( ) ∨ ( ))) ∧(Fc Ga Gb Gc( ) ∧( ( ) ∨ ( ) ∨ ( )))
? (Fa Fb Fc( )∧ ( )∧ ( ))∧ (Ga Gb Gc( )∨ ( )∨ ( ))
乙的演算过程如下：
?xFx(( ) ∧?yGy( )) ??xFx( ) ∧?yGy( )
? (Fa Fb Fc( )∧ ( )∧ ( ))∧ (Ga Gb Gc( )∨ ( )∨ ( ))
显然，乙的演算过程简单，试指出乙在推演过程中的关键步骤。
答：乙在演算中的关键步骤是，开始利用量词辖域收缩与扩张等值式，将量词的辖域缩小，从而简化了演算。
2. 设个体域D={a，b，c}，消去下列各式的量词：
（1） ??xyFx Gy( ( )∧ ( ))
（2） ??x yFx Gy( ( )∨ ( )) （3）
?xFx( ) →?yGy( )
（4）?xFxy( ( , ) →?yGy( )) 答：1) ( ( )Fa Fb
Fc∧ ( ) ∧ ( )) ∧( ( )Ga Gb Gc∨ ( ) ∨ ( ))
2) 3) 4)
(Fa Fb Fc( ) ∧ ( ) ∧ ( )) ∧(Ga GbG c( ) ∧ ( ) ∧( )) ( ( )Fa Fb Fc∧ ( )∧ ( )) →( ( )Ga Gb Gc∧ ( )∧ ( )) (Fay Fby Fcy( , )∨ ( , ) ∨ ( , )) →(Ga Gb Gc( ) ∨ ( ) ∨ ( ))
3．设个体域D={1,2}，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。 （1） ?xFx( ( ) →Gx( )) （2） ?xFx Gx( ( )∧ ( ))
答：解释为I1：F（x），x是偶数，G（x） x是素数解释为I2：F（x），x是奇数，G（x）
x是素数
4．给定公式A xFx=? ( ) →?xFx( )
a) 在解释I1中，个体域D1={a}，证明公式A在I1下的真值为1。
b) 在解释I2中，个体域D2={a1，a2，…，an}，n≥ 2，A在I2下的真值还一定是1
吗？为什么？ 答：1.在I1下，?xFx( ) →?xFx( ) ?Fa Fa( ) → ( ) ??Fa Fa( )∨ ( )?1
在I2下，?xFx( ) →?xFx( ) ? (Fa Fa( 1)∨ ( 2)....∨Fan( )) → (Fa Fa( 1) ∧ ( 2).....∧Fan( ))为可满足式，但不是永真式。设F（x）:x为奇数，此时蕴含式前件为真，后件为假，故蕴含式真值为0。若将F（x）改为令F（x），x为整数，则蕴含式的前件后件均为真，则真值为 1。问题的关键是n≥ 2，n项的析取为真，只需要其中的一项为真，而不能保证所有的项为真。 5．给定解释I如下：（a） 个体域D={3，4}； （b）
f x( )为 f(3) = 4, f x( ) = 3;
（c） Fxy( , ) 为F(3,3) =F(4,4) = 0,F(3,4) =F(4,3) =1 试求下列公式在I下的真值。 （1）? ?xyFxy( , ) （2）
? ?x yFxy( , )
（3）??x yFxy F f x f y( ( , ) → ( ( ), ( )))
答：（1）
? ?xyFxy( , ) ??xFx(( ,3) ∨Fx( ,4)) ?(F(3,3) ∨F(3,4)) ∧(F(4,3) ∨F(4,4)) ? ∧ ?1 1 1
(2).
? ?x yFxy( , ) ??xFx( ( ,3)∧Fx( ,4)) ? (F(3,3)∧F(3,4))∨ (F(4,3)∧F(4,4)) ? ∧ ?0
(3).
0 0
? ?x yFxy(( , ) →F f x f y( ( ),( ))) ??x Fx((( ,3) →F f x f( ( ),(3))) ∧(Fx( ,4) →F f x f( ( ),(4)))) ? (F(3,3) →F f( (3), f(3)))∧ (F(3,4) →F f( (3), f(4))) ∧(F(4,3) →F f( (4), f(3)))∧ (F(4,4) →F f( (4), f(4)))
? → ∧ → ∧ → ∧ → ? ∧ ∧ ∧ ?(0 0)
(1 1) (1 1) (0 0) 1
1
1
1
1
6． 甲使用量词辖域收缩与扩张等值式进行如下演算：
?xFx(( ) →Gxy( , )) ??xFx( ) →Gxy( , )
乙说甲错了，乙说的对吗？为什么？
答：乙说的对，甲错了。本题中，全称量词?的指导变元为x，辖域为Fx Gxy( ) → ( , ) ，其中F(x)与G（x，y）中的x都是约束变元，因而不能将量词的辖域缩小。 7． 请指出下面等值演算中的两处错误。
?? ?x yFx Gy( ?? ?xyFx Gy(
( ) ∧( ( ) →Hxy( , )))
( ) ∧ ( ( ) →Hxy( , )))
?? ?xy Fx((( ) →Gy( )) →Hxy( , ))
答：演算的第一步，应用量词否定等值式时丢掉了否定连接词“?”，演算的第二步，在原
(Fx Gy( ) ∧(( ) →Hxy( , ))) 错的基础上又用错了等值式即，
? ((Fx( ) →Gy( )) →Hxy( , ))
8. 在一阶逻辑中将下面命题符号化，要求用两种不同的等值形式。 （1）没有小于负数的正数（2）相等的两个角未必都是对顶角答： (1).??xFx Gx( (1)
( )∧ ( )) ??xGx( ( ) →?Fx( )),
其中Fx x( ): 小于负数，Gx x( ): 是正数。
(2).
??xFx Gx(( ) → ( ) ??xFx(( ) ∧?Gx( )), 其中Fx( ):两个角相等，Gx( ):两个角是对顶角
9. 设个体域D为实数集合，命题“有的实数既是有理数，又是无理数”。这显然是个假命题。
可是某人却说这是真命题，其理由如下：设F（x）：x是有理数，G（x）：x是无理 数。?xFx( )与?xGx( )都是真命题，于是，?xFx( )∧?xGx( ) ?xFx Gx( ( ) ∧ ( ))，由于
?xFx xGx( )∧? ( )是真命题，故?xFx Gx( ( ) ∧ ( ))也是真命题，即有的实数是有理数，也
是
无理数，问此人的结论对吗？为什么？ 答：不对，因为存在量词对于∧无分配率。 10. 在求前束范式时，有人说??xFx Gxy(
式的前面。他说的对吗？为什么？
答：前束范式中，否定连联接词不能在量词前面出现。 11. 有人说无法求公式
( ) ∧ ( , )) 已是前束范式，理由是量词已在公
?xFx Gx(( ) → ( )) →?xGxy( , ) 的前束范式，因为公式中的两个量词的指导变元相同。 他的理由正确吗？为什么？答：用换名规则可使两个指导规则不同。
12. 求下列各式的前束范式：
(1)?(2)?(3)?
xFx( ) →?yGxy( , ) xFxy( ( , ) →?yGxyz( , , )) xFxy( , ) ??xGxy( , )
( 1, 2)) → ?( xHx2 ( 2) →?xLx x3 ( 2,
(4)?xFx Gxx1( ( 1) →
3
)) (5)?xFxx1 ( 1, 2) → (Fx( 1) →??xGxx2 ( 1, 2)) 答：(1) ?
?x yFx Gzy( ( ) → ( , ))
(2)? ?
xtFxy Gxtz( ( , ) → ( , , ))
2
3
4
(3)? ? ? ?x x x x Fx y Gx y Gx y Fx y1 (( ( 1, ) → ( 2, ))∧ (
( 3, )→ ( 4, )))
(4)? ? ?y y y Fy Gyx1 (5)? ?y y Fyx1
2 3
(( ( 1) → ( 1, 2)) → (Hy Lx y( 2) → ( 2, 3)))
2
( ( 1, 2) → (Fx( 1) →?Gx y( 1, 2)))
13. 将下列命题符号化，要求符号化的公式全为前束范式： (1)有的汽车比有的火车跑得快 (2)有的火车比所有汽车跑得快
(3)说所有的火车比所有的汽车跑得快是不对的 (4)说有的飞机比有的汽车慢也是不对的
答：(1)F(x):x 是汽车，G(y):y 是火车，H(x,y):x 比 y 跑得快
? ?xyFx Gy Hxy( ( ) ∧ ( ) ∧ ( , ))
(2) )F(x):x 是火车，G(y):y 是汽车，H(x,y):x 比 y 跑得快 ? ?x
yFx Gy( ( ) ∧ ( ( ) →Hxy( , )))
(3) F(x):x 是火车，G(y):y 是汽车，H(x,y):x 比 y 跑得快
? ?xyFx Gy(( ) ∧ ( ) ∧?Hxy( , ))
(4) F(x):x 是飞机，G(y):y 是汽车，H(x,y):x 比 y 慢
? ?x yFx Gy(( ) ∧ ( ) →?Hxy( , )) 、
14. 在自然推理系统 F 中，指出下面各证明序列中的错误： (1)○1 Fx( ) →?xGx( )
前提引入 ○2 Fc Gc( ) → ( ) ○1 EI 规则
前提引入 ○2 Fa( ) →Fb( )
○1 EI 规则 前提引入 ○1 EG 规则 前提引入 ○1 EG 规则 前提引入 ○1 UG 规则
(2)○1 ?xFx( ) →?yGy( ) (3)○1 Fy Gy( ) → ( ) ○2 ?xFx Gx(( ) → ( )) (4)○1 Fa Gb( ) ∧ ( ) ○2 ?xFx Gx(( ) ∧ ( )) (5)○1 Fc Gc( ) → ( ) ○2 ?xFx Gx(( ) → ( ))
答：(1)对Fx( ) →?xGx( )不能使用 EI 规则。它不是前束范式，化为前束范式得
Fx( ) →?xGx( ) ??xFy Gx(( ) → ( ))，因为量词辖域(Fy Gx( ) → ( ))中，除了
x 外还有自由出现的 y，所以不能使用 EI 规则。
(2) 对 Fc Gc( ) → ( ) 也应先化成前束范式才能消去量词，其前束范式为
? ?xyFx Gy(( ) → ( ))，要消去量词，既要使用 UI 规则又要使用 EI 规则。
Ac( )
(3)在自然推理系统 F 中，EG 规则为
，其中 c 为特定的个体常项，这里
∴?xAx( )
Ay Fy Gy( ) = ( ) → ( ) 不满足要求。
(4)这里使 F(a)为真的 a 不一定使 G(a)为真，同样地使 G(b)为真的 b 不一定使 F(b)为真，如 F(x):x 为奇数，G(x):x 为偶数，显然F(3) ∧G(4)为真，但不存在使Fx Gx( ) ∧ ( )为真的个体。
(5)这里 c 为个体常项，不能对?xHx( ( ) →?Fx15.在自然推理系统 F 中，构造下面推理的证明： (1)前提：?xFx( ) →?y Fy Gy((
( )
( )引入全称量词。
( )∨ ( )) →Ry xFx( )),? ( ) 结论：
?xRx( )
(2)前提：?xFx(
( ) →( ( )Ga Rx∧ ( ))),?xFx( ) 结论：?xFx
Rx( ( ) ∧ ( ))
(3)前提：?xFx Gx(
( ) ∨ ( )),??xGx( ) 结论：
?xFx( )
(4)前提：?xFx Gx x Gx( ( ) ∨ ( )),? ?(( )∨?Rx xRx( )),?
( ) 结论：
?xFx( )
证明：(1)○1 ?xFx( )
前提引入
前提引入 ○1 ○2 假言推理 ○1 EI
○2 ?xFx( ) →?y Fy Gy((( )∨ ( )) →Ry( ))○3 ?y Fy Gy((( )∨ ( )) →Ry( )) ○4 F(c)
○5 (Fc Gc( ) ∨ ( )) →Rc( ) ○6 Fc Gc( ) ∨ ( ) ○7 R(c) ○8 ?xRx( ) (2)○1 ?xFx( )
○2 ?xFx(( ) →(Ga Rx( ) ∧ ( )))○3 F(c)
○4 Fc( ) → (Ga Rc( )∧ ( )) ○5 Ga Rc( ) ∧ ( ) ○6 R(c)
○7 Fc Rc( ) ∧ ( ) ○8 ?xFx Rx(( ) ∧ ( )) (3)○1 ??xFx( ) ○2 ? ?x Fx( ) ○3 ?Fc( )
○4 ?xFx Gx(( ) ∨ ( )) ○5 Fc Gc( ) ∨ ( ) ○6 F(c) ○7 ?xFx( )
(4)○1 ?xFx Gx(( ) ∨ ( )) ○2 Fy Gy( )∨ ( ) ○3 ? ?x Gx(( ) ∨?Rx( )) ○4 ?Gy( )∨?Ry( )
○3 UI ○4 附加 ○5 ○6 假言推理 ○7 EG 前提引入 前提引入 ○1 EI
○2 UI ○3 ○4 假言推理○5 化简 ○3 ○6 合取 ○7 EG 前提引入 ○1 置换 ○2 UI 前提引入 ○4 UI ○3 ○5 析取三段论 ○6 EG 前提引入 ○1 UI 前提引入 ○3 UI