数理逻辑试题B卷 2006—2007

哈尔滨工业大学（威海）2006 /2007学年秋 季学期

数理逻辑试题（B卷）

适用班级（0404101 1—6）（0404201 1-2 ）

一. 判别下列各句是否为命题，在括号中回答T与F（每题1分，共10分）

1）8小于10 （ ） 2）8大于10 （ ） 3）请勿吸烟 （ ） 4）期中考试，张三没有考及格了 （ ） 5）期中考试，张三和李四都考及格了 （ ） 6）如果张三能考90分，那么李四也能考90分 （ ） 7）如果张三能考上研究生当且仅当李四也能考上（ ） 8）我正在说谎（ ） 9）x大于y （ ） 10）请进来 （ ）

二.根据题意将下列句子表示成符号公式（每题2分，共10分）

即： 设个体域是整数，并以N（x）表示“x为非负整数”， E（x）表示“x是偶数，Q（x）表示

“x是奇数，P（x）表示“x是素数，请将下列论断写成谓词公式

1）存在一个偶数 2）每个整数是偶数或奇数 3）不是所有的整数为奇数 4）不是所有的素数为奇数 5）如果一个整数不是奇数 ，那么就是偶数

三. 证明下列各题 （每题5分，共10分）

1）请采用化为析取范式方法证明公式永真

（（P→Q）∧┐Q）→┐P

2）请使用逐次指派法证明公式永假

（P→Q）∧┐Q∧P

四.指出下列公式的自由变元与约束变元（每题2分，共12分） 1）?x（P（x）→F（x））

2）? x P（x，z） 3）?x（P（x，y）→F（x）） 4）? x ? y（P（x，y）→N（x，y，z））∧Q（x，z） 5）?u （A∧（G（u）∨┐G（u）） 6）? x1 ? x2 ?? xn-1 ?y（Px1??xn，y） 五.对下列命题和谓词变元进行代入（共15分）

1）? y （P→A y ）→（P→? x A x ）是把P代以?yBxy和P代以?xBxy（5分） 2）?x（Xxy→Yx）→?y Xty把Xe1e1代以?ta（e1，e2，x，t）（10分）

六.采用数理逻辑推理将下面高级语言写成的一段程序化简 (共10分）

1.请化简下列程序段 （5分）

if A then if B then X else Y else if B then X else Y

2.请给出将1中程段化简前的流程图 （3分）

3.请给出将1中程段化简后的流程图 （2分）

七.根据题意做出推导（共15分）

1）写出下列公式的对偶式与内否式（7分）

（┐（┐p→q）∨┐（┐q∧r））→（p∨┐r） 2）写出下列公式的导出规则（8分） （p∧（p→q））→（p∧q）

2006/2007年秋季学期数理逻辑试题答案

（B卷）

一：判别下列各句是否为命题，在括号中回答T与F

1）（T ） 2）（T ）3）（F ）4）（T ） 5）（T ）6）（T ）

7）（T ） 8）（F ）9）（F ）10）（F ）

二：根据题意将下列句子表示成符号公式

即： 设个体域是整数，并以N（x）表示“x为非负整数”， E（x）表示“x是偶数，Q（x）表示“x是

奇数，P（x）表示“x是素数，请将下列论断写成谓词公式

1）存在一个偶数 解：ヨx E（x）2）每个整数是偶数或奇数 解： ?x（E（x）∨Q（x）） 3）不是所有的整数为奇数 解：┐?x E（x）∨Q（x）或ヨx ┐Q（x）

4）不是所有的素数为奇数解： ┐?x（ P（x）→Q（x））或ヨx （P（x）∧┐Q（x）） 5）如果一个整数不是奇数 ，那么就是偶数 解：?x（┐Q（x）→E（x）） 三： 证明下列各题

1）请采用化为析取范式方法证明公式永真 （（P→Q）∧┐Q）→┐P

解：=┐（（P→Q）∧┐Q））∨┐P

=┐（（┐P∨Q）∧┐Q））∨┐P

=┐（（┐P∧┐Q）∨（Q∧┐Q））∨┐P =┐（（┐P∧┐Q）∨（F）∨┐P =┐（（┐P∧┐Q））∨┐P =（P∨Q）∨┐P =（Q∨P）∨┐P

=（Q∨（P∨┐P）） =Q∨T

=T

2）请使用逐次指派法证明公式永假

（P→Q）∧┐Q∧P

解：=（┐P∨Q）∧┐Q∧P

=（┐P∧┐Q∧P）∨（Q∧┐Q∧ P） =F∨F

=F

四.指出下列公式的自由变元与约束变元（12分） 1）?x（P（x）→F（x））

解：x二次出现均为约束出现

2）? x P（x，z）

解：z为自由变元，x为约束变元

3）?x（P（x，y）→F（x））

解： y为自由变元，x为约束变元

4）? x ? y（P（x，y）→N（x，y，z））∧Q（x，z）

解：z为自由变元

x为自由变元也为约束变元， y 为约束变元

5）?u （A∧（G（u）∨┐G（u））

解： 命题A为自由出现

6）? x1 ? x2 ?? xn-1 ?y（Px1??xn，y）

解：xn为自由变元

五.对下列命题和谓词变元进行代入

1）? y （P→A y ）→（P→? x A x ）是把P代以?yBxy和P代以?xBxy

解：因约束关系不发生变化所以可以直接进行代入。 ? y （?yBxy →A y ）→（?xBxy →? x A x ）

2）?x（Xxy→Yx）→?y Xty把Xe1e1代以?ta（e1，e2，x，t） 解：1）代入式改名， ?ua（e1，e2，x，u） 2）原式改名 ?z（Zzy→Yz）→?y Xty 3）对Xzy代入式的填式?ua（z，y，x，u） 4）对Xty代入式的填式?ua（t，y，x，y） 5）将二各填式代到原式有

?z（?ua（z，y，x，u）→Yz）→?y?ua（t，y，x，y） 证毕

六.采用数理逻辑推理将下面高级语言写成的一段程序化简 1.请化简下列程序段

if A then if B then X else Y else if B then X else Y

1）根据所给程序有：此程序执行x之前的条件为：

解： A∧B∨┐A∧B 执行y之前的条件为： A∧┐B ∨┐A∧┐B 所以

A∧┐B ∨┐A∧┐B = B∧A∨B∧┐A = B∧（A∨┐A ） =B∧T = B

A∧┐B ∨┐A∧┐B = ┐B∧ A∨┐B∧┐A =┐B∧ （A∨┐A） =┐B∧T = T∧┐B =┐B

故此简化为：if B then x elde y

2）.请给出将1中程段化简前的流程图

T F T F T B B A X Y F

3）请给出将1中程段化简后的流程图

T F

X A Y 七.根据题意做出推导 1）写出下列公式的对偶式与内否式

（┐（┐p→q）∨┐（┐q∧r））→（p∨┐r） 解 ：=（┐（P ∨q）∨┐（┐q∧r））→（p∨┐r）

=┐┐（（P ∨q）∧┐（q∧r））∨（p∨┐r） =（P ∨q）∧（┐q∧r）∨（p∨┐r） 对偶式为：（P∧q）∨（┐q∧r）∧（p∨┐r）

内否式为：（┐ P∧┐ q）∨（q∧┐ r）∧（┐p∨ r） 2）写出下列公式的导出规则（8分） （p∧（p→q））→（p∧q）

解 ： =┐（P∧（P→q））∨（p∧q）

=┐（P∧（┐P∨q））∨（p∧q） =（┐P∨┐（┐P∨q））∨（p∧q） =（┐P∨（┐┐P∨q））∨（p∧q） =（┐P∨P∨q）∨（p∧q）