计算机数学-1

计算机数学-1

《计算机数学》南京邮电大学计算机学院王海艳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的条件是一个复合命题，记作PQ,读作“若P则Q”或“如果P，那么Q”，P—前件，Q--后件。PQ仅当P为T，Q为F时，其值为F，其余情况皆为T。如：P:我借到这本小说。Q:我今夜读完这本小说。PQ:如果我借到这本小说，那么今夜我就读完它。1-2联结词\n1-2联结词PQPQTTTTFFFTTFFT注：P为F时，PQ总为T。而在日常生活中往往无法判断，在数理逻辑中，我们作“善意的推定”，确定值为T。另外在数理逻辑中，PQ前后中可根本毫无联系也能构成条件式。如P:1+1=2Q:今天下雨。PQ:如果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）复　习