离散数学p1.13.pptVIP

数理逻辑 用数学的方法来研究推理的规律统称数理逻辑 为什么研究数理逻辑 程序=算法+数据 算法=逻辑+控制 数理逻辑是用数学方法即通过引入表意符号研究推理的学问。因此，数理逻辑又名为符号逻辑。 命题逻辑，研究由命题为基本单位构成的前提和结论之间的可推导关系。也称命题演算，记为Ls。 它与谓词逻辑构成数理逻辑的基础，而命题逻辑又是谓词逻辑的基础。 1-1 命题及其表示方法 一.基本概念 命题：具有确定真值的陈述句。 or 真值客观存在且唯一 or 能区分真假 可以看出： （1）一个命题，总是具有一个“值”，称为真值。命真真命题：真值为真(T，1)的命题。 假命题：真值为假(F，0)的命题。 （2）判断命题规则： 只有具有确定真值的陈述句才是命题； 感叹句，疑问句，祈使句等都不是命题。 真值必须唯一，与是否知道其真值无关。  （3）判断命题的两个步骤： 1、是否为陈述句； 2、是否有确定的、唯一的真值。  1、100是自然数。2、这周四是否开会？3、1＋101＝1104、How do you do ?5、别的星球上有生物。 6、2011年国庆是晴天。7、x+398、我正在说谎。9、全体立正！ 10、离散数学是我们的基础必修课。 11、我学英语，或者我学日语。 12、 只有天下大雨，他才乘车去上班。 （2）（4）（9）不是命题。 （3）在十进制中为假，二进制中为真，不能确定其真值。不是命题 （7）根据x的值而定，无唯一真值，不是命题。 （5）（6）目前无法确定，但从事物的本质而言，它本身是有真假可言的，即客观存在且唯一，为命题。 （8）是悖论。？ 所以，（1）（5） （6） （10）（11）（12）是命题。 “悖论”这个词的意义比较丰富，它包括一切与人们直觉和日常经验相矛盾的数学结论。由真推出假，由假推出真。 (1) 说谎者悖论 我们陷入了著名的说谎者悖论之中。下面是它的简单形式。 这句话是错的 上面这个句子对吗? 如果是对的，这句话就是错的！ 如果这句话是错的，那这个句子就对了！ 像这样矛盾的说法比你所能想到的还要普遍得多。 著名的理发师悖论是伯特纳德·罗素提出的。 告示: 城里所有不自己刮脸的男人都由我给他们刮脸，我也只给这些人刮脸。 谁给这位理发师刮脸呢？ 如果他自己刮脸，那他就属于自己刮脸的那类人。但是，他的招牌说明他不给这类人刮脸，因此他不能自己来刮。 如果另外一个人来给他刮脸，那他就是不自己刮脸的人。但是，他的招牌说他要给所有这类人刮脸。因此其他任何人也不能给他刮脸。看来，没有任何人能给这位理发师刮脸了！ 伯特纳德·罗素提出这个悖论，为的是把他发现的关于集合的一个著名悖论用故事通俗地表述出来。 简单/原子命题：由不能再分解为更简单的陈述句的陈述句构成。(1) (5) (6) (10) 1、100是自然数。 5、别的星球上有生物。 6、2011年国庆是晴天。 10、离散数学是我们的基础必修课。 复合命题：由简单命题通过联结词联结而成的陈述句。它由原子命题、命题联结词和圆括号组成。 11、我学英语，或者我学日语。 12、 只有天下大雨，他才乘车去上班。 常用大写字母、带下标的大写字母、数字表示命题，称之为命题标识符。 例如：P： 北京是中国的首都。 [2]：北京是中国的首都。 命题常量：表示一个确定的命题的命题标示符。 命题变元：任意命题的位置标志。命题变元不是命题（表示任意命题，不能确定真值） 当命题变元P用一个特定的命题取代时，P才能确定真值，也称对P进行指派。 本节的主要内容有: 1.给出了命题的概念； 2.命题的判断结果称为命题的真值； 3.分类：原子命题, 复合命题。 1-2 联结词 (1)否定联结词 (2) 合取联结词∧ 例1 P ：今天下雨。 Q： 明天下雨。 上述命题的合取为： P∧Q：今天下雨而且明天下雨 or 今天与明天都下雨。 or 这两天都下雨。 例2 P: 地球在运转。Q：2＋2＝4 则 P∧Q：地球在运转 且 2＋2＝4 注意： （1）自然语言中的表示“并且”意思的联结词，如“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”等都可以符号化为∧ 。 （2） 合取的概念与自然语言中的“与”意义类似，但并不完全相同。尤其例2在自然语言中是没有意义的，但在数理逻辑中仍能成为一个新的命题。 （3）不要