离散数学课程教学的理性思考

离散数学教学的理性思考主要内容基本问题数理逻辑数理逻辑是基础离散数学是基础基本问题离散数学数理逻辑集合论图论代数系统常识问：学习离散数学有什么有？答：离散数学是计算机专业基础基本问题“离散数学是计算机专业基础”是什么意思？“离散数学如何是计算机专业基础”是什么意思？离散数学与计算机专业课程关系问题核心课程先修课程计算机导论程序设计基础计算机导论离散结构数学分析或高等数学算法与数据结构高级语言程序设计、离散结构计算机组成基础计算机导论、数字逻辑计算机体系结构计算机组成基础操作系统算法与数据结构数据库系统原理算法与数据结构、离散数学编译原理程序设计、离散结构、算法与数据结构软件工程程序设计、算法与数据结构计算机图形学程序设计、离散数学计算机网络计算机导论、计算机组成、操作系统、算法与数据结构人工智能高级语言程序设计、离散结构数字逻辑计算机导论《高等学校计算机科学与技术专业发展战略报告暨专业规范》为什么离散数学的前导课程是数学？为什么数字逻辑课程前导课程是计算机导论？如何体现离散数学课程的基础性？计算机专业的基础问题逻辑是所有数学推理及其所有自动推理的基础。对于计算机的设计、系统规范说明、人工智能、计算机程序设计、程序设计语言以及计算机科学的其它许多领域，逻辑都有实际的应用。————KennethH.RosenACMComputerScienceCurricula2013DS.离散结构（37个核心一级学时，4个核心二级学时）核心一级学时核心二级学时比例DS/集合、关系与函数49%DS/基础逻辑922%DS/证明方法10127%DS/计数基础512%DS/树和图3110%DS/离散概率6220%集合、基本逻辑和证明方法的知识点集合维恩图并集、交集、补集笛卡尔积、幂集、有限集合的基数关系自反性、对称性、传递性等价关系、偏序关系函数满射、单射、双射反函数函数的复合命题逻辑（参考：命题逻辑同时出现在智能系统/知识推理）逻辑联结词真值表范式（合取范式、析取范式）合式公式的有效性命题推理定律（肯定前件式和否定后件式的概念）谓词逻辑全称量词与存在量词命题逻辑和谓词逻辑的局限蕴含、等价、逆命题、否命题、逆否命题、否定和矛盾等概念数学证明架构直接证明反例证伪反证法数学归纳法结构归纳法弱归纳法与强归纳法（即，第一类数学归纳法和第二类数学归纳法）数学上的递归定义主要内容基本问题数理逻辑数理逻辑是基础离散数学是基础最简单的论域—逻辑域逻辑对象：{0,1}逻辑运算：{,,,,,}逻辑关系：{=,╞}真值表一组逻辑自变量与一个逻辑因变量的对应表真值表定义逻辑运算和关系命题逻辑公式与语言定义：(1).常量0和1是逻辑公式；(2).命题变量是逻辑公式；(3).若Q,R是逻辑公式，则(Q)、(QR)、(QR)、(QR)、(QR)、(QR)是逻辑公式；(4).只有有限次应用(1)—(3)构成的公式是逻辑公式。真值表验证运算性质结合律(P∨Q)∨R=P∨(Q∨R)(P∧Q)∧R=P∧(Q∧R)(PQ)R=P(QR)分配律P∨(Q∧R)=(P∨Q)∧(P∨R)P∧(Q∨R)=(P∧Q)∨(P∧R)P∧(QR)=(P∧Q)(P∧R)交换律Q∨R=R∨QQ∧R=R∧QQR=RQ德摩根律(Q∨R)=Q∧R(Q∧R)=Q∨R逻辑表达式一般方法若xi,j=1，则x'i,j=xk，若xi,j=0，则x'i,j=xi,j若yk=1，k=0,…,n，则yk=x'm-1,k…x'0,ky=y0…yn功能可以用真值表表达所有逻辑运算都可以表达为,

,,的运算。x0…xk…xm-1y000000……………………k100101…………………2m-11…111…逻辑哲学世界是由事实构成的《逻辑哲学论》事实是事物的性质，以及事物之间的关系《我们关于外间世界的知识-哲学上科学方法应用的一个领域》维特根斯坦罗素根据维特根斯坦和罗素的哲学思想，事实是表达事物的性质或表达一些事物之间的关系。世界由事实构成，而命题与事实对应，事实使一个命题为真或为假。最简单的事实称为原子事实，与原子事实对应的是原子命题。原子命题的真或假取决于它与相应的原子事实是否符合。谓词定义：研究对象统称为客体。定义：事物的性质词和事物的关系词统称为谓词。谓词可以表示为Q(x1,...,xn)，其中，Q是谓词，x1,...,xn是客体Q(x)是一元谓词，Q(x,y)二元谓词，Q(x1,...,xn)是n元谓词。谓词对于任意客体都有真值。谓词形式如果谓词形式是Q(x)表示客体x有Q性质；如果谓词形式是Q(x1,...,xn)表示客体x1,...,xn之间有Q关系。量词表示所有客体具有某性质或关系的词称为全称量词，记为x(Q(x)R(x))表示至少有一个客体具有某性质或关系的词称为存在量词，记为

x(Q(x)R(x))合式公式与一阶谓词语言定义：合式公式是按如下规则构成的有穷长符号串。(1).若是x1,…,xn是变元，Qin是n元谓词，则Qin(x1,…,xn)是合式公式。(2).若Q是合式公式，则(Q)是合式公式；(3).若Q和R是合式公式，则(QR)、(QR)、(QR)、(QR)及(QR)是合式公式；(4).若Q是合式公式，x是变元，则(xQ)及(xQ)是合式公式。(5).只有有限次应用(1)—(4)构成的公式是合式公式。思想理论与逻辑语言弗雷格思想理论思想是陈述句的含义思想有真假思想有结构思想通过语言来表达和传递存在判定思想同一性的标准思想影响人的意志自然语言符合逻辑语言在保持思想的情况下，自然语言变换为逻辑语言GottlobFrege1848-1925自然（科学）语言命题符合逻辑语言定义：具有确定真或假含义的陈述句称为原子命题，或简单命题。在自然语言中，'并且'、'或'、'并非'、'如果...，则...。'、'当且仅当'等词也称为联接词。复合语句是一些陈述句用'并且'、'或'、'并非'、'如果...，则...。'、'当且仅当'等联接为一条语句。量化语句是用'所有'、'存在'等量词约束陈述句或复合语句。定义：原子命题用'并且'、'或'、'并非'、'如果...，则...。'、'当且仅当'等联接词联接的语句称为复合命题。定义：用'所有'和'存在'量词约束的原子命题或复合命题称为量化命题。定义：原子命题、复合命题和量化命题统称为命题。符号化机械过程自然语言的命题符号化方法是机械式过程，无需理解具体概念的含义，仅仅将相同的客体、函数、性质或关系分别用相同符号表示。复合语句由简单语句、联接词及量词构成。首先，识别出简单语句，而后，简单语句符号化。复合语句由符号化的简单命题形式和联接词及量词构成。复合语句就可以根据联接词及量词的含义，形成符号化的命题。符号化机械过程（续）自然知识可以表示为命题，所有的自然律也可以表达为命题。自然语言的命题符号化方法：(1).在复合语句中识别出陈述句，并用下划线标出(2).陈述语句符号化相同（不同）的客体用相同(不同)符号表示相同（不同）函数用相同（不同）符号表示相同（不同）性质或关系用相同（不同）符号表示(3).联接词及量词符号化'并且'表示为''，'或'表示为''，'并非'表示为''，'如果...，则...。'表示为''，'当且仅当'表示为'‘'所有'表示为''，'存在'表示为''，形成符号化的命题。数学分析概念在研究过程中，首先用定义的方式给出概念，而后研究概念的性质以及概念之间的关系，形成定理。概念的定义是复合语句，也能够用机械方式符号化。自然语言表达序列极限、函数极限、连续、一致连续、导数等概念，人们可能有二义性理解，即人们对这些概念含义会有不同的理解。如果这些概念符号化，那么，人们对这些概念的理解就会相同。定义（极限）是命题定义：设{xn}是序列，对于任意ε>0，存在N>0，对于任何n，当n>N时，都有|xn-b|<ε，则称序列{xn}的极限是b，记为

。(1)陈述句识别：对于所有ε，ε>0，存在N，N>0，对于任何n，当n>N时，都有|xn-b|<ε。(2).陈述句符号化：所有ε，ε>0，存在N，N>0，对于所有n，当n>N时，都有|xn-b|<ε。(3).联接词和量词符号化ε(ε>0N(N>0n(n>N|xn-b|<ε)))定理是命题定理

：若序列的极限存在，则极限值唯一。ε(ε>0N1(N1>0n(n>N1|xn-a|<ε)),ε(ε>0N2(N2>0n(n>N2|xn-b|<ε))├a=b定理

：若序列{xn}有极限，则{xn}有界。ε(ε>0N(N>0n(n>N|xn-a|<ε)))├M(M>0n(n>0|xn|<M))欧几里德几何学欧几里德（325BC-265BC），古希腊数学家；《几何原本》是一个实质公理系统把点、线、面、角等分为原始定义概念（23）和可定义概念；命题分为公理（5）、公设（5）；由公理公设出发加以证明的定理（467）从简单到复杂，证明相当严格。从而建立了欧几里得几何学的第一个公理化数学体系。公设1.由任意一点到另外任意一点可以画直线。2.一条有限直线可以继续延长。3.以任意点为心及任意的距离可以画圆。4.凡直角都彼此相等。5．(平行公设)若一直线与两直线相交，且若同侧所交两内角之和小于两直角，则两直线无限延长后必相交于该侧的一点。公理1．等于同量的量彼此相等。2．等最加等量，其和仍相等。3，等量减等量，其差仍相等。4．彼此能重合的物体是全等的。5．整体大于部分。希尔伯特证明论通过形式化第一次使证明本身成为数学研究对象。给出初始符号集合构造合式公式规则Γ├Q的证明，构造出1~m个合式公式序列，其中，第m个合式公式是Q，并且1~m合式公式或者是前提或者是公理或者是推导规则形式证明正确性的验证。DavidHilbert1826-1943逻辑证明有何不同？领域知识是提出概念，形成定理，对定理进行证明。通过思想概念的涵义以及关系，形成一个个推理步骤，最后完成证明。领域知识不同，证明方法也不同。在逻辑公理系统中，已知语言、公理、推理规则Γ是前提集,Q是结论Γ是语句集合，Q是语句在逻辑公理系统中，各个领域知识都抽象为形式语言。从形式语言表示的公理和前提集开始，一步步推理到结论。因为推理过程没有领域概念及其涵义，仅有抽象的符号，按照推理规则一步一步进行推理，所以，推理具有统一方法。逻辑公理系统公理系统从一些公理出发，根据演绎法，推导出一系列定理，形成的演绎体系叫作公理系统。公理系统的组成：语言集公理集公理是用于表达推理由之出发的初始肯定命题；推理规则集推理规则是由公理及已证定理得出新定理的规则；定理集表达了肯定的所有命题。谓词逻辑公理系统(1)谓词逻辑语言：L=<{,},{},P,F,C>(2).公理集合：1).公理模式A

1：Q(RQ)2).公理模式A

2：(P(QR))((PQ)(PR))3).公理模式A3：(QR)(RQ)4).公理模式A4：xQ(x)Q(x)[x/t]

其中，项t对于Q中的x是可代入的。

5).公理模式A5：x(QR(x))(QxR(x))

其中x不是Q中自由变元。(3).推理规则1).分离规则（简称MP规则）：从Q和QR推出R。2).全称概括（简称UG规则）：从Q(x)推出(xQ)。演绎与证明Γ├Q的证明，就是要构造一个合式公式的变换序列，其中每一步产生的合式公式，并且或者是公理模式或者是前提模式或者是由分离规或者是全称概括（谓词逻辑）├xQ(x)yQ(y)(y不在Q中出现)证明：

证据：A1=xQ(x)Q(y)A4

A2=y(xQ(x)Q(y))UGA3=y(xQ(x)Q(y))(xQ(x)yQ(y))A5

A4=xQ(x)yQ(y)A3=A2A4证毕定理(传递律)：PQ,QR├PR证明：

证据：A1=(QR)(P(QR))A1A2=QRA2

ΓA3=P(QR)A1=A2

A3

A4=(P(QR))((PQ)(PR))A2A5=(PQ)(PR)A4=A3

A5

A6=(PQ)A6

Γ

A7=(PR)A5=A6→A7证毕定律与规则思维直觉、思维定律与定理。充分理由律（三段论）：Q,QR├R传递律：PQ,QR├PR反证律：如果Γ,Q├R,Γ,Q├R,则Γ├Q归谬律：如果Γ,Q├R,Γ,Q├R，则Γ├Q排中律：├(QQ)矛盾律：├(QQ)引入规则：├P(c)xP(x)选择规则：├xP(x)P(c)命题逻辑定理├(P(QR))(Q(PR))├(QR)((PQ)(PR))├(PQ)((QR)(PR))├((PQ)(PR))(P(QR)├QQ├QQ├QQ├Q((QR)

R)

├Q(QR)R├QQQ├QQQ├(QR)(RQ)├(QR)(QR)├(QR)(QR)

├(QR)(QR)├(QR)(RQ)├(QR)(RQ)├(QR)(RQ)

├Q(QR)├(QQ)(RQ)├(QQ)Q├(QRR)Q├(QR)((QR)Q)├(QR)((QR)Q)

一阶谓词逻辑定理├xR(x)

yR(y)├xR(x)

yR(y)├Q(c)xQ(x)├Q(c)xQ(x)├xR(x)

xR(x)

├xyR(x,y)

yxR(x,y)├xyR(x,y)

yxR(x,y)├xyR(x,y)

yxR(x,y)├xyR(x,y)

xR(x,x)├xR(x,x)

xyR(x,y)├x(P(x)Q(x))(xP(x)xQ(x))├x(P(x)Q(x))(xP(x)

xQ(x))├x(P(x)Q(x))(xP(x)xQ(x))├xP(x)

xQ(x))x(P(x)Q(x))├x(P(x)Q(x))(xP(x)xQ(x))├x(P(x)Q(x))(xP(x)xQ(x))├xP(x)xP(x)├xP(x)xP(x)├xP(x)xP(x)├

xP(x)xP(x)论域、解释、赋值与模型在指定论域上，对于一阶逻辑语言L解释将常元指称为论域中某客体；将谓词指称为论域上的关系；将函词指称为论域上的函数。赋值将客体变元指称为论域中的客体。一阶逻辑语言的解释，是确定该种语言里的符号表达式同某个论域之间的联系。论域和解释构成了结构。结构和赋值构成了模型。一阶逻辑语言的语义就是在模型上的逻辑真值。合式公式、合式公式集合与模型研究合式公式或合式公式集合QΓ={Q1,...,Qn}在一个模型上具有的性质；在所有模型上具有的性质真值性永真性相等性推论性存在模型可满足性模型永真模型等值模型推论所有模型有效性逻辑永真逻辑等值逻辑推论等式关系和推论关系定义：给定一阶语言L及它的两个公式Q,R，如果存在模型M=<D,σ>，使得σ(Q)=σ(R),则称Q与R是在模型M等值，记为QMR。定义：给定一个语言L,Γ是一个公式集合,Q是一个公式。

若存在模型M=<Dσ>，使得当σ(Γ)=1时，有σ(Q)=1，则称Q是Γ关于模型逻辑推论，记为Γ╞MQ。定义：如果对于任意模型M=<D,σ>，都有

σ(Q)=σ(R),则称Q与R是逻辑等价，记为QR。定义：给定一个语言L,Γ是一个公式集合,Q是一个公式。

若对于任意模型M=<D,σ>，使得当σ(Γ)=1时有σ(Q)=1，则称Q是Γ逻辑推论，或称Γ语义推出Q，记为Γ╞Q。前束范式定义：设δk为,量词，x1…xn为不同变元，Q为开公式，形式为δ1x1…δnxnQ的公式称为前束范式，称δ1x1…δnxn为前束词，称Q为母式。定理：设δk为,量词，x1…xn为不同变元，对于任意合式公式Q，存在前束范式δ1x1…δnxnR，使得Qδ1x1…δnxnR。定义：若δ1x1…δnxnQ的是前束范式，并且Q是合取范式，则称δ1x1…δnxnQ是前束合取范式。前束范式步骤(1).依次用等值公式QR(QR)QR(QR)(RQ)QR

QR进行等值变换，产生的公式仅有联结词、、以及量词、。(2).用等值公式QQ进行变换化简公式。(3).根据以上等值公式，以及如下量词变换等值公式Q(x)xQ(x)Q(x)xQ(x)(4).用德摩根律(QR)QR，(QR)QR进行化简。重复应用(2)、(3)、(4)步骤，逐次将所有联结词置于原子谓词。前束范式步骤（续）(5).用换名等值公式xQ(x)yQ(y)和xQ(x)yQ(y)将所有不同量词辖域的变元换名为互不同的变元。(6).若x不在Q中出现，则QxR(x)x(QR(x))QxR(x)x(QR(x))QxR(x)x(QR(x))QxR(x)x(QR(x))δ1x1Q(x1)δ2R(x2)δ1x1δ2x2(Q(x1)R(x2))δ1x1Q(x1)δ2R(x2)δ1x1δ2x2(Q(x1)R(x2))重复应用(6)步骤，逐次将量词前置，使得公式变换为前束范式。(7).用等值变换交换量词次序xyQ(x,y)yxQ(x,y)xyQ(x,y)yxQ(x,y)等式演算一般方法命题公式:Q的范式是Q'，R的范式是R'，因为QQ'，

Q'R'，R'R。所以QR谓词公式:Q的前束合取范式是Q'，R的前束合取范式是R'，因为QQ'，

Q'R'，R'R。所以QR主要内容基本问题数理逻辑数理逻辑是基础离散数学是基础结构主义在《结构主义》中，皮亚杰给出结构特征结构由对象集合S以及关系集合R、运算集合F和常元集合C组成，<S,R,F,C>整体性、转换、自身调整性结构主义是知识表征的重要方法从结构主义观点看集合论性质定义概念外延与内涵图论结构集合定义概念代数系统操作定义概念定义运算保持封闭性定义关系洞察性质，形成定理逻辑表达概念、运算和关系一般方法证明等式演绎形式证明命题的逻辑构造基本概念与导出概念命题：概念定义是命题。运算定义是命题。关系定义是命题。定理是命题。逻辑命题能由自然语言描述机械式的变换为逻辑描述。联接词,,,,量词,谓词、函词和常元逻辑命题是形式的。集合基本概念、概括性公理集合是一些能够明确区分的对象构成的整体。集合一般用大写英文字母表示，构成集合的对象称为元素，一般用小写英文字母表示。元素与集合有“属于”基本关系，关系如果对象a在集合A中，则称a是A的元素，或者a属于A，记为aA，否则记为aA。概括性公理谓词ψ(x)是给定的一个性质，则ψ(x)确定唯一一个集合。设A={x|ψ(x)}，满足性质ψ(x)的对象都在A中，不满足该性质的对象都不在A中。即x(ψ(x)xA)关系定义设X，Y是集合，若RXY，则称R为从X到Y的关系，简称为关系R。 R={<x,y>|xXyY}若R是从X到Y的关系，就是集合X中元素与集合Y中元素之间的对应。函数定义：设f是从集合X到Y的关系若对每个xX存在唯一yY使得<x,y>f，则称f为从X到Y的函数(映射)，记为f:XY。从X到Y的函数指的是单值全函数，满足 fXYdom(f)=Xran(f)Y <x,y>f<x,z>fy=z满射、单射和双射定义：设函数f:XY，(1).若对于每个yY，都存在xX使得f(x)=y，则称f为满射，即y(yYx(xXf(x)=y))(2).若对于任意xX,yY，只要f(x)=f(y)，就有x=y，或只要xy，就有f(x)f(y)，则称f为单射，即xy(xXyXf(x)=f(y)x=y)(3).若函数f既是单射又是满射，则称f为双射，也称为一一对应。单调性函数定义：设X，Y为集合，≤是全序关系，f:XY，(1).如果对于任意x1<x2，则f(x1)≤f(x2)，则称f是单调递增的x1x2(x1<x2f(x1)≤f(x2))(2).如果对于任意x1<x2，则f(x1)<f(x2)，则称f是严格单调递增的x1x2(x1<x2f(x1)<f(x2))(3).如果对于任意x1<x2，则f(x1)≥f(x2)，则称f是单调递减的x1x2(x1<x2f(x1)≥f(x2))(4).如果对于任意x1<x2，则f(x1)>f(x2)，则称f是严格单调递减的x1x2(x1<x2f(x1)>f(x2))集合运算定义：设A,B为二集合，称由A和B的所有元素组成的集合为A与B的并集，记作AB，称为并运算符。 AB={x|xAxB}AB={x|xAxB}交运算A-B={x|xAxB}差运算A+B={x|xAxB}对称差运算A={x|xA}补运算集合运算也是由集合及“”这两个基本概念的导出概念。关系运算定义：设关系R和S是从X到Y的两个关系，则RS,RS,RS,R+S,R为RS={<x,y>|<x,y>R<x,y>S}RS={<x,y>|<x,y>R<x,y>S}RS={<x,y>|<x,y>R<x,y>S}R+S={<x,y>|<x,y>R<x,y>S}R={<x,y>|<x,y>R}复合运算、指数运算及逆运算R∘S={<x,z>|y(<x,y>R<y,z>S}Rn+1=Rn

∘R（R0=IX）R1={<y,x>|<x,y>R}集合相等关系定义(外延性公理）：如果集合A和B含有相同的元素，则称A和B相等，记为A=B。A=Bx(xAxB)

x(xAxB)x(xBxA)其中表示当且仅当关系。在数理逻辑证明中，用“符号”代替集合符号“”。集合的“=”是集合之间的一种关系，即相等关系；这个等关系也可以是表示相等谓词。谓词“=”概念是由集合及“”这两个基本概念的导出概念。集合包含关系（子集）定义

若集合A的元素都是集合B的元素，则称A是B的子集，也称A包含于B，或者B包含A，记为AB或BA。ABx(xAxB)定义

若AB且AB，则称A是B的真子集，也称A真包含于B，或者B真包含A，记为AB或BA。ABx(xAxB)

x(xBxA)关系“”和“”概念也是由集合及“”这两个基本概念的导出概念。在数理逻辑证明中，“”和“”也可以看作是包含谓词。集合运算性质结合律

(AB)C=A(BC)(AB)C=A(BC)交换律AB=BAAB=BA分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)德摩根律(AB)=A

B(AB)=A

B幂等律AA=AAA=A吸收律A(AB)=AA(AB)=A同一律A

=AAU=A零

律A

=AU=U互补律A

A=A

A=U 对合律

A=A

=U U=关系运算性质

(R1∘R2)∘R3=R1∘(R2∘R3)(R1

R2)∘R3=R1∘R3

R2∘R3

R1∘(R2

R3)=R1∘R2

R1∘R3(R1

R2)∘

R3

R1

∘R3

R2∘

R3

R1

∘(R2

R3)R1

∘R2

R1∘

R3(R1

R2)∘R3

R1

∘R3

R2∘R3RmRn=Rm+n(Rn)m=Rmn(R1R2)-1=R1-1R2-1(R1R2)-1=R1-1R2-1(R1-R2)-1=R1-1-R2-1(~R1)-1=~R1-1

(R∘S)1=S1

∘R1函数运算性质定理：设f:XY，则f∘

IX=IY

∘

f=f。定理

设f:XY，g:YZ，h:ZW，则 h∘

(g∘

f)=(h∘

g)∘

f定理：设f是从X到Y的函数，g是从Y到Z的函数。

若f和g都是满射，则g∘

f是满射。

若f和g都是单射，则g∘

f是单射。

若f和g都是双射，则g∘

f是双射。定理：设f是从X到Y的函数，g是从Y到Z的函数。

若g∘f是满射，则g是满射。

若g∘f是单射，则f是单射。

若g∘f是双射，则g是满射，f是单射。函数运算性质（续）性质：f满足单值性当且仅当f1满足唯一性性质：f满足唯一性当且仅当f1满足单值性定理：设f:XY是双射函数，则存在逆函数f1:YX，并且f1是双射函数。定理

若f:XY是可逆的，则 f1

∘

f=IX且f∘f1=IY定理：设双射f:XY及双射g:YX，g=f1，当且仅当g∘f=IX

且f∘g=IY。定理若双射f:XY及双射g:YZ，则g∘f也是双射，并且(g∘f)1=f1

∘g1

。定理：设f是从X到Y的函数，g是从Y到Z的函数，若f和g是单调增加的，则g∘f是单调增加的。用集合和逻辑定义图概念定义：设V是一个非空顶点集合，E是无向边集合，V和E的有序偶称为无向图G，记为G=<V,E>，其中 E={(x,y)|xVyV}定义：设V是一个非空顶点集合，E是有向边集合，V和E的有序偶称为有向图D，记为D=<V,E>，其中E={<x,y>|xVyV}图的基本结构是指图的顶点之间，边之间及边与顶点之间的连接关系。顶点之间是邻接关系顶点与边是关联关系边与边是相邻关系图包含关系（子图）定义（子图）：设G=<V,E>和GS=<VS,ES>是两个图。若VSV并且ESE则称GS是G的子图。

记为GSG。如果GS是子图并且VSV或ESE，则称GS是G的真子图，记为GSG。 GSGVSVESE GSGGSG(VSVESE)定义（导出子图）：设GS=<VS,ES>是G=<V,E>子图。如果ES是E中所有只关联于VS中的顶点的边的集合，则称GS为VS所导出的子图，简称图G的导出子图，即 ES={e|uVS

vVSe=(u,v)E}定义（生成子图）：设图GS=<VS,ES>是图G=<V,E>的子图。如果VS=V，则称GS为G的生成子图。 GS

GVS=V典型图问题（集合和逻辑表征）连通性穿程问题欧拉图、哈密顿图通路问题最短通路、关键通路树二叉树、生成树二分图及匹配问题图着色问题平面图群的基本概念定义：设G是一个非空集合，∘是二元代数运算，如果满足以下条件：(1).代数运算∘满足结合律，即对G中任意元素a，b，c都有(a∘b)∘c=a∘(b∘c)(2).G中有元素e，称为G的左单位元，对于G中每个元素a都有e∘a=a(3).对G中每个元素a，都有元素a-1，称为a的左逆元，使得a-1∘a=e则称G对代数运算∘作成一个群。群是用运算定义概念群（公理）群理论可以采用数理逻辑方法表示，它有3条公理。定义：设<G,∘>是一个代数系统，<G,∘>称为一个群，如果满足以下条件：(1).对于任意xG，yG，zG，有xyz((x∘y)∘z=x∘(y∘z))(结合律)(2).常元素eG，对于任意xG，有x(e∘x=x)(左单位元)(3).对于每一元素xG，存在元素y，使得xy(y∘x=e)(左逆元)群运算定义：设A，B是群G的任二非空子集，称AB为A与B的乘运算 AB={a∘b|aAbB}定义：设A，B是群G的任二非空子集，称A-1为A的逆运算 A-1={a-1|aA}群包含关系（子群）定义：设G是一个群，H是G的一个非空子集。

如果H本身对G的乘法也作成一个群，则称H为G的一个子群，记为HG。

若H是G的真子群，则简记为HG。 HGx(xHxG) {e}G，GG。群的性质群G的元素a的左逆元a-1也是a的一个右逆元。├a∘a-1=e群G的左单位元e也是G的一个右单位元。├a∘e=a群G的每个元素的逆元都是唯一的。a'∘a=e├a-1=a'群G的单位元是唯一的。x(e'∘x=x)├e'=e设G为群，对于任意aG，bG，有(1).├(a-1)-1=a(2).├(a∘b)-1=b-1∘a-1(1).├(a-1)-1=a群中运算满足消去律。(1).a∘b=a∘cb=c(2).a∘c=b∘ca=b(1).A(BC)=(AB)C(2).A(B∪C)=AB∪AC(3).(A-1)

-1=A(4).(AB)

-1=B-1A-1定理证明方法集合和逻辑表征概念、运算、关系及其定理等式形式的定理有一般的证明方法演绎形式定理有公理方法公理：逻辑公理、专用公理正确证明验证：或者是公理或者是前提或者是推导规则主要内容基本问题数理逻辑数理逻辑是基础离散数学是基础计算机专业基础指令集、操作系统和语言文法都有规范，需求明确基于需求，设计出系统模型判定系统模型正确的准则是什么？软件测试逻辑定义功能，形式建模，定理证明用集合和逻辑进行系统的形式建模数字逻辑（逻辑模型）计算机组成（结构模型）操作系统（操作模型）编译系统（语言模型）用公理系统方法进行形式证明证明之验证数字逻辑数字逻辑是关于数字（二进制数）的逻辑运算、关系判断及操作的逻辑表示方法，以及物理实现。数字逻辑主要有组合逻辑和时序逻辑。数字逻辑部件组合逻辑设计，包括编码器、译码器、比较器、数据选择器、数据分配器、奇偶校验器、算术逻辑单元、乘法器、数据扩展器等。时序逻辑设计，包括计数器、寄存器、移位器等基本问题数字逻辑的理论基础是什么？布尔代数？数字逻辑与离散数学有什么关系？设计数字逻辑部件的一般方法是什么？物理基础组合逻辑：与门、或门、非门时序逻辑：D触发器存贮单元：SRAM、DRAM命题逻辑是数字逻辑基础概念与逻辑表达式数字逻辑部件功能用真值表表达功能：输入与输出之间的关系。结构：实现功能的逻辑表达式。逻辑结构的一般构建方法：给定功能真值表命题逻辑方法求出（、、）逻辑范式构建逻辑部件（非门、与门、或门、寄存器）Verilog等软件实现3线—8线译码器功能表译码是的输入是一个二进制数X，用Xn-1,…,X1,X0表示，输出是二进制数2n-1，用Y2**n-1,…,Y1,Y0表示。输入输出X2X1X0Y7Y6Y5Y4Y3Y2Y1Y00000000000100100000010010000001000110000100010000010000101001000001100100000011110000000Y0=

X2

X1X0Y1=

X2

X1X0Y2=

X2X1X0Y3=

X2

X1X0Y4=

X2

X1X0Y5=

X2

X1X0Y6=

X2X1X0Y7=

X2

X1X0一般性方法求逻辑表达式32位译码器Verilog程序多路选择器多路选择器是一种多路数据输入并且一路数据输出的逻辑部件输入输出C1C0X0kX1kX2kX3kYk00D0k×××D0k01×D1k××D1k10××D2k×D2k11×××D3kD3kZ0=C1C0Z1=C1C0Z2=C1C0Z3=C1C0Yk=Z0X0kZ1X1kZ2X2kZ3X3k一般性方法求逻辑表达式多路选择器Verilog程序按位逻辑运算设a31-1~0,b31~0是32位二进制数，二进制数逻辑运算是按位做非、与、或以及异或运算，运算记为~、&、|、^，即~a31~0=(~ak)31~0a31~0&b31~0=(ak&bk)31~0a31~0|b31~0=(ak|bk)31~0a31~0^b31~0=(ak^bk)31~0moduleAndmodule(A,B,D); input[31:0]A; input[31:0]B; output[31:0]D; assignD=A&B; endmoduleassignD=A|B;assignD=A&~B|~A&B;二进制加法运算S'0=A'0+B'0，被加数位A'0，加数位B'0以及进位位C'-1，输出有和数位S'0和进位位C'0。A'0，B'0和C'-1按二进制数相加，产生的二进制数的位20为S'0，位21为C'0。输入输出A'0B'0C'-1S'0C'00000000110010100110110010101011100111111S'0=~A'0&~B'0&C'-1|~A'0&B'0&~C'-1|A'0&~B'0&~C'-1|A'0&B'0&C'-1C'0=~