哈尔滨工业大学(威海)2006 /2007学年秋季学期
数理逻辑试题(A卷)
一.将下列各试用前置方式表示出来(共5)
1)(a+(b+c))=((a+d)+c)(1分)
2)(a×(b+c))=((a×b)+(a×c))(1分)
3)(((a+b)×c)÷d)-(e×f)(1分)
4)(3d+4×(a b-4xy))÷((4xyz)÷2y)(2分)
二.判别下列各句是否为命题,在括号中回答T与F(每题1分,共10分)
齐次线性方程组是无解的.()
请做汽车去!()
您复习完了吗?()
18是6和3的公倍数。()
这句话是假的。()
如果天气好,那么我去到自习室()
昨天下雨且昨天打雷。()
9不是43的约数。()
小张不会德文。()
21世纪末,人类将在太空。()
三.请用命题演算理论解答下列各式. (每题2分,共14分)
1.将下列句子表示成符号公式.
1)小张不会德文也不会法文
2)如果6大于4,3不大于4,则18不大于16
3)只有明天上午七点不下雪且不下雨我们才去学校
4)除非你同我一起或坐公共汽车,否则我不去
5)天黑了我得回家
2. 证明下列等式.
1)┐(┐p∧(┐q∨┐r))=(p∨q)∧(p∨ r)
2)(p→q)∧(p→r)=p→(q∧r)
四. 请用谓词演算理论解答下列各式. (每题2分,共12分)
1.将下列句子用谓词填式表示
1)这座大楼建成了
2)这个人正在看那本红皮书
3)没有不犯错误的人
2. 将下列谓词译成句子.
1)?x (R(x)→>(x,0)∨=(x,0)∨<(x,0))
其中: x大于0表示>(x,0) x小于0表示<(x,0)
x 等于0表示=(x,0),特性谓词x为实数
2)?x (M(x)→D(x)),M(c)┝ D(c)
其中: M(x)表示:x是人 D(x)表示:x必死
c表示:张三
3)?x(┐Q(x)→E(x)
其中: Q(x)表示x是奇数E(x)表示x是偶数
五. 请用谓词演算理论及量词解答下列各式.(每题2分,共16分)
1.指出下列公式中的自由变元,约束变元及约束关系.
1)?x(x2≥0∧?y(x= y∧?z(z> y)))
2)?u?z(y∧u∨?u(z> y))
3)?x ? y (x>z∧?z(y= z∨ (x2> y)))
4)?y(Xxy∧?xYx)→?x(Xx y≡?xYx))
2. 请使用谓词演算表达式表示下列各式.
1) 对于任何一个事业有成者都是努力工作或是努力学习.
2) 如果您努力学习必对国家有贡献
3) 尽管有人聪明,但未必一切人都聪明.
4)必须对环境进行治理否则对人类生存产生较大影响
六.采用数理逻辑推理将下面高级语言写成的一段程序化简 (共12分)
1.请化简下列程序段
if A then if B then X (7分)
else Y else if B then X else Y
2.请给出将1中程段化简前的流程图(3分)
3.请给出将1中程段化简后的流程图(2分)
七.证明下列各式. (每题5分。共15分)
1) 试证:((P→Q)∧┐Q)→┐P为重言式
2) 试证:P→Q=┐P∨Q为重言式
3 ) 试证:任一含有∧,∨,┐,,→真值连接词的逻辑公式均可由┐,∧及┐,∨来表示
八) 根据数理逻辑的理论判断程序的正确性请写出I/0断言及中间断言
(每题8分,共16 分)即:计算两个非负数且不同时为零的整数X1与X2最大公约数Y的程序
1) 请写出输出断言
Program GCD
Read(X1,X2)
()写出输入断言
( z1, z2)=(X1,X2)
While z1≠0 do
od
y= z2
()写出输出断言
Write ( y )
End GCD
2) 请写出中间断言
( z1, z2)=(X1,X2)
While()写出中间断言
If z1≥z2 then z2= z2-z1,else ( z1, z2)
od
()写出中间断言
y= z2
2006/2007年秋季学期数理逻辑试题答案
(A卷)
适用班级(0404101 1—6, 0404201 1-2)
一. 1) =+a+bc++abc
2) =×a+bc+×ab×ac
3) -÷×+abcd×ef
4)÷+×3d×4-×ab××4xy÷×××4xyz÷×2y
二 T,F,F,T,F,T,T,T,T,T.
三 1: 1)p:设小张不会德语q:设小张不会法语
原式可表示为:p≡q
2)p:设6>4 q:设3≠>4 r:设8≠>16
原式可表示为:(p∧q)→r
3)设p:明天上午七点不下雪 q:明天上午七点部下雨 r:我去学校原式可表示为:(p∧q)→r
4)设p:你不和我一起 q:座公共汽车 r:我不去
原式可表示为:(┐p∧q)→r
5)设p:天黑了 q:我回家
原式可表示为:p≡q
注明:这种答案不是唯一的,是根据每个人逻辑设计不同而不同。
2:1)┐(┐p∧┐(q ∧r))
= p∨(q ∧r)
=(p ∨q)∧(p ∨r)
2)=(┐p∨q)∧(┐p ∨r)
= ┐p∨q∧r
=(p→q)∧r
四1:1)F(x)表示:x建成了 G(x)表示:x是大的 H(x)表示:x是大楼则可表示为:F(x)∧G(x)∧H(x)
2)F(x,y)表示:x正看y G(x)表示:x是人
H(y)表示:y是红皮的 U(y)表示:y是书
a表示这个 b表示那个
则全句可表示为:F(a,b)∧G(a)∧H(b)∧U(b)3)设F(x)为:x犯错误其特性谓词为M(x):表示x为人
则此句可表示为:┐ヨx(M(x)∧┐F(x))
2: 1)任何一个实数或大于0或小于0或等于0
2)推理三段论:凡人必死,张三是人,故张三必死。
3)对任意自然数不是奇数则是偶数。
五 1:1)x、y、z约束变元
约束关系为若x2大于等于0并且对所有的y、x等于y并且z大于y
2)u、z约束变元y为自由变元
约束关系为对于一切变元u都存在一个z使得z大于y
3)x、y、约束变元z即为约束变元又为自由变元
其约束关系为x大于z 存在y= z或者x2大于y
4)y为约束变元x为约束变元也为自由变元
其约束关系为如果二元谓词X(x,y)且谓词Y(x)则有X(x,y)等价Y(x)21)?x N(x)≡G(y)∨G(z)
设N为…有成,x表示事业
G表示…努力
Y表示工作
Z表示学习
2)N(x)→G(y)
3)ヨxN(x)→?x((┐N(x))
4)N(x)∧G(x)→┐(N(x)∧G(x))∧R(x)
六
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
3)
八 1:1(输入断言)
2)y=MAXu(u≒x1∧u≒x2))(输出断言)
2:1)(z1≥0∧z2≥0)∧(z1≠0∨z2≠0)∧MAXu(u≒z1∧u≒z2)= MAXu(u≒x1∧u≒x2))(中间断言)
2)(z1≥0∧z2≥0)∧(z1≠0∨z2≠0)∧MAXu(u≒z1∧u≒z2)= MAXu(u≒x1∧u≒x2))因进入循环起点,(中间断言)
3)(z2= MAXu(u≒x1∧u≒x2))(中间断言)