1.数理逻辑-01.ppt

离散数学(Discrete Mathematics) 第一部分 数理逻辑（Mathematical Logic) 第一部分 数理逻辑（Mathematical Logic) 逻辑：是研究推理的科学。公元前四世纪由希腊的哲学家亚里斯多德首创。作为一门独立科学，十七世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符号, 又称为数理逻辑(或符号逻辑)。 逻辑可分为： 形式逻辑 数理逻辑:通过数学方法、引进一套符号体系 辩证逻辑 第一部分 数理逻辑（Mathematical Logic) 辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。 形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。 数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。它的创始人Leibniz，为了实现把推理变为演算的想法，把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。 上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。 第一部分 数理逻辑（Mathematical Logic) 从广义上讲，数理逻辑包括四论、两演算——即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题演算和谓词演算。本课在数理逻辑部分也只研究这两个演算。 第一章 命题逻辑 命题及其表示法 联结词 命题公式与翻译 真值表与等价公式 重言式与蕴含式 其他联结词 对偶与范式 推理理论 1.1 命题及其表示法 1.1.1 命题（Proposition) 1.1.2 命题的表示方法 1.1.3 命题的分类 1.1 命题及其表示法 1.1.1 命题 数理逻辑研究的中心问题是推理（inference),而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。 基本概念 命题：能够判断真假的陈述句。 命题的真值：命题的判断结果。命题的真值只取两个 值:真（用T(true)或1表示）、假（用F(false)或0表示） 。 真命题：判断为正确的命题，即真值为真的命题。 假命题：判断为错误的命题，即真值为假的命题。 1.1 命题及其表示法 因而又可以称命题是具有唯一真值的陈述句。 判断命题的两个步骤： 1、是否为陈述句； 2、是否有确定的、唯一的真值。 例：判断下列句子是否为命题。 (1). 100是自然数。 (2). 太阳从西方升起。 (3). 3+3=8 . 1.1 命题及其表示法 (4). How do you do ? 疑问句，不是命题 (5). 明年的十月一日是晴天。 是命题，其真值到明年十月一日方可知道。 (6). x+39 不是命题 (7). 我正在说谎。 是悖论 (8). 1+101=110 二进制中为真，十进制中为假。 (9). 如果太阳从西方升起，那么2是奇数。 T (10). 国足能杀入2010世界杯当且仅当2+2=4。 F 1.1 命题及其表示法 (11). 今天天气多好啊！ 感叹句，不是命题 (12). 请你关上门！ 祈使句，不是命题， (13). 别的星球上有生物。 是命题，客观上能判断真假。 关于命题的注记 某些命题可能无法查明其真值。 命题真假会因时因地而异。例如： a) 人一只手有五指 b) 现在是上午 那些‘自称谓’的陈述句可能产生自相矛盾的结论，故不在讨论之列。例如： ‘我正在说谎’ 请注意: 数理逻辑的任务不在于研究某个具体命题的真假问题，而在于它可以赋予真或假的可能性，特别是研究各命题规定其真值后它们之间的联系。 1.1.2 命题的表示方法 在本书中，用大写英文字母A,B,…,P,Q或带下标的字母P1,P2,P3 , …,或数字(1),[2], …,等表示命题，称之为命题标识符。 例如： P：罗纳尔多是球星。 Q：5是负数。 P3：明天天气晴。 (2)：太阳从西方升起。 皆为符号化的命题，其真值依次为1、0、1或0、0。 1.1.2 命题的表示方法 命题标识符又有命题常量、命题变元和原子变元 之分。 命题常量：表示确定命题的命题标识符。 命题变元：命题标识符如仅是表示任意命题的位置标 志，就称为命题变元。 原子变元：当命题变元表示原子命题时，该变元称为 原子变元。 命题变元也用A