离散数学课堂PPT(左孝凌版)

第一章命题逻辑1－1命题及其表示法1.什么是命题命题：能判断真假的陈述句。命题的值叫它的真值。真值：“真”：表示判断正确。记作True，用T表示。“假”：表示判断错误。记作False，用F表示。例1判断下列句子中哪些是命题？（1）2是素数。（2）雪是黑色的。（3）2+3=5（4）明年10月1日是晴天。（5）3能被2整除。（6）这朵花真好看呀！（7）明天下午有会吗？（8）请关上门！（9）X+Y5（10）地球外的星球上也有人。（11）我正在说谎。2．命题的符号化表示命题的符号化就是用符号表示命题。简单命题（或原子命题）：简单陈述句表示的命题。用P，Q，R,…,Pi,Qi,Ri,…表示。例P:2是偶数。Q:雪是黑色的。命题常量（或命题常元）：简单命题。命题变项（或命题变元）：真值可以变化的简单陈述句。不是命题。例：x+y5命题变项也用P，Q，R,…,Pi,Qi,Ri,…表示。复合命题：由简单命题用联结词联结而成的命题。例2将下列命题符号化。（1）3不是偶数。（2）2是素数和偶数。（3）林芳学过英语或日语。（4）如果角A和角B是对顶角，则角A等于角B。解：（1）设P：3是偶数。ᄀP（ᄀ：表示并非）（2）设P：2是素数；Q：2是偶数。P∧Q(∧:表示和)（3）设P：林芳学过英语；Q：林芳学过日语。P∨Q(∨:表示或)（4）设P：角A和角B是对顶角；Q：角A等于角B。P→Q（→个表示如果……则……）1－2.联结词定义1－2.1设P为任一命题，P的否定是一个新的命题，称为P的否定式，记作ᄀP。ᄀ为否定联结词。PᄀPTFFT例p：3是偶数。ᄀp：3不是偶数。定义1－2.2设P、Q为两命题，复合命题“P并且Q”（或“P和Q”）称为P与Q的合取式，记作P∧Q，∧为合取联结词。∧表示自然语言中的“既……又……”，“不仅……而且……”，“虽然……但是”PQP∧QTTTTFFFTFFFF例3将下列命题符号化。（1）李平既聪明又用功。（2）李平虽然聪明，但不用功。（3）李平不但聪明，而且用功。（3）李平不是不聪明，而是不用功。解：设P：李平聪明；Q：李平用功。（1）P∧Q（2）P∧ᄀQ（3）P∧Q（4）ᄀ（ᄀP）∧ᄀQ注意：不是见到“和”、“与”就用∧。例：“李文和李武是兄弟”，“王芳和陈兰是好朋友”是简单命题。定义1－2.3设P、Q为两命题，复合命题“P或Q”称为P与Q的析取式，记作P∨Q，∨为析取联结词。PQP∨QTTTTFTFTTFFF析取式P∨Q表示的是一种相容性或，即允许P和Q同时为真。例：“王燕学过英语或日语”P∨Q自然语言中的“或”具有二义性，有时表示不相容的或。例：“派小王或小李中的一人去开会”。为排斥性的或。P：派小王去开会；Q：派小李去开会。（P∧ᄀQ）∨（ᄀP∧Q），（P∨Q）∧ᄀ（P∧Q）定义1－2.4设P、Q为两命题，复合命题“如果P，则Q”称作P与Q的蕴涵式，记作P→Q，→为蕴涵联结词。PQP→QTTTTFFFTTFFT在P→Q中，Q是P的必要条件，P是Q的充分条件。表示自然语言“只要P就Q”，“P仅当Q”，“只有Q，才P”注意：1.在自然语言中，“如果P，则Q”中的P与Q往往有某种内在的联系，但在数理逻辑中，P→Q中的P与Q不一定有内在的联系。2.在数学中，“如果P，则Q”表示P为真，Q为真的逻辑关系，但在数理逻辑中，当P为假时P→Q为真。例4将下列命题符号化。(1)只要不下雨，我就骑自行车上班。(2)只有不下雨，我才骑自行车上班。(3)若2+2＝4，则太阳从东方升起。(3)若2+2≠4，则太阳从东方升起。(4)若2+2＝4，则太阳从西方升起。(5)若2+2≠4，则太阳从西方升起。解：在（1）、（2）中，设P：天下雨；Q：我骑自行车上班。（1）ᄀP→Q（2）Q→ᄀP在（3）－（6）中，设P：2+2＝4；Q：太阳从东方升起；R:太阳从西方升起。（1）P→Q，真值为T（2）ᄀP→Q，真值为T（3）P→R，真值为F（4）ᄀP→R真值为T定义1-2.5设P、Q为两命题，复合命题“P当且仅当Q”称作P与Q的等价式，记作P⇄Q，⇄为等价联结词。P⇄Q表示P与Q互为充分必要条件。PQP⇄QTTTTFFFTFFFT例5将下列命题符号化。（1）2+2＝4，当且仅当3是奇数。（2）2+2＝4，当且仅当3不是奇数。（3）2+2≠4，当且仅当3是奇数。（4）2+2≠4，当且仅当3不是奇数。（5）两圆的面积相等，当且仅当它们的半径相同。（6）两角相等当且仅当它们是对顶角。解：（1）－（4）设P：2+2＝4；Q：3是奇数。（1）P⇄Q真命题（2）P⇄ᄀQ假命题（3）ᄀP⇄Q假命题（4）ᄀP⇄ᄀQ真命题（5）设P：两圆的面积相等；Q：两圆的面积相同。P⇄Q真命题（6）设P：两角相等；Q：它们是对顶角。P⇄Q假命题4.5种联结词的优先级顺序：ᄀ，∧，∨，→，⇄1-3命题公式与翻译1.命题公式命题公式：由命题常量、命题变元、联结词、括号等组成的符号串。命题公式中的命题变元称作命题公式的分量。定义1－3.1（1）单个命题常量或命题变元,Q,R,…,Pi,Qi,Ri,…，F，T是合式公式。（2）如果A是合式公式，则（ᄀA）也是合式公式。（3）如果A、B是合式公式，则（A∧B）、（A∨B）、（A→B）、（A⇄B）也是合式公式。（4）只有有限次地应用（1）－（3）组成的符号串才是合式公式。例：P,ᄀP,(ᄀP)),(0∧P),P→(P→Q),((P∨Q)→R)→(ᄀR)是公式；PQ→R,,ᄀ(P→),ᄀP→Q)不是公式。2.翻译翻译就是把自然语言中的有些句子符号化。复合命题符号化的基本步骤：（1）分析出各简单命题，将它们符号化。（2）使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。例将下列命题符号化。（1）小王是游泳冠军或是百米冠军。P∨Q（2）小王现在在宿舍或在图书馆。P∨Q（排斥性或，不可能同时为真）(3)选小王或小李中的一人当班长。（P∧ᄀQ）∨（ᄀP∧Q）或ᄀ（P⇄Q）（排斥性或，可能同时为真）PQ原命题P⇄Qᄀ（P⇄Q）TTFTFTFTFTFTTFTFFFTF(4)如果我上街，我就去书店看看，除非我很累。ᄀR→(P→Q)或（ᄀR∧P）→Q（除非：如果不）(5)王一乐是计算机系的学生，他生于1968年或1969年，他是三好学生。P∧（Q∨R）∧S（6）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。A：我们要做到身体好B：我们要做到学习好C：我们要做到工作好P：我们要为祖国四化建设面奋斗。命题符号化形式为：（A∧B∧C）⇄P1－4真值表与等价公式1.真值表定义1－4.1含n个（n≥1）个命题变元（分量）的命题公式，共有2n组真值指派。将命题公式A在所有真值指派之下取值的情况列成表，称为A的真值表。构造真值表的步骤：(1)找出命题公式中所含的所有命题变元P1,P2,…,Pn。列出所有可能的真值指派。(2)对应每种真值指派，计算命题公式的各层次的值，直到最后计算出命题公式的值。例1构造求ᄀP∨Q的真值表。PQᄀPᄀP∨QTTFTTFFFFTTTFFTT例2给出（P∧Q）∧ᄀP的真值表。PQP∧QᄀP（P∧Q）∧ᄀPTTTFFTFFFFFTFTFFFFTF例3给出（P∧Q）∨（ᄀP∧ᄀQ）的真值表。PQᄀPᄀQP∧QᄀP∧ᄀQ（P∧Q）∨（ᄀP∧ᄀQ）TTFFTFTTFFTFFFFTTFFFFFFTTFTT例4给出ᄀ（P∧Q）⇄（ᄀP∨ᄀQ）的真值表。PQP∧Qᄀ（P∧Q）ᄀPᄀQᄀP∨ᄀQᄀ（P∧Q）⇄（ᄀP∨ᄀQ）TTTFFFFTTFFTFTTTFTFTTFTTFFFTTTTT由以上例子可以看出有一类命题公式不论各命题变元作何种批派，其值永为真（假），我们把这类公式记为T（F）。如例4和例22．等价公式从真值表中可以看到，有些命题公式在分量的各种指派下，其对应的真值都完全相同，如ᄀP∨Q与P→Q的对应真值相同。PQᄀPᄀP∨QP→QTTFTTTFFFFFTTTTFFTTT（P∧Q）∨（ᄀP∧ᄀQ）与P⇄Q对应的真值相同。定义1－4.2给定两个命题公式A和B，设P1，P2，…，Pn为所有出现于A和B中的原子变元,若给P1，P2，…，Pn任一组真值指派,A和B的真值都相同,则称A和B是等价的或逻辑相等。记作A⇔B。例5证明P⇄Q⇔（P→Q）∧（Q→P）证明列出真值表PQP→QQ→P(P→Q）∧(Q→P）P⇄QTTTTTTTFFTFFFTTFFFFFTTTT24个重要的等价式P⇔ᄀᄀP双重否定律P⇔P∨P等幂律P⇔P∧PP∨Q⇔Q∨P交换律P∧Q⇔Q∧P（P∨Q）∨R⇔P∨（Q∨R）结合律（P∧Q）∧R⇔P∧（Q∧R）P∨（Q∧R）⇔（P∨Q）∧（P∨R）分配律P∧（Q∨R）⇔（P∧Q）∨（P∧R）ᄀ（P∨Q）⇔ᄀP∧ᄀQ德·摩根律ᄀ（P∧Q）⇔ᄀP∨ᄀQP∨（P∧Q）⇔P吸收律P∧（P∨Q）⇔PP∨T⇔T零律P∧F⇔FP∨F⇔P同一律P∧T⇔PP∨ᄀP⇔T排中律P∧ᄀP⇔F矛盾律P→Q⇔ᄀP∨Q蕴涵等价式P⇄Q⇔（P→Q）∧（Q→P）等价等价式P→Q⇔ᄀQ→ᄀP假言易位P⇄Q⇔ᄀP⇄ᄀQ等价否定等价式（P→Q）∧（P→ᄀQ）⇔ᄀP归谬论其中P、Q和R代表任意的命题公式。例6验证吸收律P∨（P∧Q）⇔P和P∧（P∨Q）⇔PPQP∧QP∨（P∧Q）P∨QP∧（P∨Q）TTTTTTTFFTTTFTFFTFFFFFFF定义1-4.3如果X是合式公式A的一部分,且X本身也是一个合式公式,则称X为公式A的子公式。定理1－4.1如果X是合式公式A的子公式，若X⇔Y，如果将A中的X用Y来置换，所得到公式B与公式A等价，即A⇔B。证明因为在相应变元的任一种指派下，X与Y的真值相同，故以Y取代X后，公式B与公式A在相应的指派下，其真值必相同，故A⇔B。满足定理1－4.1的置换称为等价置换（等价代换）例7证明P→Q⇔ᄀ（P∧ᄀQ）证明P→Q⇔ᄀP∨Q，（根据蕴涵等价式）ᄀP∨Q⇔ᄀ（P∧ᄀq），（德·摩根律）即P→q⇔ᄀ（P∧ᄀq）例8证明P→(Q→R)⇔(P∧Q)→R证明P→(Q→R)⇔ᄀP∨(Q→R)（蕴涵等价式）⇔ᄀP∨(ᄀQ∨R)（蕴涵等价式）⇔(ᄀP∨ᄀQ)∨R（结合律）⇔ᄀ(P∧Q)∨R（德·摩根律）⇔(P∧Q)→R（蕴涵等价式）例9证明P⇔(P∧Q)∨(P∧ᄀQ)证明P⇔P∧1(同一律)⇔P∧(Q∨ᄀQ)（排中律）⇔(P∧Q)∨(P∧ᄀQ)（分配律）练习1.证明Q∨ᄀ((ᄀP∨Q)∧P)⇔T;2.证明(P∨ᄀP)→((Q∧ᄀQ)∧R)⇔F3.证明(P→Q)∧ᄀP⇔ᄀP1,证明Q∨ᄀ((ᄀP∨Q)∧P)⇔Q∨ᄀ((ᄀP∧P)∨(P∧Q))（分配律）⇔Q∨ᄀ(F∨(P∧Q))（矛盾律）⇔Q∨ᄀ(P∧Q)（同一律）⇔Q∨(ᄀP∨ᄀQ)（德·摩根律）⇔(Q∨ᄀQ)∨ᄀP（结合律）⇔T∨ᄀP（排中律）⇔T（零律）2.证明(P∨ᄀP)→((Q∧ᄀQ)∧R)⇔T→((Q∧ᄀQ)∧R)（排中律）⇔T→(F∧R)（矛盾律）⇔T→F（零律）⇔ᄀT∨F（蕴涵等值式）⇔F∨F⇔F（等幂律）3.证明(P→Q)∧ᄀP⇔(ᄀP∨Q)∧ᄀP（蕴涵等价值式）⇔ᄀP（吸收律）1-5重言式与蕴涵式定义1－5.1给定一命题公式，若无论对分量作什么样的指派，其对应的真值永为T，则称该命题公式为重言式或永真式。定义1－5.2给定一命题公式，若无论对分量作什么样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假式。定理1－5.1任何两个重言式的合取或析取，仍然是一个重言式。定理1－5.2一个重言式，对同一分量，都用任何合式公式置换，其结果仍为一重言式。证明由于重言式的真值与分量的指派无关，帮对同一分量以任何合式公式置换后，重言式的真值仍永为真。对于矛盾式也有类似于定理1－5.1和定理5－1.2的结果。例1证明（（P∨S）∧R）∨ᄀ（（P∨S）∧R）为重言式。证明因为P∨ᄀP⇔T，用（（P∨S）∧R）置换P得（（P∨S）∧R）∨ᄀ（（P∨S）∧R）⇔T定理1－5.3设A、B为两命题公式A⇔B，当且仅当A⇄B为一个重言式。证明若A⇔B，则A、B有相同的真值，即有A⇄