西南交大离散数学1_1.ppt

逻辑学,逻辑学是一门研究思维形式及思维规律的科学,判断1,判断2,判断3,新判断,推理,真话,假话,烧死,绞死,我会被绞死,什么是数理逻辑？,用数学方法来研究推理的规律称为数理逻辑。这里所指的数学方法，就是引进一套符号体系的方法，所以数理逻辑又称为符号逻辑，它是从量的侧面来研究思维规律的学科。命题逻辑谓词逻辑,关于逻辑,问题：传说中有一个住在边远小镇上的剃头匠,这个剃头匠只能给那些不自己剃须的人刮胡子,他能给自己剃须吗?问题:边远村庄的每个人要么总说真话,那么总说谎.对旅游者的问题,村民要么回答“是”,要么回答“否”.假定你在这一地区旅游,走到一个岔路口,一条岔路通向你想去的遗址,一条岔路通向丛林深处,此时恰好有一村民站在岔路口,问村民什么样的一个问题就能决定走哪条路?,关于逻辑,问题：甲、乙、丙、丁四人参加拳击比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜；如果甲不获胜，则丁不失败。能否推出结论：如果丙获胜，则丁不失败问题：设计一个控制客厅照明的电路，使得分别装在卧室和客厅的两只开关都能控制照明。,例：,现在是晚上十一点，天很冷。,如果我的程序通过，那么，我很快乐。,如果我很快乐，那么，阳光很好。,由这些前提，可以得到什么结论？,现在是晚上十一点，天很冷。,如果我的程序通过，那么，我很快乐。,如果我很快乐，那么，阳光很好。,PQ,QR,PQ,QR,QP,RQ,R,Q,P,P：程序通过Q：我快乐R：阳光很好,R,第一章数理逻辑,一命题逻辑命题及其表示法联结词命题公式与翻译真值表与等价式重言式与蕴含式对偶与范式推理理论,二谓词逻辑谓词的概念与表示命题函数与量词谓词公式与翻译变元的约束谓词演算的等价式与蕴含式前束范式谓词演算的推理理论本章作业,判断：通过概念对事物是否具有某种属性进行肯定或否定的回答。,一、命题及其表示,1、命题的定义,命题：指能表达判断的陈述句。一个命题，总是具有一个“值”，称为真值。真值只有“真”和“假”两种，记作True（真）和False（假），分别用符号T和F表示。只有具有确定真值的陈述句才是命题，一切没有判断内容的句子，无所谓是非的句子，如感叹句，疑问句，祈使句等都不能作为命题。,2、命题类型命题有两种类型：原子命题：不能分解为更简单的陈述语句的命题。复合命题：由联结词，标点符号和原子命题复合构成的命题。所有这些命题，都应具有确定的真值。联结词的例子，如：“并且”、“或者”、“如果则”等。,例：判断下面的句子是否为命题。（1）中国人民是伟大的。（2）雪是黑的。（3）1+101=110（4）别的星球上有生物。（5）全体立正。（6）明天是否开大会？（7）天气多好啊！（8）我正在说谎。（9）我学英语，或者我学日语。,3、命题的表示在本课程中，我们将使用大写字母A、B、P、Q、，或带下标的大写字母，或方括号括起来的数字。来表示命题。如：P：太阳从西边出来。12：太阳从西边出来。即命题既可用字母也可用数字来表示,命题标识符表示命题的符号。命题常量一个具体的命题。命题变元命题标识符只表示任意命题的位置。注：命题变元不是命题。指派当命题变元P用一个特定的命题取代时，P才能确定真值，称对P进行指派。,命题逻辑与程序语言的对应关系命题标识符程序语言标识符。命题常量逻辑常量。命题变元逻辑变量。指派给逻辑变量赋值。,二、命题联结词,在自然语言中，常常使用“或者”，“并且”，“不是”等一些联结词，对于这种联结词的使用，一般没有很严格的定义。在数理逻辑中，复合命题是由原子命题与联结词组合而成，联结词不仅是复合命题中的重要组成部分，而且起到了运算符的作用。为了便于书写和进行推理演算，必须对联结词作出明确规定并符号化。下面介绍各个联结词。,1）否定,定义：设P为一命题，P的否定是一个新的命题，记作：P。若P为T，P为F；若P为F，P为T。“”是一元运算。其运算规则表如下：,例：P：太阳从东边出来,P：,P：太阳不从东边出来注意：“”表示命题的否定。,2）合取,定义：两个命题P和Q的合取是一个复合命题，记作PQ。当且仅当P、Q同时为T时，PQ为T，其他情况下PQ的真值都是F。“合取”是一个二元运算，称为“与”运算。其运算法则表如下：,联结词“”的运算法则：,注：合取的概念与自然语言中的“并且”意义相似。,例：P：北京是中国的首都。Q：北京是一个故都。PQ：,PQ：北京是中国的首都并且是一个故都。,3）析取,定义：两个命题P和Q的析取是一个复合命题，记作PQ。当且仅当P、Q同时为F时，PQ的真值为F，否则PQ的真值为T。注：从析取的定义可以看到，联结词与汉语中的“或者”的意义类似。“析取”也是二元运算，称为“或”运算，其运算法则表如下：,联词“”的运算法则：注意：“”为可兼或,例：P：成都是中国的首都。Q：成都是一个故都。PQ：,PQ：成都是中国的首都或者是一个故都。,4）条件,定义：给定两个命题P和Q，其条件命题是一个复合命题，记作PQ,读作：“如果P，那么Q”或“若P则Q”。当且仅当P的真值为T，Q的真值为F时，PQ的真值为F，否则PQ的真值为T。我们称P为前件，Q为后件。,联给词“”的运算法则：,例：P：xyQ：x-y0PQ：,PQ：如果xy则x-y0,5）双条件,定义：给定两个命题P和Q，其复合命题PQ称作双条件命题，读作“P当且仅当Q”，当P和Q的真值相同时，PQ的真值为T，否则PQ的真值为F。,联结词“”的运算法则：,注：双条件命题也可以不顾其因果联系，而只根据联结词定义确定真值。亦可记作“”或“iff”。它亦是二元运算。,例：P：两个三角形全等Q：两个三角形的三组对应边相等PQ：,PQ：两个三角形全等当且仅当它们的三组对应边相等。,6）异或（不可兼析取）定义：两个命题P和Q的异或是一个复合命题，记作PQ，异或也称为不可兼析取。当且仅当P、Q不同时为T时，PQ为T，其他情况下的真值都是F。即：相异为T，相同为F。注意：或（）与异或（）区别,可举例说明如下：他是100米或200米冠军。(可兼析取)他是7点或8点离开的。(不可兼析取)异或运算法则表如下：,联结词“”的运算法则：,7）条件否定（PQ）运算法则：,8）与非（PQ）运算法则：,9）或非（PQ）运算法则：,BACK,命题公式与翻译,命题公式：若P和Q是命题变元，则P,PQ,(PQ)(PQ),P(QP)都称作命题公式。注：命题公式是没有真假值的，仅当在一个公式中命题变元用确定的命题代入时，才得到一个命题。,定义:命题演算的合式公式（wff），规定为：（1）单个命题变元本身是一个合式公式。（2）如果A是合式公式，那么A是合式公式。（3）如果A和B是合式公式，那么AB，AB，AB和AB都是合式公式。（4）当且仅当能够有限次地应用1、2、3、所得到的包含命题变元，联结词和括号的符号串是合式公式。,书写规则：1）公式（G）的括号省略，写成G；2）去掉整个公式外的括号3）五种逻辑联结词的优先次序为、则PQR也是合式公式。,上面介绍了5种常用的联结词，在命题逻辑中，可以用这些联结词将各种各样的复合命题符号化，基本步骤如下：,试以符号形式写出命题：例题1我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。例题2飞机九点或十点起飞例题3张三是游泳冠军或百米赛跑冠军,例题4他虽聪明但不用功。例题5除非你努力，否则你将失败。例题6张三或李四都可以做这件事。,BACK,例题1、解：找出各原子命题，并用命题符号表示：A：我们要做到身体好。B：我们要做到学习好。C：我们要做到工作好。P：我们要为祖国四化建设而奋斗。故命题可形式化为：(ABC)P,例题2、解：P：飞机9点起飞。Q：飞机十点起飞。故命题可表达为（PQ）（PQ）例题3、解：P：张三是游泳冠军。Q：张三是百米赛跑冠军。故命题可表达为：PQ,4、解：这里“虽但”这个词不能用前述联结词表达，但其实际意义是：他聪明且不用功。若设：P：他聪明。Q：他用功。则可表示为：