2.1命题逻辑的基本概念

1离散数学唐存琛刘峰武汉大学国际软件学院2教材与参考资料•教材：–《离散数学》（第2版），屈婉玲、耿素云、张立昂编，清华大学出版社•参考资料：–《离散数学》，刘玉珍、刘咏梅编，武汉大学出版社–《DiscreteMathematicalStructures》BernardKolman,FobertC.BusbyandSharonRoss著PrenticeHall出版社–DiscreteMathematicsandItsApplications，[美]KennethH.Rosen3课程主要内容•数理逻辑•集合论•图论•代数系统*4目的、意义和要求•研究内容：离散量的结构及其相互间的关系。•意义：计算机科学的理论基础。•目的：打基础–必备的数学知识–培养抽象思维能力、逻辑推理能力•教学要求：–内容：第1-7章、第9章（重点），第14章备选，第8、11章自学，第10、12、13章不要求–作业：按时交、课后复习（概念、定理）5学习要求1、课堂要求：•按时上课•认真听讲2、课外要求：•复习(每次课后，安排半个小时)•认真、按时完成作业(每次课后，安排1个小时)6学习考查方法1、出勤率：10%不定期检查出勤情况2、作业完成情况：10%对作业完成情况进行登记3、课堂测验+期中考试：20%共5次4、期末考试（闭卷）：60%7第一篇数理逻辑第1章导论•数理逻辑的概念•数理逻辑的发展简史•数理逻辑的地位和作用8（1）定义§1.1数理逻辑的概念数理逻辑是采用数学方法研究抽象思维推理规律（形式推理）的一门科学。命题逻辑是数理逻辑的基本组成部分之一推理的基本要素是命题把命题作为基本单位来分析符号化研究公式间的关系推导、演算9（2）方法引入一套数学符号系统来进行研究，强调推理过程中前提和结论之间的形式关系。例：A、B、C、D4人做百米竞赛，观众甲、乙、丙预报比赛结果的名次为：甲：C第一，B第二乙：C第二，D第三丙：A第二，D第四比赛结束后发现甲乙丙每人报告的情况都各对一半，试问实际名次如何？1.引入pi,qi,ri,si分别表示“A排名第i，B排名第i，C排名第i，D排名第i”2.给出个命题之间的关系（1）(r1∧┐q2)∨(┐r1∧q2)1（2）(r2∧┐s3)∨(┐r2∧s3)1（3）(p2∧┐s4)∨(┐p2∧s4)13.通过演算规则，得出结果10（3）内容谓词逻辑命题逻辑11（4）分支模型论证明论公理集合论递归论12§1.2数理逻辑的发展简史创立阶段起源阶段完善阶段发展历史13起源阶段德国数学家、哲学家G.Leibniz（1646~1716），提出建立一种普遍的符号语言，利用符号语言进行思维演算的设想。14创立阶段英国数学家G.Bool于1847年发表《逻辑的数学分析》，创建一套表示逻辑推理的基本符号以及符号的运算规律，建立了布尔代数。德国数学家G.Frege于1879年在《概念的演算》一书中引进谓词符号和量词符号，创建第一个比较严格的逻辑演算系统。15完善阶段英国逻辑学家A.N.Witehead和B.Russel于1910将当时的数理逻辑写入了《数学原理》中，使数理逻辑成为了一门专门的学科。20世纪30年代，由于众多科学家的努力，衍生出许多新的分支，如：直觉主义逻辑、多值逻辑、组合逻辑等。16§1.3数理逻辑的地位和作用1、计算机科学的重要的理论基础之一；2、对数学、计算机科学、人工智能、语言学、控制论等诸多学科产生深远的影响。3、在计算机科学中的应用：软件、硬件设计17第2章命题逻辑•2.1命题逻辑基本概念•2.2命题逻辑等值演算•2.3范式•2.4命题逻辑推理理论182.1命题逻辑基本概念•2.1.1命题与联结词–命题与真值(简单命题,复合命题)–联结词(¬,,,,)•2.2.2命题公式及其分类–命题公式及其赋值–真值表–命题公式的分类19§2.1.1命题与联结词1、命题及相关概念（1）命题的定义两者必居其一且只居其一——二值逻辑•命题定义的理解：从两个方面把握这个概念（1）陈述句；（2）真值唯一性（注意：真值可能目前还不知道答案）。命题：一个具有真假意义的陈述句。•什么是真值：只包含真/假两个值的量。T/1—真F/0—假20注意：（1）感叹句、祈使句、疑问句都不是命题（2）陈述句中的悖论以及判断结果不唯一确定的也不是命题21中国的首都在北京。1+1=10请开门！x+y=1明年10月1日是晴天。本命题是假的。李红既学英语又学日语。例1判断下列个自然语言是否是命题22（2）几个基本概念真命题与假命题命题变元与命题常元真命题:真值为真的命题假命题:真值为假的命题若p即可以表示真命题，又可以表示假命题，则称p为命题变元。T永远表示真命题，F表示假命题，称T和F为命题常元。23例2真命题假命题真值不确定疑问句感叹句祈使句悖论(1),(2),(5)是命题,(3),(4),(6)~(8)都不是命题真值确定,但未知下列句子中哪些是命题？并指出命题的真值。(1)北京是中华人民共和国的首都.(2)2+5＝8.(3)x+5＞3.(4)你会开车吗？(5)2050年元旦北京是晴天.(6)这只兔子跑得真快呀！(7)请关上门！(8)我正在说谎话.24（1）简单命题与复合命题（2）联结词的定义（3）联结词的优先级2.联接词25（1）简单命题与复合命题简单命题(原子命题):简单陈述句构成的命题。简单命题的符号化:用p,q,r,…,pi,qi,ri(i≥1)表示用“1”表示真，用“0”表示假复合命题:由简单命题通过联结词联结而成的陈述句。例如如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,如果p,则q又如张三一面喝茶一面看报设p:张三喝茶,q:张三看报,p并且q26（2）联结词的定义•否定词（┐）定义2.1设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作p，符号称作否定联结词,并规定p为真当且仅当p为假。例如p:2是合数,p:2不是合数。p为假,p为真。27•合取词（∧）定义2.2设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作p∧q,∧称作合取联结词,并规定p∧q为真当且仅当p与q同时为真.例如p:2是偶数,q:2是素数,p∧q:表示的含义是2是偶素数。因为p为真,q也为真，所以p∧q为真。28例3将下列命题符号化.解：记p:王晓用功,q:王晓聪明(1)p∧q(2)p∧q(3)p∧q(4)记r:张辉是三好生,s:王丽是三好生,r∧s(5)简单命题,记t:张辉与王丽是同学(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.29•析取词（∨）定义2.3设p、q为命题，复合命题“p或q”称作p与q的析取式，记作p∨q,∨称作析取联结词,并规定p∨q为假当且仅当p与q同时为假。例如张三和李四至少有一人会英语设p:张三会英语,q:李四会英语,符号化为p∨q。30相容或与排斥或析取词表示的是相容或，即p和q均为真时(p∨q)亦为真，而与之对应的还有一个是排斥或，它表示的含义是p和q不能同时为真。例如这件事由张三和李四中的一人去做设p:张三做这件事,q:李四做这件事应符号化为(p∧q)∨(p∧q)31例4将下列命题符号化，并指出其真值解：记p:2是素数,q:3是素数,r:4是素数,s:6是素数(1)p∨r,(2)p∨q,(3)r∨s,(4)记t:元元拿一个苹果,u:元元拿一个梨真值:1真值:1真值:0(t∧u)∨(t∧u)(5)记v:王晓红生于1975年,w:王晓红生于1976年(v∧w)∨(v∧w)又可形式化为v∨w(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.32•蕴涵词（）定义2.4设p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作pq,并称p是蕴涵式的前件,q为蕴涵式的后件.称作蕴涵联结词,并规定,pq为假当且仅当p为真且q为假.例如如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,形式化为pq33蕴涵词的其它表述方式pq的逻辑关系:q为p的必要条件,p为q的充分条件。“如果p,则q”的多种表述方式：若p,就q只要p,就qp仅当q只有q才p除非q,才p除非q,否则非p当p为假时，pq为真(不管q为真,还是为假)34例5设p:天冷,q:小王穿羽绒服，将下列命题符号化注意：pq与qp等值（真值相同）pqpqqp或pqpqqpqppq或qpqp(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.35•等价词（）定义2.5设p,q为命题,复合命题“p当且仅当q”称作p与q的等价式,记作pq,称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假。pq的逻辑关系:p与q互为充分必要条件例如这件事张三能做好,且只有张三能做好设p:张三做这件事,q:这件事做好了形式化为:pq36例6求下列复合命题的真值：10110(1)2+2＝4当且仅当3+3＝6.(2)2+2＝4当且仅当3是偶数.(3)2+2＝4当且仅当太阳从东方升起.(4)2+2＝5当且仅当美国位于非洲.(5)f(x)在x0处可导的充要条件是它在x0处连续.37分析找出简单命题用字母表示简单命题用联接词联接命题符号•命题符号化的一般规则38分析找出简单命题用字母表示简单命题用联接词联接命题符号解令p:我上街q:我累r:我去书店看看则可符号化为：（pq)r例7将下列命题符号化：如果我上街并且我不累，我就去书店看看。简单命题：我上街。我累。我去书店看看。39例8试将下列命题符号化：–如果你不看电影，那么我也不看电影–小王一边吃饭，一边看书解:（1）设p：你看电影，q：我看电影，则：pq（2）设p：小王吃饭，q：小王看书，则：pq40（3）联结词的优先级联结词优先级:(),,,,,同级按从左到右的顺序进行41•【例】分析下列各命题的真值（1）2+2=4当且仅当3是奇数（2）2+2=4当且仅当3不是奇数（3）2+2≠4当且仅当3是奇数（4）2+2≠4当且仅当3不是奇数•【例】将下列命题符号化（1）小王是游泳冠军或者百米赛跑冠军（2）小王现在在宿舍或者在图书馆（3）选小王或者小李中的一人当班长（4）如果我上街，我就去书店看看，除非我很累课堂练习（1）42课堂练习（2）•【例】将下列命题符号化（1）李平既聪明又用功（2）李平虽然聪明，但不用功（3）李平不但聪明，而且用功（4）李平不是不聪明，而是不用功•【例】将下列命题符号化（1）只要不下雨，我就骑自行车上班（2）只有不下雨，我才骑自行车上班（3）若2+2=4，则太阳从东方升起（4）若2+2≠4,则太阳从东方升起43§2.1.2合式公式及其分类1.命题语言的字母表：2.合式公式的基本概念3.真值表4.合式公式的分类441.命题语言的字母表命题语言的字母表：•命题常元：T,F(或1，0)•命题变元：p1,p2,…,pn•联接词：┐，∧，∨，→，•辅助符号：（）45（1）合式公式(命题公式,公式)的定义定义2.6合式公式递归定义如下：(1)单个命题常项或变项是合式公式，并称作原子合式公式；(2)若A是合式公式,则(A)也是合式公式；(3)若A,B是合式公式,则(AB),(AB),(AB),(AB)也是合式公式；(4)只有有限次地应用(1)~(3)形成的符号串才是合式公式。2、合式公式的基本概念说明:(1)元语言符号与对象语言符号(2)在不影响运算顺序时,括号可以省去例如0,p,pq,(pq)(pr),pqr,(pq)r46（2）合式公式的