离散数学 命题逻辑讲义.pdf

命题逻辑 Propositional Logic 虞慧群 yhq@ecust.edu.cn 1 数理逻辑体系 数理逻辑是采用数学的方法，研究思维形式及其规律的一 门学科。  对思维的研究转变为对符号的演算。  避免了自然语言的歧义性。  奠定了自动推理的理论基础。 语法（Syntax）：语言符号及表达规则。 语义（Semantics ）：语言符号及表达规则的含义。 形式系统（Formal System）：利用逻辑语言的形式结 构（即从语法的角度）来表达逻辑语句之间的关系。 2 内容提要 1. 命题公式 2. 公式的真值 3. 范式 4. 联结词的完备集 5. 推理理论 3 1 、命题公式 概念： 命题， 联结词(，，，，)，合式公式，子公式 命题：具有确定真值的陈述句。 命题的定义中包含二层含义： (1)在语法上．命题必须是陈述句。而疑问句、祈使 句和感叹句等无所谓真假，所以不是命题。 (2)命题具有惟一的真值，这与我们是否知道它的真 假是两回事。 真值：1(或T)表示 “真”；0(或 F)表示 “假” 命题判断举例 下列句子中那些是命题？ (1) 2是有理数. 假命题 (2) 2 + 5 = 7. 真命题 (3) x + 5 3. 不是命题 (4) 你去教室吗？ 不是命题 (5) 这个苹果真大呀！ 不是命题 (6) 请不要讲话！ 不是命题 (7) 2050年元旦下大雪. 命题，但真值现在不知道 (8) 理发师Richard专门为那些不 不是命题，悖论 给自己理发的人理发。 6 命题符号：用来表示命题符号。  通常用小写英文字母p , q, r, …, p , q , r (i1)表示命题。 i i i 例如，令 p ： 是有理数，则p 的真值为0， 2 q ：2 + 5 = 7，则q 的真值为1  命题符号分类：  命题常元 （命题常项）： （bottom) ，  （top ）  命题变元 （命题变项）: p , q, r, … 7 命题分类 • 简单命题（也称原子命题）：再分解为更简单的 命题。 • 复合命题：若干简单命题通过联结词(connec1ives) 而构成的新命题。 常见的5个联结词  否定(negation)  合取(conjunction)  析取(disjunction)  蕴含(implication)  等价(equailvalence) 这些联结词有明确的含义，注意与自然语言对应词的联系与区别! 否定词符号  设