2010-2011学年第一学期离散数学期中考试试卷答案
一、（本题满分12分）在命题逻辑中将下列命题符号化。

（1）小王边走路边听音乐。

（2）除非a能被2整除，a才能被4整除。

（3）派小张、小李中的一人去开会。

（4）小张和小李是同学。

（5）今天是星期一仅当明天是星期二。

（6）若2+2≠4，则3+3≠6；反之亦然。

解：（1）令p：小王走路；q：小王听音乐。

符号化为p∧q
（2）令p：a能被2整除；q：a能被4。

符号化为q→p
（3）令p：派小张去开会；q：派小李去开会。

符号化为（p∧┐q）∨（┐p∧q）
（4）令p：小张和小李是同学。

符号化为p
（5）令p：今天是星期一；q：明天是星期二。

符号化为p→q
（6）令p：2+2=4；q：3+3=6。

符号化为┐p↔┐q
二、（本题满分12分）在一阶逻辑中将下列命题符号化。

（1）有的有理数能被2整除。

（2）没有不犯错误的人。

（3）人都不一样高。

（4）说火车比汽车跑的快是不对的。

（5）4>2与3≥1互为充要条件。

（6）除非李键是东北人，否则他一定怕冷。

解：（1）令F(x)：x为有理数；G(x)：x能被2整除。

符号化为∃x(F(x)∧G(x))
（2）令F(x)：x是人，G(x)：x犯错误，则命题符号化为：∀x（F（x）→G(x)）
（3）令F(x)：x是人；H(x,y)：x与y一样高。

符号化为∀x∀y（F（x）∧F（y）→┐H（x，y））（4）令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快，┐∀x∀y（F（x）∧G（y）→H（x，y））（5）令F(x,y)：x>y，G(x,y):x≥y，a:4，b:2，c:3，d:1。

符号化为F(a,b)↔G(c,d)
（6）令F(x)：x是东北人，G(x)：x怕冷，a：李键，符号化为┐G（a）→F（a）
三、（本题满分8分）给出公式(q →r) ∧ ( p→p)的真值表并求出成真赋值和成假赋值。

解：真值表如下
成真赋值：000、001、011、100、101、111；成假赋值：010、110
四、（本题满分10分）设p:2能整除5，q:太阳从西方升起，r:一年分四季。

求下列复合命题的真值：
（1）((p ∨q) → r)∧(r→ (p ∧q)) （2）((┐q ↔p) → (r ∨p)) ∨ ((┐p ∧┐q) ∧r)
解：由题意，p、q、r的真值分别为0、0、1。

（1）的真值为0；（2）的真值为1。

五、（本题满分12分）使用等值演算法判断公式下列公式的类型。

（1）(p → q ) ∧ (q → r ) ∧ p → r （2）p ∧ (((p ∨ q ) ∧ ┐p ) → q )
解：（1）（（p→q ）∧（q→r ）∧p ）→r ⇔┐（（┐p ∨q ）∧（┐q ∨r ）∧p ）∨r ⇔（p ∧┐q ）∨（q ∧┐r ）∨┐p ∨r
⇔（p ∨┐p ）∧（┐q ∨┐p ）∨（q ∨r ）∧（┐r ∨r ）⇔（┐q ∨┐p ）∨（q ∨r ） ⇔┐q ∨┐p ∨q ∨r ⇔1。

所以该公式为重言式。

（2）p ∧(((p ∨q) ∧┐p) →q) ⇔p ∧(┐((p ∨q) ∧┐p)∨q) ⇔p ∧(┐((p ∧┐p)∨（q ∧┐p ）)∨q)
⇔p ∧(┐（0∨（q ∧┐p ））∨q) ⇔p ∧(┐（q ∧┐p ）)∨q) ⇔p ∧（┐q ∨p ）∨q) ⇔p ∧1⇔p 。

所以该公式为非重言式的可满足式。

六、（本题满分10分）将公式p → (q → r )化成与之等值且仅含有┐和∧这两个联结词的公式。

解：使用等值演算法可得p → (q → r ) ⇔ ┐(p ∧ q ∧ ┐r )
七、（本题满分12分）求公式（p →q ）∧（q →r ）的主析取范式与主合取范式，并分别写出公式的成真赋值和成假赋值。

解：主析取范式为：m 0∨m 1∨m 3∨m 7；主合取范式为：M 2∧M 4∧M 5∧M 6；
公式的成真赋值为：000，001，011，111；公式的成假赋值为：010，100，101，110。

八、（本题满分12分）在命题逻辑中构造下面推理的证明：只要今天天气不好，考生就不能提前进入考场；考试准时进行当且仅当考生提前进入考场。

所以，如果考试准时进行，那么今天天气就好。

解：令p ：今天天气好；q ：考生提前进入考场；r ：考试准时进行；
前提：p q ⌝→⌝，q r ↔
结论：r p →
证明： ① q r ↔
前提引入
② ()()q r r q →∧→ ①置换 ③ r q → ②化简 ④ p q ⌝→⌝ 前提引入 ⑤ q p → ④置换
⑥ r p → ③⑤假言三段论
九、（本题满分12分）在命题逻辑中解决如下问题：有人问甲、乙、丙、丁四人谁的成绩最好，甲说“不是我”，乙说“是丁”，丙说“是乙”，丁说“不是我”。

已知四人的回答只有一人符合实际，问谁的成绩最好？
解：设p ：甲成绩最好，q ：乙成绩最好，r ：丙成绩最好，s ：丁成绩最好
则甲所说符合实际：A=┐p ∧┐s ∧┐q ∧s ⇔0
乙所说符合实际：B=p ∧s ∧┐q ∧s ⇔p ∧s ∧┐q 丙所说符合实际：C=p ∧┐s ∧q ∧s ⇔0
丁所说符合实际：D=p ∧┐s ∧┐q ∧┐s ⇔p ∧┐s ∧┐q
易见只有丁所说符合实际，即甲最好。

附加题（本题满分5分）一个人起初说“占据空间的，有质量的而且不断变化的叫做物质”；后来他改说“占据空间的有质量的叫做物质，而物质是不断变化的”，问他前后主张的差异在什么地方，试在命题逻辑中加以分析。

解：p ：它占据空间，q ：它有质量，r ：它不断变化，s ：它是物质
这个人起初主张：（p ∧q ∧r ）↔s ；后来主张：（p ∧q ↔s ）∧（s→r ） 不同点在于：后来认为如有p ∧q 则必有r ，开头时并没有这样的主张。