离散数学复习课件

1、离 散 数 学,2020年9月4日星期五,计算机学院 侯文邦 ,课程复习,命题逻辑 谓词逻辑 集合论 二元关系 图论 特殊的图 组合分析初步(计数问题) 形式语言和自动机初步,2020/9/4,数理逻辑（Mathematical Logic） 是研究推理的一门学科，用数学的方法来研究推理的规律统称为数理逻辑。,第一篇 数理逻辑,2020/9/4,第1章 命题逻辑,2020/9/4,1.2.1 命题 定义 具有确切真值的陈述句称为命题, 该命题可以取一个“值”，称为真值。 真值只有“真”和“假”两种，分别用“”(或“”)和“”(或“”)表示。,1.2 命题与命题联结词,注意：命令句、感叹句、疑问

2、句、祈使句等都不能作为命题。,2020/9/4,一般来说，命题可分两种类型： 原子命题(简单命题)：不能再分解为更为简单命题的命题。 复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或者”、“并且”、“不”、“如果.则.”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。,命题的分类,2020/9/4,命题联结词,设命题P,Q表示任意两个命题,则最常见的命题联结词有：,3.析取,P或者Q,P与Q的析取,PQ,PQ=1P=1或Q=1,2.合取,P并且Q,P与Q的合取,PQ,PQ=1P=1且Q=1,1.否定,非P,P的否定,P,P=1 P=0,4.蕴涵,若P,则Q

3、,P蕴涵Q,PQ,PQ=0 P=1,Q=0,5.等价,P当且仅当Q,P等价于Q,PQ,PQ=1P=1,Q=1 或P=0,Q=0,2020/9/4,说明,1、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等的联结； 2、联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何内在联系；,例： 2 + 2 = 4当且仅当雪是白的。,2020/9/4,3、联结词与自然语言之间的对应：,2020/9/4,例1.2.4 符号化下列命题 （1）四川不是人口最多的省份； （2）王超是一个德智体全面发展的好学生；,1.2.3 命题符号化,解：（1）设：四川是人口最多的省份。

4、 则命题（1）可表示为。 （2）设：王超是一个思想品德好的学生； ：王超是一个学习成绩好的学生； R：王超是一个体育成绩好的学生。 R,2020/9/4,为了不使句子产生混淆，作如下约定，命题联结词之优先级如下：,否定 合取, 析取 蕴涵 等价 同级的联结词合取, 析取，按其出现的先后次序(从左到右)确定运算顺序 若运算要求与优先次序不一致时，可使用括号；同级符号相邻时，也可使用括号。括号中的运算为最优先级。,约 定,2020/9/4,1.3 命题公式、解释与真值表,定义 一个特定的命题是一个常值命题，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。 一个任意的没有赋予具体内容的原子

5、命题是一个变量命题，常称它为命题变量(或命题变元)。 该命题变量无具体的真值，其变域是集合T，F,注意 (1)复合命题为命题变元的“函数”,称为真值函数或命题公式。 (2)真值函数或命题公式，没有确切真值。,2020/9/4,1.3.1 命题公式,定义 命题公式(递归定义) 命题变元本身是一个公式； 如G是公式，则(G)也是公式； 如G，H是公式，则(GH)、(GH)、(GH)、(GH)也是公式； 仅由有限步使用规则1-3后产生的结果。该公式常用符号G、H、等表示。,2020/9/4,1.3.2 公式的解释与真值表,为什么要引入解释？P6 定义 设P1、P2、Pn是出现在公式G中的所有命题变元

6、，指定P1、P2、Pn一组真值，则这组真值称为G的一个解释,常记为。 一般来说，若有个命题变元，则应有2n个不同的解释。 定义 将公式G在其所有可能解释下的真值情况列成的表，称为G的真值表。,2020/9/4,例1.3.4,求下面公式的真值表： (P(PQ)R)Q 其中，、是的所有命题变元。,1,0,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,1,0,0,1,1,1,1,0,1,0,0,1,1,1,1,0,1,1,1,2020/9/4,定义：,公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。 公式G称为永假公式(矛盾式),如果在它的所有解释之下都

7、为“假”。 公式G称为可满足式，如果它不是永假的。,2020/9/4,设存在G和H两个公式，例如令： ， 。 若是一个永真公式，即这两个公式对任何解释都必同为真假，此时，说和相等，记为。为此可定义：,分析公式（1）,定义 设G、H是公式，如果在任意解释下，G与H的真值相同，则称公式G、H是等值的，记作GH。,2020/9/4,证明: “”假定G，H等值，则G，H在其任意解释下或同为真或同为假。 于是由“”的意义知，GH在其任何的解释下，其真值为“真”，即GH为永真公式。 “”假定公式GH是永真公式，是它的任意解释，在下，GH为真，因此，G、H或同为真，或同为假，由于的任意性，故有GH。,定理：

8、 公式G、H等值的充分必要条件是公式GH是永真公式,2020/9/4,设G，H，S是任何的公式，则：,基本等值公式,1) 1：GGG (幂等律) 2：GGG 2) 3：GHHG (交换律) 4：GHHG 3) 5：G(HS)(GH)S(结合律) 6: G(HS)(GH)S 4) 7：G(GH) G (吸收律) 8：G(GH) G,2020/9/4,5) 9：G(HS)(GH)(GS)(分配律） 10：G(HS)(GH)(GS) 6) 11：GG(同一律) 12：GG 7) 13：G(零律） 14：G 8) 15：GG1(排中律) 9) 16：GG (矛盾律),基本等值公式（续）,2020/9/

9、4,基本等值公式（续）,10) 17：(G)G (双重否定律) 11) 18：(GH)GH (De MoRGan定律) 19：(GH)GH。 12) 20: (GH)(GH)(HG)(等价) 13) 21：(GH)(GH) (蕴涵) 14) E22：G G。 (假言易位) 15) E23：G G。 (等价否定等式) 16) E24：(G ) (G)G (归谬论),2020/9/4,设G G(P1,P2,Pn) 是一个命题公式，其中：P1, P2, , Pn是其命题变元。设G1, G2,., Gn为任意的命题公式，并设分别用G1、G2、Gn取代G中的P1、P2、Pn后得到新的命题公式： G=G(

10、G1,G2,Gn) 若G是永真(或永假)式，则G也是永真(或永假)式。,定理： 代入定理,2020/9/4,定理：替换定理,设G1是G的子公式(即 G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1替换，得到新的命题公式H，若G1 H1，则G H。,利用24个基本等价公式及代入定理和替换定理，可判断公式的类型判断公式是否等值以及对公式进行简化。,2020/9/4,1.3.6 命题公式的应用,例1.3.11 利用基本的等值关系，化简下列电路图,解：上述电路图可描述为： （1）(PQR)(PQS)(PR)(PS) （2）(PQR)(PQS)(PST),2020/9/4,1.5

11、 公式的标准型范式,1.5.1 析取范式和合取范式 定义： （1）命题变元或命题变元的否定称为文字 （2）有限个文字的析取称为析取式(也称为子句） （3）有限个文字的合取称为合取式(也称为短语） （4）P与 P称为互补对。,2020/9/4,定义：,（1）有限个短语的析取式称为析取范式 （2）有限个子句的合取式称为合取范式,2020/9/4,例子,（1）、是析取范式、合取范式； （2）是析取式、析取范式、合取范式； （3） 是合取式、析取范式、合取范式； （4）()()是析取范式； （5）()()是合取范式； （6）()、()既不是析取范式也不是合取范式,2020/9/4,范式的求解方法,定理

12、：对于任意命题公式，都存在与其等价的析取范式和合取范式。,转换方法：,（1）利用等价公式中的等价式和蕴涵式将公式中的、用联结词 、来取代，这可利用如下等价关系：,() = ()； () = ()() = ()()。,2020/9/4,范式的求解方法(续),（2）重复使用德摩根定律将否定号移到各个命题变元的前端，并消去多余的否定号，这可利用如下等价关系：() =； () = ； () = 。,（3）重复利用分配律，可将公式化成一些合取式的析取，或化成一些析取式的合取，这可利用如下等价关系：() = ()()； () = ()()。,2020/9/4,范式的不惟一性,考虑公式： ()()， 其与之

13、等价的析取范式： ()； ()()； ()()； ()()。 这种不惟一的表达形式给研究问题带来了不便。,2020/9/4,1.5.2 主析取范式和主合取范式,1 极小项和极大项,定义：在含有n个命题变元P1、P2、P3、Pn的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，则称此短语或子句为关于P1、P2、P3、Pn的一个极小项或极大项。,对于n个命题变元，可构成2n个极小项和2n个极大项,2020/9/4,2 主析取范式和主合取范式,定义： （1）在给定的析取范式中，每一个合取范式都是极小项，则称该范式为主析取范式 （2）在给定的合取范式中，每一个析取范式都

14、是极大项，则称该范式为主合取范式 （3）如果一个主析取范式不包含任何极小项，则称该主析取范式为“空”；如果一个主合取范式不包含任何极大项，则称主合取范式为“空”。,2020/9/4,3 求主析取范式和主合取范式的方法,主范式,用等值演算法求公式的主范式的步骤：,(1) 先求析取范式（合取范式） (2) 将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若干个极小项的析 取（极大项的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等. (3) 极小项（极大项）用名称mi（Mi）表示，并 按角标从小到大顺序排序.,2020/9/4,利用真值表求主析（合）取范式,（1

15、）列出公式对应的真值表，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个解释所对应的极小项，将这些极小项进行析取即可得到相应的主析取范式。,（2）列出公式对应的真值表，选出公式的真值结果为假的所有的行，在这样的每一行中，找到其每一个解释所对应的极大项，将这些极大项进行合取即可得到相应的主合取范式。,2020/9/4,4 主析取范式与主合取范式的转换,（1）已知公式G的主析取范式，求公式G的主合取范式,（a）求G的主析取范式，即G的主析取范式中没有出现过的极小项的析取，若,为的主析取范式。其中，mji(i=1,2,2n-k)是mi(i=0,2n-1)中去掉mli(i=,k)后剩下

16、的极小项。,为的主析取范式，则,2020/9/4,主析取范式主合取范式,（b）G=(G)即是G的主合取范式。即，,为G 的主合取范式。,主范式的用途与真值表相同,(1) 求公式的成真赋值和成假赋值 (2) 判断公式的类型 (3) 判断两个公式是否等值,第2章 谓词逻辑,2.1 谓词逻辑基本概念 2.2 谓词逻辑合式公式及解释 2.3 谓词逻辑等值式与前束范式,2.1 谓词逻辑中的基本概念与表示,定义：在原子命题中，可以独立存在的客体（句子中的主语、宾语等），称为个体词(Individual)。 而用以刻划客体的性质或客体之间的关系即是谓词(Predicate)。,个体词的分类,（1）表示具体的

17、或特定的个体词称为个体常量(Individual Constant)； （2）表示抽象的或泛指的个体词称为个体变量(Individual Variable) 。,个体域,定义： （1）个体词的取值范围称为个体域(或论域) (Individual Field)，常用D表示； （2）而宇宙间的所有个体域聚集在一起所构成的个体域称为全总个体域(Universal Individual Field)。,量词,有些x； 至少有一个x； 某一些x； 存在x；等等。,所有的x； 任意的x； 一切的x； 每一个x；等等。,全称量词与存在量词,定义： 称(x)为全称量词（Universal Quantifier

18、）， (x)为存在量词（Existential Quantifier）。 在(x)F(x)和(x)F(x)中，F(x)称为全称量词和存在量词的辖域(Scope)。,特性谓词,例如，符号化“所有的老虎都要吃人”这个命题,若P(x)：x会吃人 U(x)：x是老虎 则符号化的正确形式应该是 (x)(U(x)P(x) 它的含义是：“对于任意的x,如果x是老虎，则x会吃人”。,将个体域统一为全总个体域，而对每一个句子中个体变量的变化范围用一元特性谓词刻划之。,谓词的语言翻译,特殊的，当个体域D x0, x1, 是可数集合时，上述(x)G(x)、(x)G(x)的真值可表示为： (x)G(x) = G(x0

19、)G(x1). (x)G(x) = G(x0)G(x1).,不全是即为假！,全不是才为假！,2.2 谓词合式公式与解释,谓词公式涉及如下四种符号： （1）常量符号：a, b, c, , a1, b1, c1, 。 （2）变量符号：x, y, z, ., x1, y1, z1,.。 （3）函数符号：f, g, h, ., f1, g1, h1, . 。当个体域名称集合D给出时，n元函数符号f(x1, x2, , xn)可以是DnD的任意一个函数； （4）谓词符号：用大写英文字母P, Q, R,., P1, Q1, R1.来表示。当个体域名称集合D给出时，n元谓词符号P(x1, x2, , xn)

20、可以是Dn0，1的任意一个谓词。,项（递归定义）,定义：谓词逻辑中的项（Term），被递归地定义为： （1）任意的常量符号或任意的变量符号是项； （2）若f(x1,x2,xn)是n元函数符号，t1,t2,tn 是项，则f(t1, t2, , tn)是项； （3）仅由有限次使用(1)，(2)产生的符号串才是项。,原子公式,定义：若P(x1, x2, , xn)是n元谓词，t1，t2，tn是项，则称P(t1, t2, , tn)为原子谓词公式(Atomic Propositional Formula)，简称原子公式(Atomic Formula)。,定义：,满足下列条件的表达式，称为合式公式(We

21、ll-Formed Formula/Wff)，简称公式(Formula)。 （1）原子公式是合式公式； （2）若G，H是合式公式，则(G)、(H)、 (GH)，(GH)、(GH)、(GH)也是合式公式； （3）若G是合式公式，x是个体变量，则 (x)G、(x)G 也是合式公式； （4）仅仅由(1)-(3)产生的表达式才是合式公式。,自由变元和约束变元,定义： 给定一个合式公式G，若变元x出现在使用变元的量词的辖域之内，则称x的出现为约束出现(Bound Occurrence)，此时的x称为约束变元(Bound Variable)。 若x的出现不是约束出现，则称它为自由出现(Free Occur

22、rence)，此时的x称为自由变元(Free Variable)。,问题：变元混淆,（4）(x)(P(x)R(x)(y)Q(x, y),约束变元,自由变元,为了不致引起混淆，对于表示不同意思的个体变元，应该用不同的变量符号来表示。,谓词合式公式的解释,定义：谓词逻辑中公式G 的每一个解释I(Expl-anation)由如下四部分组成： （1）非空的个体域集合D； （2）G中的每个常量符号，指定D中的某个特定的元素； （3）G中的每个n元函数符号，指定Dn到D中的某个特定的函数； （4）G中的每个n元谓词符号，指定Dn到0,1中的某个特定的谓词。,公式的解释,例5 设有公式： (x)(P(x)Q

23、(x)(x)P(x)(x)Q(x)， 个体域D = a, b，构造使公式分别为真和假的解释。 解：对个体域D = a, b，公式可展开为： (x)(P(x)Q(x)(x)P(x)(x)Q(x) = (x)(P(x)Q(x)(x)P(x)(x)Q(x) = (P(a)Q(a)(P(b)Q(b) (P(a)P(b)(Q(a)Q(b),例5 （续）,(P(a)Q(a)(P(b)Q(b) (P(a)P(b)(Q(a)Q(b) 解：（1）构造解释I1为 P(a) = 0，P(b) = 0，Q(a) = 1，Q(b) = 1，则： (P(a)Q(a)(P(b)Q(b)在此解释I1下为真 (P(a)P(b)

24、(Q(a)Q(b)在此解释I1下为真 因此，解释I1使得原公式的真值为真。,一阶逻辑中命题符号化,例 在一阶逻辑中将下面命题符号化 (1)人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 . 解：,(a) (1) 设G(x): x爱美, 符号化为 x G(x) (2) 设G(x): x用左手写字, 符号化为 x G(x),(b) 设F(x): x为人，G(x): 同(a)中 (1) x (F(x)G(x) (2) x (F(x)G(x),这是两个基本公式, 注意它们的使用,一阶逻辑中命题符号化(续),例 在一阶逻辑中将下面命题符号化 (1) 正数都大于负数 (2) 有的无理数大于有的有理数 解,注意: 题目中没给个体域, 使用全总个体域,(1) 令F(x): x为正数, G(y): y为负数, L(x,y): xy x(F(x)y(G(y)L(x,y) 或 xy(F(x)G(y)L(x,y) 两者等值,(2) 令F(x): x是无理数, G(y): y是有理数, L(x,y)：xy x(F(x)y(G(y)L(x,y) 或 xy(F(x)G(y)L(x,y) 两者等值,一阶逻辑中命题符号化(续),几点注意： 1元谓词与多元谓词的区分 无