第一章命题逻辑-最终版精要.ppt

第一篇 数理逻辑 Mathematical Logic 数理：Mathematical，数学理论 逻辑：Logic 什么是逻辑 逻辑通常指人们思考问题，从某些已知条件出发推出合理的结论的规律。 逻辑学：一门研究思维形式及思维规律的科学。 逻辑学主要研究对象：推理形式。 公元前四世纪亚里斯多德《工具论》奠定了逻辑学的理论基础。中国最早的一部逻辑专著－－《墨经》也创造了一个比较完整的逻辑体系。 什么是数理逻辑 字面含义：数学理论的逻辑。 广义理解：用数学方法研究演绎规律的学科。 狭义理解：用数学方法研究数学中演绎规律的学科。 研究对象：推理过程的正确性标准。 更深入的理解：就是采用数学的方法来研究思维形式的逻辑结构及其规律的一门科学。 所谓数学的方法就是用一套符号(即人工符号语言)的方法。 1930s-1970s，成为数学的独立分支。 数理逻辑与传统逻辑的区别 1. 使用一整套符号语言，从而简化了推理形式。 2. 借助人工符号语言，使整个推理形式化。 3. 具有系统性。 命题的符号化 目的：把自然语言的句子翻译成由命题变量和逻辑联结词组成的表达式。 1. 首先要明确给定命题的含义。 2. 对于复合命题，找联结词，用联结词断句，分解出各个原子命题。 3. 设原子命题符号，并用逻辑联结词联结原子命题符号，构成给定命题的符号表达式。 二、 等价公式 +, -, ×, ÷看作是数与数间的联结词 可以建立许多等值式 x2-y2=(x+y)(x-y) sin2x+cos2x=1 (x+y)2=x2+2xy+y2 … … 命题逻辑里也同样可以建立一些重要的等值式 数学证明中非常重要的一类步骤是用真值相同的一个语句取代另一个。 因此，在构造数学证明时广泛使用从已知复合命题产生具有相同真值的其他命题的方法。 例如：H1: ?P，H2: (P∨Q) ，C: Q，用真值表法判断  H1，H2 ?C成立吗？ （2）判断： 法一：? P，P ∨ Q的真值都为T的情况为第三行, 而第三行中Q的真值为T, 故有:?P ∧(P∨Q) ?Q 法二：后件Q真值为F的情况为第二和第四行， ? P和P ∨ Q中至少有一个为F，故有:?P ∧(P∨Q) ?Q 解: （1）建立 真值表： P Q H1:?P H2:P∨Q C：Q T T F T T T F F T F F T T T T F F T F F 例如：H1:?P，H2:(P → Q) ，C: Q。用真值表法判断  H1，H2 ?C成立吗？ P Q H1:?P H2: P → Q C：Q T T F T T T F F F F F T T T T F F T T F （2）判断： 法一： ? P，P → Q的真值都为T的情况为第三、四行, 而第 四行中Q的真值为F，故 :?P ∧(P → Q) ?Q。 法二：后件Q真值为F的情况为第二和第四行， 但第四行中 ? P和P →Q中不存在F，故 :?P ∧(P∨Q) ?Q。 解: （1）建立真值表： 证明是一个描述推理过程的命题公式序列，其中每个命题公式或者是已知前提，或者是由前面的公式应用基本等价或蕴含公式得到的结论。 使用这种方法，从前提推导出结论，必须依据事先提供的公认的推理规则。 在数理逻辑中， 两个推理规则。 P规则 (前提引入规则)： T规则 (结论引入规则)： 证明法的要点 （一）规范化形式 （二）推理规则的依据：重要等价式和蕴含式。 （三）三种证明的方法 利用基本等价式或蕴含式，由推理过程中某些先前步骤变换出的新公式（新结论）可以引入。 在推理的任何步骤都可以引入已知的前提。 * 二、证明法 * （一）规范化的形式： 可用3列若干行构成的一张表来表示。 序号 公式 理由（注释行） (1) B1 或P (2) B2 或T (序号) E或 I (3) B3 注意： 并非B1?B2?B3 Bi的获取：前提、中间结论 前提(P),结论(T)，推理规则(I),等价公式(E), 推理的过程实际上是证明条件式是重言式的过程。只不过证明的过程采用另外一种书写格式。 * （二）重要的蕴含式(如教材第43页所示) I1.P∧Q?P I2. P∧Q?Q I3. P?P∨Q I4. Q?P∨Q I5. ?P?P?Q I6. Q?P?Q