离散数学笔记

离散数学教案1第一章命题逻辑内容：命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法教学目的：1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。2．熟练掌握常用的基本等价式及其应用。3．熟练掌握（主）析/合取范式的求法及其应用。4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。5．熟练掌握形式演绎的方法。教学重点：1．命题的概念及判断2．联结词，命题的翻译3．主析（合）取范式的求法4．逻辑推理教学难点：1．主析（合）取范式的求法2．逻辑推理1.1命题及其表示法1.1.1命题的概念数理逻辑将能够判断真假的陈述句称作命题。1.1.2命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如Ai，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。1.2命题联结词1.2.1否定联结词﹁PPP01101.2.2合取联结词∧PQQP000010100111离散数学教案21.2.3析取联结词∨PQQP0000111011111.2.4条件联结词→PQQP0010111001111.2.5双条件联结词PQQP0010101001111.2.6与非联结词↑PQQP001011101110性质：（1）P↑P﹁（P∧P）﹁P；（2）（P↑Q）↑（P↑Q）﹁（P↑Q）P∧Q；（3）（P↑P）↑（Q↑Q）﹁P↑﹁QP∨Q。1.2.7或非联结词↓PQQP001010100110性质：（1）P↓P﹁（P∨Q）﹁P；（2）（P↓Q）↓（P↓Q）﹁（P↓Q）P∨Q；（3）（P↓P）↓（Q↓Q）﹁P↓﹁Q﹁（﹁P∨﹁Q）P∧Q。离散数学教案31.3命题公式、翻译与解释1.3.1命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、PQ、PQ都是公式；（4）当且仅当能够有限次的应用(1)、(2)、(3)所得到的包括命题变元、联结词和括号的符号串是公式。例如，下面的符号串都是公式：（（（（﹁P）∧Q）R）∨S）（（P﹁Q）（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）（∧Q））（∧Q）1.3.2命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。命题翻译时应注意下列事项：（1）确定所给句子是否为命题。（2）句子中联结词是否为命题联结词。（3）要正确的选择原子命题和合适的命题联结词。例：假如上午不下雨，我去看电影，否则就在家里读书或看报。解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。本例可表示为：（PQ）∧（P（R∨S））。1.3.3命题公式的解释定义设P1，P2，…，Pn是出现在命题公式G中的全部命题变元，指定P1，P2，…，Pn的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作TI（G）。例如，G=（P∧Q）R，则I：PQR110是G的一个解释，在这个解释下G的真值为1，即TI（G）=1。1.4真值表与等价公式1.4.1真值表定义将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。构造真值表的方法如下：（1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，…，Pn。（2）列出G的2n个解释，赋值从00…0（n个）开始，按二进制递加顺序依次写离散数学教案4出各赋值，直到11…1为止（或从11…1开始，按二进制递减顺序写出各赋值，直到00…0为止），然后从低到高的顺序列出G的层次。（3）根据赋值依次计算各层次的真值并最终计算出G的真值。例：G=（P→Q）∧QPQQP)(QPQQP)(001000110010010111001.4.2命题公式的分类定义设G为公式：（1）如果G在所有解释下取值均为真，则称G是永真式或重言式；（2）如果G在所有解释下取值均为假，则称G是永假式或矛盾式；（3）如果至少存在一种解释使公式G取值为真，则称G是可满足式。1.4.3等价公式定义设A和B是两个命题公式，如果A和B在任意赋值情况下都具有相同的真值，则称A和B是等价公式。记为AB。性质定理设A、B、C是公式，则（1）AA（2）若AB则BA（3）若AB且BC则AC定理设A、B、C是公式，则下述等价公式成立：（1）双重否定律AA（2）等幂律A∧AA；A∨AA（3）交换律A∧BB∧A；A∨BB∨A（4）结合律（A∧B）∧CA∧（B∧C）（A∨B）∨CA∨（B∨C）（5）分配律（A∧B）∨C（A∨C）∧（B∨C）（A∨B）∧C（A∧C）∨（B∧C）（6）德·摩根律（A∨B）A∧B（A∧B）A∨B（7）吸收律A∨（A∧B）A；A∧（A∨B）A（8）零一律A∨11；A∧00（9）同一律A∨0A；A∧1A（10）排中律A∨A1（11）矛盾律A∧A0（12）蕴涵等值式A→BA∨B（13）假言易位A→BB→A（14）等价等值式AB（A→B）∧（B→A）离散数学教案5（15）等价否定等值式ABABBA（16）归缪式（A→B）∧（A→B）A1.4.4置换规则定理（置换规则）设（A）是一个含有子公式A的命题公式，（B）是用公式B置换了（A）中的子公式A后得到的公式，如果AB，那么（A）（B）。1.5对偶与范式1.5.1对偶定义在仅含有联结词Ø、∧、∨的命题公式A中，将联结词∧换成∨，将∨换成∧，如果A中含有特殊变元0或1，就将0换成1，1换成0，所得的命题公式A*称为A的对偶式。例：公式（P∨Q）∧（P∨Q）的对偶式为：（P∧Q）∨（P∧Q）定理设A和A*互为对偶式，P1，P2，…，Pn是出现在A和A*中的所有原子变元，若将A和A*写成n元函数形式，则（1）A（P1，P2，…，Pn）A*（P1，P2，…，Pn）（2）A（P1，P2，…，Pn）A*（P1，P2，…，Pn）定理（对偶原理）设A、B是两个命题公式，若AÛB，则A*B*，其中A*、B*分别为A、B的对偶式。1.5.2范式定义仅由有限个命题变元及其否定构成的析取式称为简单析取式，仅由有限个命题变元及其否定构成的合取式称为简单合取式。定义仅由有限个简单合取式构成的析取式称为析取范式。仅由有限个简单析取式构成的合取式称为合取范式。定理（范式存在定理）任何命题公式都存在着与之等价的析取范式和合取范式。1.5.3主范式定义在含有n个命题变元P1，P2，…，Pn的简单合取范式中，若每个命题变元或其否定不同时存在，但二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左起的第i个位置上（若命题变元无脚标，则按字典顺序排列），这样的简单合取式称为极小项。相应的，满足上述条件的简单析取式称为极大项。n个命题变元P1，P2，…，Pn的极小项用公式可表示为Pi*，极大项可表示为Pi*，其中，Pi*为Pi或Pi（i=1，2，…，n）。定义设G为公式，P1，P2，…，Pn为G中的所有命题变元，若G的析取范式中每一个合取项都是P1，P2，…，Pn的一个极小项，则称该析取范式为G的主析取范式。矛盾式的主析取范式为0。离散数学教案6定理任意的命题公式都存在一个唯一的与之等价的主析取范式。用等值演算求主析取范式步骤如下：（1）求G的析取范式G'；（2）若G中某个简单合取式m中没有出现某个命题变元Pi或其否定Pi，则将m作如下等价变换：mm∧（Pi∨Pi）（m∧Pi）∨（m∧Pi）（3）将重复出现的命题变元、矛盾式和重复出现的极小项都消去；（4）重复步骤（2）、（3），直到每一个简单合取式都为极小项；（5）将极小项按脚标由小到大的顺序排列，并用∑表示。如m0∨m1∨m7可表示为∑（0，1，7）。定义设G为公式，P1，P2，…，Pn为G中的所有命题变元，若G的合取范式中每一个析取项都是P1，P2，…，Pn的一个极大项，则称该合取范式为G的主合取范式。通常，主合取范式用∏表示。重言式的主合取范式中不含任何极大项，用1表示。定理任意的命题公式都存在一个唯一的与之等价的主合取范式。1.6公式的蕴涵1.6.1蕴涵的概念定义设G、H是两个公式，若G→H是永真式，则称G蕴涵H，记作GH。蕴涵关系有如下性质：（1）对于任意公式G，有GG；（2）对任意公式G、H，若GH且HG，则GH；（3）若GH且HL，则GL。广义的蕴涵概念定义设G1，G2，…，Gn，H是公式，如果（G1∧G2∧…∧Gn）→H是永真式，则称G1，G2，…，Gn蕴涵H，又称H是G1，G2，…，Gn的逻辑结果，记作（G1∧G2∧…∧Gn）H或（G1，G2，…，Gn）H。1.6.2基本蕴涵式（1）P∧QP；（2）P∧QQ；（3）PP∨Q；(4)QP∨Q；（5）P（P→Q）；（6）Q（P→Q）；（7）（P→Q）P；（8）（P→Q）Q；（9）P，P→QQ；（10）Q，P→QP；（11）P，P∨QQ；（12）P→Q，Q→RP→R；（13）P∨Q，P→R，Q→RR；（14）P→Q，R→S（P∧R）→（Q∧S）；（15）P，QP∧Q。离散数学教案71.7其它联结词与最小联结词组1.7.1其它联结词定义设P、Q为命题公式，则复合命题PQ称为P和Q的不可兼析取，当且仅当P与Q的真值不相同时，PQ的真值为1，否则PQ的真值为假。定义设P、Q是两个命题公式，复合命题PcQ称为命题P、Q的条件否定，当且仅当P的真值为1，Q的真值为0时，PcQ的真值为1，否则PcQ的真值为0。1.7.2最小联结词组定义设S是一些联结词组成的非空集合，如果任何的命题公式都可以用仅包含S中的联结词的公式表示，则称S是联结词的全功能集。特别的，若S是联结词的全功能集且S的任何真子集都不是全功能集，则称S是最小全功能集，又称最小联结词组。定理{，∧，∨，→，}是联结词的全功能集。定理{，∧，∨}是联结词的全功能集。定理{，∧}，{、∨}，{，→}是最小联结词组。定理{↑}，{↓}是最小联结词组。1.8命题逻辑推理理论1.8.1命题逻辑推理理论定义如果G1，G2，…，Gn蕴涵H，则称H能够由G1，G2，…，Gn有效推出，G1，G2，…，Gn称为H的前提，H称为G1，G2，…，Gn的有效结论。称（G1∧G2∧…∧Gn）→H是由前提G1，G2，…，Gn推结论H的推理的形式结构。1.8.2推理规则下面给出推理中常用的推理规则。1．前提引入规则：可以在证明的任何时候引入前提；2．结论引入规则：在证明的任何时候，已证明的结论都可以作为后续证明的前提；3．置换规则：在证明的任何时候，命题公式中的任何子命题公式都可以用与之等价的命题公式置换。4．言推理规则：P，P→QQ5．附加规则：PP∨Q；6．化简规则：P，QP；7．拒取式规则：Q，P→QP；8．假言三段论规则：P→Q，Q→RP→R；9．析取三段论规则：P，P∨QQ；10.构造性二难规则：P∨Q，P→R，Q→RR；11.合取引入规则：P，QP∧Q1.8.3推理常用方法1.直接证法直接证法就是根据一组前提，利用前面提供的一些推理规则，根据已知的等离散数学教案8价公式和蕴涵式，推演得到有效的结论的方法，即有前提直接推导出结论。例构造下列推理的证明。前提：P∨Q，P→R，Q→S结论：S∨R证明（1）P∨Q前提引入规则（2）P→R前提引入规则（3）Q→S前提引入规则（4）S∨R（1）（2）（3）构造性二难规则2．间接证法间接证法主要有如下两种情况。（1）附加前提证明法有时要证明的结论以蕴涵式的形式出现，即推理的形式结构为：（G1∧G2∧…∧Gn）（R→C）设（G1∧G2∧…∧Gn）为S，则上述推理可表