数理逻辑 n逻辑学: 研究人的思维形式和规律的科学 由于研究的对象和方法各有侧重而又分为形式逻 辑、辩证逻辑和数理逻辑 n数理逻辑: 用数学方法研究推理，是研究推理 中前题和结论之间的形式关系的科学所谓推理 就是由一个或几个判断推出一个新判断的思维形 式. 这里所说的数学方法就是建立一套表意符 号体系，对具体事物进行抽象的形式研究的方法 因此，数理逻辑又称符号逻辑这种方法的优 点是表达简洁、推理方便、概括性好、易于分析 等 数理逻辑 n 一般认为，数理逻辑是由德国数学家兼哲学家莱布 尼兹(G.W.Leibnitz)在17世纪中叶创立的其后由英 国数学家布尔(G.Bool)于1847年出版的逻辑的数学 分析一书发展了逻辑代数，即通常称为布尔代数还 有德国数学家弗雷树(F.L.G.Frege)于1879年出版了 表意符号,引入了量词、约束变元，使逻辑演算趋于完 备1930年出生于奥地利的美藉数学家哥德尔 (K.Gdel)的完全性定理证明，使数理逻辑的基础得到 完善意大利数学家皮亚诺(G.Peano)，英国数学家德 摩根(A.DeMorgen)、罗素(B.A.W.Russell)等人都做 了很大贡献，丰富和发展了数理逻辑 数理逻辑 n数理逻辑主要包括五部分：逻辑演算、证明论、 公理化集合论、模型论和递归函数论本篇仅介绍 计算机科学领域中所必需的数理逻辑基础知识： q命题逻辑 q谓词逻辑 1.1命题题逻辑 n能判断真假的陈述语句称为命题。 一个语句如果不能再进一步分解成更为简单的语句, 而且又是一个命题则称此命题为原始命题 n 作为命题的陈述句所表达的判断结果称为命题 的真值，真值只取两个值：真或假。真值为真的命 题称为真命题，真值为假的命题称为假命题。真命 题表达的判断正确，假命题表达的判断错误。任何 命题的真值都是唯一的。 命题题逻辑 n判断给定句子是否为命题，应该分两步 ： n首先判定它是否为陈述句 n其次判断它是否有唯一的真值。 例1 判断是否为命题? n(1) 雪是黑色的。 n(2) x大于y。 n(3) 月球上有冰。 n(4) 2100年元旦是晴天。 n(5)大于3.14 吗？ n(6) 请不要吸烟！ n(7) 这朵花真美丽啊！ n(8) 我正在说假话。 n本例中的8个句子中，(5)是疑问句，(6)是 祈使句，(7)是感叹句，因而这3个句子都不是 命题。 n剩下的5个句子都是陈述句，但(2)无确定的 真值，根据x,y的不同取值情况它可真可假， 即无唯一的真值，因而不是命题。 n虽然今天我们不知道(3)，(4)的真值，但它 们的真值客观存在，而且是唯一的，将来总会 知道(3)的真值，到2100年元旦(4)的真值就 真相大白了。 n若(8)的真值为真，即“我正在说假话”为真 ，也就是“我正在说真话”，则又推出(9)的真 值应为假；反之，若(9)的真值为假，即“我正 在说假话”为假，也就是“我正在说假话”，则又 推出(9)的真值应为真。于是(9)既不为真又不 为假，因此它不是命题。像(9)这样由真推出 假，又由假推出真的陈述句称为悖论。凡是悖 论都不是命题。 例2 n2是偶素数； 2或4是素数； 如果2是素数 ，则3也是素数； 2是素数当且仅当3也是素 数。 全是命题。 n 上述命题都是通过诸如“或”，“如果 ，则”等连词联结而成，这样命题 ，称为复合命题。相对地，构成复合命题的 命题称为简单命题。 1.2 逻辑联词 n联结词是逻辑联结词或命题联结词的简称 ，它是自然语言中连词的逻辑抽象. 有了联 结词，便可以用它和原子命题构成复合命题 常用联结词有以下5种 1.2 逻辑联词 (1) 否定(Negation)， 命题P的否定是命题P,读作非P。从真值表易见 P与P的取值关系：P真，当且仅当P假。 PP T F F T (2) 合取(Conjunction)， 命题P与Q的合取是命题PQ,读作P与Q。 PQ取值“真”，当且仅当P与Q都取真值“真” 。 PP 是一永假式。 P QPQ T T T F F T F F T F F F 1.2 逻辑联词 1.2 逻辑联词 (3) 析取(Disjunction)， n命题P与Q的析取是命题PQ,读作P或Q。 PQ假，当且仅当P与Q都假。 P QP Q T T T F F T F F T T T F 1.2 逻辑联词 (4) 条件联结词(Implication)， n命题PQ,读作“P条件Q”或“如果P,则Q”。当 P为F, PQ为T,称为“善意推定”. PQ假，当 且仅当P真而Q假。 P QPQ T T T F F T F F T F T T 1.2 逻辑联词 (5) 双条件(Bicondition)， n命题P与Q组成双条件命题PQ,读作P当且仅当Q。 PQ 取真，当且仅当P与Q取相同的真值(同真或同假) 。这里称P为双条件命题的左支,称Q为右支。 P Q PQ T T T F F T F F T T T T 1.2逻辑联词 n 以上定义了五种最基本、最常用、也是最 重要的联结词， ，将它们组 成一个集合， ，称为一个 联结词集。其中为一元联结词，其余的都是 二元联结词。 n使用这些联结词的好处就是： 可以将复杂命 题表示成简单的符号公式。 n连接词的优先级: n， 1.3 命题形式与真值函数 n从上可知，命题分两类：一类是原子命题；另一 类是复合命题，它是由原子命题和联结词复合而成 判断一个命题是否为复合命题，其关键是联结词 出现否？出现，则是复合命题；不出现，则是原子 命题 1.3 命题形式与真值函数 1.命题公式 n前面讲了联结词、原子命题变元再加上 圆括号“(”、“)”，便可以进行有限次的连接 ，得到许多字符串，这些字符串是否都有意 义呢？即对其中命题变元作指派后，它们是 否都有确定的真值？答案为否那些有意义 的字符串，称为约中的合式公式，简称命题 公式或公式如何连接才能得到合式公式， 这就需要给出一定的规则 n下面，使用归纳法定义合式公式 1.3命题公式 n(1)单个命题变项称为原子命题公式。单个命题 变项是合式公式，并称为原子命题公式。 n(2)若A是合式公式，则(A)也是合式公式。 n(3)若A，B是合式公式，则(AB)，(AB)， (AB)，(A B)也是合式公式。 n(4)只有有限次地应用(1)(3)形式的符号串才 是合式公式。 n如：(pq)(q r)，(pq)r， p(qr)等都是合式公式，而pqr，（ p(rq)等不是合式公式。 1.3 真值表与等值公式 定理1.3.1 AB当且仅当AB是永真式 n显然，根据有关定义，不难证明此定理所以，又称 AB是永真双条件式 n等价式有下列性质： 自反性，即对任意公式A，有AA 对称性，即对任意公式A和B，若AB，则BA 传递性，即对任意公式A,B和C，若AB、BC， 则AC 4基本等价式命题定律 n在判定公式间是否等价，有一些简单而又经常使用的 等价式，称为基本等价式或称命题定律牢固地记住它 并能熟练运用，是学好数理逻辑的关键之一， 1.3 真值表与等值公式 n应该注意到这一点现将这些命题定律列出如下： (1)双否定: AA (2)交换律: ABBA, AB BA, AB BA (3)结合律: (AB)CA(BC), (AB)CA(BC)， (AB)CA(BC) (4)分配律： A(BC)(AB)(AC)， A(BC)(AB)(AC)， (5)德摩根律: (AB) A B, (AB)A B 1.3 真值表与等值公式 (6)等幂律: AAA，AAA (7)同一律: ATA，AFA (8)零律: AFF， ATT (9)吸收律: A(AB)A, A(AB)A (10)互补律: AAF (矛盾律) AAT (排中律) (11)条件式转化律：AB AB, AB B A (12)双条件式转化律：AB (AB)(BA) , AB(AB)(A B), AB (AB) (13)输出律: (AB)CA(BC) (14)归谬律: (AB)(A B) A 1.3 真值表与等值公式 n上面这些定律，即是通常所说的布尔代数或 逻辑代数的重要组成部分它们的正确性利用 真值表是不难给出证明的 5. 代入规则和替换规则 n在定义合成公式时，我们已看到逻辑联结词 能够把已知公式合并成新的公式，从这个意义 上可把逻辑联结词看成运算除逻辑联结词外 ，还要介绍“代入和“替换”，它们也有从已知公 式得到新的公式的作用，因此也可将它们看成 运算，这不无道理，而且在今后讨论中，它们 的作用也是不容忽视的 1.3 真值表与等值公式 (1)代入规则 定理1.3.2 在一个永真式A中，任何一个原子命 题变元R出现的每一处，用另一个公式代入，所 得公式B仍是永真式本定理称为代入规则 证明: 因为永真式对任意解释，其值都是真， 与所给的某个命题变元指派的真值是真还是假 无关，因此，用一个命题公式代入到原子命题 变元R出现的每一处后，所得命题公式的真值仍 为真，证毕 1.3 真值表与等值公式 例. 求证 (PQ) (PQ)为永真式 证明 由排中律可知，RRT，即R R为永真式今用公式(PQ)代人前面公 式中的命题变元R，则得(PQ)(PQ) 根据代人规则可知，给定公式是永真式 注意，若仅仅把(PQ)代入到一个析取项R ，得到(PQ)R，显然它不是永真式，因 为这不符合代入规则所要求的处处代入 1.3 真值表与等值公式 (2)替换规则 定理1.3.3 设A1是合式公式A的子公式，若 A1B；并且将A中的A1用B1替换，得到公式B理 ，则AB. 本定理称为替换规则 证明 因为A1B, 即对于它们的命题变元做任 何真值的指派；A1与B1的真值相同. 故以B1替 换A1后,公式B与A在对其命题变元做相应的任何 真值指派,它们的真值也相同, 因此AB成立 n满足定理1.3.3条件的替换，称为等价替换 1.3 真值表与等值公式 n利用命题定律和定理1.3.3，可以推演出一些更 为复杂的等价式从定理及例题，可看到，代入和 替换有两点区别： 代入是对原子命题变元而言的，而替换可对命题 公式实行 代入必须是处处代入，替换则可部分替换，亦可 全部替换 1.3命题公式的真值判定方法 n1、真值表法 n真值表，就是能显示一个真值形式在它的命题变 项的各种真值组合下所取真值的图表。 n其作用是判定一个真值形式是重言式、可满足式 或者是矛盾式。 构造真值表的一般方法 n（1）找出给定真值形式中的所有命题变项，列 举出它们的各种真值组合。 n（2）根据真值形式的构成过程，由简到繁列举 出该真值形式的构成部分，真值表的最后一列就是 说要判定的真值形式。 n（3）根据所涉五个基本真值联结词的逻辑特性，分别计 算出每一行中各构成部分的真值，最后得出该真值形式的真 值。 用真值表判定(p q) r) (p (q r)是否为重言式。 pqrp q(p q) rq rp (q r) (p q) r) (p (q r) TTTTTTTT TTFTFFFT TFTFTTTT TFFFTTTT FTTFTTTT FTFFTFTT FFTFTTTT F F FFTTTT 用真值表判定下述推理 n或者逻辑学难学，或者没有多少学生喜欢 它