离散前三章总结20081209.ppt

1 1总结总结第第一一章章 命题逻辑命题逻辑(1)(1)命命题题；(2)(2)命命题题联联结结词词：否否定定()，合合取取()，析析取取()，异异或或()，蕴蕴含含()()，等，等值值()()；(3)(3)原子命原子命题题和复合命和复合命题题；(4)(4)命命题题符号化符号化。1.1.命命题题 (1)(1)命命题题常元，命常元，命题变题变元，命元，命题题公式公式(或称公式或称公式)；(2)(2)命命题题公式公式F(PF(P1 1,P,P2 2,P Pn n)的真的真值值指派，公式的真指派，公式的真值值表；表；(3)(3)命命题题公公式式的的分分类类：重重言言式式(或或永永真真式式)、矛矛盾盾式式(或或永永假假式式)和可和可满满足公式；足公式；2.2.命命题题公式公式 2 2总结总结第第一一章章 命题逻辑命题逻辑3.3.命命题题公式公式间间的关系的关系 (1)(1)命命题题公式公式间间的等价关系的等价关系()()(2)(2)命命题题公式公式间间的的蕴蕴含关系含关系()()(3)(3)基本的等价式；基本的等价式；(4)(4)基本的基本的蕴蕴含式含式；(5)(5)判断公式判断公式类类型的方法型的方法(真真值值表、等价公式表、等价公式变换变换、主范式、主范式)；(6)(6)判定两公式是否具有等价和判定两公式是否具有等价和蕴蕴含关系的方法含关系的方法。3 3总结总结第第一一章章 命题逻辑命题逻辑(1)(1)推理的概念：推理的概念：(2)(2)推理推理规则规则：四个：四个规则规则；4.4.命命题逻辑题逻辑的推理理的推理理论论 4 4练习练习9-11.判断下列语句哪些是命题，若是命题，则指出其真值。判断下列语句哪些是命题，若是命题，则指出其真值。（1）只有小孩才爱哭。只有小孩才爱哭。（2）X+6=Y（3）银是白的。银是白的。（4）起来吧，我的朋友。起来吧，我的朋友。(是是假假)(不是不是)(是是真真)(不是不是)2将下列命题符号化将下列命题符号化 （1 1）我看见的既不是小张也不是老李。）我看见的既不是小张也不是老李。解解 令令P：我看见的是小张；我看见的是小张；Q：我看见的是老李。我看见的是老李。则该命题可表示为则该命题可表示为 P Q（2）如果晚上做完了作业并且没有其它的事，他就会如果晚上做完了作业并且没有其它的事，他就会看电视或听音乐。看电视或听音乐。解解令令P：他晚上做完了作业；他晚上做完了作业；Q：他晚上有其它的事；他晚上有其它的事；R：他看电视；他看电视；S：他听音乐。他听音乐。则该命题可表示为则该命题可表示为（P Q）（RS）5 5“如果嫦娥是虚构的，而如果圣诞老人也是虚构的，那如果嫦娥是虚构的，而如果圣诞老人也是虚构的，那么许多孩子受骗了。么许多孩子受骗了。”解：解：令令P：嫦娥是虚构的；嫦娥是虚构的；Q：圣诞老人是虚构的；圣诞老人是虚构的；R：许多孩子受骗了。许多孩子受骗了。则一上语句可表示为：则一上语句可表示为：或或3判断下面一段论述是否为真：判断下面一段论述是否为真：“是是无理数，并且，如果无理数，并且，如果3是无理数，则是无理数，则也是无理数，也是无理数，另外，只有另外，只有6能被能被2整除时，整除时，6才能被才能被4整除整除”解：解：令令P：是无理数；是无理数；S：6能被能被2整除整除Q：3是无理数：是无理数：H：6能被能被4整除整除R：是无理数是无理数语句符号化为：语句符号化为：10101命题的真值为真。命题的真值为真。6 64.证明下列命题公式的等值关系证明下列命题公式的等值关系（1）（PQ）（PQ）（PQ）（2）（）（P（QR）（P Q）（PR）解解(1)（PQ）（PQ）（P Q）E12（PQ）（PQ）E10，E6（PQ）（PQ）（PQ）（2）（P Q）（PR）（P Q）（PR）E11（P P）（QR）E1，E2 P（QR）E7P（QR）（P P （Q Q R R）（P P Q Q）（P P R R）7 75、求出下式的主析取范式、求出下式的主析取范式1）（PQ）（RP）2）（）（PQ）（R P）解：解：1）（PQ）（RP）=（P Q）（R P）=（PQ）（R P）=（PQR）（PQ）=（PQR）（PQ R）（PQ R）2）（）（PQ）（R P）=（P Q）（R P）=（P Q）（R P）=（PQ）（R P）=（P R）（PQ R）=（P Q R）（PQ R）=M0M2=m1,m3,m4,m5,m6,m7=(PQ R)(P Q R)(PQR)(PQ R)(P QR)(P Q R)8 86.利用主范式判断下列两个命题公式是否等价利用主范式判断下列两个命题公式是否等价（1）(PQ)(PR)(QR)（2）(PQ)(PR)解：解：(PQ)(PR)(QR)=(PQ(R R)(P(Q Q)R)(P P)QR)=(PQR)(PQ R)(PQR)(P QR)(PQR)(PQR)=(PQR)(PQ R)(PQR)(P QR)=m1,3,6,7(PQ)(PR)=(PQ(R R)(P(Q Q)R)=(PQR)(PQ R)(PQR)(P QR)=m1,3,6,79 97.设计一盏灯的开关电路时，要求三个开关设计一盏灯的开关电路时，要求三个开关A，B，C的控制：的控制：当且仅当当且仅当AC同时关闭或者同时关闭或者BC同时关闭时灯亮。用同时关闭时灯亮。用F表示灯亮，表示灯亮，p,q,r分别表示开关分别表示开关A，B，C关闭，求关闭，求F=F(p,q,r)的逻辑表达式的逻辑表达式以及以及F的主范式。的主范式。解：解：F=F(p,q,r)=(pr)(qr)F的主析取范式为：的主析取范式为：F=(p(q q)r)(p p)qr)=(pqr)(p qr)(pqr)(pqr)=(pqr)(p qr)(pqr)=m111m101m011=m3,5,7=M0,1,2,4,610108.某电路中有某电路中有1只灯泡和只灯泡和3个开关个开关A，B，C。已知当且仅当在。已知当且仅当在下述下述4种情况之一灯亮。种情况之一灯亮。（1）C的搬键向上，的搬键向上，A和和B的搬键向下。的搬键向下。（2）A的搬键向上，的搬键向上，B和和C的搬键向下。的搬键向下。（3）B和和C的搬键都向上，的搬键都向上，A的搬键向下。的搬键向下。（4）A和和B的搬键都向上，的搬键都向上，C的搬键向下。的搬键向下。求灯亮的逻辑表达式以及主范式。求灯亮的逻辑表达式以及主范式。解：另解：另F表示灯亮，表示灯亮，p,q,r分别表示分别表示A,B,C的搬键向上，则的搬键向上，则F=F(p,q,r)=(p qr)(p q r)(pqr)(pq r)=m001m100m011m110=m1,3,4,6=M0,2,5,7=(pqr)(p qr)(pq r)(p q r)11119.用形式证明方法证明用形式证明方法证明（1）PS是前提是前提 PQ，QR，RS的结论。的结论。（2 2）S S Q Q，SRSR，R R，P P Q Q P P(1)证明证明编编号号公公式式依依据据（1）（2）（3）（4）（5）（6）（7）（8）P PQQ QRRRSSPSP(附加前提附加前提)PT（1），（），（2）PT,（3），（），（4）PT,（5），（），（6）CP,（1），（），（7）PQ，QR，RSPS1212（2）证明证明编编号号公公式式依依据据（1）（2）（3）（4）（5）（6）（7）（8）（9）(10)P PQQSR RSS Q QQ QPP(假设前提假设前提)PT,（1），（），（2）PPT,（4），（），（5）PT（6），（），（7）T,（3），（），（8）F,(1),(9)131310构造下面推理的证明：构造下面推理的证明：如果今天是星期六，我们就要到颐和园或圆明园去玩。如果如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们就不去颐和园玩。今天是星期天，颐和园颐和园游人太多，我们就不去颐和园玩。今天是星期天，颐和园游人太多。所以我们去圆明园玩。游人太多。所以我们去圆明园玩。解：解：令令P：今天是星期六；今天是星期六；Q：我们到颐和和园去玩；我们到颐和和园去玩；R：我们到圆明园去玩；我们到圆明园去玩；S：颐和园游人太多。颐和园游人太多。前提：前提：，结论：结论：R证明：证明：(1)P(2)PP(3)T，(1)(2)(4)P(5)SP(6)T，(4)(5)(7)RT，(3)(6)141411.在一次研讨会上，在一次研讨会上，3名与会者根据王教授的口音分别进行名与会者根据王教授的口音分别进行下述判断：下述判断：甲说：甲说：“王教授不是苏州人，是上海人王教授不是苏州人，是上海人”乙说：乙说：“王教授不是上海人，是苏州人王教授不是上海人，是苏州人”丙说：丙说：“王教授不是杭州人，也不是上海人王教授不是杭州人，也不是上海人”王教授听后笑道：王教授听后笑道：“你们你们3人中有人中有1人全说对了，有一人全说人全说对了，有一人全说错了，有错了，有1人对错各半人对错各半”。请问王教授是哪里人？请问王教授是哪里人？151511.符号化下列命题，并用推理方法证明谁是做案者：符号化下列命题，并用推理方法证明谁是做案者：（1）A或或B盗窃了金项链盗窃了金项链（2）若）若A作案，则作案时间不在营业时间作案，则作案时间不在营业时间（3）若）若B提供的证据正确，则货柜不上锁提供的证据正确，则货柜不上锁（4）若）若B提供的证据不正确，则作案时间在营业时间提供的证据不正确，则作案时间在营业时间（5）货柜上锁）货柜上锁另另P：A盗窃了金项链盗窃了金项链Q：B盗窃的金项链盗窃的金项链R：作案时间在营业时间：作案时间在营业时间S：B提供的证据正确提供的证据正确G：货柜上锁：货柜上锁161612.用主范式方法证明下列命题公式的等值关用主范式方法证明下列命题公式的等值关系系（1）(AB)（AC）A（BC）（2）(AB)(AB)(AB)（BA A）1717总结总结第二章第二章 谓词逻辑谓词逻辑(1)(1)个体个体词词、谓词谓词和量和量词词：(2)(2)个体常元、个体个体常元、个体变变元、元、约约束束变变元、自由元、自由变变元元；(3)(3)命命题题函数，个体域，全函数，个体域，全总总个体域。个体域。1.1.基本概念基本概念 (1)(1)原子公式，原子公式，谓词谓词公式：公式：(2)(2)谓词谓词公式的解公式的解释释；(3)(3)谓词谓词公式的分公式的分类类：永真公式，永假公式，可：永真公式，永假公式，可满满足公式。足公式。2.2.谓词谓词公式公式 1818总结总结第第二二章章 谓词逻辑谓词逻辑3.3.谓词谓词公式公式间间的关系的关系 (1)(1)谓词谓词公式公式间间的等价关系的等价关系()()(2)(2)谓词谓词公式公式间间的的蕴蕴含关系含关系()()(3)(3)基本的等价式；基本的等价式；(4)(4)基本的基本的蕴蕴含式含式；(5)(5)判定两公式是否具有等价和判定两公式是否具有等价和蕴蕴含关系的方法含关系的方法 。4.4.谓词逻辑谓词逻辑的推理理的推理理论论 (1)(1)含含有有量量词词的的推推理理规规则则：全全称称特特指指规规则则(US)(US)、存存在在特特指指规规则则(ES)(ES)；(2)P(2)P，T T，CPCP，F F。全称推广全称推广规则规则(UG)(UG)、存在推广存在推广规则规则(EG)(EG)。1919 习习 题题1 1 将下列命题符号化将下列命题符号化.（1 1）在上海高校学习的学生，未必都是上海籍的学生。）在上海高校学习的学生，未必都是上海籍的学生。解解令令H(x)：x是在上海高校学习的学生是在上海高校学习的学生S(y)：y是上海籍的学生是上海籍的学生 或者或者（2 2）没有一位女同志既是国家选手又是家庭妇女。）没有一位女同志既是国家选手又是家庭妇女。解解 令令W(x):x是一位女同志；是一位女同志；C(x):x是国家选手；是国家选手；H(x):x是家庭妇女是家庭妇女 x(W(x(W(x)C(x)H(x)2020（3 3）对对于每一个于每一个实实数数x x，存在一个更大的存在一个更大的实实数数y y。解解 令令R(x)：x是实数；是实数；G(x,y):x比比y大。大。x(R(x)y y(R(y)GR(y)G(y,x)（4 4）某些汽车比所有的火车都慢，但至少有一列火车比每）某些汽车比所有的火车都慢，但至少有一列火车比每辆汽车快。辆汽车快。解解 令令C(x)：x是汽车；是汽车；H(x)：x是火车；是火车；S(x,y):x比比y慢。慢。21212将将下下一一命命题题符符号号化化。分分析析到到个个体体词词、谓谓词词和和量量词词，使用全总个体域。使用全总个体域。“有些大学生不钦佩任何运动员有些大学生不钦佩任何运动员”解：解：令令P(x):x是大学生是大学生Q(y):y是运动员是运动员H(x,y):x钦佩钦佩y22223.将下列各公式翻译成自然语言，个体域为整数集将下列各公式翻译成自然语言，个体域为整数集I，并判断并判断各命题的真值。各命题的真值。(1)(2)(3)解解:(1)对任意整数对任意整数任意整数任意整数，存在整数，存在整数，使得使得。（真命题）。（真命题）(2)对任意整数对任意整数，存在整数，存在整数，使得，使得（假命题）（假命题）(3)存在整数存在整数，使得对于任意整数，使得对于任意整数和任意整数和任意整数，有有（假命题）（假命题）23234试判断下列公式是否永真公式试判断下列公式是否永真公式(1)解：解：原式原式因此，（因此，（1）式是永真公式。）式是永真公式。2424（2）解：原式解：原式此公式不是永真公式此公式不是永真公式设设Q(y)F，个体域，个体域E=a,b,P(a)=T,P(b)=F，则，则但但因此因此不是永真公式。不是永真公式。25255 5 用等价公式变换法证明下一等值式用等价公式变换法证明下一等值式证明证明(1)2626(2)证明证明27276 6 证明下一蕴含式证明下一蕴含式证法一：证法一：此题等价于证明此题又等价于证明282829296 6 证明下一蕴含式证明下一蕴含式证法二：证法二：因此，必存在个体因此，必存在个体c，使，使P(c)为真，为真，Q(c)为真。为真。3030 7.7.用构造推理过程的方法证明用构造推理过程的方法证明证明证明3131证明证明3232用反证法（即用反证法（即F规则）证明规则）证明（x）(A(x)B(x),（x）B(x)(x)A(x)解：解：1、(x)A(x)P规则（假设前提）规则（假设前提）2、（、（x）A(x)T规则和规则和13、A(x)US规则和规则和24、（、（x）(A(x)B(x)P规则规则5、A(x)B(x)US规则和规则和46、B(x)T规则规则3和和57、（、（x）B(x)P规则规则8、B(x)US规则和规则和79、B(x)B(x)T规则规则6和和810、(x)A(x)F规则规则1和和93333用用CP规则证明下式：规则证明下式：（x）（）（y）(P(x)Q(y)(x)P(x)(y)Q(y)解：解：1、(x)P(x)P规则（附加前提）规则（附加前提）2、P(a)ES规则和规则和13、（、（x）（）（y）(P(x)Q(y)P规则规则4、（、（y）(P(a)Q(y)US规则和规则和35、P(a)Q(y)US规则和规则和46、Q(y)T规则规则2和和57、(y)Q(y)UG规则和规则和68、(x)P(x)(y)Q(y)CP规则规则1和和734348、鸟会飞，猴子不会飞，所以猴子不是鸟、鸟会飞，猴子不会飞，所以猴子不是鸟35359、桌上的每本书都是杰作，写出杰作的都是天才，某个不出、桌上的每本书都是杰作，写出杰作的都是天才，某个不出名的人写了桌上的某本书。那么，某个不出名的人是天才。名的人写了桌上的某本书。那么，某个不出名的人是天才。证：证：谓词谓词B(x)：x是桌上的书；是桌上的书；M(x)：x是杰作；是杰作；T(x)：x是天才；是天才；F(x)：x是不出名的；是不出名的；P(x)：x是人。是人。W(x,y)：x写出了写出了y。前提：前提：结论：结论：3636 10.10.求下列公式的前束范式求下列公式的前束范式3737第三章第三章 集合集合 (1)(1)集合以及集合的两种表示方法：枚举法和构造法。集合以及集合的两种表示方法：枚举法和构造法。(2)(2)集合的基数、有限集和无限集。集合的基数、有限集和无限集。(3)(3)集合的子集和幂集。集合的子集和幂集。1.1.集合的基本概念集合的基本概念(1)(1)集合间的包含关系集合间的包含关系(用用 表示表示)。(2)(2)集合集合间间的相等关系的相等关系(用用A=BA=B表示表示)。(3)(3)集合集合间间的真包含关系的真包含关系(用用 表示表示)。2.2.集合集合间间的关系的关系 总结总结3838总结总结第三章第三章 集合集合 由由给给定的集合定的集合A A、B B，(1)(1)求并集求并集ABAB；(2)(2)求交集求交集ABAB；(3)(3)求差集（相求差集（相对补对补集）集）B-AB-A；(4)(4)求补集求补集A=U-AA=U-A；(5)(5)求求对对称差集称差集3.3.集合集合间间的运算的运算 用直用直观观、形象的方法表示集合、形象的方法表示集合间间的关系，有助于集合的关系，有助于集合的的计计数和分析。数和分析。4.4.文氏文氏图图 3939总结总结第三章第三章 集合集合 5.5.包含与排斥原理包含与排斥原理 重点是序偶重点是序偶和两个集合的笛卡尔积和两个集合的笛卡尔积AB。这两个。这两个概念是关系这一概念建立的基础。概念是关系这一概念建立的基础。6.6.多重序元与笛卡多重序元与笛卡尔尔乘乘积积 40401.1.列举出下一集合中所有的元素列举出下一集合中所有的元素 解解:“1010的整数倍的集合的整数倍的集合”2.2.选择适当的定义条件来表达下一集合选择适当的定义条件来表达下一集合解：解：41413.(1)3.(1)给出集合给出集合A A、B B、C C 的例子，使的例子，使,但但。(2)(2)给出集合给出集合A A、B B、C C 的例子，使的例子，使 ,且且 。解解:(1)(1)令令(2)(2)令令4.4.证明集合证明集合 的补集是的补集是 证明证明:42425 5 对于任意集合对于任意集合A A，B B，等式等式 是否成立是否成立？先作一例，试看等式是否成立。先作一例，试看等式是否成立。例：设例：设 则则 由此可知，对任意集合由此可知，对任意集合A A，B B，上述等式不成立。上述等式不成立。4343对任意集合对任意集合A A，B B 进行讨论：进行讨论：任取任取 ，则，则 任取但此时无法推出任取但此时无法推出 或或 ，因此无法确定因此无法确定 或或 abcAB例如：取图中例如：取图中 反之，任取反之，任取 ，则，则 或或 于是于是 或或 ，因此，因此 ，故故 由上可知，对任意集合由上可知，对任意集合A A，B B，但，但 不成立。不成立。44446.设设A=a,b，求，求和和A的幂集。的幂集。解：解：45457.设某班有设某班有20人，其中英语为优的有人，其中英语为优的有10人，数学为优的有人，数学为优的有10人，两者都为优的有人，两者都为优的有5人，问两门都不为优的有多少人？人，问两门都不为优的有多少人？解：解：设英语为优的学生的集合为设英语为优的学生的集合为A，数学为优的学生的集，数学为优的学生的集合为合为B，根据题设，有，根据题设，有|A|=10，|B|=10，则则即两门都不为优的人有即两门都不为优的人有5人人4646补充：基数补充：基数对于有限集合：集合中不同元素的个数。那么对于无对于有限集合：集合中不同元素的个数。那么对于无限集呢限集呢?是否所有无限集的基数都一样？是否所有无限集的基数都一样？等势：当且仅当集合等势：当且仅当集合A的元素与集合的元素与集合B的元素之间存在着的元素之间存在着一一对应，则称一一对应，则称A与与B是等势的，记作是等势的，记作AB B或或A AB B正整数的集合正整数的集合N和正偶整数的集合和正偶整数的集合E是等势的。是等势的。4747补充：基数补充：基数可数集合：与自然数集合等势的任何集合称为可数集合可数集合：与自然数集合等势的任何集合称为可数集合（或称可数无限集合），它们的基数记作（或称可数无限集合），它们的基数记作（阿列夫（阿列夫零）零）与实数集合等势的任何集合，它们的基数记作与实数集合等势的任何集合，它们的基数记作无限集合可以和它的真子集等势，而有限集合不行无限集合可以和它的真子集等势，而有限集合不行