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

第一章第一章 命题逻辑命题逻辑11 命题及其表示法命题及其表示法1.什么是命题什么是命题命题：能判断真假的陈述句命题：能判断真假的陈述句命题的值叫它的真值命题的值叫它的真值 真值：真值：“真真”：表示判断正确记作：表示判断正确记作True，用，用T表示 “假假”：表示判断错误记作：表示判断错误记作False，用，用F表示1例例1 判断下列句子中哪些是命题？判断下列句子中哪些是命题？ （1）2是素数 （2）雪是黑色的雪是黑色的 （3）2+3=5 （4）明年）明年10月月1日是晴天日是晴天 （5）3能被能被2整除 （6）这朵花真好看呀！）这朵花真好看呀！ （7）明天下午有会吗？）明天下午有会吗？ （8）请关上门！）请关上门！ （9）X+Y5 （10）地球外的星球上也有人地球外的星球上也有人11）我正在说谎我正在说谎22命题的符号化表示命题的符号化表示 命题的符号化就是用符号表示命题命题的符号化就是用符号表示命题简单命题（或原子命题）：简单陈述句表示简单命题（或原子命题）：简单陈述句表示的命题用的命题用P，Q，R,Pi,Qi,Ri,表示例例 P:2是偶数 Q:雪是黑色的雪是黑色的命题常量（或命题常元）：简单命题。

命题常量（或命题常元）：简单命题命题变项（或命题变元）：真值可以变化的命题变项（或命题变元）：真值可以变化的简单陈述句不是命题简单陈述句不是命题 例：例：x+y5 3命题变项也用命题变项也用P，Q，R, Pi,Qi,Ri,表示复合命题：由简单命题用联结词联结而成的命题复合命题：由简单命题用联结词联结而成的命题4例例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 等于角等于角BPQ（个表示如果个表示如果则则）512.联结词定义定义12.1 设P为任一命题，P的否定是一个新的命题，称为P的否定式，否定式，记作P为否定联结词否定联结词。

PP T F F T例例 p：3是偶数 p：3不是偶数不是偶数6定义定义12.2 设P、Q为两命题，复合命题“P并且Q”（或“P和Q”）称为 P与Q的合取式，合取式，记作PQ，为合取联结词合取联结词表示自然语言中的“既又”， “不仅而且”， “虽然但是”PQP QTTTTFFFTFFFF7例例3将下列命题符号化将下列命题符号化1）李平既聪明又用功李平既聪明又用功2）李平虽然聪明，但不用功李平虽然聪明，但不用功3）李平不但聪明，而且用功李平不但聪明，而且用功3）李平不是不聪明，而是不用功李平不是不聪明，而是不用功解：设解：设P：李平聪明；：李平聪明；Q：李平用功李平用功1）P Q（2）P Q（3）P Q（4）（P）Q注意：不是见到注意：不是见到“和和” 、“与与”就用就用 例：例：“李文和李武是兄弟李文和李武是兄弟”，“王芳和陈兰是好朋友王芳和陈兰是好朋友”是简是简单命题8定义定义12.3 设P、Q为两命题，复合命题“P或Q”称为 P与Q的析取式，析取式，记作PQ，为析取联结析取联结词PQP QTTTTFTFTTFFF9 析取式析取式P Q表示的是一种相容性或，即允许表示的是一种相容性或，即允许P和和Q同时为真。

同时为真例：例：“王燕学过英语或日语王燕学过英语或日语” P Q自然语言中的自然语言中的“或或”具有二义性，有时表示具有二义性，有时表示不相容的或不相容的或例：例：“派小王或小李中的一人去开会派小王或小李中的一人去开会” 为排斥性的或P：派小王去开会；：派小王去开会；Q：派小李去开会派小李去开会P Q）（P Q） ， （P Q）（P Q）10定义定义12.4 设P、Q为两命题，复合命题“如果P，则Q”称作 P与Q的蕴涵式，蕴涵式，记作PQ，为蕴涵联蕴涵联结词PQP QTTTTFFFTTFFT11 在PQ中，Q是P的必要条件，P是Q的充分条件表示自然语言 “只要P就Q” ，“P仅当Q”，“只有Q，才P”注意：注意：1.在自然语言中，在自然语言中，“如果如果P，则，则Q”中的中的P与与Q往往有某往往有某 种内在的联系，但在数理逻辑中，种内在的联系，但在数理逻辑中，PQ中的中的P与与Q不一定有内在的联系不一定有内在的联系2.在数学中，在数学中，“如果如果P，则，则Q”表示表示P为真，为真，Q为真的为真的逻辑关系，但在数理逻辑中，当逻辑关系，但在数理逻辑中，当P为假时为假时PQ为真12例例4将下列命题符号化。

将下列命题符号化1)只要不下雨，我就骑自行车上班只要不下雨，我就骑自行车上班2)只有不下雨，我才骑自行车上班只有不下雨，我才骑自行车上班3)若若 2+24，则太阳从东方升起则太阳从东方升起3)若若 2+24，则太阳从东方升起则太阳从东方升起4)若若 2+24，则太阳从西方升起则太阳从西方升起5)若若 2+24，则太阳从西方升起则太阳从西方升起解：在（解：在（1）、（）、（2）中，设）中，设P：天下雨；：天下雨；Q：我骑自行车上：我骑自行车上班1）PQ（2）Q P在（在（3）（）（6）中，设）中，设P： 2+24；Q：太阳从东方升起；：太阳从东方升起；R: 太阳从西方升起太阳从西方升起1）PQ， 真值为真值为T （2）PQ， 真值为真值为T（3）PR ， 真值为真值为F （4）PR 真值为真值为T13定义定义1-2.5 设P、Q为两命题，复合命题“P当且仅当 Q”称作 P与Q的等价式，等价式，记作P Q， 为等价联结等价联结词PQ表示表示P与与Q互为充分必要条件互为充分必要条件 PQP QTTTTFFFTFFFT14例例5将下列命题符号化将下列命题符号化1）2+24，当且仅当，当且仅当3是奇数。

是奇数2）2+24，当且仅当，当且仅当3不是奇数不是奇数3）2+24，当且仅当，当且仅当3是奇数4）2+24，当且仅当，当且仅当3不是奇数不是奇数5）两圆的面积相等，当且仅当它们的半径相同两圆的面积相等，当且仅当它们的半径相同6）两角相等当且仅当它们是对顶角两角相等当且仅当它们是对顶角解：（解：（1）（）（4）设）设P：2+24；Q：3是奇数1）PQ 真命题真命题（2）PQ 假命题假命题（3）PQ假命题假命题（4）PQ真命题真命题（5）设）设P：两圆的面积相等；：两圆的面积相等；Q：两圆的面积相同两圆的面积相同PQ真命题真命题（6）设）设P：两角相等；：两角相等；Q：它们是对顶角它们是对顶角 PQ假命题假命题154.5种联结词的优先级顺序：种联结词的优先级顺序：， 16 1-3命题公式与翻译命题公式与翻译 1.命题公式命题公式命题公式：由命题常量、命题公式：由命题常量、命题变元命题变元、联结词、括号、联结词、括号 等组成的符号串等组成的符号串 命题公式中的命题变元称作命题公式的分量命题公式中的命题变元称作命题公式的分量17定义定义13.1 （1）单个命题常量或命题变）单个命题常量或命题变 元元,Q,R,Pi,Qi,Ri,，F，T是合式公式。

是合式公式2）如果）如果A是合式公式，则（是合式公式，则（A）也是合式公式也是合式公式3）如果）如果A、B是合式公式，则（是合式公式，则（A B）、（）、（A B）、（）、（AB）、（）、（AB）也是合式公式也是合式公式4）只有有限次地应用（）只有有限次地应用（1）（）（3）组成的符号）组成的符号串才是合式公式串才是合式公式例：例：P, P, (P), (0 P),P(PQ), (P Q) R) (R)是公式；是公式； PQR, (P), PQ)不是公式不是公式182.翻译 翻译就是把自然语言中的有些句子符号化翻译就是把自然语言中的有些句子符号化复合命题符号化的基本步骤：复合命题符号化的基本步骤：（1）分析出各简单命题，将它们符号化分析出各简单命题，将它们符号化2）使用合适的联结词，把简单命题逐个联结起来，）使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示组成复合命题的符号化表示19例例 将下列命题符号化将下列命题符号化1）小王是游泳冠军或是百米冠军小王是游泳冠军或是百米冠军P Q（2）小王现在在宿舍或在图书馆小王现在在宿舍或在图书馆P Q （排斥性或，不可能同时为真）（排斥性或，不可能同时为真）(3)选小王或小李中的一人当班长。

选小王或小李中的一人当班长P Q） （P Q）或）或 （PQ）（排斥性或，可能同时为真）（排斥性或，可能同时为真）PQ原命题原命题PQ（PQ）TTFTFTFTFTFTTFTFFFTF20(4)如果我上街，我就去书店看看，除非我很累如果我上街，我就去书店看看，除非我很累R(PQ) 或或 （R P）Q （除非：如果不）（除非：如果不）(5)王一乐是计算机系的学生，他生于王一乐是计算机系的学生，他生于1968年或年或1969年，他年，他是三好学生是三好学生P （Q R）S（6）我们要做到身体好、学习好、工作好，为祖国四化建设）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗A：我们要做到身体好：我们要做到身体好B：我们要做到学习好：我们要做到学习好C：我们要做到工作好：我们要做到工作好P：我们要为祖国四化建设面奋斗我们要为祖国四化建设面奋斗命题符号化形式为：（命题符号化形式为：（A B C） P21 14真值表与等价公式真值表与等价公式1.真值表真值表定义定义14.1含含n个（个（n1）个命题变元（分量）的命题公式，）个命题变元（分量）的命题公式，共有共有2n组真值指派将命题公式组真值指派。

将命题公式A在所有真值指派之下取值在所有真值指派之下取值的情况列成表，称为的情况列成表，称为A的真值表的真值表构造真值表的步骤：构造真值表的步骤：(1)找出命题公式中所含的所有命题变元找出命题公式中所含的所有命题变元P1,P2,Pn列出所有可能的真值指派有可能的真值指派2)对应每种真值指派，计算命题公式的各层次的值，直到最对应每种真值指派，计算命题公式的各层次的值，直到最后计算出命题公式的值后计算出命题公式的值22例例1 构造求构造求P Q的真值表的真值表PQPP QTTFTTFFFFTTTFFTT23例例2 给出（给出（P Q）P的真值表的真值表PQP QP （P Q）PTTTFFTFFFFFTFTFFFFTF24例例3 给出（给出（P Q）（P Q）的真值表的真值表PQ P QP QP Q（P Q）（P Q）TTFFTFTTFFTFFFFTTFFFFFFTTFTT25例例4 给出给出（P Q） （P Q）的真值表的真值表PQP Q（P Q）PQ P Q（P Q） （P Q）T T TFFFFTT F FTFTTTF T FTTFTTF F FTTTTT 由以上例子可以看出有一类命题公式不论各命题变元作何种批派，其值永为真由以上例子可以看出有一类命题公式不论各命题变元作何种批派，其值永为真（假），我们把这类公式记为（假），我们把这类公式记为T（F）。