[理学]离散数学教案3.ppt

数理逻辑（Mathematical Logic）是研究演绎推理的一门学科，用数学的方法来研究推理的规律统称为数理逻辑。第二篇 数理逻辑主要研究内容：推理 着重于推理过程是否正确 着重于语句之间的关系 主要研究方法：数学的方法 就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（Symbolic Logic）。第二篇 数理逻辑什么是数理逻辑？用数学的方法来研究推理的规律统称为数理逻辑。为什么要研究数理逻辑？程序算法数据 算法逻辑控制总结总结第二篇 数理逻辑命题逻辑命题逻辑 命题的基本概念命题的基本概念命题联结词命题联结词命题公式命题公式命题的范式命题的范式 主要研主要研 究内容究内容谓词逻辑谓词逻辑谓词的基本概念谓词的基本概念谓词公式谓词公式公式的标准型公式的标准型推理与证明技术推理与证明技术命题逻辑推理理论命题逻辑推理理论谓词逻辑推理理论谓词逻辑推理理论数学归纳法数学归纳法按定义证明法按定义证明法第三章 命题逻辑 命题逻辑也称命题演算，或语句逻辑。研究内容：（1）研究以命题为基本单位构成的前提和结论之间的可推导关系 （2）研究什么是命题？（3）研究如何表示命题？（4）研究如何由一组前提推导一些结论？第三章 命题逻辑 命题逻辑的特征：在研究逻辑的形式时，我们把一个命题只分析到其中所含的命题成份为止，不再分析下去。不把一个简单命题再分析为非命题的集合，不把谓词和量词等非命题成份分析出来。第三章 命题逻辑命题公式命题公式3命题基本概念命题基本概念1命题联结词命题联结词23.1 本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1、五种基本、五种基本联结词联结词2 2、2424个个基本基本的等价公式的等价公式3联结词完备集联结词完备集的理解和学习的理解和学习2公式的代入规公式的代入规则和替换规则则和替换规则3.2.1 命题定义3.2.1具有确切真值的陈述句称为命题,该命题可以取一个“值”，称为真值。真值只有“真”和“假”两种，分别用“”(或“”)和“”(或“”)表示。3.2 命题与命题联结词（1）太阳是圆的；（2）成都是一个旅游城市；（3）北京是中国的首都；（4）这个语句是假的；（5）1110；（6）+y；（7）我喜欢踢足球；（8）3能被2整除；（9）地球外的星球上也有人；（10）中国是世界上人口最多的国家；（11）今天是晴天；例3.2.1TTT/F非命题非命题T/FFT/FTTT非命题非命题例3.2.1（续）（12）把门关上；（13）滚出去！（14）你要出去吗？（15）今天天气真好啊！非命题非命题非命题非命题非命题非命题非命题非命题注意：注意：一切没有判断内容的句子都不能作为命题一切没有判断内容的句子都不能作为命题，如命令，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。句、感叹句、疑问句、祈使句、二义性的陈述句等。命题一定是陈述句，但并非一切陈述句都是命题。命题的真值有时可明确给出，有时还需要依靠环境、条件、实际情况时间才能确定其真值。结论：结论：在在数数理理逻逻辑辑中中像像字字母母“x x”、“y y”、“z z”等字母总是表示等字母总是表示变量。变量。约定：约定：下列语句是否是命题？并判断其真值结果？（1）四川不是一个国家；（2）3既是素数又是奇数；（3）张谦是大学生或是运动员；（4）如果周末天气晴朗，则我们将到郊外旅游；（5）2+2=4当且仅当雪是白的。例例3.2.23.2.2一般来说，命题可分两种类型：1)原子命题(简单命题)：不能再分解为更为简单命题的命题。2)复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或者”、“并且”、“不”、“如果.则.”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。命题的分类1)今天天气很冷。2)今天天气很冷并且刮风。3)今天天气很冷并且刮风，但室内暖和。例3.2.3 通常用通常用大写的带或不带下标的英文字母大写的带或不带下标的英文字母、.P.P、Q Q、R R、.A Ai i、B Bi i、C Ci i、.P.Pi i、Q Qi i、R Ri i、.等表示命题等表示命题3.2.2 命题联结词设命题设命题P,QP,Q表示任意两个命题表示任意两个命题,则则最常见的命题联结词有：最常见的命题联结词有：联接词记号复合命题读法 记法真值结果 3.3.析取析取 P P或者或者Q QP P与与Q Q的析取的析取P P Q QP PQ=1Q=1P=1P=1或或Q=1Q=12.2.合取合取 P P并且并且Q QP P与与Q Q的合取的合取PQPQPQPQ=1=1P=1P=1且且Q=1Q=11.1.否定否定 非非P PP P的否定的否定P PP=1P=1 P=0P=04.4.蕴涵蕴涵若若P,P,则则Q QP P蕴涵蕴涵Q QP PQQP PQ=0Q=0 P=1,Q=0P=1,Q=05.5.等价等价 P P当且仅当当且仅当Q QP P等价于等价于Q QP PQ QP PQ=1Q=1P P=1=1,Q=1Q=1或或P P=0=0,Q=0Q=0例如：命题例如：命题P P：2 2是素数；是素数；Q Q：北京是中国的首都：北京是中国的首都总结P QPPQPQPQPQ0 0100110 1101101 0001001 101111说明1、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等的联结；2、联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何地内在联系；3、联结词与自然语言之间的对应并非一一对应；联结词自然语言既又、不仅而且、虽然但是、并且、和、与，等等；如P则Q、只要P就Q、P仅当Q、只有Q才P、除非Q否则P，等等等价、当且仅当、充分必要、等等；相容（可兼）的或符号化下列命题（1）四川不是人口最多的省份；（2）王超是一个德智体全面发展的好学生；（3）教室的灯不亮可能是灯管坏了或者是停电了；（4）如果周末天气晴朗，那么学院将组织我们到石像湖春游；（5）两个三角形全等当且仅当三角形的三条边全部相等。例3.2.4例3.2.4 解（1）设：四川是人口最多的省份。则命题（1）可表示为 。（2）设：王超是一个思想品德好的学生；：王超是一个学习成绩好的学生；R：王超是一个体育成绩好的学生。则命题（2）可表示为R。（3）设：教室的灯不亮可能是灯管坏了 ：教室的灯不亮可能是停电了 则命题（3）可表示为。（4）设：周末天气晴朗；：学院将组织我们到石像湖春游。则命题（4）可表示为。（5）设：两个三角形全等；：三角形的三条边全部相等。则命题（5）可表示为。为了不使句子产生混淆，作如下约定，命题联结词之优先级如下：1.1.否定否定合取合取析取析取蕴涵蕴涵等价等价2.2.同同级级的的联联结结词词，按按其其出出现现的的先先后后次次序序(从从左左到右到右)3.3.若若运运算算要要求求与与优优先先次次序序不不一一致致时时，可可使使用用括括号号；同同级级符符号号相相邻邻时时，也也可可使使用用括括号号。括括号号中的运算为最优先级中的运算为最优先级。约 定设命题P：明天上午七点下雨；Q：明天上午七点下雪；R：我将去学校。符号化下述语句：1)如果明天上午七点不是雨夹雪，则我将去学校2)如果明天上午七点不下雨并且不下雪，则我将去学校3)如果明天上午七点下雨或下雪，则我将不去学校4)明天上午我将雨雪无阻一定去学校可符号化为：可符号化为：(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)。或或(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)R(PQ)R。例3.2.5可符号化为：可符号化为：(PQ)R(PQ)R。可符号化为可符号化为:(PQ)R:(PQ)R。可符号化为可符号化为:(PQ)R:(PQ)R。例3.2.6设命题P：你陪伴我；Q：你代我叫车子；R：我将出去。符号化下述语句：除非你陪伴我或代我叫车子，否则我将不出去 如果你陪伴我并且代我叫辆车子，则我将出去 如果你不陪伴我或不代我叫辆车子，我将不出去R(PQ)R(PQ)或或 (PQ)RPQ)R(PQ)RPQ)R(PQ)RPQ)R例设P:雪是白色的;Q:2+2=4。将下列命题符号化：（1）因为雪是白色的，所以2+2=4；PQ（2）如果2+2=4，则雪是白色的；QP（3）只有雪是白色的，才有2+2=4；QP（4）只有2+2=4，雪才是白色的；PQ（5）只要雪不是白色的，就有2+2=4；PQ（6）除非雪是白色的，否则2+24；P Q或QP（7）雪是白色的当且仅当2+2=4；P Q3.3 命题公式、解释与真值表定义3.3.1 一个特定的命题是一个常值命题，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元)，该命题变量无具体的真值，它的变域是集合T，F(或0，1)注意(1)复合命题为命题变元的“函数”,其函数值仍为真或“假”值。(2)真值函数或命题公式，没有确切真值。真值函数真值函数3.3.1命题公式定义3.3.2(命题公式)1.命题变元本身是一个公式；2.如G是公式，则(G)也是公式；3.如G，H是公式，则(GH)、(GH)、(GH)、(GH)也是公式；4.仅由有限步使用规则1-3后产生的结果。该公式常用符号G、H、等表示。符号串符号串：(P(QR)(Q(SR)；(PQ)；(P(PQ)；(PQ)(RQ)(PR)。等都是命题公式。等都是命题公式。例例3 3.3.13.1例例3.3.23.3.2符号串：符号串：(PQPQ)QQ)；(PQPQ；(PQPQ(R R；PQPQ。等都不是合法的命题公式。等都不是合法的命题公式。例例3.3.33.3.3试用符号形式写出下列命题：（1）虽然今天天气晴朗，老陈还是不来；（2）除非你陪伴我或代我叫车子，否则我将不出去；（3）停机的原因在于语法错误或者程序错误；（4）若a和b是偶数，则a+b是偶数；（5）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。（1）P：今天天气晴朗,Q：老陈要来,则有：PQ；（2）P：你陪伴我；Q：你代我叫车子；R：我出去。则有：RPQ或PQR；（3）P：停机的原因在于语法错误，Q：停机的原因在于程序错误，则有：PQ；（4）P：a是偶数；Q：b是偶数，R：a+b是偶数，则有：PQR；（5）P：我们要做到身体好,Q：我们要做到学习好,R：我们要做到工作好，S：我们要为祖国四化建设而奋斗，则有：PQR S。定义3.3.3 设P1、P2、Pn是出现在公式G中的所有命题变元，指定P1、P2、Pn一组真值，则这组真值称为G的一个解释,常记为。一般来说，若有个命题变元，则应有2n个不同的解释。如果公式G在解释下是真的，则称满足G；如果G在解释下是假的，则称弄假G。定义3.3.4 将公式G在其所有可能解释下的真值情况列成的表，称为G的真值表。3.3.2 公式的解释与真值表例例3 3.3.43.4求下面公式的真值表：(P(PQ)R)Q 其中，、是的所有命题变元。P Q R PPQ(PQ)RP(PQ)R)G0 0 0 10 0 110 0 1 10 0 110 1 0 1 1 0 1 10 1 1 1 1 1 111 0 0 0 1 0 001 0 1 0 1 1 111 1 0 0 0 0 011 1 1 0 0 0 01P Q R(P(PQ)R)Q0 0 010 0 110 1 010 1 111 0 001 0 111 1 011 1 1 1进一步化简为：进一步化简为：例例3.3.53.3.5 P Q()()()(Q)0 0 1 00 0 1 1 00 1 01 00 1 11 10 求下面这组公式的真值表：求下面这组公式的真值表：1 1 ()；2 2()；3 3 ()(Q)Q)。从这三个真值表可以看到一个非常有趣的事实：公式公式G G1 1对所有可能的解释具有对所有可能的解释具有“真真”值值公式公式G G3 3对所有可能的解释均具有对所有可能的解释均具有“假假”值值公式公式G G2 2则具有则具有“真真”和和“假假”值值结论定义3.3.51.公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。2.公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。3.公式G称为可满足的，如果它不是永假的。从上述定义可知三种特殊公式之间的关系：1)1)永真式永真式G G的否定的否定 G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定 G G是是永真式。永真式。2)2)永真式一定是可满足式永真式一定是可满足式,可满足式不一定是永真式可满足式不一定是永真式3)3)可满足式的否定不一定为不可满足式可满足式的否定不一定为不可满足式(即为矛盾式即为矛盾式)结论例例3.3.63.3.6写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。（1）G1=()()；（2）G2=(Q)(Q)(Q)；（3）G3=(PQ)Q。P Q()()(Q)(Q)(Q)(P Q)Q0 01 0 10 11 0 11 0 1 0 11 11 0 0永真公式永真公式永假公式永假公式可满足公式可满足公式三个公式的真值表如下：三个公式的真值表如下：若将其看成两个公式，分别令：，。则是一个永真公式，即这两个公式对任何解释都必同为真假，此时，说和相等，记为。为此可定义：分析公式（分析公式（1 1）定义定义3 3.3.63.6 设设G G、H H是是公式，公式，如果在任意解释下，如果在任意解释下，G G与与H H的的真值相同，则称公式真值相同，则称公式G G、H H是是等价的等价的，记作记作G GH H。公式G、H等价的充分必要条件是公式GH是永真公式证明:“”假定G，H等价，则G，H在其任意解释下或同为真或同为假，于是由“”的意义知，GH在其任何的解释下，其真值为“真”，即GH为永真公式。“”假定公式GH是永真公式，是它的任意解释，在下，GH为真，因此，G、H或同为真，或同为假，由于的任意性，故有GH。定理3.3.1 首先，双条件词“”是一种逻辑联结词，公式GH是命题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。而逻辑等价“”则是描述了两个公式G与H之间的一种逻辑等价关系，GH表示“命题公式G等价于命题公式H”，GH 的结果不是命题公式。其次，如果要求用计算机来判断命题公式G、H是否逻辑等价，即GH那是办不到的，然而计算机却可“计算”公式GH是否是永真公式。“”与“”的区别“=”的性质由于“=”不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：（1）自反性 G=G；（2）对称性 若G=H，则H=G；（3）传递性 若G=H，H=S，则G=S。这三条性质体现了“=”的实质含义。3.3.4 命题公式的基本等价关系例3.3.7 证明公式G1()与公式G2(PQ)(QP)之间是逻辑等价的。解：根据定理3.3.1，只需判定公式G3()(PQ)(QP)为永真公式。P Q G3()(Q)(Q)0 0 1 1 1 1 10 1 0 1 1 0 0 1 0 0 1 0 0 11 1 1 1 1 1 1设G，H，S是任何的公式，则：基本等价公式1)1)1 1：GGGGG G (幂等律幂等律)2 2：GGGGG G2)2)3 3：GHGHHG HG (交换律交换律)4 4：GHGHHGHG3)3)5 5：G(HS)G(HS)(GH)S(GH)S(结合律结合律)6 6:G(HS)G(HS)(GH)S(GH)S4)4)7 7：G(GH)G(GH)G G (吸收律吸收律)8 8：G(GH)G(GH)G G5)9：G(HS)(GH)(GS)(分配律）10：G(HS)(GH)(GS)6)11：GG(同一律)12：GG 7)13：G(零律）14：G8)15：GG1(排中律)9)16：GG0(矛盾律)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 (归谬论)这种图是将G，H理解为某总体论域上的子集合，而规定GH为两集合的公共部分（交集合），GH为两集合的全部（并集合），G为总体论域（如矩形域）中G的补集，将命题中的真值“1”理解为集合中的总体论域（全集），将命题中的真值“0”理解为集合中的空集，则有：GH GH GGH GH GUABUABUA命题与集合之间的关系命题与集合之间的关系“”对“”与“”对“”的对比等幂律;GGG GGG交换律=GHHG GHHG结合律A(BC)=(AB)CA(BC)=(AB)CG(HS)=(GH)SG(HS)=(GH)S恒等律；GGG GG GG G零律；G G吸收律 A(AB)=A A(AB)=A G(GH)=G G(GH)=G否定律 (G)G分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)G(HS)=(GH)(GS)G(HS)=(GH)(GS)设G(P1,P2,Pn)是一个命题公式，其中：P1、P2、Pn是命题变元，G1(P1,P2,Pn)、G2(P1,P2,Pn)、.、Gn(P1,P2,Pn)为任意的命题公式，分别用G1、G2、Gn取代G中的P1、P2、Pn后得到新的命题公式：G(G1,G2,Gn)G(P1,P2,Pn)若G是永真公式（或永假公式），则G也是一个永真公式（或永假公式）。定理3.3.2(代入定理)例例3.3.83.3.8设(,)()，证明公式G是一个永真公式。另有两个任意公式：(,)()；(,)()。进一步验证代入定理的正确性。解解 建立公式建立公式G G的真值表如的真值表如右所示。可见右所示。可见为永真公式。为永真公式。P Q()0 010 111 011 11 将，代入到中分别取代G中的命题变元P、Q，所得到的公式为：(P,Q)=G(H,S)=(H(HS)S =()()()()建立新公式(P,Q)的真值表。P Q()()()()0 0 1 1 1 1 1 1 1 1 00 1 0 0 0 0 0 1 0 1 01 0 1 1 0 1 1 0 0 1 01 1 1 0 1 1 0 1 1 1 1定理3.3.3(替换定理)设G1是G的子公式(即 G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到新的命题公式H，若G1H1，则GH。利用利用2424个基本等价公式及代入定理和替换定个基本等价公式及代入定理和替换定理，可完成公式的转化和等价判定。理，可完成公式的转化和等价判定。例3.3.9利用基本的等价关系，完成如下工作：（1）判断公式的类型：证明()()()()是一个永真公式。（2）证明公式之间的等价关系：证明()=()（3）化简公式：证明(P(R)(R)(PR)=R（1）()()()()=()()()()=()()()()()=()()()()()=()()()()=T 即:()()()()为永真公式；（2）P(QR)=P(QR)=P(QR)=(PQ)R=(PQ)R=(PQ)R 即有:P(QR)=(PQ)R；（3）(P(QR)(QR)(PR)=(PQ)R)(QP)R)=(PQ)R)(QP)R)=(PQ)(QP)R =TR=R 即有:(P(QR)(QR)(PR)=R。