“离散数学”数理逻辑部分考核试题答案--------------------------- ★-----------------------------一、命题逻辑基本知识（5分）1、将下列命题符号化（总共4题，完成的题号为学号尾数取4的余，完成1题。

共2分）（0）小刘既不怕吃苦，又爱钻研。

解：—p ∧q ,其中，P :小刘怕吃苦；q :小刘爱钻研。

（1）只有不怕敌人，才能战胜敌人。

解：q→-p ,其中，P :怕敌人；q :战胜敌人。

（2）只要别人有困难，老张就帮助别人，除非困难已经解决了。

解：—r→（P→P）,其中，P:别人有困难；q :老张帮助别人；r:困难解决了。

（3）小王与小张是亲戚。

解：p，其中，P:小王与小张是亲戚。

2、判断下列公式的类型（总共5题，完成的题号为学号尾数取5的余，完成1题。

共1分）（0）A ：（-（p^q）_；（（P -q）（.p^q））） r（1）B : （P 一9一；P））（r q）（2）C: （P -r）＞（q r）（3）E : p-;（P q r）（4）F ：—（q-；r） r------------------------------------------------------------------------ 解：用真值表判断，A为重言式，B为矛盾式，C为可满足式，E为重言式，F为矛盾式。

3、判断推理是否正确（总共2题，完成的题号为学号尾数取.2的余，完成1题。

共2分）（0）设y=2∣x∣，X为实数。

推理如下：如y在x=0处可导，则y在x=0处连续。

发现y在x=0处连续，所以，y在x=0处可导。

解：设y=2|x|，X为实数。

令P: y在x=0处可导，q：y在x=0处连续。

由此，P为假，q为真。

本题推理符号化为：（p—；q） q—；P。

由P、q的真值，计算推理公式真值为假，由此，本题推理不正确。

（1）若2和3都是素数，则6是奇数。

2是素数，3也是素数。

所以，5或6是奇数。

解：令P:2是素数，q:3是素数，r:5是奇数，S:6是奇数。

由此，p=1，q=1，r=1，S=O。

本题推理符号化为：（（P q）→ S） P q）→ （r S）。

计算推理公式真值为真，由此，本题推理正确。

二、命题逻辑等值演算(5分)1、用等值演算法求下列公式的主析取范式或主合取范式(总共3题，完成的题号为学号尾数取3的余，完成1题。

共2分)(0)求公式p→ ((q ∧r) ∧(P ∨(―q ∧-r)))的主析取范式。

解：p→((q ∧r) ∧(P ∨(—q ∧-「)))：= 一p∨(q ∧r∧P) ∨(q ∧r ∧一q ∧—r)二一P ∨(q ∧r∧P) ∨0 二(P ∧q∧r) ∨= (一p∧1 ∧1) ∨(q ∧r∧P)二(—p ∧(q ∨-q) ∧(r ∨-r)) ∨(q ∧r∧P) U (~p ∧(q ∨-q) ∧(r ∨一r)) ∨m7二(一P ∧—q ∧ F ∨ (一P ∧—q ∧r) ∨ (一P ∧q ∧_r) ∨ (一P ∧q ∧r) ∨m7 m0 ∨m1 ∨m2 ∨m3 ∨m7.(1)求公式一(一(P → q)) ∨(—q → 一P)的主合取范式。

解：一(一(P → q)) (—q →-p)二(P → q) (P →q) U (P → q)U —P0q U M2.(2)求公式(P→(P ∨q)) ∨r的主析取范式。

解：(p→ (P q)) r -P (P q) r 二(—p P q r)二1U m0 ∨ml ∨m2 ∨m3 ∨m4 ∨m5 ∨m6 ∨m7.2、应用分析(总共2题，完成的题号为学号尾数取2的余，完成1题。

共3分)(0)某村选村委，已知赵炼玉、钱谷王、孙竹湾被选进了村委，三村民甲、乙、丙预言：甲预言：赵炼玉为村长，钱谷王为村支书。

乙预言：孙竹湾为村长，赵炼玉为村支书。

丙预言：钱谷王为村长，赵炼玉为村妇女主任。

村委分工公布后发现，甲乙丙三人各预测正确一半。

赵炼玉、钱谷王、孙竹湾各担任什么职务？解：设P1 :赵炼玉为村长，p2 :钱谷王为村长，p3 :孙竹湾为村长，q1 :赵炼玉为村支书，q2:钱谷王为村支书，r1 :赵炼玉为村妇女主任。

判断公式F=( (p1 -q2) (一p1 q2)) ( (p3 — q1) (—p3 q1)) ( (p2 —「1) (一p2 r1)) U — p1 q2 p3 一q1 — q2 r1=1=q2 p3 r1，由此，钱谷王为村支书，孙竹湾为村长，赵炼玉为村妇女主任。

说明：p1、p2、p3有且仅有一个为真，q1、q2有且仅有一个为真。

一个人不能担任两职，一个职务不可由两人同时担任。

(1)某公司派赵、钱、孙、李、周五人出国学习。

选派条件是：①若赵去，钱也去。

②李、周两人必有一人去。

③ 钱、孙两人去且仅去一人。

④孙、李两人同去或同不去。

⑤ 如周去，则赵、钱也同去。

如何选派他们出国？解：①设P:派赵去，q :派钱去，r:派孙去，s:派李去，u派周去。

②⑴(P >q) ⑵(S U) (3) ((q F (-q r))(4) ((r S) (■唇S)) (5) ( u-;(P q))③⑴~⑸构成的合取式为：A= (p—；q) (S U) ((q F (一q r)) ((r S) (一r -S)) (U r(P q))=(―p _q r S -U) (P q _r -S U)由此可知，A的成真赋值为00110与11001，因而派孙、李去(赵、钱、周不去) ，或派赵、钱、周去(孙、李不去) 。

三、命题逻辑推理(5分)在自然推理系统中，构造下列推理过程(总共3题，完成的题号为学号尾数取3的余，完成1题。

共5 分)(0)如果张老师出国，则若李老师出国，王老师出国。

现在的情况是张老师与李老师都要出国。

所以，王老师不出国，则孙老师出国。

解：形式化：P :张老师出国；q :李老师出国；r:王老师出国；S :孙老师出国。

前提:pτ(qτr)，PM结论:-I IS证明：①pτ(qτr)【前提引入】②^ψ V (^Vr) U PAL r【①置换】③PAq【前提引入】④r【②③假言推理】⑤r VS【④附加规则】⑥m^r∨S【⑤置换】⑦-rτs【⑥置换】证毕。

(1)若张同学与李同学是乐山人，则王同学是雅安人， 若王同学是雅安人，则他喜欢吃雅鱼，然而,王同学不喜欢吃雅鱼，张同学是乐山人。

所以，李同学不是乐山人。

解：形式化：P:张同学是乐山人；q ：李同学是乐山人；r ：王同学是雅安人；S:王同学喜欢吃雅鱼。

前提: (PmT r , r -⅛ S ,-s , P结论:F证明： ①(PM)τr 【前提引入】②r τ S【前提引入】③(P F q)T S【①②假言三段论】④-S 【前提引入】⑤-(PAq) 【③④拒取式】⑥-Pt Iq【⑤置换】 ⑦P【前提引入】⑧-q【⑥⑦析取三段论】证毕。

(2) 若n 是偶数并且大于5 ,则m 是奇数。

只有n 是偶数，m 才大于6。

现有n 大于5。

所以，若四、一阶逻辑的基本概念(5分)1、一阶逻辑命题形式化(总共6题，完成的题号为学号尾数取 6的余，完成1题。

共2分)(0)人人都生活在地球上。

解：-X(F(X) →G(X)),其中，F(X) : X 是人，G(X) : X 生活在地球上。

(1) 有的人长着金色的头发。

解：X (F(X)G(X)),其中，F(X) : X 是人，G(X) : X 长着金色的头发。

(2) 没有能表示成分数的无理数。

解：—X (F(X)G(X)),其中，F(X) : X 是无理数，G(X) : X 能表示成分数。

(3) 说所有的男人比所有的女人力气大是不正确的。

解：一-x-y (F(X)G(y) →S(x,y)),其中，F(X) : X 是男人，G(X) : X 是女人，S(x,y) : X 比 y 力气大。

(4) 有的学生不住在校内。

解：X (F(X) -G(X)),其中，F(X) : X 是学生，G(X) : X 住在校内。

(5)说有的男人比所有的女人力气大是正确的。

解：X (F(X)-y(G(x) → S(x,y))),其中，F(X) : X 是男人，G(X) : X 是女人，S(x,y) : X 比y 力气大。

m 大于6 ,则m 是奇数。

解：形式化：P : n 是偶数；q : n 大于5 ； r ： 前提：(P q)-∙ r ，S > P ，q 结论：S r r 证明：① q------------- ② r 思q -----------------------③ S J q ④ S T P⑤(S T q )( S T P )⑥ sτ(p,∙∖q ) ⑦ (P q)》r⑧S r rm 是奇数；S : m 大于6。

【前提引入】【①附加规则】(这是证明的关键) 【②置换】 【前提引入】 【③④合取】 【⑤置换】 【前提引入】 【⑥⑦假言三段论】 证毕。

2、给出下列公式的一个成真解释和一个成假解释(总共3题，完成的题号为学号尾数取3的余，完成1题<共3分)(0)-X(F(X) G(X))解：取解释11 :个体域为人的集合，F(X) : X是男人，G(X) : X是女人。

----------- 则在I1解释下，-X(F(X) G(X))为真命题。

取解释I2 :个体域为人的集合，F(X) : X是中国人，G(X) : X是美国人。

则在I2解释下，-X(F(X) G(X))为假命题。

(1)X(F(X) G(X) H(X))解：取解释11:个体域为人的集合，F(X) : X是教师，G(X) : X是党员，H(X) : X是班主任。

则在I1解释下，次F(X) A G(X) A H(X))为真命题。

取解释I2 :个体域为人的集合，F(X) : X是男人，G(X) : X是女人，H(X) : X是班主任。

则在I2解释下，ΞX(F(X) A G(X) A H(X))为假命题。

(2)X(F(X) -y( G(y) H(x,y)))解：取解释I1 :个体域为整数集合，F(X) : X是正整数，G(X) : X是负整数，H(x,y) : X比y大。

则在I1 解释下，X(F(X) -y( G(y) H(x,y)))为真命题。

取解释I2 :个体域为自然数集合，F(X) : X是奇数，G(X) : X是偶数，H(x,y) : X比y大。

则在I2 解释下，X(F(X) -y( G(y) H(x,y)))为假命题。

五、一阶逻辑等值演算(5分)1、证明等值式(总共2题，完成的题号为学号尾数取2的余，完成1题。

共1分)(0)证明等值式:-X(A(X)Jj B)= XA(X) >B。

证明：一X(A(X)「.B) x( — A(X) B) χ-A(x) B^-X A(X) B ：= X A(X) → B O(1)证明等值式: X(A(X)》B>=-XA(X) >B。