离散数学命题逻辑 (2)

,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,离散数学,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,第一章 命 题 逻 辑,命题与联结词,逻辑,研究人类思维的科学。公元前四世纪亚里斯多德,工具论,奠定了逻辑学的理论基础。中国最早的一部逻辑专著,墨经,也创造了一个比较完整的逻辑体系。,形式逻辑,辨证逻辑,数理逻辑,数理逻辑,数理逻辑是一门用,数学方法,来研究推理规律的科学。,所谓,数学方法,主要是,指引进一套符号体系的方法,，所以数理逻辑也称做符号逻辑。,（创始人：十七世纪，德国数学家莱布尼兹）,形式符号体系,由于自然语言存在模棱两可、含糊的特性，所以有必要引入,形式化语言,。,形式化语言,在数理逻辑中称为,目标语言,。,例如：今天晚上八点中央一台播放连续剧,或,纪录片。,我吃苹果,或,雪梨。,定义,目标语言,：具有单一、明确的含义的语言。（基本元素是命题）,定义,形式符号体系,：由目标语言和一些规定的公式与符号构成的体系,为何学习数理逻辑,程序,=,算法,+,数据结构,算法,=,逻辑,+,控制,数理逻辑的主要内容,数理逻辑内容丰富，但其主要包括“,两个演算,”,加“,四论,”，即：,逻辑演算,。包括,命题演算,和,谓词演算,证明论,。主要研究数学理论系统的相容性（即不矛盾、协调性）的证明。,递归论,（能行性理论）。自从电子计算机发明后，迫切需要在理论上弄清计算机能计算哪些函数。递归论研究能行可计算的理论，它为能行可计算的函数找出各种理论上精确化的严密类比物。,模型论,。主要是对各种数学理论系统建立模型，并研究各模型之间的关系以及模型与系统之间的关系。,公理集合论,。主要研究在消除已知集合论悖论的情况下，用公理方法把有关集合的理论充分发展下去。,现代数理逻辑,命题逻辑研究的内容,命题逻辑也称为命题演算,研究以命题为基本单位构成的前提和结论之间的可推导关系,.,(1),什么是命题？,(2),如何表示命题？,(3),如何由一些前提推导出一些结论,?,命题与联结词,命题,联结词,命题的概念,具有判断内容（非真即假）的陈述句称为命题。,能够,确定或分辨,其,真假,的,陈述句,。,命题有一个值，称为真值，真值只有“,真,”和“,假,”两种，分别用“,T,”,（或“,1,”,）和“,F,”,（或“,0,”,）表示。,命题中的判断正确，其真值为真，称为真命题，命题中的判断错误，真值为假，称为假命题。,命题示例,1,中华人民共和国的首都是北京。,我们在学习,离散数学,的数理逻辑部分。,所有素数都是奇数。,雪是黑色的。,命题示例,2,某些,感叹句,、,祈使句,、,疑问句,等没有真假之分，所以不是,命题,。,明天开会吗？,多美妙啊！,请进来。,全体立正。,判断语句是否为命题要注意的问题：,目前无法确定真值，但从本质而言，真值存在的语句是命题。,例：,(1),别的星球上有生物。,(2)2046,年世界杯在中国举行。,真值因时因地而异的判断性陈述句是命题。,例：,(1),现在是上午。,(2),今天下雨。,含有未确定内容的代词，不能判断真假的语句不是命题。,例：,(1)1+101=110,。,当,1,和,101,是二进制数，语句为真，为十进制数，语句为假。,(2)x+y10,。,悖论不是命题。,例：我正在说慌。,命题的分类,根据命题的构成形式，可以将命题分为：,定义,原子命题,：不包含任何联结词的,命题,。,定义,复合命题,：,由,原子命题,和联结词组成的命题,。连接词一般译为：,“,或者,”,、,“,并且,”,、,“,不,”,、,“,如果,则,”,、,“,仅当,”,、,“,当且仅当,”,等。,例如：,“,明天下雪,”,、,“,9,是素数,”,都是,原子命题,，,“,2,不,是素数,”,是,复合命题,“,明天下雪,或,明天下雨,”,是,复合命题,。,“,中国获得,2008,奥运的主办权,并且,加入了,WTO,”,是,复合命题,。,“,如果,A,和,B,是对顶角，,则,角,A,等于角,B,”,是,复合命题,。,命题的表示,定义,命题标识符：,表示命题的符号，通常是大写英文字母。,定义,命题符号化：,将表示命题的符号放在该命题的前面。,例：,P：,北京是中国的首都,。,Q,：,北京承办,2008,年奥运。,命题的表示（续）,定义,命题常量：,表示,确定命题,的命题标识符。,定义,命题变元：,可表示任意一个（,原子或复合,）命题的,命题标识符,，就称为,命题变元,。当,命题变元,表示,原子命题,时，该变元称为,原子变元。,当命题变元,P,用一个特定命题去取代时，才能确定,P,的真值，这时也称对,P,进行,指派。,例：若,P,是,命题变元，,P：,北京是中国的首都,。（指派,P,为命题北京是中国的首都）,命题,小结,判断一句话是否是命题的步骤：,1,）看它是否是,陈述句,，如果是疑问句、感叹句和祈使句则,不是,命题,；,2,）看它是否是,悖论,，悖论不是命题，如“我正在说谎”；,3,）看它真值,是否,唯一，如果不唯一，则不是,命题,。,命题与联结词,命题,联结词,命题联结词,1.,否定：,2.,合取：,3.,析取：,4.,排斥析取：,5.,条件（蕴含）：,6.,双条件：,否定,设,P,为,命题,，,P,的,否定,也是一个,命题,，记作,P,当,P,为,T,时，,P,为,F,当,P,为,F,时，,P,为,T,P,与,P,的关系如右表,例：,设,P,：上海是个大城市。,则,P,：上海不是一个大城市。,或：上海是个不大的城市。,P,P,F,T,T,F,合取,设,P,、,Q,是命题，,P,和,Q,的,合取,也是个命题，记作,PQ,当且仅当,P,、,Q,同时为,T,时，,PQ,为,T,其他情况下，,PQ,的真值都是,F,读作“,P,并且（与）,Q”,P,Q,PQ,F,F,F,F,T,F,T,F,F,T,T,T,合取示例,(1)P:,我富有,。,Q:,我快乐,。,PQ,：,我富有,并且,快乐,。,(2)P:,我们去食堂吃饭,。,Q:,教室里有三块黑板,。,PQ:,我们去食堂吃饭,并且,教室里有三块黑板,。,注：,复合命题,中的,原子命题,之间无需有一般逻辑意义上的关联，如,(2),。,析取,设,P,、,Q,是命题，则,P,和,Q,的,析取,也是个命题，记作,PQ,。,当且仅当,P,、,Q,同时为,F,时，,PQ,为,F,其他情况下，,PQ,的真值都是,T,读作“,P,或,Q”,（与自然语言中的“或”不完全相同，是兼并或）,P,Q,PQ,F,F,F,F,T,T,T,F,T,T,T,T,析取例子,例：,(1)P,：,猴子吃香蕉,。,Q,：,猴子吃橘子,。,猴子,吃香蕉,或者,吃橘子,？,PQ,(2)P,：,他明天早上吃蛋糕,。,Q,：,他明天早上喝牛奶,。,PQ,？,他明天早上,吃蛋糕,或者,喝牛奶,。,(3)P:,我明天早上,9,点在家看书。,Q:,我明天早上,9,点出去打球。,我明天早上,9,点在家看书,或,出去打球,PQ,？,排斥析取,设,P,、,Q,是命题，,P,和,Q,的,排斥析取,也是个命题，记作,P,Q,当且仅当,P,和,Q,的真值不相同时，,P,Q,为,T,，,其他情况下,P,Q,的真值都是,F,读作“,P,或,Q”,（排斥或）,P,Q,P,Q,F,F,F,F,T,T,T,F,T,T,T,F,P,Q,PQ,F,F,F,F,T,T,T,F,T,T,T,T,排斥析取示例,指出下列命题中的“或”是,析取,还是,排斥析取,今晚我去看演出或在家里看电视现场转播。,他是一百米冠军,或,跳高冠军。,派小王,或,小赵出差去上海。,派小王,或,小赵中的一个出差去上海。,2,、,3,为析取，,1,、,4,为排斥析取,P,Q,P,Q,F,F,F,F,T,T,T,F,T,T,T,F,P,Q,PQ,F,F,F,F,T,T,T,F,T,T,T,T,条件,/,蕴含,设,P,、,Q,是命题，,P,对于,Q,的条件命题记为,PQ,，或称为,P,蕴含,Q,。,当且仅当,P,的真值为,T,，,Q,的真值为,F,时，,PQ,的真值为,F,，,其他情况，,PQ,的真值为,T,。,读作“如果（若）,P,，则,Q”,、“,Q,是,P,的必要条件”、“仅当,Q,为真时，,P,为真”,称,P,为,前件,，,Q,为,后件,。,P,Q,PQ,F,F,T,F,T,T,T,F,F,T,T,T,条件示例,P,：天不下雨,Q,：我去看电影,如果天不下雨，那么我去看电影：,PQ,。,P,：我不到学校去。,Q,：我生病。,PQ,：如果我不到学校去，那么我生病。,P,：我去踢足球。,Q,：我有时间。,仅当我有时间，我去踢足球。,P,Q,?,F,F,T,F,T,T,T,F,F,T,T,T,P,Q,双条件,P,、,Q,是命题，,P,和,Q,的,双条件,命题记作：,P,Q,当,P,和,Q,的真值相同时，,P,Q,的真值为,T,，,否则,P,Q,的真值为,F,翻译为：“,P,当且仅当,Q,”,或者“若,P,则,Q,，否则，则,Q,”,P,Q,P,Q,F,F,T,F,T,F,T,F,F,T,T,T,双条件示例,P,：整数,a,能被,2,整除,Q,：,a,是偶数。,当且仅当,整数,a,能被,2,整除，,a,才是偶数：,P,Q,。,P,：天不下雨,Q,：我去看足球,P,Q,：如果天不下雨，我就去看足球，否则，我就不去看足球。,P,：,2,2,4,Q,：雪是白的,2,2,4,当且仅当,雪是白的：,P,Q,注,：,复合命题,中的,原子命题,之间无需有一般逻辑意义上的关联。如此例中,P,和,Q,并无因果关系，,P,Q,仍是命题，其真值根据联结词定义以及,P,和,Q,的真值来确定。,综合示例,设,P,表示命题“天下雪”。,Q,表示命题“我去看电影”。,R,表示命题“我有时间”。,试以,符号形式,表示下列命题：,P,PQ,Q R,(QR)P,天不下雪。,如果天不下雪，那么我去看电影。,我去看电影，仅当我有时间。,如果我去看电影且我有时间，那么天不下雪。,联结词小结,1.,复合命题,的真值只取决于构成它们的,原子命题,的真值和命题联结符的定义，而与它们的内容、含义无关，与联结词所连接的两个,原子命题,之间是否有关系无关。,2.,，和,具有,可交换性,，而，没有。,联结词小结,1.“,只要,(,若、当,)A,成立，则,B,成立,”,：,A,B,2.“,仅当,A,成立时,B,成立,”和“,只有,A,成立时，,B,成立,”：,B,A,3.,“,A,成立,否则,B,成立,”：,A,B,。,4.,遇到“,或,”，就需要考察两件事情可否同时发生，若不能同时，则是,，否则用“”。,联结词运算顺序,优先级从高到底排列：,、,/,/,、,命题（合式）公式,定义,命题合式公式,：,(1),单个命题变元本身是一个命题合式公式。,(2),如果,A,是合式公式，则,A,是命题合式公式。,(3),如果,A,和,B,是合式公式，则,A,B,AB,、,A,B,、,AB,、,A,B,都是命题合式公式。,(4),当且仅当能够有限次应用,(1),、,(2),、,(3),所得到的包含命题变元，联结词和括号的符号串是命题合式公式。,命题（合式）公式举例,设,P,、,Q,、,R,、,S,、,T,都是命题变元，判断下列字符串哪些是合式公式：,(1),(P,Q),(2)(P,Q,),(Q,R),(S,T),(3)(P,Q,),(,Q),(4)(P,Q,),，,(P,Q),Q,),(1),和,(2),是命题合式公式