离散数学教案3

《离散数学教案3》由会员分享，可在线阅读，更多相关《离散数学教案3（58页珍藏版）》请在装配图网上搜索。

1、会计学1离散数学教案离散数学教案3第1页/共58页总结总结第2页/共58页命题逻辑命题逻辑 命题的基本概念命题的基本概念命题联结词命题联结词命题公式命题公式命题的范式命题的范式 主要研主要研 究内容究内容谓词逻辑谓词逻辑谓词的基本概念谓词的基本概念谓词公式谓词公式公式的标准型公式的标准型推理与证明技推理与证明技术术命题逻辑推理理论命题逻辑推理理论谓词逻辑推理理论谓词逻辑推理理论数学归纳法数学归纳法按定义证明法按定义证明法第3页/共58页（4）研究如何由一组前提推导一些结论？第4页/共58页第5页/共58页命题公式命题公式3命题基本概念命题基本概念1命题联结词命题联结词2第6页/共58页重点掌握

2、重点掌握一般掌一般掌握握了解了解11 1、五种基本、五种基本联结词联结词2 2、2424个个基本基本的等价公式的等价公式3联结词完备集联结词完备集的理解和学习的理解和学习2公式的代入规公式的代入规则和替换规则则和替换规则第7页/共58页第8页/共58页的国家；（11）今天是晴天；TTT/F非命题非命题T/FFT/FTTT非命题非命题第9页/共58页非命题非命题非命题非命题非命题非命题非命题非命题注意：注意：一切没有判断内容的句子都不能作为命题一切没有判断内容的句子都不能作为命题，如命令，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等句、感叹句、疑问句、祈使句、二义性的陈述句等。第10页/共

3、58页结论：结论：在数理逻辑中像在数理逻辑中像字母字母“x x”、“y y”、“z z”等字母总是表示等字母总是表示变量。变量。约定：约定：第11页/共58页例例3.2.23.2.2第12页/共58页.的关联词和标点符号复合而构成一个复合命题。第13页/共58页 通常用通常用大写的带或不带下标的英文字母大写的带或不带下标的英文字母、.P.P、Q Q、R R、.A Ai i、B Bi i、C Ci i、.P.Pi i、Q Qi i、R Ri i、.等表示命题等表示命题第14页/共58页设命题设命题P,QP,Q表示任意两个命题表示任意两个命题,则则最常见的命题联结词有：最常见的命题联结词有：联接词

4、记号复合命题读法 记法真值结果 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或

5、或P P=0=0,Q=0Q=0例如：命题例如：命题P P：2 2是素数；是素数；Q Q：北京是中国的首都：北京是中国的首都第15页/共58页P QPPQPQPQPQ0 0100110 1101101 0001001 101111第16页/共58页第17页/共58页联结词自然语言既又、不仅而且、虽然但是、并且、和、与，等等；如P则Q、只要P就Q、P仅当Q、只有Q才P、除非Q否则P，等等等价、当且仅当、充分必要、等等；相容（可兼）的或第18页/共58页（5）两个三角形全等当且仅当三角形的三条边全部相等。第19页/共58页则命题（2）可表示为R。（3）设：教室的灯不亮可能是灯管坏了：教室的灯不亮可能

6、是停电了则命题（3）可表示为。第20页/共58页第21页/共58页1.1.否定否定合取合取析取析取蕴涵蕴涵等价等价2.2.同级的联结词，按其出现的先后次序同级的联结词，按其出现的先后次序(从从左到右左到右)3.3.若运算要求与优先次序不一致时，可使用若运算要求与优先次序不一致时，可使用括号括号；同级符号相邻时，也可使用括号。；同级符号相邻时，也可使用括号。括号中的运算为最优先级括号中的运算为最优先级。第22页/共58页4)明天上午我将雨雪无阻一定去学校可符号化为：可符号化为：(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)。或或(PQ)(PQ)(PQ)(PQ)(

7、PQ)(PQ)(PQ)R(PQ)R。可符号化为：可符号化为：(PQ)R(PQ)R。可符号化为可符号化为:(:(PQ)RPQ)R。可符号化为可符号化为:(PQ)R:(PQ)R。第23页/共58页车子，我将不出去R(PQ)R(PQ)或或 (PQ)RPQ)R(PQ)RPQ)R(PQ)RPQ)R第24页/共58页52+2=4；PQ（6）除非雪是白色的，否则2+24；P Q或QP（7）雪是白色的当且仅当2+2=4；P Q第25页/共58页注意(1)复合命题为命题变元的“函数”,其函数值仍为真或“假”值。(2)真值函数或命题公式，没有确切真值。真值函数真值函数第26页/共58页H、等表示。第27页/共58

8、页例例3.3.23.3.2符号串：符号串：(PQPQ)QQ)；(PQPQ；(PQPQ(R R；PQPQ。等都不是合法的命题公式。等都不是合法的命题公式。第28页/共58页（5）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。第29页/共58页（5）P：我们要做到身体好,Q：我们要做到学习好,R：我们要做到工作好，S：我们要为祖国四化建设而奋斗，则有：PQR S。第30页/共58页定义3.3.4 将公式G在其所有可能解释下的真值情况列成的表，称为G的真值表。第31页/共58页P Q R PPQ(PQ)RP(PQ)R)G0 0 0 10 0 110 0 1 10 0 110 1 0 1 1

9、 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 01第32页/共58页P Q R(P(PQ)R)Q0 0 010 0 110 1 010 1 111 0 001 0 111 1 011 1 1 1进一步化简为：进一步化简为：第33页/共58页 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)。第34页/共58页公式公式G G1 1对所有可能的解释具有对所有可

10、能的解释具有“真真”值值公式公式G G3 3对所有可能的解释均具有对所有可能的解释均具有“假假”值值公式公式G G2 2则具有则具有“真真”和和“假假”值值第35页/共58页第36页/共58页1)1)永真式永真式G G的否定的否定 G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定 G G是永真式。是永真式。2)2)永真式一定是可满足式永真式一定是可满足式,可满足式不一定是永真可满足式不一定是永真式式3)3)可满足式的否定不一定为不可满足式可满足式的否定不一定为不可满足式(即为矛盾即为矛盾式式)第37页/共58页第38页/共58页P Q()()(Q)(Q)(Q)(P Q)Q0 01 0

11、10 11 0 11 0 1 0 11 11 0 0永真公式永真公式永假公式永假公式可满足公可满足公式式三个公式的真值表如下：三个公式的真值表如下：第39页/共58页分析公式（分析公式（1 1）定义定义3 3.3.63.6 设设G G、H H是是公式，公式，如果在任意解释如果在任意解释下，下，G G与与H H的的真值相同，则称公式真值相同，则称公式G G、H H是是等价的等价的，记作记作G GH H。第40页/共58页GH为真，因此，G、H或同为真，或同为假，由于的任意性，故有GH。第41页/共58页命题公式G、H是否逻辑等价，即GH那是办不到的，然而计算机却可“计算”公式GH是否是永真公式。

12、第42页/共58页含义。第43页/共58页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第44页/共58页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 G第45页/共58页14：G8)15：GG1(排

13、中律)9)16：GG0(矛盾律)第46页/共58页第47页/共58页有：GH GH GGH GH GUABUABUA命题与集合之间的关系命题与集合之间的关系第48页/共58页等幂律;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)AA 第49页/共58页若G是永真公式

14、（或永假公式），则G也是一个永真公式（或永假公式）。第50页/共58页解解 建立公式建立公式G G的真值表如的真值表如右所示。可见右所示。可见为永真公式。为永真公式。P Q()0 010 111 011 11第51页/共58页第52页/共58页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第53页/共58页利用利用2424个基本等价公式及代入定理和替换个基本等价公式及代入定理和替换定理，可完成公式的转化和等价判定。定理，可完成公式的转化和等价判定。第54页/共58页（3）化简公式：证明(P(R)(R)(PR)=R 第55页/共58页第56页/共58页第57页/共58页