- 1.00 MB
- 2022-08-30 发布
- 1、本文档由用户上传,淘文库整理发布,可阅读全部内容。
- 2、本文档内容版权归属内容提供方,所产生的收益全部归内容提供方所有。如果您对本文有版权争议,请立即联系网站客服。
- 3、本文档由用户上传,本站不保证质量和数量令人满意,可能有诸多瑕疵,付费之前,请仔细阅读内容确认后进行付费下载。
- 网站客服QQ:403074932
《计算机数学》南京邮电大学计算机学院王海艳wanghy@njupt.edu.cn10/7/20211\n主要参考书:(1)上海科技文献出版社《离散数学理论.分析.题解》左孝凌等编著(2)清华大学出版社《离散数学学练考全面冲刺》王海艳编著(3)清华大学出版社《离散数学习题与解析》胡新启等编著(4)高等教育出版社《离散数学结构》第四版影印版DISCRETEMATHEMATICALSTRUCTURESBERNARDKOLMAN等著说 明\n计算机数学是现代数学的一个重要分支,是计算机科学中的基础课程,它具有两个特点:(1)以离散量为研究对象,以讨论离散量的结构和相互之间的关系为主要目标,这些对象一般是有限个或可数个元素,充分描述了计算机科学离散性的特点,与我们以前学过的连续数学如高等数学、数学分析、函数论形成了鲜明对比。(2)它是数学中的一个分支,因而它有数学的味道,比如用一些符号、引进一些定义、运用定理推导等等。因而学习离散数学,对提高我们的抽象能力,归纳能力、逻辑推理能力将有很大帮助。我们只介绍集合论与数理逻辑前两部分,共40学时。课程简介\n我们学习前四章:命题逻辑、谓词逻辑、集合论、函数。第一篇数理逻辑逻辑学是研究思维形式和规律的科学。它包括辨证逻辑和形式逻辑。而数理逻辑是:用数学方法来研究形式逻辑的推理规则。这里所指的数学方法,就是指引进一套符号体系,所以又称为符号逻辑。下面介绍数理逻辑的最基本的内容:命题逻辑和谓词逻辑。第一章命题逻辑1-1命题及其表示法所谓命题是指能够判别真假的陈述句。一个命题,总是具有一个确定的“值”,称之为“真值”。一种是True,记为T,另一种是False,记为F。只有能够判别真假的陈述句才是命题。例(1):我是老师。这是一个命题,其真值为T。第一篇 数理逻辑\n(4):本句是假的。若它是命题,若其值为T,则本句是真的;若说它是假,则本句是真的。这是悖论,不能算是命题。(不能确定真假)(2):你住哪儿?(疑问句)(3):这真是太好了!(感叹句)(5):我正在说谎。若它是命题,则应有确定的真值。若为T,则我确定说谎,我讲的是真话,与说谎矛盾。若为F,则我不在说谎,我说的是真话,则“我确实是在说谎”1-1命题及其表示法\n成立,与“不在说谎”矛盾。所以它不是命题,不能确定真假,是悖论。(6):X=3不是命题不能判断真假。命题有两种类型。一是原子命题(不能分解为更简单的陈述句)二是复合命题(由原子命题,联结词,标点符号复合构成的命题)如:我学英语,或者我学日语。由两个原子命题,联结词“或者”,标点符号“,”构成。又如:王英和王兰是姐妹。它是原子命题。关于联结词我们下一节将做详细介绍。1-1命题及其表示法\n在数理逻辑中,用大写英文字母P,Q,R,…表示命题,或带下标的大写字母如Pi,Pj,…或数字如[12]等表示命题,这些表示命题的符号称为命题标识符。如果一个命题标识符表示确定的命题,称之为命题常量;如果一个命题标识符表示任意的命题,称之为命题变元;命题变元不能确定真值,不是命题,就如函数中自变量不代表特定值一样,只是变量。但当命题变元用一个特定命题取代时,就能确定真值,如P用一特定命题取代,称对P进行指派。另外,当命题变元表示原子命题时,称为原子变元。1-1命题及其表示法\n将介绍五个联结词(基本的)(1)否定若P是一命题,则P的否定是一个新的命题,记作P,读作“非P”,其取值情况如下:PPTFFT如P:上海是一个大城市。P:上海不是一个大城市。或:上海是个不大的城市。P取值为T,而P取值为F。1-2联结词\n又如Q:南京是一个小城市。Q:南京不是个小城市。Q值为F,Q取值为T“”是一元运算,相当于数学中的“求相反数”运算。(2)合取(与)P,Q是命题,P,Q的合取是一个复合命题,记做PQ,读作“P与Q”,或“P且Q”。PQ当且仅当P与Q的值都真时,其值为T,否则为F。1-2联结词\nPQPQTTTTFFFTFFFF注意:这里的“与”运算与日常生活中的“与”意义不尽相同。注:列表时P,Q均是先取T后取F如P:今天下雨;Q:明天下雨PQ:今天下雨且明天下雨。又如,P:我们去看电影;Q:房间里有张桌子。PQ:我们去看电影和房间里有张桌子。上述命题PQ在日常生活中无意义,无联系,但在数理逻辑中,PQ是一新的命题。“”是二元运算。1-2联结词\n(3)析取(或)P,Q是命题,P与Q的析取是复合命题,记做PQ,读作“P或Q”。PQ:只要P,Q之一T,则PQ值为T,否则为F。PQPQTTTTFTFTTFFF从取值可以看出,这里的或是指“可兼或”,即P,Q均可都为T,也可一个为T,另一为F。1-2联结词\n例如1:他可能是100米或400米赛跑冠军。P:他可能是100米赛跑冠军。Q:他可能是400米赛跑冠军。则原命题:PⅴQ可兼或但实际中也有不可兼或的例子.例如2:今天晚上我在家看电视或去剧场看戏.P:今晚我在家看电视。Q:今天晚上我去剧场看戏。用PⅴQ表示是否正确呢?PQPⅴQ原命题TTTF1-2联结词\n排斥或、不可兼或,不能用PⅴQ表示,具体表示法以后再学。同学可以自己先思考。又如3:他昨天做了二十或三十道习题。或:大概,不是复合命题。(4)条件P、Q是命题,P和Q的条件是一个复合命题,记作PQ,读作“若P则Q”或“如果P,那么Q”,P—前件,Q--后件。PQ仅当P为T,Q为F时,其值为F,其余情况皆为T。如:P:我借到这本小说。Q:我今夜读完这本小说。PQ:如果我借到这本小说,那么今夜我就读完它。1-2联结词\n1-2联结词PQPQTTTTFFFTTFFT注:P为F时,PQ总为T。而在日常生活中往往无法判断,在数理逻辑中,我们作“善意的推定”,确定值为T。另外在数理逻辑中,PQ前后中可根本毫无联系也能构成条件式。如P:1+1=2Q:今天下雨。PQ:如果1+1=2,那么今天下雨。\n1-2联结词(5)双条件P、Q是命题,其双条件命题是一复合命题,记作PQ,读作“P当且仅当Q”,仅当P、Q真假值相同时,PQ为T,否则为F。PQPQ(P、Q同为F时,PQ值为T)TTT如:P:两个三角形全等。TFFQ:两个三角形对应边相等。FTFR:两个三角形对应角相等。FFTPQ:两个三角形全等当且仅当它们对应边相等。PR:两个三角形全等当且仅当它们对应角相等。\n1-2联结词总结:共介绍了五个联结词。一元运算P,P否定式二元运算P,QPQ合取式PQ析取式PQ条件式PQ双条件式又如P:2+2=4,Q:雪是白的。PQ:2+2=4当且仅当雪是白的。P、Q可毫无联系。\n前面我们介绍了命题的概念,它是可以判别真假的陈述句。学习了其表示方法,介绍了五种基本联结词:否定、合取、析取、条件、双条件。我们将日常生活中的命题用原子命题以及这些联结词表达,将之符号化为公式。但是许多日常生活中的命题是不能用这五个联结词单独写出,而且不是所有一些命题变元、联结词组成的符号串都有意义的公式。而数理逻辑首先就要引进一些符号体系,将实际生活中的命题符号化,给出其命题公式,也就是翻译。下面我们来介绍1-3命题公式与翻译首先给出命题公式的定义定义:命题公式(合式公式),按规律构成:1-3命题公式与翻译\n其中(1)为基础,(2),(3)为归纳,(4)为界限,这是一个递归的定义。是否是否否否否否1-3命题公式与翻译(1)单个命题变元是合式公式(2)若P是一公式,则P也是公式;(3)若P,Q是公式,则(PQ),(PQ),(PQ),(PQ)也是公式:(4)只有有限次地应用(1)、(2)、(3)所得的结果才是公式。例如:判别下列式子是否是公式?(PQ)(PQ(P(PQ))(PQ)(((PQ)R)(PQ))(PQR)(PQ)R)\n注意:“(”,“)”必须成对出现。从定义可以看出:(1)为了减少括号的数目,我们约定:1.最外层括号可以省略:2.运算优先级为:3.具有相同优先级的联结词,按其出现的次序进行运算。1-3命题公式与翻译(2)命题公式实际上是一函数,值域为{T,F),每一个命题变元取值也是{T,F},因而它没有真假值,只有当公式中命题变元用确定的命题代入后,才到一个命题,才能判断其真假。\n例1:他既聪明又用功。1-3命题公式与翻译如((PQ)R)(PQ)可改写为:PQRPQ有了命题公式的定义后,我们如何将日常生活中的命题用具体的公式表示呢?也就是说,如何将之翻译成公式呢?举例说明:首先找出原子命题,有两个:他聪明,用P表示;他用功,用Q表示。P:他聪明。Q:他用功。联结词“既…又…”和联结词“与”意思一致。所以原命题所对应的命题公式为:PQ因而翻译一个命题,关键有两个:\n1-3命题公式与翻译例2:他虽聪明但不用功。这里原子命题也是P.Q.联结词“虽…但”也是“与”,所以公式应为:PQ。找出所有原子命题,并符号表示出来。找出原子命题之间关系对应的联结词。\n例3:如果明天上午七点不下雨,则我去学校。P:明天上午七点下雨;Q:我去学校。“如果…则”与“若,则”一致,所以公式为:PQ。例4:除非你努力,否则你将失败。P:你努力;Q:你将失败。“除非…否则”相当于“如果不…那么…”,所以译为:PQQP1-3命题公式与翻译\n例5:说数理逻辑枯燥无味或毫无价值,那是不对的。P:说数理逻辑是枯燥无味的;Q:说数理逻辑是毫无价值的。这里“或”是“可兼或”,与“ ”意义一致,所以译为:(PQ)。例6:上海到北京的14次列车是下午五点半或六点开。P:上海到北京的14次列车是下午五点半开;Q:上海到北京的14次列车是下午六点开;这里的“或”是“不可兼或”,因而用“PQ”是错误的。1-3命题公式与翻译\n1-3命题公式与翻译我们对P、Q取不同值看原命题的真值情况:PQ原命题PQ(PQ)利用联结词组合起来TTFTFP、Q真值相同时为F,否则为TTFTFT原命题与(PQ)真值相同FTTFT(PQ)FFFTF例7:张三或李四都可以做这件事。P:张三可以做这件事;Q:李四可以做这件事意为张三可以做,李四也能做这件事,所以PQ\n1-3命题公式与翻译以上三个例子“或”意义各不相同,在翻译公式时,务必准确理解其等价含义。例8:我们要做到身体好、学习好、工作好、为祖国四化建设而奋斗。P:我们要做到身体好;Q:我们要做到学习好;R:我们要做到工作好;S:我们要为祖国四化建设而奋斗。PQRS对于命题翻译就举这么多例子,在做题时要针对具体情况而定。\n在介绍真值表前,先介绍分量定义:公式PQS,其中P、Q、S称为公式的分量。定义:命题公式中,对于分量指派真值的各种可能组合,就确定了这个命题公式的各种真值情况,把它汇列成表,就是命题公式的真值表。1、公式PQ,PQPPQ分量为:P、QTTFTTFFF此表就称为公式PQ的真值表FTTTFFTT1-4真值表与等价公式\n2、(PQ)P,其真值表为:PQPPQ(PQ)PTTFTFTFFFFFTTFFFFTFF1-4真值表与等价公式\n1-4真值表与等价公式3、(PQ)(PQ),其真值表为:PQPQPQPQ(PQ)(PQ)TTTFFFTTFFFTFFFTFTFFFFFFTTTT4、 (PQ) (PQ),其真值表为:\nPQPQ(PQ)PQPQ(PQ)(PQ)TTTFFFFTTFFTFTTTFTFTTFTTFFFTTTTT(1)从上面看出,有一些公式,不论分量如何指派,真值永为真,称为永真公式,记为T;有些则真值永为假,记为F。(2)可以看出,在真值表中,命题公式真值的取值数目决定于分量的个数。一个分量,取值可能为2;两个分量,取值可能为4;n个分量,取值可能为。1-4真值表与等价公式\n5.再看PQ,PQ这两个公式的真值表,(为便于比较,写在一起)PQPPQPQTTFTTTFFFFFTTTTFFTTT(3)对于任何指派,这两个公式的真值完全相同,我们把这样的两个公式称为是等价的。1-4真值表与等价公式\n定义:两个公式A和B,设,,…为所有出现于A和B中的原子变元,若给,,…任一组真值指派,A和B的真值相同,则称A和B是等价的,或逻辑相等。记做AB所以,由上式可得PQPQ再由真值表可得(PQ)(PQ)PQ另外,利用真值表可验证下列命题定律:(非常重要)1,对合律:PP2,幂等律:PPP,PPP3,结合律:(PQ)RP(QR)(PQ)RP(QR)1-4真值表与等价公式\n4,交换律:PQQP,PQQP5,分配律:P(QR)(PQ)(PR)P(QR)(PQ)(PR)6,吸收律:P(PQ)P,P(PQ)P7,德.摩根律:(PQ)PQ,(PQ)PQ8,同一律:PFP,PTP9,零律:PTT,PFF10,否定律:PPT,PPF1-4真值表与等价公式\n“”对于“”的分配律,相当与数学中:x(y+z)=xy+xz有了这些等价的公式,我们就考虑能否将它们相互替代,以简化一些运算。首先引入子公式。定义:若X是公式A的一部分,且X是公式,则称X是A的子公式。等价代换定理:设X是公式A的子公式,且XY,如果将A中的X用Y代替,得到公式B,则AB。证明:XY,在相应变元的任意指派下,X和Y的真值相同A和B在相应变元指派下,也取相同的值,故AB利用等价代换定理可以证明一些公式的等价性1-4真值表与等价公式\n例1:求证;Q(P(PQ))QP证:X=P(PQ)P=Y,用P替换X得到QP两式等价。例2:求证(PQ)(PQ)P证:(PQ)(PQ)P(QQ)PTP分配律否定律同一律1-4真值表与等价公式\n例3求证:证:左1-4真值表与等价公式\n1-4真值表与等价公式\nP19.(9)1.ACBCAB?否.若有某种指派,使C的真值为T,但A为T,B为F。则AC与BC真值为T,但AB不成立。讲完1-3,1-4两节,我们来看书上几条习题。P12.(6)用命题形式进行分析。P:它占据空间。R:它不断变化Q:它有质量。S:它是物质。则这个人开始主张:PQRS后来变为:(PQS)(SR)复 习\n如A:PQ.C:QB:P2.ACB?AB否A:PQC:QB:P3.AB?AB是AB则对任一组真值指派。A与B真值相同,则A与B的真值也必相同。由定义AB。请同学们自己做P17(1)作业:P12(5)(7)P18(7)(8)复 习