1 命题逻辑的基本概念.ppt

,主讲：凌卫新理学院信息与计算科学系,引言,现代科学技术的各和领域，都提出了大量离散结构的科学问题。例如计算机科学、程序设计、计算机网络、信息论与编码、通信理论、现代密码学、数字信号处理和形式语言等它们都与离散数学密切相关。离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。主要目标研究离散量的结构和相互之间关系研究对象一般是有限个或可数个元素研究内容数理逻辑、集合论、代数学、组合数学、图论、计算理论、复杂网络、网格及网络计算等,数理逻辑与集合论的主要内容,第一部分数理逻辑第1章命题逻辑的基本概念第2章命题逻辑的等值和推理演算第4章谓词逻辑的基本概念第5章谓词逻辑的等值和推理演算第二部分集合论第9章集合第10章关系第11章函数第12章实数集合与集合的基数,本课程的要求,授课总学时32学时：授课周数为16周，每周2学时；作业课后布置的作业逢单周星期五交，只有当作业收齐交到讲台上后才开始上课；成绩评定平时成绩：20%30%期末考成绩：70%80%,第一部分数理逻辑,先看著名物理学家爱因斯坦出的一道题:一个商人想招聘一个聪明的助手，有两人前来应聘，商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“桌子上有五顶帽子，两顶红色，三顶黑色，现在把灯关掉，并把帽子的位置弄乱，然后我们每人摸一顶帽子戴在自己头上，我再藏起余下的两顶帽子，开灯后，你们要尽快说出自己头上戴的帽子的颜色。”当开灯后，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”请问这个人说得对吗？他是怎么推导出来的呢？,第一部分数理逻辑,这需要经历如下过程：什么是前提？有哪些前提？结论是什么？根据什么进行推理？怎么进行推理？数理逻辑将回答这些问题，它包括命题逻辑一阶逻辑数理逻辑（符号逻辑）是用数学方法来研究推理的形式结构和推理规律的数学学科它除了研究数学基础课题个，还扩展到了现代科学技术中，如程序语言、自动机理论、逻辑网络、机器翻译与机器证明等,第1章命题逻辑的基本概念,1.1命题1.2命题联结词及真值表1.3合式公式1.4重言式1.5命题形式化1.6波兰表达式,1.1命题,命题的概念引例就是要对“我戴的是黑帽子”。进行判断。这样的陈述句称为命题。命题可判断真假的陈述句。如：2是素数。雪是黑色的。命题的真值判断的结果真值的取值真（1或T）与假（0或F）真命题:真值为真的命题（判断正确）假命题:真值为假的命题（判断错误）任何命题的真值都是唯一的。,命题,注意:感叹句、祈使句、疑问句都不是命题如：你跑得真快！全体起立！又开学了吗？陈述句中的判断结果不惟一确定以及悖论也不是命题如：x+531+1=10我正在说谎。判断给定句子是否为命题的步骤首先判定它是否为陈述句，其次判断它是否有唯一的真值。,除地球外的星球有生物。,太阳明天会出来。,命题变项,约定：用大写英文字母（如：P,Q,R,）来形式化命题，如用P表示“2是素数”。用Q表示“2+5=7”。当P表示任一命题时，P称为命题变项（变元）命题与命题变项的区别命题指具体确定真值的陈述句相当于常量如：“2是素数”。命题变项的真值不确定，它不是命题，当它用确定命题取代后，它才能确定真值。,命题的分类,简单命题(原子命题)不能分解为更简单的句子的陈述句。如“2是素数”复合命题由几个简单命题与联结词按一定规则复合而成的命题如：3不是偶数。2是素数和偶数。,1.2命题联结词及真值表,1.否定词定义:设P是一个命题,构造一个新命题是原命题的否定,称该命题是命题P的取否命题,表示成“P”.规定:P为真当且仅当P为假,例如:P:今天下雨.P:今天不下雨.,自然语言中用到的联结词:非,不,并非,真值表公式在所有赋值下的取值情况列成的表,联结词,2.合取词定义:设命题P和Q是两个命题,构造一个新命题“P与Q”,称作命题P和Q的合取,表示成“PQ”.规定当且仅当P和Q都为真时,PQ为真.自然语言中用到的联结词:“和”，“与”,“并且”“既.又.”“不仅.而且.”“虽然.但是.,例:将下列命题符号化,P:李平聪明.Q:李平用功.(1)李平既聪明又用功.(2)李平虽然聪明但不用功.(3)李平不但聪明而且用功.(4)李平不是不聪明而是不用功.,PQPQPQ(P)Q,例:P:今天下雨.Q:3+3=6今天下雨与3+3=6.可表示为:PQ“”可以连接两个完全没有联系的命题.,联结词,3.析取词定义:设命题P和Q是两个命题,构造一个新命题“P或Q”,称作命题P和Q的析取,表示成“PQ”.规定PQ为假当且仅当P与Q同时为假.当且仅当P和Q中至少一个为真时,PQ为真.,联结词,例如：P:灯泡有故障.Q:开关有故障.灯泡有故障或开关有故障.(可能同时发生)应表示为PQ注意:析取词表示的是“可兼或”.例如:P:小李正在家里看书.Q:小李正在剧场看戏.小李正在家里看书或正在剧场看戏.（不可能同时发生）表示为：(PQ)(PQ)=PQ,4.蕴涵词定义:设P,Q为二命题，复合命题“如果P,则Q”称作P与Q的蕴涵式，记作PQ，并称P是蕴涵式的前件，Q为蕴涵式的后件.称作蕴涵联结词，P是Q的充分条件，Q是P的必要条件。常见错误不分充分与必要条件混淆充分与必要条件,联结词,“如果P，则Q”的不同表述法很多若P，就Q只要P，就QP仅当Q只有Q才P除非Q,才P除非Q,否则非P,联结词,（1）只要不下雨，我就骑自行车上班。（2）只有不下雨，我才起自行车上班。,设：P：天下雨。Q：我骑自行车上班。,（1）等价为：除非下雨，否则我就骑自行车上班。PQ（2）等价为：如果下雨，我就不骑自行车上班。QP注意：PQ中的P和Q不一定有内在联系。,例:将下列命题符号化,联结词,规定PQ为假当且仅当P为真Q为假.当P为假时，PQ为真说明如：P：“天气好”Q：“我去接你”则PQ：“若天气好，则我去接你”当天气好时，我去接了你，此时，PQ真我没去接你，此时，PQ假当天气不好时，我无论去或不去接你均未食言，此时认定PQ为真是适当的,PQ=PQ,联结词,5.双条件词定义：设P，Q为二命题，“P当且仅当Q”称作P与Q的等价式，记作PQ，规定PQ为真当且仅当P与Q真值相同.说明:PQ的逻辑关系:P与Q互为充分必要条件,PQ=(PQ)(QP),联结词举例,P：两个三角形是全等的。Q：两个三角形的三条对应边相等。,则等价命题：PQ：,两个三角形全等，当且仅当它们的三条对应边分别相等。,下列复合命题的真值为(1)2+24当且仅当3+36.(2)2+24当且仅当3是偶数.(3)2+24当且仅当太阳从东方升起.,1,1,0,联结词的优先顺序为：,1.3合式公式,合式公式它由命题、命题变项按照一定的逻辑顺序用命题联结词连接起来构成合式公式（公式）的递归定义：简单命题是合式公式若A是合式公式，则(A)也是合式公式若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式当且仅当经过有限次地使用(1)(3)所组成的符号串才是合式公式说明:(PQ),P(QR),(PQ)R是合式公式PQR,PQ，(PR)(RP)不是合式公式,例如：合式公式A=（PQ）R若P:“2是素数”，Q:“3是奇数”，R:“4能被2整除”则A为真命题。若P:“2是素数”，Q:“3是奇数”，R:“3能被2整除”则A为假命题。,合式公式的真值,一个含有命题变项的合式公式的真值是不确定的.只有对合式公式的每个命题变项用指定的命题代替后，合式公式才成为命题，其值才唯一确定。,公式的赋值,定义给公式A中的命题变项P1,P2,Pn指定一组真值称为对A的一个赋值或解释成真赋值:使公式为真的赋值成假赋值:使公式为假的赋值说明：A中仅出现P1,P2,Pn，给A赋值12n是指P1=1,P2=2,Pn=n，i=0或1.如：A=（PQ）R。010（P=0，Q=1，R=0）为成真赋值，110（P=1，Q=1，R=0）为成假赋值含n个变项的公式有2n个赋值.,1.4重言式,给出公式A=(QP)QP的真值表,若公式A无成假赋值，则称A为重言式(也称永真式),给出公式B=(PQ)Q的真值表,若公式B无成真赋值，则称B为矛盾式(也称永假式),公式的分类,给出公式C=(PQ)R的真值表,若公式C不是矛盾式，则称C为可满足式,注意：重言式是可满足式，但反之不真.,公式的分类,1.6波兰表达式,源程序中算逻表达式的计算机词法分析过程如：(P(QR)(ST)计算机要先识别括号的匹配后才能进一步执行计算(P(QR)(ST),这种多次重复扫描，降低了机器的使用效率，其原因并不在括号的使用上，而在公式中的表示方法。,波兰式,一般地，使用联结词构成公式有三种方式中辍式如：PQ后