高级数理逻辑-习题.doc

1. 逻辑语言由哪些内容构成？现代逻辑扩张的方法有哪些？举例说明。1. 一个字母表(alphabet)：记为A或S，其元素称为符号，符号(symbol,sign)的有限串构成字(word)。2. 一个项集(term set)：记为TERM，其元素称为项(term)，是某种合法的字。3. 一个公式集(formula set,well-formed formula-wff)：记为FORMULA，其元素称为合式公式(wff)，简称公式，是某种合法的字。一般地，项集与公式集是不的，即TERMFORMULA=。4. 有关的一些语法理论。(1)项形成规则(formation rule of terms)：规定合法的项；(2)公式形成规则(formation rule of wffs)：规定合法的公式；(3)括号省略的原则：缩写约定；(4)代入规则(substitution rule)：代入的原则及为保持这一原则所作的规定；(5)其它语法概念：为涉及的其它语法问题所作的规定。1. 先从语义开始，对已有的各种联结词、算子做出新的语义解释，从而引出有关这些联结词、算子的新公理、新规则，进而导致产生新的逻辑系统(从语义到语法)； 例如：三值逻辑、多值逻辑、模糊逻辑、归纳逻辑等。2. 先从语法开始，对已有的逻辑系统增加新的词项及新的算子，从而引出有关这些词项、算子的新公理、新规则，进而导致产生新的逻辑系统，新的逻辑体系立即引发出全新的语义解释(从语法到语义)3. 两种扩张的方法混合使用。1. 三值逻辑是如何从二值逻辑扩张而来的(1) 经典的二值逻辑对联结词的语义解释赋值 :FORMULAVAULE (这里：VAULE=t,f) 其真值表如下：tftftftftfttftttttfttfftfffftffttfft2.从语法到语义的扩张例如：以下是各非经典逻辑所增加的新算子。n 模态逻辑：(必然)，(可能)；n 时态逻辑：(总是)，(有时)，o(下一个)，(下一时)，U(直到)；n 二阶逻辑：二阶变项，二阶量词；n 道义逻辑：O(必须)，P(允许)，F(禁止)；n 优先逻辑：P(优先)；n 时间逻辑：P(过去)，R(现在)，F(将来)；n 时相逻辑：H(发生)，B(未发生)，A(事后)，G(完成)；n 信念逻辑：B(相信)； 断定逻辑：A(断定)；等。 3. 两种扩张的方法混合使用。例如：非经典的莱欣巴哈(Reichenbach)三值量子逻辑。在联结词方面莱欣巴哈三值量子逻辑增加了：n 两种否定词：(循环否定)，(完全否定)，(原否定词()称为直接否定()；n 两种蕴涵词：(二者择一蕴涵)，(准蕴涵)，(原蕴涵词()称为标准蕴涵()；n 一种等价词：(二者择一等价)，(原等价词()称为标准等价()；n (并且原合取词()记为()。 2. 求命题公式（PQ）（PQ）的析取范式与合取范式。（PQ）（PQ）(（PQ）（PQ）)(（PQ）（PQ）)(（PQ）（PQ）)( （PQ）（PQ）)(（PQ）（PQ）)(（PQ）（PQ）)（PQ）（PQ）(合取)（PQ）（PQ）（析取）3. 试求下列公式的主析取范式：（1）=P(P Q) (PQ)=(P(Q Q)(PQ)=(PQ) (P Q)(PQ)（2）=P(P (Q (QR) =PQR=(P(QQ)(RR)(PP)Q(RR)(PP)(QQ)R)=(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)4. 利用基本等值式证明下列命题公式为恒真公式。（PQ）（QR）（PR）（PQ）（ Q R）（P R） (PQ）（P R）（ Q R）)（P R） Q R P RT（PQ）（P（QR）（PQ）（PR） (PQ) (P(QR) （PQ）（PR）P(PQ) (QR) （PQ）（PR） (QR) PQ（PR）R QPRT5. 设已知： (1)能阅读者是识字的； (2)海豚不识字； (3)有些海豚是很聪明的。试证明：有些聪明者并不能阅读证 首先，定义如下谓词： R(x)：x能阅读。 L(x)：x识字。 I(x)：x是聪明的。 D(x)：x是海豚。 然后把上述各语句翻译为谓词公式：(1) x(R(x)L(x)(2) x(D(x) L(x) 已知条件(3) x(D(x)I(x) (4) x(I(x)R(x) 需证结论 求题设与结论否定的子句集，得(1) R(x)L(x)(2) D(y) L(y)(3)D(a)(4)I(a)(5) I(z)R(z)消解得 (6) R(a) (5)，(4)，a/z (7) L(a) (6)，(1)，a/x (8) D(a) (7)，(2)， a/y (9) (8)， (3)6. 规范对当推理共有几种？1. 矛盾关系对当推理2. 差等关系对当推理3. 反对关系对当推理4. 下反对关系对当推理7. 下列各组命题是否等值？如不等值，写出第一个命题的等值命题。1）“不必然p”与“可能不p” 是 口PP2）“可能p”与“必然不p” 否 P口P3) “这种商品一定会畅销”与“这种商品一定不会畅销”否 口P口P4）“火星上可能有生命”与“火星上可能没有生命”是 PP8. 用时态逻辑公式表示下列系统性质对于电梯的控制系统，要求：1). 电梯在开动的时候，门是不能打开的 (door_open / moving)2). 到第i层去的请求会被满足. (elevator_atj / request_fori / ij (elevator_ati /door_open)9. 什么是l-演算？l-演算相对于一阶谓词逻辑具有哪些优点？-演算是一套用于研究函数定义、函数应用和递归的简单、最小的形式系统-演算由 Alonzo Church 和 Stephen Cole Kleene 在20世纪三十年代引入，最开始，Church试图创制一套完整的形式系统作为数学的基础，当他发现这个系统易受罗素悖论的影响时，就把-演算单独分离出来，用于研究可计算性， 清晰地定义什么是一个可计算函数-演算对函数式编程有巨大的影响，特别是Lisp 语言在-演算的基础上，发展起来的-演算、-演算，成为近年来的并发程序的理论工具l-演算相对于一阶谓词逻辑具有如下的优点：1. 1. l-演算中的l-记号表示法是一种命名法，它为任何函数冠以复杂而又有规则的省缺名。一阶逻辑一个不尽如人意的地方是，它在许多方面显得表达能力不够强，而在l-演算中都大部分的得到了改善2. 2. l-演算的转换规则允许代入、改名、替换操作，而且操作方式都是等式方式，所以自动推理过程的效率很高，因而具有“可运算”的精确定义。一阶逻辑过于复杂，自动推理过程主要依靠搜索、匹配、合一、消解，效率从理论上难以提高3. 3. l-演算的基本计算手段就是归约(把操作符施用于操作数)，必要时采取预先重新命名(相当于一阶逻辑的约束变项改名，以后这两者被认为是一样的，可以通用)，以避免自由变项受约束；一阶逻辑可以说没有计算功能，而l-演算的归约计算模型有多种10. 给出lK-演算系统的不动点定理及其证明。对任意l-项F，存在l-项X，使得lKFX=X，此时，称X为F的不动点(fixed points)。证 (构造法)令Wlx.F(xx), (这里：x在F中不自由出现，即xfree(F) 于是： F的不动点就是X0WW验证如下：X0WW = (lx.F(xx)W= F(WW) (b-转换及条件: xfree(F) FX0证明完毕。11. 证明等价式。证明：=(PQ)R)(PQ)R=(PQ)(PQ)R=(PQ)(PQ)R=R12. 构造推理的证明。前提：结论：证明：因为：PQ=PQQR=QR且： RS所以： PQRS即PS13. 用附加前提法构造推理的证明：前提：（结论：A证明：1）A 附加前提引入2）AB 假言推理，根据（1）3）(AB)(CD) 前提引入4）CD 假言推理，根据（2）（3）5）D 假言推理，根据（4）6）DF 假言推理，根据（5）7）(DF)E 前提引入8）E