离散数学2省名师优质课赛课获奖课件市赛课一等奖课件.pptVIP

;第一部分

数理逻辑

PartOne

Mathematicslogic;逻辑学:研究人思维形式和规律科学．因为研究对象和方法各有侧重而又分为形式逻辑、辩证逻辑和数理逻辑．

数理逻辑是用数学方法来研究推理形式结构和推理规律数学学科。这里所指数学方法就是引进一套符号体系方法。所以数理逻辑又称符号逻辑，它是从量侧面来研究思维规律。

当代数理逻辑可分为逻辑演算、证实论、公理集合论、递归论和模型论。

本部分仅介绍计算机科学领域中所必需数理逻辑基础知识：命题逻辑和谓词逻辑（一阶逻辑）。;;1.1命题与联结词;一、命题

命题：能判断真假(非真即假)陈说句。

命题真值：命题判断结果。;（1）??4是素数。;定义1.1设p为命题，复合命题“非p”(即“p否定”)称为p否定式，记为┐p。符号┐称为否定联结词。

要求：┐p为真当且仅当p为假。;定义1.2设p,q为两个命题。复合命题“p与q”即“p而且q”称为p与q合取式，记为p∧q。符号∧称为合取联结词。

要求：p∧q为真当且仅当p与q同时为真。;(1)???吴颖既用功又聪明.

(2)???吴颖不但用功而且聪明.

(3)????吴颖即使聪明，但不用功.

(4)???张辉和王丽都是三好学生.

(5)???张辉和王丽是同学.;定义1.3设p,q为两个命题,复合命题“p或q”称为p与q析取式,记为p∨q。符号∨称为析取联结词。

要求：p∨q为假当且仅当p与q同时为假。

注:自然语言中“或”联结两个命题能够含有相容性，也能够含有排斥性。

前者称为相容或，后者称为排斥或。

析取联结词∨指是“相容或”。;（1）张晓静爱唱歌或爱听音乐。

（2）张晓静只能挑选202房或203房。

（3）张晓静是江西人或安徽人。

解：(1)令p:张晓静爱唱歌；q:张晓静爱听音乐，

则：;定义1.4设p,q为两个命题。复合命题“假如p,则q”称为p与q蕴涵式，记作p→q。符号→称为蕴涵联结词，

称p是蕴涵式前件，q是蕴涵式后件，q是p必要条件。

要求：p→q为假当且仅当p为真q为假。

注：1.在自然语言中，“假如p,则q”这种命题还有其它叙述方式，比如：“只要p,就q”，“因为p，??以q”,“p仅当q”,“只有q才p”，“除非q才p”,“除非q，不然非p”等等，它们都可符号化为p→q。

2.在数学或其它自然科学中，“假如p,则q”往往表示是前件p为真，后件q也为真推理关系。但在数理逻辑中，作为一个要求，当p为假时，不论q是真是假，p→q均为真（因为考虑整个语句）。

3.在自然语言中，“假如p,则q”中前件p和后件q往往含有某种内在联络，而在数理逻辑中，p与q能够无任何内在联络。;(1)??假如3+3=6,则雪是白色。

(2)??假如3+3≠6,则雪是白色。

(3)??假如3+3=6,则雪不是白色。

(4)??假如3+3≠6,则雪不是白色。

(5)??只要a能被４整除，则a一定能被２整除。

(6)??a能被４整除，仅当a能被２整除。

(7)??除非a能被２整除，a才能被４整除。

(8)??除非a能被２整除，不然a不能被４整除。

(9)??只有a能被２整除，a才能被４整除。

(10)只有a能被４整除，a才能被２整除。(a是一个给定正整数）。;定义1.5设p,q是两个命题，复合命题“p当且仅当q”称为p与q等价式，记为p?q。符号?称为等价联结词。

要求：p?q为真当且仅当p与q同时为真或同时为假。

注：p?q可了解为“q与p互为充分必要条件”；

它与(p→q)∧(q→p)逻辑关系完全一致。;(1)?√3是无理数当且仅当加拿大位于亚洲。

(2)?2+3=5充要条件是√3是无理数。

(3)?若两圆面积相等,则它们半径相等,反之亦然。

(4)?当王小红心情愉快时,她就唱歌,反之,当她唱歌时,一定心情愉快。;;屡次使用联结词集中联结词，可组成更为复杂复合命题。求复杂复合命题真值时，可依据上述真值表逐次求取。但运算过程中应注意联结词优先次序(包含括号)：

(),┐,∧,∨,→，?。

对同一优先级联结词，按出现先后次序运算。

例1.7令：p：北京比天津人口多；q：2+2=