1、离 散 数 学计算机学院 软件与理论教研室（ 313）Email:Tel： 4994019 808Discrete Mathematics* 1第一部分数理逻辑基础数理逻辑基础Date 2数理逻辑n 逻辑学 : 研究人的思维形式和规律的科学 ，称为逻辑学。n 由于研究的对象和方法各有侧重而分为形式逻辑、辩证逻辑和数理逻辑。n 数理逻辑 : 是 用数学方法研究推理 ，是 研究推理中前题和结论之间的形式关系的科学 。 所谓推理就是由一个或几个判断推出一个新判断的思维形式 。n 一般认为，数理逻辑是由德国数学兼哲学家 莱布尼兹(G.W.Leibnitz)在 17世纪中叶创立的；n 英国数学家 乔治
2、布尔 (G.Bool)在 1847年出版的逻辑的数学分析一书中发展了逻辑代数（通常称为布尔代数）；Date 3第一章命题逻辑命题逻辑Date 41.1 命 题1.命题的概念p 命题 (Proposition),是指 具有真假之一值的陈述句例 1 几点钟了？ 真开心！ 仔细读这个！ 北京是我们国家的首都（ P） 6不是自然数 (并非 6是自然数 , P)语句 、 和 不是命题 (分别是疑问句、感叹句和祈使 (命令形式 )句 )； 、 是命题，其中 是真命题、 是假命题。Date 5命题的概念n 像 (北京是我们国家的首都 )这样一些 不能被表示 或分解 为更简单的命题 (陈述句 ),称 为 原子
3、命题n 语句 (6不是自然数 )含有逻辑联词 ,不是原子命题， 称 复合 (亦称分子 )命题 。n 一个命题的真或假称为命题的真值。 真值真 用T(True)或 1表示 ； 真值假 用 F(False)或 0表示 。n 由于命题只有真值真、真值假两个真值，所以 命题逻辑也称 二值逻辑 。n 应该 注意 ， 一个陈述句能否分辨真假，与是否知道它的真假，往往并非一回事 。Date 6命题的概念例 2 中国有 12亿人。q 这句话 ,虽不能马上分辨其真假，但是只要认真地去数一数，还是可以确定其真假的。a 如何 判断一个句子是否为命题？p 从语法上看是否为陈述句p 判别该陈述句是否具有真假之一值J 应
4、特别指出的是 : 那些 “自指谓 ”的陈述句 , 不在其列。p 因为这种自指谓的句子 , 往往产生自相矛盾的判断。例 3 我说慌 。显然 ,这个句子从表义上看 , 说它说谎 ,它不说谎；说它不说谎 ,它说谎。即说它真时 , 它却假；说它假时 , 它却真 ;其真假不能确定。Date 7命题的概念a 严格地说 ，一个陈述句中当含有可变时间、可变地点或可变代词时，在可变对象被具体指定之前，不能认为是命题。例 4 这个城市是自治区首府 ; 今天是 30号 (日 ); 她穿着大方。说明： 只有指出讲话人所处地点后 ,才能确定其真假 ; 只有指出讲话人所处的日期才能确定其真假 ; 这个她 ,只有具体指定后
5、才能确定她是否 穿着大方 。n 不过 ,对这类陈述句 我们往往 并不去 “严格说 ”。Date 8命题的概念n 因为 ，在数理逻辑中，我们并不去纠缠各种具体命题的真假问题，而是将命题视为一种形式或一个数学概念。 从语义上讲 ，命题是具有真假之一值的一个个陈述句 而已 。n 即 我们所关心的并不重在陈述句究竟是真还是假，我们所 关心的只是对表示命题的符号怎样赋予真或假 ，并且被赋予真假后如何确定包含这些形式符号的复合命题公式的真与假。Date 9命题符号2.命题符号n 在 命题逻辑 中 ,采用一种形式符号 ,之形式语言与我们通常使用的自然语言不同 , 它由特定意义的命题符号和规则组成 ,其特征是 表义精确 。n 规定原子命题，用大写 (亦可小写 )字母或带下标的字母，如P,Q,R,或 Pi,Qi,Ri,等表示，称表示原子命题的符号为 命题标识符 。Date 10
