[离散数学discrete2A.doc

第二讲 数理逻辑 一、命题逻辑(Propositional Logic) 1. 内容概述 ·简单命题与复合命题：什么是命题？命题联结词及其含义。 ·命题公式与赋值：命题逻辑公式的归纳定义，命题公式的真值表。 ·等值演算：命题公式的等值赋值，重要的等值式。 ·命题联结词的完备集：通过等值演算得到命题联结词的完备集和极小完备集。 ·命题公式的范式：析取范式与合取范式。 ·命题演算系统：使用命题逻辑公式进行推理的形式系统。 ·命题演算系统的语义与命题演算系统的元性质：注意区别形式系统的语法和语义。 2. 简单命题与复合命题 ·命题(proposition)：经典命题逻辑中，称能判断真假但不能既真又假的陈述句为命题。 ·命题对于命题逻辑来说是一个原始的概念，不能在命题逻辑的范围内给出它的精确定义，只能描述它的性质。 ·命题必须为陈述句，不能为疑问句、祈使句、感叹句等，例如下述句子为命题： 1. ?3 是有理数 2. 8小于10 3. 2是素数 4. 乌鸦是黑色的 下列句子不是命题： 1. 这个小男孩多勇敢啊！ 2. 乌鸦是黑色的吗？ 3. 但愿中国队能取胜。 4. 请把门开一开！ 下列句子不可能判断其为真或为假，所以也不是命题： 1. x + y 10 2. 我正在撒谎 ·命题必须具有真假值，从某种意义上来说，疑问句、祈使句、感叹句没有真假之分。但能判断真假，并不意味着现在就能确定其是真还是假，只要它具有能够唯一确定的真假值即可，例如下述陈述句是命题： 1. 明年的中秋节的晚上是晴天 2. 地球外的星球上存在生物 3. 21世纪末，人类将居住在太空 4. 哥德巴赫猜想是正确的 ·经典命题逻辑不区分现在已确定为真，还是将来可能确定为真这种情况，处理与时间有关的真值问题是时态逻辑的任务。经典命题逻辑也不区分是在技术上可以确定为真，还是现在的技术条件下不可以确定为真的这种情况，只承认在技术上，或者说能给出某种方法确定为真的那些东西才为真是直觉逻辑的观点。 ·真命题和假命题：命题是为真或为假的陈述句，称这种真假的结果为命题的真值。如果命题的真值为真，则称为真命题，否则称为假命题。 ·命题常量与命题变量：使用符号来表示命题，通常用p, q或带下标来表示命题常量或者变量。如果命题符号p代表命题常量则意味它是某个具体命题的符号化，如果p代表命题变量则意味着它可指代任何具体命题。如果没有特别指明，通常来说命题符号p等是命题变量，即可指代任何命题。 ·简单命题与复合命题：不能分成更简单的陈述句的命题为简单命题或原子命题，否则称为复合命题，复合命题使用命题联结词联结简单命题而得到。 ·复合命题的联结词通常包括： ·设p是任意命题，复合命题“非p”称为p的否定（非），记为? p。 ·设p和q是任意命题，复合命题“p且q”称为p和q的合取（与），记为p?q。 ·设p和q是任意命题，复合命题“p或q”称为p和q的析取（或），记为p?q。 ·设p和q是任意命题，复合命题“如果p则q”称为p蕴涵q，记为p?q。 ·设p和q是任意命题，复合命题“p当且仅当q”称为p与q等价，记为p?q。 ·上述定义中的非(negation)、合取(conjunction)、析取(disjunction)、蕴涵(implication)和等价(equivalence)是在命题逻辑中的术语，而引号中给出的复合命题是自然语言中的典型用法。当然，命题逻辑中符号化形式的复合命题在自然语言中有许许多多的表达方法，这也是为什么自然语言有歧义的原因，参见教材中的各例题，并注意以下几点： ·p?q的逻辑关系是p?q为真当且仅当p和q中至少有一个为真。但自然语言中的“或”既可能具有相容性，也可能具有排斥性。命题逻辑中采用了“或”的相容性。 ·p?q的逻辑关系是p?q为假当且仅当p为真，而q为假，称p为蕴涵式的前件，q为蕴涵式的后件。现实世界中的“如果…则…”与这种蕴涵有比较大的区别。简单命题逻辑中的这种蕴涵常常称为“实质蕴涵”，相对应地有“严格蕴涵（p严格蕴涵q，意味着p为真，则q不可能为假）”、“相干蕴涵”等。实质蕴涵意味着可从假的前提推出任何命题来，或两个不没有内在联系的命题之间存在蕴涵关系。 ·将日常生活中的陈述句符号化为命题逻辑中的公式是在今后的程序编写等课程中应用数理逻辑知识的重要基础。但就数理逻辑这门课程本身而言，我们只关心公式之间的真值关系，而不关心公式所具体指代的命题。 ·复合命题与简单命题之间的真值关系可用下表给出，其中0代表假，1代表真： p q ? p p?q p?q p?q p?q 0 0 1 0 0 1 1 0