离散数学 命题

1、离散数学离散数学一、一、地位作用地位作用:二、二、研究对象研究对象:三、三、主要内容主要内容:引引 言言数学分支，计算机核心课程数学分支，计算机核心课程离散量结构及相互关系离散量结构及相互关系数理逻辑、集合论、图论等数理逻辑、集合论、图论等 离散数学与其他专业课的关系离散数学与其他专业课的关系数理逻辑数理逻辑: :人工智能、形式语义学人工智能、形式语义学集合集合: :形式语言、编译技术、计算复杂性形式语言、编译技术、计算复杂性关系关系: :关系数据库关系数据库函数函数: :算法设计与分析、软件形式化方法算法设计与分析、软件形式化方法图图: :数据结构、网络技术、人工智能数据结构、网络技术、人工

2、智能代数系统代数系统: :数字电路设计、软件形式化方法数字电路设计、软件形式化方法 第1节基本概念第2节逻辑联结词第3节命题公式第4节等价式（恒等式）和永真蕴涵式第5节对偶原理第6节主析取范式和主合取范式第7节命题演算的推论理论1 1、命题的定义、命题的定义第1节基本概念第1节、基本概念5、原子命题、原子命题2、命题的真值、命题的真值3、真值的表示、真值的表示4、命题标识符、命题标识符6、原子变元、原子变元7、分子命题（复合命题）、分子命题（复合命题）1、命题的定义一个具有一个具有确定确定的的真假真假意义的意义的陈述句陈述句称为称为命题；一般用英文大写字母表示。命题；一般用英文大写字母表示。疑

3、问句疑问句, ,祈使句祈使句, ,感叹感叹句等均不是命题句等均不是命题命题要么正确命题要么正确, ,要么要么错误错误 2、命题的真值一个命题的取值或一个命题的取值或真真或或假假，这两种可能，这两种可能的取值称为命题的真值。的取值称为命题的真值。正确正确 错误错误 3、真值的表示真值是真真值是真真值是假真值是假1T0FTrueFalse(1)(1)上海是一个小山村。上海是一个小山村。(2)(2)抽烟的人均要得肺癌。抽烟的人均要得肺癌。(3)(3)十是整数。十是整数。(4)(4)上课去！上课去！(5)(5)你吃饭了吗？你吃饭了吗？ (6)(6)今天天气多好啊！今天天气多好啊！(7)(7)蚊子是鸟类

4、动物。蚊子是鸟类动物。(8)(8)我正在说谎。我正在说谎。(F)(F)(F)(T)()()()()例、判断下列命题的真假关于悖论“我正在说谎。我正在说谎。” 如果真值为如果真值为“真真”，则隐含着我正在说谎；，则隐含着我正在说谎；真值不确定真值不确定悖论悖论如果真值为如果真值为“假假”，则隐含着我没有说谎。，则隐含着我没有说谎。4、命题标识符用用英文大写字母英文大写字母表示命题表示命题命题标识符命题标识符命题常量命题常量:命题变元命题变元:表示表示确定的命题确定的命题表示表示任意的命题任意的命题真值真值0，1或或T，F5、原子命题不能再分解成更简单的命题不能再分解成更简单的命题本原命题本原命题

5、6、原子变元若命题变元表示原子命题时，该变若命题变元表示原子命题时，该变元称原子变元。元称原子变元。例：命题变元是命题吗？命题变元是命题吗？第1节基本概念解：命题变元不是命题，因为命题变元命题变元不是命题，因为命题变元的真值不确定。的真值不确定。当命题变元当命题变元P用特定的命题取代时，用特定的命题取代时，P才才能确定真值能确定真值对对P进行进行真值指派真值指派7、分子命题由由原子命题原子命题通过通过逻辑联结词逻辑联结词构成的新命题构成的新命题复合命题第2节 逻辑联结词1 1、真值表的概念、真值表的概念 2 2、否定（、否定（ ）3 3、合取（、合取（，与与） 4 4、析取（、析取（，或，或）

6、5 5、单条件（、单条件（） 6 6、双条件（、双条件（ ）7 7、命题符号化、命题符号化1、真值表的概念在复合命题中，对命题变元的所有种可在复合命题中，对命题变元的所有种可能的真值指派，复合命题都有一个确定的能的真值指派，复合命题都有一个确定的真值与其相对应，形成一个表，称为真值真值与其相对应，形成一个表，称为真值表。表。n个命题变元，个命题变元，2n种真值指派种真值指派:两个命题变元两个命题变元, 224种真值指派种真值指派00011011(03)02n -12、否定（ ）一元运算符，当且仅当一元运算符，当且仅当P为真时，为真时， P为为假。真值表如表假。真值表如表1.1所示。所示。表表1

7、.11.1逻辑联结词逻辑联结词“ ”的的真值表真值表P P1001例、给出下列命题的否定命题（1 1）大连的每条街道都临海。）大连的每条街道都临海。（2 2）天津是一个城市。）天津是一个城市。并非并非大连的每条街道都临海。大连的每条街道都临海。大连的每条街道大连的每条街道不不都临海。都临海。大连的每条街道都大连的每条街道都不不临海。临海。天津天津不不是一个城市。是一个城市。注意：注意：否定是对命题的部分否定。否定是对命题的部分否定。3、合取（，与）二元运算符，当且仅当二元运算符，当且仅当P、Q的真值均为的真值均为真时，真时，PQ Q的真值才为真的真值才为真。真值表如表。真值表如表1.2所示。所

8、示。表表1.21.2逻辑联结词逻辑联结词“”的的真值表真值表PQP Q000110110001第2节逻辑联结词例：P P：20082008年将在北京举行奥运会；年将在北京举行奥运会；QQ：两个三角形全等；两个三角形全等；P P Q Q代表什么命题？代表什么命题？2008年将在北京举行奥运会年将在北京举行奥运会并且并且两个三两个三角形全等。角形全等。注意：注意：在数理逻辑中，只要在数理逻辑中，只要P和和Q的真值确定，的真值确定， P Q的真值即可确定，就可以成为新的的真值即可确定，就可以成为新的命题，不管这个新命题在自然语言中是否命题，不管这个新命题在自然语言中是否有意义。有意义。将下列命题符号

9、化将下列命题符号化(1)(1)我虽然生病，但我仍去学校。我虽然生病，但我仍去学校。(2)(2)我虽然有钱，但我不去看电影。我虽然有钱，但我不去看电影。(3)(3)张华与李明在吃饭。张华与李明在吃饭。解：命题符号化过程及结果解：命题符号化过程及结果(1)(1)我虽然生病，但我仍去学校。我虽然生病，但我仍去学校。P P：我生病；我生病；QQ：我去学校；我去学校； (2)(2)我虽然有钱，但我不去看电影。我虽然有钱，但我不去看电影。P P：我有钱我有钱; ; QQ：我去看电影我去看电影; ; (3)(3)P:P:张华在吃饭张华在吃饭; ;Q:Q:李明在吃饭李明在吃饭; ; 注意：注意：用命题变元表示

10、肯定的命题。用命题变元表示肯定的命题。P QP QP Q第2节逻辑联结词4、析取（，或、可兼或）二元运算符，当且仅当二元运算符，当且仅当P、Q的真值均为的真值均为假时，假时，PQ Q的真值才为假的真值才为假。真值表如表。真值表如表1.3所示。所示。表表1.31.3逻辑联结词逻辑联结词“”的的真值表真值表PQP Q000110110111第2节逻辑联结词例:将下列命题符号化：（1 1）张三或李四可以做这件事。）张三或李四可以做这件事。（2 2）我们不能既划船又跑步。）我们不能既划船又跑步。解：命题符号化过程及结果解：命题符号化过程及结果(1)(1)张三或李四可以做这件事。张三或李四可以做这件事。

11、P P：张三可以做这件事；张三可以做这件事；QQ：李四可以做这件事；李四可以做这件事；(2)(2)我们不能既划船又跑步。我们不能既划船又跑步。P P：我们划船我们划船; ; QQ：我们跑步我们跑步; ; P Q P Q (P Q)第2节逻辑联结词例：P P：20082008年将在北京举行奥运会；年将在北京举行奥运会；QQ：两个三角形全等；两个三角形全等；P P QQ代表什么命题？代表什么命题？2008年将在北京举行奥运会年将在北京举行奥运会或者或者两个三两个三角形全等。角形全等。第2节逻辑联结词不可兼或（ ）二元运算符，存在一种可能性或另一种二元运算符，存在一种可能性或另一种可能性，但二者不能

12、同时为真。真值表如可能性，但二者不能同时为真。真值表如表表1.4所示。所示。表表1.41.4逻辑联结词逻辑联结词“ “ ”的的真值表真值表PQP Q000110110110第2节逻辑联结词例:将下列命题符号化：今天晚上他要么去体育场看足球赛，要今天晚上他要么去体育场看足球赛，要么在家里看电视的实况转播。么在家里看电视的实况转播。P P：今天晚上他去体育场看足球赛；今天晚上他去体育场看足球赛；QQ：今天晚上他在家里看电视的实况转今天晚上他在家里看电视的实况转播；播； P Q解：命题符号化过程及结果解：命题符号化过程及结果第2节逻辑联结词5、单条件（ ，善意的推定）二元运算符，当且仅当二元运算符，

13、当且仅当P为真，为真，Q为假时，为假时， PQ Q的真值才为假，否则，均为真的真值才为假，否则，均为真。真值。真值表如表表如表1.5所示。所示。善意的推定：善意的推定：当条件为假时，无论后件为真当条件为假时，无论后件为真为假，结论均为真。为假，结论均为真。第2节逻辑联结词PQP Q00011011表表1.51.5逻辑联结词逻辑联结词“”的的真值表真值表0111第2节逻辑联结词例:将下列命题符号化：（1 1）如果我生病，那么我不去学校。）如果我生病，那么我不去学校。（2 2）如果我有钱，那么我就去看电影。）如果我有钱，那么我就去看电影。解：命题符号化过程及结果解：命题符号化过程及结果(1)(1)

14、如果如果我生病，我生病，那么那么我不去学校。我不去学校。P P：我生病；我生病；QQ：我去学校；我去学校； (2)(2)如果我有钱，那么我就去看电影。如果我有钱，那么我就去看电影。P P：我有钱我有钱; ; QQ：我去看电影我去看电影; ; P QP Q第2节逻辑联结词例：P P：20082008年将在北京举行奥运会；年将在北京举行奥运会；QQ：两个三角形全等；两个三角形全等；P P QQ和和Q Q P P代表什么命题？代表什么命题？第2节逻辑联结词解：P P Q Q：如果如果20082008年将在北京举行奥运会，年将在北京举行奥运会，那么那么两个三角形全等。两个三角形全等。Q Q P P ：

15、如果如果两个三角形全等，两个三角形全等，那么那么20082008年将在年将在北京举行奥运会。北京举行奥运会。 第2节逻辑联结词6、双条件（ ）二元运算符，当且仅当二元运算符，当且仅当P、Q的真值相同的真值相同时，时， PQ Q的真值才为真，否则，均为假的真值才为真，否则，均为假。真值表如表真值表如表1.6所示。所示。第2节逻辑联结词PQP Q00011011表表1.61.6逻辑联结词逻辑联结词“”的的真值表真值表1100第2节逻辑联结词例:将下列命题符号化：（1 1）只有只有在我生病的时候，我在我生病的时候，我才才不去学校。不去学校。（2 2）当且仅当当且仅当我有钱时，我才去看电影。我有钱时，

16、我才去看电影。解：命题符号化过程及结果解：命题符号化过程及结果(1)(1)只有在我生病的时候，我才不去学校。只有在我生病的时候，我才不去学校。P P：我生病；我生病；QQ：我去学校；我去学校； (2)(2)当且仅当我有钱时，我才去看电影。当且仅当我有钱时，我才去看电影。 P P：我有钱我有钱; ; QQ：我去看电影我去看电影; ; P QP Q第2节逻辑联结词例：P P：20082008年将在北京举行奥运会；年将在北京举行奥运会；QQ：两个三角形全等；两个三角形全等；P PQQ代表什么命题？代表什么命题？第2节逻辑联结词解：P P Q Q：20082008年将在北京举行奥运会，年将在北京举行奥

17、运会，当且仅当当且仅当两个三角形全等。两个三角形全等。第2节逻辑联结词逻辑联结词的优先级 高高 低低 注意：注意： “”的优先级比的优先级比“”“”高，而不是相高，而不是相同。同。第2节逻辑联结词例：列出下列各式的真值表：P P(QQR)R)( (P PQ)Q)R R 第2节逻辑联结词PQRQQR RP P( (QQR)R)P PQQ( (P PQ)Q)R R000000100100011100010101100111表表1.71.7 P P( (QQR)R)和和( (P PQ)Q)R R的的真值表真值表11111110000011111111100000P(QR)PQR(PQ)RPQR第2节

18、逻辑联结词7、 命题符号化的原则：（1 1）“”“”： （并列、递进、转折）（并列、递进、转折）同时、不但同时、不但而且、即而且、即又、和又、和（2 2）“”“”： （相容、选择）（相容、选择）或许、大概、可能或许、大概、可能（3 3）“”“”： （条件）条件）如果如果则则、如果、如果那么那么第2节逻辑联结词 命题符号化的原则（续）：（4 4）“”： （等价）（等价）充分必要、当且仅当、只有充分必要、当且仅当、只有才能才能（5 5）“ ” ” ： （否定）否定）非、不非、不 第2节逻辑联结词命题符号化的步骤：（1 1）找出原子命题；）找出原子命题；（2 2）用符号（大写英文字母）定义原子命题；

19、）用符号（大写英文字母）定义原子命题；（3 3）使用正确的逻辑联结词，将自然语言变）使用正确的逻辑联结词，将自然语言变成与之等价的符号化语言。成与之等价的符号化语言。第2节逻辑联结词例：将下列命题符号化：（1 1）如果如果明天上午明天上午7 7点不是雨点不是雨加加雪，雪，则则我去我去学校。学校。（2 2）只有只有明天上午明天上午7 7点不下雨点不下雨而且而且不下雪，不下雪，我我才才去学校。去学校。解：命题符号化过程及结果解：命题符号化过程及结果(1)P:明天上午明天上午7 7点下雨；点下雨；Q:明天上午明天上午7 7点下雪；点下雪；R:我去学校；如果如果明天上午明天上午7 7点不是雨点不是雨加

20、加雪，雪，则则我去学校。我去学校。 (PQ)R第2节逻辑联结词第2节逻辑联结词( P只有只有明天上午明天上午7 7点不下雨点不下雨而且而且不下雪，我不下雪，我才才去学校。去学校。R Q) 第2节逻辑联结词例：P：我生病；Q：我去学校；（1 1）我虽然生病，但我仍去学校。我虽然生病，但我仍去学校。（2 2）只有在我生病的时候，我才不去学校。）只有在我生病的时候，我才不去学校。（3 3）如果我生病，那么我不去学校。）如果我生病，那么我不去学校。PQP QP Q第3节命题公式第3节命题公式(合式的公式）1 1、命题公式（合式的公式）的递归定义、命题公式（合式的公式）的递归定义2 2、永真式（重言式）

21、、永真式（重言式）3 3、永假式（矛盾式）、永假式（矛盾式）4 4、可满足式、可满足式5 5、永真式的特点、永真式的特点第3节命题公式1、命题公式（合式的公式）的递归定义合式的公式（合式的公式（ WffWff）是由命题变元、逻辑联是由命题变元、逻辑联结词、圆括号组成的：结词、圆括号组成的：(1)(1)单个的命题变元是合式的公式；单个的命题变元是合式的公式；(2)(2)如果如果A A是是WffWff，则则 A A是是WffWff(3)(3)如果如果A A和和B B是是WffWff，则则( (AB)AB)、(AB)(AB)、(A(AB)B)、(A(AB)B)都是都是WffWff(4)(4)当且仅当

22、有限次地使用当且仅当有限次地使用(1)(1)、(2)(2)、(3)(3)所得到所得到的包含命题变元、逻辑联结词、圆括号的符号串的包含命题变元、逻辑联结词、圆括号的符号串是是WffWff(递归基础）递归基础）；（递归方法）递归方法）；（递归方法）递归方法）。（递归界限）递归界限）第3节命题公式去括号原则(1)(1)最外层括号可省；最外层括号可省；(2)(2) 、的优先级由高到低，的优先级由高到低，有的括号可省；有的括号可省；第3节命题公式例、根据定义判断下列公式是否是合式公式(1)(1)、( ( (ABAB) )A)A)(2)(2)、A A(BB) ) (3)(3)、(PQ) (PQ) (4)(

23、4)、 ?(AB)(AB)(5)(5)、(P(P( (P P ?QQ) ) ) (6)(6)、( ( ( (PQPQ) )( (QRQR) ) )( (S ST T) ) )(7)(7)、(PQ)(Q) (PQ)(Q) (8)(8)、(PQ (PQ (9)(9)、( (PQPQ) ) Q) Q) （）（）( 是二元运算符是二元运算符 ）（)(括号不匹配括号不匹配）（）（）括号不匹配括号不匹配（)( 是二元运算符）是二元运算符）（）（）（）（）第3节命题公式2、永真式（重言式）对于命题变元的所有种可能的真值指派，对于命题变元的所有种可能的真值指派，命题公式的真值均为命题公式的真值均为真真，称该合

24、式公式为，称该合式公式为永真式。永真式。第3节命题公式例、构造下列命题公式的真值表(1)(1)、(P(P Q) )Q(P(P Q) )Q(2)(2)、PP?P P(3)(3)(PQ)R) PQ)R) ?(PQ)R)(PQ)R)(4) (4) P QP Q、 ?P QP Q、 ?( ( PP ? Q)Q)表表1.8(1.8(P(PQ)QP(PQ)Q的真值表的真值表PQ00011011P QP(PQ) (P(PQ)Q011110001111(P(P Q) )Q是永真式是永真式第3节命题公式表表1.9 1.9 PP?P P的真值表的真值表P01? PP?P1011P?P是永真式是永真式第3节命题公式

25、表表1.10(1.10(PQ)R)PQ)R)?(PQ)R)(PQ)R)的真值的真值表表PQR000001010011100101110111P Q(PQ)R ?(PQ)R)(PQ)R)?(PQ)R)00111111111000001110101011111111(PQ)R) ?(PQ)R)是永真式是永真式第3节命题公式表表1.101.10 P Q P Q、 ?P QP Q、 ?( ( PP ? Q)Q)的真值表的真值表PQ 00011011注意：注意： 以上三个命题公式的以上三个命题公式的真值表完全相同真值表完全相同，称，称这三个命题公式这三个命题公式等价等价。P Q0111? P? P Q1

26、1001101? QP ? Q?( P ? Q)101000101101第3节命题公式第3节命题公式3、永假式（矛盾式）给定一命题公式，给定一命题公式， 若对任何的真值指派若对任何的真值指派, ,其对应的真值永为其对应的真值永为F F， 则称该命题公式为则称该命题公式为矛盾式或永假式。矛盾式或永假式。第3节命题公式例、构造下列命题公式的真值表(1)(1)、PP?P P(2)(2)、(PQ)(PQ)?P P表表1.11 1.11 P P?P P的真值表的真值表P01? PP ?P1000P ?P是永假式是永假式第3节命题公式表表1.12(1.12(PQ)PQ) P P的真值表的真值表PQ0001

27、1011第3节命题公式PQ P(PQ) P100011000000(PQ)?P是永假式是永假式第3节命题公式4、可满足式至少至少有一组真值指派使得命题公式取值有一组真值指派使得命题公式取值为为真真， 则称该命题公式为可满足式。则称该命题公式为可满足式。注意：注意：永真式是可满足式的一种特例永真式是可满足式的一种特例。第3节命题公式例、构造下列命题公式的真值表1. (PR)(P Q)2. P (QR)3. (PQ)(QP)4. (P (QR) (PQ)(PR)表表1.131.13 (PR)(PQ)(PR)(PQ)的真值表的真值表PQR000001010011100101110111第3节命题公式

28、P R P Q(PR)(P Q)000001011111001101111111(PR)(P Q)是可满足式是可满足式表表1.141.14 P(QR)P(QR)的真值表的真值表PQR000001010011100101110111第3节命题公式QRP (QR)0111011101111111P (QR)是可满足式是可满足式表表1.151.15 (PQ)(PQ)(QP)(QP)的真值表的真值表PQ00011011第3节命题公式P QQP(PQ)(QP)011101111111(PQ)(QP)是永真式是永真式表表1.16 1.16 WFFA=(P(QR)WFFA=(P(QR)(PQ)(PR)(PQ

29、)(PR)的真值表的真值表PQ R000001010011100101110111第3节命题公式QRP (QR)PQ PR (PQ)(PR)WFFA001111110111111100111111001111110111111111111111(P (QR) (PQ)(PR)是永真式是永真式第3节命题公式5、永真式的特点（1 1）永真式的否定为矛盾式，反之亦然；）永真式的否定为矛盾式，反之亦然；（2 2）永真式的）永真式的“”、” ” ”、” ” ”、” ” ”仍为永真式；仍为永真式；（3 3）由永真式可以产生许多）由永真式可以产生许多恒等式恒等式。等价式等价式第4节等价式（恒等式）和永真蕴涵

30、式第4节等价式（恒等式）和永真蕴涵式1 1、等价式、等价式2 2、等价式的性质、等价式的性质3 3、永真蕴涵式、永真蕴涵式4 4、永真蕴涵式的性质、永真蕴涵式的性质5 5、代入规则和替换规则、代入规则和替换规则第4节等价式（恒等式）和永真蕴涵式1、 等价式的定义给定两个命题公式给定两个命题公式A A和和B, PB, P1 1，P P2 2，P Pn n为所有出现于为所有出现于A A和和B B中的原子变元，若给中的原子变元，若给n n个个命题变元命题变元P P1 1，P P2 2，P Pn n指派指派2 2n n个可能的真个可能的真值，命题公式值，命题公式A A和和B B的真值都相同，则称公的真

31、值都相同，则称公式式A A等价公式等价公式B B，或：如果或：如果A AB BT T，则则A AB B记作记作AB。第4节等价式（恒等式）和永真蕴涵式例、利用真值表证明下列等价式1. 1. (P(PQ)Q)(PQ) (PQ) (PQ)(PQ)2. P(QR)2. P(QR)(P (P Q)RQ)R3. P(PQ)3. P(PQ)P P表表1.17 1.17 (P(PQ)Q)、(PQ)(PQ) (PQ)(PQ) 的真值表的真值表PQ00011011所以：所以： (P(PQ)Q)(PQ) (PQ) (PQ)(PQ)第4节等价式（恒等式）和永真蕴涵式PQ (PQ)11000110PQ0111PQ00

32、01 (PQ)1110(PQ) (PQ)0110表表1.18 1.18 P(QR)P(QR)、(P(P Q)RQ)R的真值表的真值表PQ R000001010011100101110111所以：所以： P(QR) P(QR)(P (P Q)RQ)R第4节等价式（恒等式）和永真蕴涵式QR01110111P (QR)11110111 Q11001100P Q00001100(P Q)R11110111表表1.19 1.19 P(PQ)P(PQ)的真值表的真值表PQ00011011所以：所以：P(PQ)P(PQ)P P第4节等价式（恒等式）和永真蕴涵式PQ0111P(PQ)0011第4节等价式（恒等

33、式）和永真蕴涵式九组常见的等价式（1 1）交换律；）交换律；（2 2）结合律；）结合律；（3 3）分配律；）分配律；（4 4）否定深入；）否定深入；（5 5）变元等同；）变元等同；（6 6）常值与变元的联结；）常值与变元的联结；（7 7）联结词的化归；）联结词的化归；（8 8）吸收律；）吸收律；（9 9）输出律；）输出律；第4节等价式（恒等式）和永真蕴涵式（1）交换律（ 、 、 ）PQPQ QPQPQPPQPQ第4节等价式（恒等式）和永真蕴涵式（2）结合律（ 、 、 ）( (PQ)RPQ)RP(QR)P(QR)(PQ)R P(QR)(PQ)R第4节等价式（恒等式）和永真蕴涵式（3）分配律（ 对

34、、 对、对 ）P(QR)P(QR)(PQ)(PR)(PQ)(PR)P(QR)(PQ)(PR) P(QR)证明：证明：P(QR)P(QR)(P(PQ)(PR)Q)(PR)PQR000001010011100101110111所以：所以： P(QR)P(QR)(P(PQ)(PR)Q)(PR)QR01110111P (QR)00000111PQ00000011PR00000101(PQ)(PR)00000111第4节等价式（恒等式）和永真蕴涵式第4节等价式（恒等式）和永真蕴涵式（4）否定深入双重否定定律：双重否定定律：P QP P德摩根定律：德摩根定律： (PQ) P Q (PQ) P Q (PQ)

35、 PQP Q证明：证明： ( (P PQ)Q)PP QQ P PQ Q00011011所以：所以： ( (P PQ)Q)PP Q Q P Q0001 (PQ)1110 P1100 Q1010 P Q1110第4节等价式（恒等式）和永真蕴涵式第4节等价式（恒等式）和永真蕴涵式（5）变元等同等幂律：等幂律：PP PPP PP PFP P TPP TP P P PP PPP TP P PP F第4节等价式（恒等式）和永真蕴涵式（6）常值与变元的联结同一律：同一律：PF PPT P零律：零律：PTTPF FTP PFP TPT TPF PPT PPF P第4节等价式（恒等式）和永真蕴涵式（7）联结词的

36、化归PQPQ P Q ( P Q)PQ ( P Q)PQ PQPQ (PQ)(QP)( PQ)( QP)(PQ)( P Q)证明：证明： P PQQ (P (PQQ) )( ( PP Q)Q)P PQ Q00011011所以：所以： P PQ Q (P (PQQ) )( ( PP Q)Q)PQ0001 P1100 Q1010 P Q1000(PQ)( P Q)1001PQ1001第4节等价式（恒等式）和永真蕴涵式第4节等价式（恒等式）和永真蕴涵式（8）吸收律P P(P(PQ)Q)P(PQ)PP第4节等价式（恒等式）和永真蕴涵式（9）输出律PQRPQRP(QR)第4节等价式（恒等式）和永真蕴涵式

37、说明：(1)QP称为称为PQ的逆换式；的逆换式；(2)?P ?Q称为称为PQ的反换式；的反换式；(3)?Q ?P称为称为PQ的逆反式。的逆反式。注意：注意：PQPQ QQ P P第4节等价式（恒等式）和永真蕴涵式2、 等价式的性质（1 1）自反性：）自反性：则则AC。AA；（2）对称性：）对称性：如果如果AB， 则则BA；（3）可传递性：）可传递性：如果如果AB，BC，第4节等价式（恒等式）和永真蕴涵式3、 永真蕴涵式A称为称为B的逻辑前提的逻辑前提,B称为称为A的逻辑结果；的逻辑结果；由由A能推出能推出B，B是由是由A推出的。推出的。若若AB TA永真蕴涵永真蕴涵B永真蕴涵式永真蕴涵式AB第

38、4节等价式（恒等式）和永真蕴涵式证明永真蕴涵式的方法（1 1）真值表法）真值表法: :则则AB；若若ABT，则则AB；（2）假设前件假设前件A为真，为真， 若能证明后件若能证明后件B必为真，必为真，则则AB；（3）假设后件）假设后件B为假，为假， 若能证明前件若能证明前件A必为假，必为假，第4节等价式（恒等式）和永真蕴涵式例、试用不同的方法证明下列蕴涵式P(PQ)P(PQ)QQ证明证明P(PQ)P(PQ)QQ方法方法1 1真值表法：真值表法：P PQ Q00011011即：即：P(PQ)P(PQ)QQPQ11010001P(PQ)(P(PQ)Q1111第4节等价式（恒等式）和永真蕴涵式证明证明

39、P(PQ)P(PQ)QQ方法方法2 2假设前件为真，证明后件必为真假设前件为真，证明后件必为真假设前件假设前件P(PQ)P(PQ)为真为真即：即：P(PQ)Q真真真真真真第4节等价式（恒等式）和永真蕴涵式证明证明P(PQ)P(PQ)QQ方法方法3 3假设后件为假，证明前件必为假假设后件为假，证明前件必为假假设后件假设后件QQ为假为假则对前件则对前件P(PQ)P(PQ)中的中的P P进行如下讨论：进行如下讨论：即：即：P(PQ)Q（1）P为真时：为真时：P(PQ)（2）P为假时：为假时：P(PQ)真真假假假假假假真真假假第4节等价式（恒等式）和永真蕴涵式第4节等价式（恒等式）和永真蕴涵式4、永真

40、蕴涵式的性质（1 1）自反性：）自反性：（4）若）若AB， CB，A A；（2）可传递性：）可传递性： 如果如果AB， BC， 则则AC；（3）若）若AB， AC，则则ABC；则则ACB。证明：若证明：若A AB B， A AC C，则则A ABCBC假设前件假设前件A A为真，证明后件为真，证明后件BCBC必为真：必为真：即即ABCABA为真为真B必为真必为真ACA为真为真C必为真必为真BC为真为真第4节等价式（恒等式）和永真蕴涵式第4节等价式（恒等式）和永真蕴涵式常见的永真蕴涵式（1 1）化简式：）化简式： PQPQP P， PQ PQQ Q（2 2）附加式：）附加式： P PPQPQ，

41、Q QP PQQ（3 3）析取三段论：）析取三段论： P P，PQPQQ Q（4 4）假言推论：）假言推论：P P， PQ PQQ Q（5 5）拒取式：）拒取式： Q Q，PQPQP P（6 6）假言三段论：）假言三段论： PQPQ， QR QR PRPR（7 7）二难推论：）二难推论： PQPQ，PRPR，QRQRR R 注意：注意：，即即 证明：析取三段论：证明：析取三段论： P P，PQPQQQ假设前件假设前件 P P，PQPQ为真，证明后件为真，证明后件QQ为真为真即即 P，PQQ P为真为真PQ为真为真P必为假必为假真真第4节等价式（恒等式）和永真蕴涵式证明：假言三段论：证明：假言三

42、段论： PQPQ， QR QR PRPR假设后件假设后件PRPR为假为假, ,证明前件证明前件PQ, QRPQ, QR必为假：必为假：即即PQ， QR PR PR为假为假P必为真必为真R必为假必为假对对Q进行以下讨论：进行以下讨论：(1)Q为真时为真时:(2) Q为假时为假时:PQ为真为真QR为假为假(PQ) ( QR)必为假必为假PQ为假为假QR为真为真(PQ) ( QR)必为假必为假第4节等价式（恒等式）和永真蕴涵式第4节等价式（恒等式）和永真蕴涵式5、 代入规则和替换规则（1 1）代入实例）代入实例；（2 2）代入规则）代入规则；（3 3）替换规则（置换定理）替换规则（置换定理）；（4

43、4）等价式的证明方法）等价式的证明方法；（5 5）代入规则和替换规则的不同点。代入规则和替换规则的不同点。第4节等价式（恒等式）和永真蕴涵式（1）、 代入实例WffB(P1，P2，Pi,，Pn)命题变元命题变元 WffAi代换代换所有出现所有出现WffAWffB的代入实例。的代入实例。注意：注意：（1）只能代换）只能代换命题变元命题变元；（2）代换该命题变元的）代换该命题变元的所有出现所有出现；代入实例举例已知：命题公式已知：命题公式( (P PQ) (Q) (P PR)R)试用命题公式（试用命题公式（A AB B）代换代换P P的所有出现，的所有出现，得到以下的命题公式：得到以下的命题公式：

44、 第4节等价式（恒等式）和永真蕴涵式( Q)( R)(AB)(AB)第4节等价式（恒等式）和永真蕴涵式（2）、 代入规则永真式的任何代入实例仍为永真式。永真式的任何代入实例仍为永真式。第4节等价式（恒等式）和永真蕴涵式代入规则举例PP P P为永真式；为永真式；以命题公式：以命题公式：QRQR代换命题变元代换命题变元P P的所有出现；的所有出现；得到的命题公式：得到的命题公式：(QR) (QR)永真式永真式第4节等价式（恒等式）和永真蕴涵式（3）、替换规则（置换定理）WffAWffA子公式子公式WffAWffB替换WffB注意：注意： （1）实现的是）实现的是等价变换等价变换；（2）不需要代换

45、所有出现；）不需要代换所有出现；第4节等价式（恒等式）和永真蕴涵式（4）证明等价式的方法（1 1）真值表法；）真值表法；（2 2）利用）利用置换定理置换定理产生等价序列产生等价序列；证明 ( ( PP Q)Q) ( ( PQ)PQ)P P方法一方法一真值表法：真值表法：P P Q Q0 00 11 01 1第4节等价式（恒等式）和永真蕴涵式 P1100 Q1010 P Q1110 ( P Q)0001 PQ1101 ( PQ)0010 ( P Q) ( PQ)0011 ( P Q) ( PQ)P证明 ( ( PP Q)Q) ( ( PQ)PQ)P P方法二方法二置换定理： ( ( PP Q)Q

46、) ( ( PQ)PQ)第4节等价式（恒等式）和永真蕴涵式(PQ)(P Q)(德摩根定律）德摩根定律）P（分配率）分配率）P(Q Q)PT第4节等价式（恒等式）和永真蕴涵式（5）代入规则和替换规则的不同点（1 1）代入规则：被替换的是命题变元；）代入规则：被替换的是命题变元； 替换规则：被替换的可以是命题常量、命题替换规则：被替换的可以是命题常量、命题 变元、合式公式；变元、合式公式；（2 2）替换规则：要求替换和被替换的合式公式必）替换规则：要求替换和被替换的合式公式必 须是等价的；须是等价的； 代入规则：不必；代入规则：不必；（3 3）代入规则：若对命题变元）代入规则：若对命题变元P P使

47、用代入规则，使用代入规则， 则合式公式中所有则合式公式中所有P P的出现均要的出现均要 使用代入规则；使用代入规则； 替换规则：不必。替换规则：不必。第4节等价式（恒等式）和永真蕴涵式例、证明下列等价式1. (1. (AD)(BD)AD)(BD)(AB)D(AB)D2. (AB)C)(B(DC)2. (AB)C)(B(DC)(B(DA)C(B(DA)C3. P(QR)3. P(QR)Q(PR)Q(PR)?R(QR(Q?P)P)证明：证明：( (AD)(BD)AD)(BD)(AB)D(AB)D左式左式( (AD)(BD)AD)(BD)第4节等价式（恒等式）和永真蕴涵式( AD )( BD)(AB

48、)D（分配率）分配率）( A B)D(德摩根定律）德摩根定律） (AB)D右式右式证明：证明：( (AB)C)(B(DC)AB)C)(B(DC)(B(DA)C(B(DA)C左式左式( ( ( (AB)AB)C)(C)( B B(DC)(DC)第4节等价式（恒等式）和永真蕴涵式(B(DA)C(B(DA)C(德摩根定律）德摩根定律）( ( A A B BC C)()( B BDDC C) )（分配率）分配率）( ( A A B B )( )( B BD)CD)C（分配率）分配率）( ( B B( ( AD)AD)C)C(德摩根定律）德摩根定律） ( ( B B ( (A A D)D)CC(德摩根定

49、律德摩根定律) ( (BB(A(A D)D)C)C ( (B(DA)CB(DA)C右式右式证明：证明：P(QR)P(QR)Q(PR)Q(PR) R(QR(Q?P)P)左式左式 P P( ( QQ R) R) 第4节等价式（恒等式）和永真蕴涵式 R(Q?P)（交换率交换率,结合律）结合律） QQ( P PR)R) QQ( ( PR)PR) Q(PR) QQ P PR R（交换率交换率,结合律）结合律） R R( QQ P)P) R R(Q(Q?P)P)第5节对偶式和对偶原理第5节 对偶式和对偶原理1 1、对偶式、对偶式2 2、对偶原理、对偶原理第5节对偶式和对偶原理1、对偶式WffA仅含仅含 、

50、 、 TFFTWffA* 互互为为对对偶偶式式第5节对偶式和对偶原理例、写出下列命题公式的对偶式(1) (PQ) R(2) (PQ)T(3) (PQ)(P(Q S ) )(PQ)R(PQ)F (PQ)(P(Q S) )F第5节对偶式和对偶原理定理设设A A和和A A* *互为对偶式互为对偶式, , P P1 1，P P2 2，P Pn n为为所有出现于所有出现于A A和和A A* *中的中的命题变元命题变元，则：，则： A(A(P P1 1，P P2 2，, ,P Pn n) )A A* *( ( P P1 1, , P P2 2，, , P Pn n) )A(A( P P1 1， P P2

51、2, , , P Pn n) ) A A* *( (P P1 1,P,P2 2, , ,P Pn n) )第5节对偶式和对偶原理例、使用下例验证上述定理WffAWffA=(=( P PQ) )RWffA=( PQ)R WffA*=( PQ)R A= ( PQ) R(P Q) RA*( P, Q, R)= ( P Q) R (P Q) R A (P, Q, R) A*( P, Q, R)同理：A ( P, Q, R)A*(P, Q, R)( PQ)R) 第5节对偶式和对偶原理第5节对偶式和对偶原理2、对偶原理若若:AB仅含仅含 、 、 则：则： A*B*对偶原理证明 ABABTA( )B( )T

52、P1,P2,PnP1,P2,Pn A(P1，P2，,Pn)A*( P1, P2，, Pn) A(P1，P2，,Pn)A*( P1, P2，, Pn)B(P1，P2，,Pn)B*( P1, P2，, Pn)同理：A*( P1, P2，, Pn)B*( P1, P2，, Pn) T永真式的任何代入实例仍为永真式永真式的任何代入实例仍为永真式用用 Pi代替代替Pi的所有出现的所有出现 (1 i n)得：得：A*(P1,P2，,Pn)B*(P1,P2，,Pn)T A*B*第5节对偶式和对偶原理定理若若A AB B，则：则： B B* *A A* *定理证明 ABABTA( )B( )TP1,P2,Pn

53、P1,P2,Pn A(P1，P2，,Pn)A*( P1, P2，, Pn) A(P1，P2，,Pn)A*( P1, P2，, Pn)同理：B(P1，P2，,Pn)B*( P1, P2，, Pn) A*( P1, P2，, Pn) B*( P1, P2，, Pn)TA*( P1, P2，, Pn) B*( P1, P2，, Pn)T B*( P1, P2，, Pn)A*( P1, P2，, Pn)TB*( P1, P2，, Pn)A*( P1, P2，, Pn)T用用 Pi代替代替Pi的所有出现的所有出现 (1 i n)得：得：B*(P1,P2，,Pn)A*(P1,P2，,Pn)T B*A*第5

54、节对偶式和对偶原理功能完备集设有一个联结词集合设有一个联结词集合A A，如果：如果：（1 1）用）用A A中的联结词能够表达任何命题公式；中的联结词能够表达任何命题公式；（2 2）删除）删除A A中的任何联结词得到一个联结词集合中的任何联结词得到一个联结词集合AA，至少有一个公式不可能用仅含于至少有一个公式不可能用仅含于AA中的逻中的逻辑联结词的等价式表达出来，则集合辑联结词的等价式表达出来，则集合A A称为功能称为功能完备集。完备集。?, ,?, 是功能完备集P PQ QP PQ QP PQ Q(P(PQQ) )( ( PP Q)Q)PQPQ( ( PP Q)Q)PQPQ( ( PP Q)Q

55、)第5节对偶式和对偶原理第5节对偶式和对偶原理例、写出与下式等价并仅含?， 的最简式 P(QR) P( Q R)( (PQ R)第6节主析取范式和主合取范式第6节 主析取范式和主合取范式1 1、析取范式和合取范式、析取范式和合取范式2 2、主析取范式和主合取范式、主析取范式和主合取范式第6节主析取范式和主合取范式1、析取范式和合取范式（1 1）基本积和基本和）基本积和基本和（2 2）析取范式）析取范式（3 3）合取范式）合取范式（4 4）求合取范式或析取范式的步骤）求合取范式或析取范式的步骤第6节主析取范式和主合取范式（1）基本积和基本和合式公式中的一些变元和一些变元的否合式公式中的一些变元和

56、一些变元的否定的定的合取合取，称为基本，称为基本积积；合式公式中的一些变元和一些变元的否合式公式中的一些变元和一些变元的否定的定的析取析取，称为基本，称为基本和和；如：如： P Q如：如： PR Q第6节主析取范式和主合取范式（2）析取范式注意：注意：一个命题公式的析取范式不唯一一个命题公式的析取范式不唯一 WffA由基本积的由基本积的和和组成的公式组成的公式A的的析取析取范式范式A A1A2An n1记作：记作：基本积基本积第6节主析取范式和主合取范式（3）合取范式注意：注意：一个命题公式的合取范式不唯一一个命题公式的合取范式不唯一 WffA由基本和的由基本和的积积组成的公式组成的公式A的的

57、合取合取范式范式A A1 A2 An n1记作：记作：基本和基本和(4)求合取范式或析取范式的步骤将公式中的联结词化归成将公式中的联结词化归成、 ；利用德利用德摩根定律将否定符号摩根定律将否定符号 直接移到各直接移到各个命题变元之前；个命题变元之前；利用分配律、结合律将公式化为合取范式利用分配律、结合律将公式化为合取范式或析取范式。或析取范式。第6节主析取范式和主合取范式析取范式和合取范式举例(1)(1) 求求( (P(QR)SP(QR)S的合取范式的合取范式(2)(2) 求求 (PQ)(PQ)(PQ )(PQ )的析取范式的析取范式第6节主析取范式和主合取范式求求(P(QR)S的合取范式的合

58、取范式基本和基本和基本和基本和第6节主析取范式和主合取范式(P(QR)S (P( QR)S（德摩根定律）德摩根定律）( P ( QR)S（德摩根定律）德摩根定律）( P(Q R)S（分配律）分配律）( PQ)( P R)S（分配律）分配律）( PQ S)( P R S)（合取范式）合取范式）求求 (PQ)(PQ )的析取范式的析取范式 (PQ)(PQ )( P Q)(PQ )（德摩根定律）德摩根定律）( )( )( ( ) ( ) P QPQ P QPQ( P QPQ )(PQ)( P Q)F(PQ)( P Q)(PQ)( P Q)（合取范式）合取范式）(PQ) P)(PQ) Q)（分配律）分

59、配律）(P P )(Q P)(P Q)(Q Q)（分配律）分配律）( PQ)(P Q)（析取范式）析取范式）第6节主析取范式和主合取范式2、主析取范式和主合取范式、主析取范式和主合取范式（1 1）极小项）极小项（2 2）主析取范式）主析取范式（3 3）极大项）极大项（4 4）主合取范式）主合取范式（5 5）主析取范式和主合取范式的求法）主析取范式和主合取范式的求法（6 6）主析取范式和主合取范式的关系）主析取范式和主合取范式的关系（7 7）极大项和极小项的关系）极大项和极小项的关系（8 8）主析取范式和主合取范式的作用）主析取范式和主合取范式的作用第6节主析取范式和主合取范式（1）极小项编码原

60、则：编码原则：极小项中命题变元的否定对应着极小项中命题变元的否定对应着“0”“0”； 命题变元本身对应着命题变元本身对应着“1”“1”。 WffA中含有中含有n个命题变元个命题变元每个变元与其否定每个变元与其否定必出现且仅出现一次必出现且仅出现一次极小项极小项基本积基本积第6节主析取范式和主合取范式例、写出两个命题变元的极小项及其真值表两个命题变元的极小项及真值表两个命题变元的极小项及真值表PQ极小项极小项编码编码mi00011011 P Qm0 PQm1P Qm2PQm3第6节主析取范式和主合取范式例、写出三个命题变元的极小项及其真值表三个命题变元的极小项及真值表三个命题变元的极小项及真值表