离散数学是计算机科学(编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、计算机网络等)、数学、数字电路、人工智能等多学科的共同语言和基础。本学期将讲授数理逻辑与图论个部分。其中数理逻辑讲授命题逻辑、谓词逻辑两部分，分别由Boole于1847年和Frege于1879年建立。命题逻辑把简单命题作为基本单元进行推理演算；而谓词逻辑对简单命题进一步剖析，并考虑到变量数量的一般与个别。例1：在举重比赛中，有两名副裁判，一名主裁判。当两名以上裁判（必须包括主裁判在内）认为运动员举杠铃合格，按电钮，才裁决合格。试用与非门设计该电路。解：设主裁判为变元A，副裁判分别为变元B和变元C；按电钮为1，不按为0。表示合格与否的灯为Y，合格为1，否则为0。（1）根据逻辑要求列出真值表。真值表（2）由真值表写出表达式：（4）画出逻辑电路图：例2：设计一个楼上、楼下开关的控制逻辑电路来控制楼梯上的路灯。使之在上楼前，用楼下开关打开电灯，上楼后，用楼上开关关灭电灯；或者在下楼前，用楼上开关打开电灯，下楼后，用楼下开关关灭电灯。解：设楼上开关为变元A，楼下开关为变元B，灯泡为变元Y。并设A、B向上时为1，向下时为0；灯亮时Y为1，灯灭时Y为0。本题的解题关键在于：不管开关和灯处于什么状态，灯的状态改变当且仅当只有一个开关的状态发生改变。因此，本题有多解。相应逻辑表达式为（2）若A=0,B=0时Y=1，则相应真值表设计如下用同或门实现第1章命题逻辑的基本概念命题逻辑的基本概念举例说明命题变项简单命题和复合命题复合命题定义：把一个或几个简单命题用联结词(如与、或、非)联结所构成的新的命题称为复合命题．复合命题真值判断：复合命题自然也是陈述句，其真值依赖于构成该复合命题的各简单命题的真值以及联结词，如“张三学英语和李四学日语”就是一个复合命题，由简单命题“张三学英语”“李四学日语”经联结词“和”联结而成，这两个简单命题真值均为真时，该复合命题方为真．数理逻辑关心什么？不关心内容：这些具体的陈述句的真值究竟为什么是真还是假。关心形式：关心的仅是命题可以被赋予真或假这样的可能性，以及规定了真值后怎样与其他命题发生联系．命题联结词及真值表常用的逻辑联结词P例1例22.合取词P例3例4同日常自然用语关系3析取词P例5:P:今天刮风。Q:今天下雨。命题“今天刮风或者下雨”便可由P∨Q来描述了。例6:A:2小于3。B:雪是黑的。A∨B就是命题“2小于3或者雪是黑的”。由于2小于3是真的,所以A∨B必取值为真,尽管“雪是黑的”这命题取假。4蕴涵词P引入的目的：希望用来描述命题间的推理,表示因果关系。即PQ为真时,只要P为真必有Q真,。其它定义：当P=F时对PQ真值的不同定义方式将给推理的讨论带来不同的表示形式,也是允许的。性质：可由、∨来表示：PQ=P∨Q同自然用语关系：蕴涵词与自然用语“如果…那么…”有一致的一面，可表示因果关系。然而P、Q是无关的命题时,逻辑上允许讨论PQ。并且P=F则PQ=T,这在自然用语中是不大使用的。例7:P:n>3(n为整数)Q:n2>9命题PQ表示“如果n>3那么n2>9”,分析PQ的真值。1.P=Q=T。这时如n=4>3,有n2=16>9,这符合事实PQ=T,正是我们所期望的可以PQ表示P、Q间的因果关系,这时规定PQ=T是自然的。2.P=T,Q=F。如n>3而n2<9这是不会成立的,也可用PQ表示P、Q间的因果关系是不成立的,自然规定PQ=F。3.P=F而Q=F或T。如n=2<3有n2=4<9n=-4<3有n2=16>9由于前提条件n>3不成立，而n2>9成立与否并不重要，都不违反对自然用语“如果n>3那么n2>9”成立的肯定。于是P=F时可规定PQ=T。例8：P:2+2=5Q:雪是黑的PQ就是命题“如果2+2=5,那么雪是黑的”。从蕴涵词的定义看，由2+2=5是不成立的或说P取F值,不管Q取真取假都有PQ=T。5双条件词真值表解释：只有当两个命题P、Q的真值相同或说P=Q时,PQ的真值方为T。而当P、Q的真值不同时,PQ=F。性质：若建立(PQ)∧(QP)的真值表,就可发现(PQ)∧(QP)和PQ有相同的真值,于是(PQ)∧(QP)=PQ例9总结取值、真值、真值指派、真值组合、解释：由联结词构成新命题的真值表中，对仅由两个变元P、Q构成的新命题A而言,每个变元有T、F两种取值,从而P、Q共有四种可能的取值,对应于真值表中的四行,每一行中命题A都有确定的真值。对P、Q的每组真值组合(如P=T,Q=F)或说真值指派,都称作命题A的一个解释。上述概念的推广：一般地说,当命题A依