第一章命题逻辑

1、2022-3-291l命题逻辑，也称命题演算，记为命题逻辑，也称命题演算，记为LsLs。它与。它与谓词逻辑构成数理逻辑的基础，而命题逻谓词逻辑构成数理逻辑的基础，而命题逻辑又是谓词逻辑的基础。数理逻辑是用数辑又是谓词逻辑的基础。数理逻辑是用数学方法即通过引入表意符号研究推理的学学方法即通过引入表意符号研究推理的学问。因此，数理逻辑又名为符号逻辑。问。因此，数理逻辑又名为符号逻辑。l命题逻辑是研究由命题为基本单位构成的命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。前提和结论之间的可推导关系。2022-3-292 1.1 命题与联结词命题与联结词 1.2 命题变元和合式公式命题变

2、元和合式公式 1.3 公式分类与等价公式公式分类与等价公式 1.4 对偶式与蕴涵式对偶式与蕴涵式 1.5 联结词的扩充与功能完全组联结词的扩充与功能完全组 1.6 公式标准型公式标准型范式范式 1.7 公式的主范式公式的主范式 1.8 命题逻辑的推理理论命题逻辑的推理理论2022-3-293. . 命题的概念命题的概念l所谓命题，是指具有非真必假的陈述句。所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。命题仅有判断其真假，故都不是命题。命题仅有两种可能的真值两种可能的真值真和假，且二者只能居真和假，且二者只能居其

3、一。真用其一。真用1 1或或T T表示，假用表示，假用0 0或或F F表示。表示。由于命题只有两种真值，所以称这种逻由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。性质的，而不是由人的主观决定的。2022-3-294l如果一陈述句再也不能分解成更为简单的语句，如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题。原子命题是命题由它构成的命题称为原子命题。原子命题是命题逻辑的基本单位。逻辑的基本单位。l命题分为两类，第一类是原子命题，原子命题用命题分为两类，第一类是原子命题，原子命题用大写英文字

4、母大写英文字母P，Q，R或带下标的或带下标的Pi，Qi，Ri，及其数字表示。其中及其数字表示。其中P,Q,R Pi，Qi，Ri，及其数字称为命题标识符及其数字称为命题标识符.l第二类是复合命题，它由原子命题、命题联结词第二类是复合命题，它由原子命题、命题联结词和圆括号组成。下面给出实例和圆括号组成。下面给出实例,说明命题的概念说明命题的概念.2022-3-2951.中国人民是伟大的中国人民是伟大的.2.雪是黑的雪是黑的.3. 别的星球上有生物别的星球上有生物.4. 我学英语我学英语,或者我学日语或者我学日语.5.如果天气好如果天气好,那么我去散步那么我去散步.6.今天下雨今天下雨.7.全体起立

5、全体起立!8.明天是否开大会明天是否开大会?9.天气多好啊天气多好啊!10.我正在说谎我正在说谎.2022-3-296 . 命题联结词命题联结词l定义定义1.1.1设设P表示一个命题，由命题表示一个命题，由命题联结词联结词l l和命题和命题P连接成连接成l lP，称，称l lP为为P的的否定式复合命题，否定式复合命题， l lP读读“非非P”。称。称l l为为否定联结词。否定联结词。l lP是真，当且仅当是真，当且仅当P为假；为假；l lP是假，当且仅当是假，当且仅当P为真。否定联结词为真。否定联结词“l l”的定义可由表的定义可由表1.1.1表示之。表示之。 2022-3-297表1.1.1

6、 的定义 P P 1 0 0 1l由于否定由于否定 修改了命题，它是对单个命题进行操作，修改了命题，它是对单个命题进行操作，称它为一元联结词。称它为一元联结词。例例 P : 上海是一个大城市上海是一个大城市. P: 上海并不是一个大城市上海并不是一个大城市.或或 P: 上海是一个不大城市上海是一个不大城市.2022-3-298l定义定义1.1.2 设设P和和Q为两个命题，由为两个命题，由命题联结词命题联结词将将P和和Q连接成连接成PQ，称，称PQ为命题为命题P和和Q的合取式复合命题，的合取式复合命题，PQ读做读做“P与与Q”，或，或“P且且Q”。称。称为合取联结词。为合取联结词。l当且仅当当且

7、仅当P和和Q的真值同为真，命题的真值同为真，命题PQ的真值才为真；否则，的真值才为真；否则，PQ的真的真值为假。合取联结词值为假。合取联结词的定义由表的定义由表1.1.2表示之。表示之。2022-3-299表表1.1.2 的定义的定义 P QP Q 0 00 0 10 1 00 1 112022-3-2910例例1 P: 今天下雨今天下雨. Q: 明天下雨明天下雨.上述命题的合取为上述命题的合取为 P Q: 今天下雨而且明天下雨今天下雨而且明天下雨. P Q: 今天与明天都下雨今天与明天都下雨. P Q: 这两天都下雨这两天都下雨.例例2 P:我们去看电影我们去看电影. Q:房间里有十张桌子房

8、间里有十张桌子.上述命题的合取为上述命题的合取为 P Q:我们去看电影与房间里有十张桌子我们去看电影与房间里有十张桌子.2022-3-2911l定义定义1.1.3 设设P和和Q为两个命题，由命为两个命题，由命题联结词题联结词把把P和和Q连接成连接成PQ，称，称PQ为命题为命题P和和Q的析取式复合命题，的析取式复合命题，PQ读做读做“P或或Q”。称。称为析取联结词。为析取联结词。l当且仅当当且仅当P和和Q的真值同为假，的真值同为假，PQ的真值为假；否则，的真值为假；否则，PQ的真值为真。的真值为真。析取联结词析取联结词的定义由表的定义由表1.1.3表示之。表示之。2022-3-2912表表 1.

9、1.3 的定义的定义PQP Q0000111011112022-3-2913l由定义可知，析取联结词表示由定义可知，析取联结词表示“可兼或可兼或”，“不可兼或不可兼或”另有别的联结词定义另有别的联结词定义l与合取联结词一样，使用析取联结词时，也不与合取联结词一样，使用析取联结词时，也不要求两命题间一定有任何关系要求两命题间一定有任何关系.例例1 P:他是他是100米赛跑冠军米赛跑冠军. Q:他是他是400米赛跑冠军米赛跑冠军.上述命题的析取为上述命题的析取为 P Q:他是他是100米或米或400米赛跑冠军米赛跑冠军.2022-3-2914l定义定义1.1.4 设设P和和Q为两个命题，由命题为两

10、个命题，由命题联结词联结词把把P和和Q连接成连接成PQ，称，称PQ为命题为命题P和和Q的条件式复合命题，简称条的条件式复合命题，简称条件命题。件命题。PQ读做读做“P条件条件Q”或者或者“若若P则则Q”。称。称为条件联结词。为条件联结词。当当P的真值为真而的真值为真而Q的真值为假时，命题的真值为假时，命题PQ的真值为假；否则，的真值为假；否则，PQ的真值的真值为真。条件联结词为真。条件联结词的定义由表的定义由表1.1.4表表示之。示之。2022-3-2915表表 1.1.4 的定义的定义PQP Q0010111001112022-3-2916l在条件命题在条件命题PQ中，命题中，命题P称为称为

11、PQ的前件或的前件或前提，命题前提，命题Q称为称为PQ的后件或结论。条件命的后件或结论。条件命题题PQ有多种方式陈述：有多种方式陈述：l“如果如果P，那么，那么Q”；“P仅当仅当Q”；“Q每当每当P”；“P是是Q的充分条件的充分条件”；“Q是是P的必要条件的必要条件”等。等。2022-3-2917例例1 P:某动物为哺乳动物某动物为哺乳动物. Q:哺乳动物必胎生哺乳动物必胎生. P Q:如果某动物为哺乳动物如果某动物为哺乳动物,则它必胎生则它必胎生.例例2 P:雪是黑的雪是黑的. Q:太阳从西边出来太阳从西边出来. P Q:如果雪是黑的如果雪是黑的,那么太阳从西边出来那么太阳从西边出来.202

12、2-3-2918l定义定义1.1.5 令令P、Q是两个命题，由命题联是两个命题，由命题联结词结词把把P和和Q连接成连接成P Q，称，称P Q为命题为命题P和和Q的双条件式复合命题，简称的双条件式复合命题，简称双条件命题，双条件命题，P Q读做读做“P当且仅当当且仅当Q”，或或“P等价等价Q”。称。称为双条件联结为双条件联结l当当P和和Q的真值相同时，的真值相同时，P Q的真值为的真值为真；否则，真；否则，P Q的真值为假。双条件联的真值为假。双条件联结词结词的定义由表的定义由表1.1.5表示之。表示之。2022-3-2919表表 1.1.5 的定义的定义PQP Q001010100111202

13、2-3-2920例例1 P:燕子飞回南方燕子飞回南方. Q:春天来了春天来了. P Q:燕子飞回南方燕子飞回南方,当且仅当春天来了当且仅当春天来了.例例2 P:2+2=4. Q:雪是黑的雪是黑的. P Q:2+2=4,当且仅当雪是黑的当且仅当雪是黑的.2022-3-2921l命题命题 1) 命题的概念命题的概念 2) 命题的判断命题的判断 3) 命题的表示命题的表示 4) 原子命题及复合命题原子命题及复合命题l联结词联结词 1)否定否定 2)合取合取 3)析取析取 4)条件条件 5)双双条件条件2022-3-2922l在本节结束时，应强调指出的是：复合在本节结束时，应强调指出的是：复合命题的真

14、值只取决于各原子命题的真值，命题的真值只取决于各原子命题的真值，而与它们的内容、含义无关，与原子命而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这题之间是否有关系无关。理解和掌握这一点是至关重要的，请读者认真去领会。一点是至关重要的，请读者认真去领会。2022-3-29231.指出下列语句那些是命题指出下列语句那些是命题,那些不是那些不是,若是命题若是命题,指出它的真值指出它的真值.(1)离散数学是计算机科学系的一门必修课离散数学是计算机科学系的一门必修课.(2)计算机有空吗计算机有空吗?(3)明天我去看电影明天我去看电影.(4)请勿随地吐痰请勿随地吐痰!(5)不存在最大质

15、数不存在最大质数.(6)9+5 12.2022-3-2924 2. P: 天下雪天下雪. Q: 我将去镇上我将去镇上. R: 我有时间我有时间. 以符号形式写出下列命题以符号形式写出下列命题 a) 如果天不下雨和我有时间如果天不下雨和我有时间,那么我将去镇上那么我将去镇上. b) 我将去镇上我将去镇上,仅当我有时间时仅当我有时间时. c) 天不下雪天不下雪. d) 天下雪天下雪,那么我不去镇上那么我不去镇上.2022-3-2925 . 命题变元命题变元l在命题逻辑中，命题又有命题常元和命题在命题逻辑中，命题又有命题常元和命题变元之分。一个确定的具体的命题，称为变元之分。一个确定的具体的命题，称

16、为命题常元；一个不确定的泛指的任意命题，命题常元；一个不确定的泛指的任意命题，称为命题变元。显然，命题变元不是命题，称为命题变元。显然，命题变元不是命题，只有用一个特定的命题取代才能确定它的只有用一个特定的命题取代才能确定它的真值：真或假。这时也说对该命题变元指真值：真或假。这时也说对该命题变元指派真值。派真值。2022-3-2926l命题常元和命题变元均可用字母命题常元和命题变元均可用字母P等表示。等表示。由于在命题逻辑中并不关心具体命题的由于在命题逻辑中并不关心具体命题的涵义，只关心其真值，因此，可以形式涵义，只关心其真值，因此，可以形式地定义它们如下：地定义它们如下： l定义定义1.2.

17、1以真或以真或1、假或、假或0为其变域为其变域的变元，称为命题变元；真或的变元，称为命题变元；真或1、假或、假或0称为命题常元。称为命题常元。2022-3-2927l2. 合式公式合式公式l通常把含有命题变元的断言称为命题公通常把含有命题变元的断言称为命题公式。但这没能指出命题公式的结构，因式。但这没能指出命题公式的结构，因为不是所有由命题变元、联结词和括号为不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。为所组成的字符串都能成为命题公式。为此常使用归纳定义命题公式，以便构成此常使用归纳定义命题公式，以便构成的公式有规则可循。由这种定义产生的的公式有规则可循。由这种定义产生的公

18、式称为合式公式。公式称为合式公式。l定义定义1.2.2单个命题变元和命题常元单个命题变元和命题常元称为原子命题公式，简称原子公式。称为原子命题公式，简称原子公式。2022-3-2928l定义定义1.2.3合式公式是由下列规则生合式公式是由下列规则生成的公式：成的公式：l单个原子公式是合式公式。单个原子公式是合式公式。l若若A是一个合式公式，则是一个合式公式，则(lA)也是一个也是一个合式公式。合式公式。l若若A、B是合式公式，则是合式公式，则(AB)、(AB)、(AB)和和(A B)都是合式公都是合式公式。式。l只有有限次使用、和生成的公只有有限次使用、和生成的公式才是合式公式。式才是合式公式

19、。2022-3-2929l当合式公式比较复杂时，常常使用很多当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可圆括号，为了减少圆括号的使用量，可作以下约定：作以下约定：l规定联结词的优先级由高到低的次序规定联结词的优先级由高到低的次序为：为：l l、 l相同的联结词按从左至右次序计算时，相同的联结词按从左至右次序计算时，圆括号可省略。圆括号可省略。l最外层的圆括号可以省略。最外层的圆括号可以省略。l为了方便计，合式公式也简称公式。为了方便计，合式公式也简称公式。2022-3-2930 .公式真值表公式真值表l定义定义1.2.4对于公式中命题变元的每对于公式中命题变元的每一种可

20、能的真值指派，以及由它们确定一种可能的真值指派，以及由它们确定出的公式真值所列成的表，称为该公式出的公式真值所列成的表，称为该公式的真值表。的真值表。l定义定义1.2.5如果如果B是公式是公式A中的一部分，中的一部分，且且B为公式，则称为公式，则称B是公式是公式A的子公式。的子公式。2022-3-2931l用归纳法不难证明，对于含有用归纳法不难证明，对于含有n个命题变个命题变元的公式，有元的公式，有2n个真值指派，即在该公个真值指派，即在该公式的真值表中有式的真值表中有2n行。行。l为方便构造真值表，为方便构造真值表，l特约定如下：特约定如下：l 命题变元按字典序排列。命题变元按字典序排列。l

21、 对每个指派，以二进制数从小到大或对每个指派，以二进制数从小到大或从大到小顺序列出。从大到小顺序列出。l 若公式较复杂，可先列出各子公式的若公式较复杂，可先列出各子公式的真值真值(若有括号，则应从里层向外层展开若有括号，则应从里层向外层展开)，最后列出所求公式的真值。最后列出所求公式的真值。2022-3-2932 4.命题的符号化命题的符号化l把一个用文字叙述的命题相应地写成由把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合命题标识符、联结词和圆括号表示的合式公式，称为式公式，称为l命题的符号化。符号化应该注意下列事命题的符号化。符号化应该注意下列事项项:l 确定给定句子是

22、否为命题。确定给定句子是否为命题。l 句子中连词是否为命题联结词。句子中连词是否为命题联结词。l 要正确地表示原子命题和适当选择命要正确地表示原子命题和适当选择命题联结词。题联结词。2022-3-2933l 命题符号化是很重要的，一定要掌命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。等于说推理的首要前提没有了。2022-3-2934 . 公式分类公式分类l定义定义1.3.1设设 A 为任意公式，则为任意公式，则l 对应每一个指派，公式对应每一个指派，公式 A

23、均相应确定均相应确定真值为真，称真值为真，称 A 为重言式，或永真式。为重言式，或永真式。l 对应每一个指派，公式对应每一个指派，公式 A 均相应确定均相应确定真值为假，称真值为假，称 A 为矛盾式，或永假式。为矛盾式，或永假式。l 至少存在一个指派，公式至少存在一个指派，公式 A 相应确定相应确定真值为真，称真值为真，称 A 为可满足式。为可满足式。2022-3-2935l由定义可知，重言式必是可满足式，反由定义可知，重言式必是可满足式，反之一般不真。之一般不真。l重点将研究重言式，它最有用，因为它重点将研究重言式，它最有用，因为它有以下特点：有以下特点：l重言式的否定是矛盾式，矛盾式的否重

24、言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。定是重言式，这样只研究其一就可以了。l两重言式的合取式、析取式、条件式两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。简单的重言式可构造出复杂的重言式。l由重言式使用公认的规则可以产生许由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。多有用等价式和蕴涵式。2022-3-2936l判定给定公式是否为永真式、永假式或判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定可满足式的问题，称为给定公式的判定问题。问题。l在在Ls中，

25、由于任何一个命题公式的指派中，由于任何一个命题公式的指派数目总是有限的，所以数目总是有限的，所以Ls的判定问题是的判定问题是可解的。其判定方法有真值表法和公式可解的。其判定方法有真值表法和公式推演法。推演法。2022-3-2937 .等价公式等价公式l定义定义1.3.2设设A和和B是两个命题公式，是两个命题公式，如果如果A、B在其任意指派下，其真值都是在其任意指派下，其真值都是相同的，则称相同的，则称A和和B是等价的，或逻辑相是等价的，或逻辑相等，记作等，记作AB，读作，读作A等价等价B，称，称AB为等价式。为等价式。l显然，若公式显然，若公式A和和B的真值表是相同的，的真值表是相同的，则则A

26、和和B等价。因此，验证两公式是否等等价。因此，验证两公式是否等价，只需做出它们的真值表即可。价，只需做出它们的真值表即可。2022-3-2938l在这里，请读者注意在这里，请读者注意和和的区别与联的区别与联系。系。l区别：区别：是逻辑联结词，属于目标语言是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；中的符号，它出现在命题公式中；不不是逻辑联结词，属于元语言中的符号，是逻辑联结词，属于元语言中的符号，表示两个命题公式的一种关系，不属于表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号这两个公式的任何一个公式中的符号l联系：可用下面定理表明之。联系：可用下面定理表明之。2

27、022-3-2939l定理定理1.3.1A B当且仅当当且仅当AB是永是永真式真式.有时也称有时也称A B是永真双条件式是永真双条件式l等价式有下列性质：等价式有下列性质：l 自反性，即对任意公式自反性，即对任意公式A，有，有A A。l 对称性，即对任意公式对称性，即对任意公式A和和B，若，若A B，则，则B A。l 传递性，即对任意公式传递性，即对任意公式A、B和和C，若，若A B、B C，则，则A C。2022-3-2940. .基本等价式基本等价式命题定律命题定律l在判定公式间是否等价，有一些简单而在判定公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式又经常使用的等价式，称

28、为基本等价式或称命题定律。牢固地记住它并能熟练或称命题定律。牢固地记住它并能熟练运用，是学好数理逻辑的关键之一，读运用，是学好数理逻辑的关键之一，读者应该注意到这一点。现将这些命题定者应该注意到这一点。现将这些命题定律列出如下：律列出如下：l(1)(1)双否定：双否定： A AA A。l(2)(2)交换律：交换律：A AB BB BA A，A AB BB BA A，A AB BB BA A。2022-3-2941l(3) (3) 结合律：结合律：( (A AB B)C CA A(B BC C) )，( (A AB B)C CA A(B BC C) )，( (A AB B) )C CA A( (

29、B BC C) )。l(4) (4) 分配律：分配律：A A(B BC C) )( (A AB B)()(A AC C) )，A A(B BC C) )( (A AB B)()(A AC C) )。l(5) (5) 德德摩根律：摩根律： ( (A AB B) )A A B B， ( (A AB B) )A A B B。l(6) (6) 等幂律：等幂律：A AA AA A，A AA AA A。2022-3-2942l(7) (7) 同一律：同一律：A AT TA A，A AF FA A。l(8) (8) 零零 律：律：A AF FF F，A AT TT T。l(9) (9) 吸收律：吸收律：A

30、A(A AB B) )A A，A A(A AB B) )A A。l(10) (10) 互补律：互补律：A A A AF F，( (矛盾律矛盾律) )lA A A AT T。( (排中律排中律) )l(11) (11) 条件式转化律：条件式转化律：A AB BA AB B，A AB BB B A A。2022-3-2943l(12) (12) 双条件式转化律：双条件式转化律：A AB B( (A AB B)()(B BA A) )( (A AB B)()( A A B B) )l A AB B( (A AB B) )l(13) (13) 输出律：输出律：( (A AB B)C CA A(B BC

31、 C) )。l(14) (14) 归谬律：归谬律：( (A AB B)()(A A B B) )A A。l上面这些定律，即是通常所说的布尔代上面这些定律，即是通常所说的布尔代数或逻辑代数的重要组成部分，它们的数或逻辑代数的重要组成部分，它们的正确性利用真值表是不难给出证明的。正确性利用真值表是不难给出证明的。2022-3-2944. .代入规则和替换规则代入规则和替换规则l在定义合成公式时，已看到了逻辑联结在定义合成公式时，已看到了逻辑联结词能够从已知公式形成新的公式，从这词能够从已知公式形成新的公式，从这个意义上可把逻辑联结词看成运算。除个意义上可把逻辑联结词看成运算。除逻辑联结词外，还要介

32、绍逻辑联结词外，还要介绍“代入代入”和和“替换替换”，它们也有从已知公式得到新，它们也有从已知公式得到新的公式的作用，因此有人也将它们看成的公式的作用，因此有人也将它们看成运算，这不无道理，而且在今后讨论中，运算，这不无道理，而且在今后讨论中，它的作用也是不容忽视的。它的作用也是不容忽视的。2022-3-2945 (1)代入规则代入规则l定理定理1.3.2 在一个永真式在一个永真式A A中，任何一个中，任何一个原子命题变元原子命题变元R出现的每一处，出现的每一处， 用另一用另一个公式代入，所得公式个公式代入，所得公式B仍是永真式。本仍是永真式。本定理称为代入规则。定理称为代入规则。 (2)替换

33、规则替换规则l定理定理1.3.3 设设A1是合式公式是合式公式A的子公式，的子公式，若若A1B1，并且将，并且将A中的中的A1用用B1 替换得替换得到公式到公式B，则，则AB。称该定理为替换规。称该定理为替换规则。则。l满足定理满足定理1.3.3条件的替换，称为等价替条件的替换，称为等价替换。换。2022-3-2946l代入和替换有两点区别：代入和替换有两点区别：l 代入是对原子命题变元而言的，而替代入是对原子命题变元而言的，而替换可对命题公式实行。换可对命题公式实行。l 代入必须是处处代入，替换则可部分代入必须是处处代入，替换则可部分替换，亦可全部替换。替换，亦可全部替换。2022-3-29

34、47 .对偶式对偶式l在上节介绍的命题定律中，多数是成对在上节介绍的命题定律中，多数是成对出现的，这些成对出现的定律就是对偶出现的，这些成对出现的定律就是对偶性质的反映，即对偶式。利用对偶式的性质的反映，即对偶式。利用对偶式的命题定律，可以扩大等价式的个数，也命题定律，可以扩大等价式的个数，也可减少证明的次数。可减少证明的次数。2022-3-2948l定义定义1.4.1 在给定的仅使用联结词在给定的仅使用联结词 、和和的命题公式的命题公式A中，若把中，若把和和互换，互换，F和和T互换而得到一个命题公式互换而得到一个命题公式A*，则称，则称A*为为A的对偶式。的对偶式。l显然，显然，A也是也是A

35、*的对偶式。可见的对偶式。可见A与与A*互互为对偶式。为对偶式。2022-3-2949l定理定理1.4.1(对偶定理对偶定理) 设设A和和A*互为对偶互为对偶式，式，P1，P2，Pn是出现是出现A和和A* 中的中的原子命题变元，则原子命题变元，则l A(P1，P2，Pn)A*( P1， P2， Pn)l A( P1， P2， Pn)A*(P1，P2，Pn)l表明，公式表明，公式A的否定等价于其命题变元的否定等价于其命题变元否定的对偶式；表明，命题变元否定否定的对偶式；表明，命题变元否定的公式等价于对偶式之否定。的公式等价于对偶式之否定。2022-3-2950l定理定理1.4.2 设设A和和B为

36、两个命题公式，若为两个命题公式，若AB则则A*B*。l有了等价式、代入规则、替换规则和对有了等价式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证偶定理，便可以得到更多的永真式，证明更多的等价式，使化简命题公式更为明更多的等价式，使化简命题公式更为方便。方便。2022-3-2951 .蕴涵式蕴涵式l定义定义1.4.2 设设A和和B是两个命题公式，若是两个命题公式，若AB是永真式，则称是永真式，则称A蕴涵蕴涵B，记作，记作AB，称，称AB为蕴涵式或永真条件式。为蕴涵式或永真条件式。l符号符号和和的区别与联系类似于的区别与联系类似于和和的关系。区别：的关系。区别：是逻辑联结词，属于是逻辑

37、联结词，属于对象语言中的符号，是公式中的符号；对象语言中的符号，是公式中的符号；而而不是联结词，属于元语言中的符号，不是联结词，属于元语言中的符号，表示两个公式之间的关系，不是两公式表示两个公式之间的关系，不是两公式中符号。联系：中符号。联系：AB成立，其充要条件成立，其充要条件AB是永真式。是永真式。2022-3-2952l蕴涵式有下列性质：蕴涵式有下列性质：l 自反性，即对任意公式自反性，即对任意公式A，有，有AA。l 传递性，即对任意公式传递性，即对任意公式A、B和和C，若，若AB，BC，则，则AC。l 对任意公式对任意公式A、B和和C，若，若AB，AC，则，则A(BC)。l 对任意公式

38、对任意公式A、B和和C，若，若AC，BC，则，则ABC。2022-3-2953l这些性质的正确性，请读者自己验证。这些性质的正确性，请读者自己验证。l下面给出等价式与蕴涵式之间的关系。下面给出等价式与蕴涵式之间的关系。l定理定理1.4.3 设设A和和B是两命题公式，是两命题公式，AB的充要条件是的充要条件是AB且且BA。2022-3-2954 .蕴涵式证明方法蕴涵式证明方法l除真值表外，还有两种方法：除真值表外，还有两种方法： 前件真导后件真方法前件真导后件真方法l设公式的前件为真，若能推导出后件也设公式的前件为真，若能推导出后件也为真，则条件式是永真式，故蕴涵式成为真，则条件式是永真式，故蕴

39、涵式成立。立。l因为欲证因为欲证AB，即证，即证AB是永真式。是永真式。对于对于AB，除在，除在A取真和取真和B取假时，取假时，AB为假外，余下为假外，余下AB皆为真。所以，皆为真。所以，若若AB的前件的前件A为真，由此可推出为真，由此可推出B亦亦为真，则为真，则AB是永真式，即是永真式，即AB。2022-3-2955 后件假导前件假方法后件假导前件假方法l设条件式后件为假，若能推导出前件也设条件式后件为假，若能推导出前件也为假，则条件式是永真式，即蕴涵式成为假，则条件式是永真式，即蕴涵式成立。立。l因为若因为若AB的后件的后件B取假，由此可推出取假，由此可推出A取假，即推证了：取假，即推证了

40、： BA。又因。又因ABB A，故，故AB成立。成立。2022-3-2956 . 联结词的扩充联结词的扩充l定义定义1.5.1 设设P和和Q是任两个原子命题，是任两个原子命题，l由合取非联结词由合取非联结词和和P，Q连接成连接成PQ，称它为称它为P和和Q的合取非式复合命题，读作的合取非式复合命题，读作“P合取非合取非Q”。PQ的真值由命题的真值由命题P和和Q的真值确定：当且仅当的真值确定：当且仅当P和和 Q均为均为时，时，PQ为为，否则，否则PQ为为。“合取非合取非”又常称为又常称为“与非与非”。2022-3-2957l由析取非联结词由析取非联结词和和P，Q连接成连接成PQ，称它为称它为P和和

41、Q的析取非式复合命题，读作的析取非式复合命题，读作“P析取非析取非Q”。PQ的真值由的真值由P和和Q的真的真值确定：当且仅当值确定：当且仅当P和和Q均为均为时，时，PQ为为，否则，否则PQ为为。“析取非析取非”又常又常称为称为“或非或非”。l由条件非联结词由条件非联结词 和和P，Q连接成连接成P Q，称它为称它为P和和Q的条件非式复合命题，读作的条件非式复合命题，读作“P条件非条件非Q”。P Q的真值由的真值由P和和Q的真的真值确定：当且仅当值确定：当且仅当P为为而而Q为为时，时，P Q为为；否则；否则P Q为为。2022-3-2958l由双条件非联结词由双条件非联结词 把把P，Q连接成连接成

42、P Q，称它为，称它为P和和Q的双条件非式复合命的双条件非式复合命题，读作题，读作“P双条件非双条件非Q”。P Q的真值的真值由由P和和 Q的真值确定：当且仅当的真值确定：当且仅当P和和Q的的真值不同时，真值不同时，P Q为为，否则，否则P Q为为。“双条件非双条件非”又常称为又常称为“异或异或”，也常，也常用符号用符号 表示之。表示之。l上面上面4个联结词构成的复合命题，其真值个联结词构成的复合命题，其真值表如下：表如下：2022-3-2959PQP QP QP QP Q0011000110011010111100002022-3-2960l由表可知，由表可知，P Q(P Q)l P Q(P

43、 Q)l P Q(PQ)l P Q(PQ)2022-3-2961 .与非、或非和异或的性质与非、或非和异或的性质l与非、或非以及异或在计算机科学中是与非、或非以及异或在计算机科学中是经常使用的经常使用的3个联结词，因此，掌握它们个联结词，因此，掌握它们的性质是十分必要的。令的性质是十分必要的。令P、Q和和R是原是原子命题变元。子命题变元。 与非的性质与非的性质l(a)PQQPl(b) PPPl(c) (PQ)(PQ)PQl(d) (PP)(QQ)PQ2022-3-2962 或非的性质或非的性质l(a) PQQPl(b) PPPl(c)(PQ)(PQ)PQl(d) (PP)(QQ)PQl从上述的

44、性质可知，联结词从上述的性质可知，联结词 、 和和 可分可分别用联结词别用联结词 或者或者 取代，读者可以自行取代，读者可以自行验证，验证， 和和 都不满足结合律。都不满足结合律。2022-3-2963 异或的性质异或的性质l(a)P QQ Pl(b) P (Q R)(P Q) Rl(c) P(Q R)(PQ) (PR)l(d) P PF，F PP，T PPl(e) 若若P QR，则，则Q RP，P PQ，且且P Q RF。2022-3-2964l以上所有性质，用真值表或命题定律都以上所有性质，用真值表或命题定律都是不难证明的。是不难证明的。l至此，已有了至此，已有了9个联结词，是否还需要扩个

45、联结词，是否还需要扩充呢？事实上，两上命题变无充呢？事实上，两上命题变无P和和Q，与，与9个联结词一共可构成个联结词一共可构成 类命题公式，类命题公式，如下表示之：如下表示之：2222022-3-2965PQF TP Q P Q P Q P Q P Q P Q000 100 110101010 101 100110100 110 010110110 111 001010所用的所用的联结词联结词序号序号1 234 56789102022-3-2966PQP Q P Q P Q P Q P Q P Q00101010011001011001011011101010所用联结所用联结词词序号序号111

46、213141516续表2022-3-2967l从列表可知，除命题常元从列表可知，除命题常元F，T及命题变及命题变元本身外，命题联结词一共有元本身外，命题联结词一共有9个就够了。个就够了。为了方便，可规定其优先级，由高到低为了方便，可规定其优先级，由高到低次序为次序为 ， ， ，等。等。2022-3-2968 .联结词功能完全组联结词功能完全组l已知有已知有9个联结词就够用了，能不能少呢？个联结词就够用了，能不能少呢？若能少，表明有些联结词的逻辑功能可若能少，表明有些联结词的逻辑功能可由其他联结词替代。事实上，也确实如由其他联结词替代。事实上，也确实如此，因为有下列等价式：此，因为有下列等价式：

47、lP Q(P Q)lP Q(P Q)lP Q(PQ)lP Q(PQ)l可见，扩充的可见，扩充的4个联结词个联结词 ， ， 和和 能能由原有由原有5个联结词分别替代之。个联结词分别替代之。2022-3-2969l又由命题定律：又由命题定律：lPQ( P Q) ( Q P)lPQP QlP Q( PQ)lP Q( PQ)l可知，原有可知，原有5个联结词个联结词 ， ， ，和和又又能由联结词组能由联结词组 ， 或或 ， 取代。那么，取代。那么，究竟最少用几个联结词？就是说，用最少究竟最少用几个联结词？就是说，用最少的几个联结词就能等价表示所有的命题公的几个联结词就能等价表示所有的命题公式。或者说，用

48、最少的几个联结词就能替式。或者说，用最少的几个联结词就能替代所有联结词的功能。这便是所要定义的代所有联结词的功能。这便是所要定义的联结词功能完全组。联结词功能完全组。2022-3-2970l定义定义1.5.2 称称G为联结词功能完全组，如为联结词功能完全组，如果果G满足下列两条件：由满足下列两条件：由G中联结词构中联结词构成的公式能等价表示任意命题公式；成的公式能等价表示任意命题公式；G 中的任一联结词不能用其余下联结词等价中的任一联结词不能用其余下联结词等价表示。表示。l可以证明，可以证明， ， ， ， ， ， ， ， 都是联结词功能完全组；而都是联结词功能完全组；而 ， ， ， ， ， ，

49、 都不是联都不是联结词功能完全组，但为了表示方便，仍经结词功能完全组，但为了表示方便，仍经常使用联结词组常使用联结词组 ， ， 。2022-3-2971.简单合取式与简单析取式简单合取式与简单析取式l定义定义1.6.1 在一公式中，仅由命题变元及在一公式中，仅由命题变元及其否定构成的合取式，其否定构成的合取式， 称该公式为简单合称该公式为简单合取式，其中每个命题变元或其否定，称为取式，其中每个命题变元或其否定，称为合取项。合取项。l定义定义1.6.2 在一公式中，仅由命题变元及在一公式中，仅由命题变元及其否定构成的析取式，其否定构成的析取式， 称该公式为简单析称该公式为简单析取式，其中每个命题

50、变元或其否定，称为取式，其中每个命题变元或其否定，称为析取项。析取项。2022-3-2972l例如，公式例如，公式P， Q，P Q和和 P Q P等都等都是简单合取式，而是简单合取式，而P，Q和和 P为相应的简为相应的简单合取式的合取项；公式单合取式的合取项；公式P， Q，P Q， P Q P等都是简单析取式，而等都是简单析取式，而P，Q和和 P为相应简单析取式的析取项。为相应简单析取式的析取项。l注意，一个命题变元或其否定既可以是注意，一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如例简单合取式，也可是简单析取式，如例中中P， Q等。等。2022-3-2973l定理定理1.6.1

51、 简单合取式为永假式的充要简单合取式为永假式的充要条件是：它同时含有某个命题变元及其条件是：它同时含有某个命题变元及其否定。否定。l定理定理1.6.2 简单析取式为永真式的充要简单析取式为永真式的充要条件是：它同时含有某个命题变元及其条件是：它同时含有某个命题变元及其否定。否定。2022-3-2974 .析取范式与合取范式析取范式与合取范式l定义定义1.6.3 一个命题公式一个命题公式A称为析取范式，称为析取范式，当且仅当当且仅当A可表为简单合取式的析取，即可表为简单合取式的析取，即AAi；其中；其中Ai为简单合取式，为简单合取式，i=1，2，n。l定义定义1.6.4 一个命题公式一个命题公式

52、A称为合取范式，称为合取范式，当且仅当当且仅当A可表为简单析取式的合取，即可表为简单析取式的合取，即AAi；其中；其中Ai为简单析取式，为简单析取式，1in。2022-3-2975l定理定理1.6.3 对于任何一命题公式，都存对于任何一命题公式，都存在与其等价的析取范式和合取范式。在与其等价的析取范式和合取范式。l求范式算法：求范式算法： 使用命题定律，消去公使用命题定律，消去公式中除式中除 、 和和 以外公式中出现的所有联以外公式中出现的所有联结词；结词；l 使用使用 ( P)P和德和德摩根律，将公式中摩根律，将公式中出现的联结词出现的联结词 都移到命题变元之前；都移到命题变元之前；l 利用

53、结合律、分配律等将公式化成析利用结合律、分配律等将公式化成析取范式或合取范式。取范式或合取范式。2022-3-2976 .范式的应用范式的应用l利用析取范式和合取范式可对公式进行利用析取范式和合取范式可对公式进行判定。判定。l定理定理1.6.4 公式公式A为永假式的充要条件是为永假式的充要条件是A 的析取范式中每个简单合取式至少包的析取范式中每个简单合取式至少包含一个命题变元及其否定。含一个命题变元及其否定。l定理定理1.6.5 公式公式A为永真式的充要条件是为永真式的充要条件是A 的合取范式中每个简单析取式至少包的合取范式中每个简单析取式至少包含一个命题变元及其否定。含一个命题变元及其否定。

54、2022-3-2977 .范式不唯一性范式不唯一性2022-3-2978l范式基本解决了公式的判定问题。但由范式基本解决了公式的判定问题。但由于范式不唯一性，对识别公式间是否等于范式不唯一性，对识别公式间是否等价带来一定困难，而公式的主范式解决价带来一定困难，而公式的主范式解决了这个问题。下面将分别讨论主范式中了这个问题。下面将分别讨论主范式中的主析取范式和主合取范式。的主析取范式和主合取范式。2022-3-2979 .主析取范式主析取范式 (1) 小项的概念和性质小项的概念和性质l定义定义1.7.1 在含有在含有n个命题变元的简单合个命题变元的简单合取式中，取式中， 若每个命题变元与其否定不

55、同若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现时存在，而二者之一出现一次且仅出现一次，则称该简单合取式为小项，或布一次，则称该简单合取式为小项，或布尔积。尔积。2022-3-2980l例如，两个命题变元例如，两个命题变元P和和Q，其构成的小，其构成的小项有项有P Q，PQ， P Q和和 PQ；而三；而三个命题变元个命题变元P、Q和和R，其构成的小项有，其构成的小项有P Q R，P QR，PQ R，PQR， P Q R ， P QR， PQ R， PQR。l可以证明，可以证明，n个命题变元共形成个命题变元共形成2n个小项。个小项。2022-3-2981l如果将命题变元按字典序排列

56、，并且把如果将命题变元按字典序排列，并且把命题变元与命题变元与1对应，命题变元的否定与对应，命题变元的否定与0对应，则可对对应，则可对2n个小项依二进制数编码，个小项依二进制数编码，记为记为mi，其下标，其下标i是由二进制数转化的十是由二进制数转化的十进制数。用这种编码所求得进制数。用这种编码所求得2n个小项的个小项的真值表，可明显地反映出小项的性质。真值表，可明显地反映出小项的性质。l表表1.7.1和表和表1.7.2分别给出了分别给出了2个命题变个命题变元元P和和Q、3个命题变元个命题变元P、Q和和R的小项的小项真值表。真值表。2022-3-2982 表表 1.7.1 两两个个命命题题变变元

57、元的的小小项项真真值值表表m(二二) m00 m01 m10 m11P Q P Q P Q P Q P Q0 0 1 0 0 00 1 0 1 0 01 0 0 0 1 01 1 0 0 0 1m(+) m0 m1 m2 m32022-3-2983 表表 1.7.2 3 个命题变元的小项真值表个命题变元的小项真值表m(二二)m000m001m010m011P Q R P Q R P Q R P Q R P Q R0 0 010000 0 101000 1 000100 1 100011 0 000001 0 100001 1 000001 1 10000m(+)m0m1m2m32022-3-2

58、984 续表续表m(二二)m100m101m110m111P Q RP Q RP Q RP Q RP Q R0 0 000000 0 100000 1 000000 1 100001 0 010001 0 101001 1 000101 1 10001m(+)m4m5m6m72022-3-2985l从表从表1.7.1，表，表1.7.2可看出，小项有如下可看出，小项有如下性质：性质：l(a)没有两个小项是等价的，即是说各没有两个小项是等价的，即是说各小项的真值表都是不同的；小项的真值表都是不同的；l(b)任意两个不同的小项的合取式是永假任意两个不同的小项的合取式是永假的：的：mimj，ij。l(

59、c)所有小项之析取为永真：所有小项之析取为永真： mi。l(d)每个小项只有一个解释为真，且其真每个小项只有一个解释为真，且其真值值1位于主对角线上。位于主对角线上。ni 12022-3-2986 (2) 主析取范式定义与存在定理主析取范式定义与存在定理l定义定义1.7.2 在给定公式的析取范式中，在给定公式的析取范式中，若其简单合取式都是小项，若其简单合取式都是小项， 则称该范式则称该范式为主析取范式。为主析取范式。l定理定理1.7.1 任意含任意含n个命题变元的非永假个命题变元的非永假命题公式命题公式A 都存在与其等价的主析取范都存在与其等价的主析取范式。式。2022-3-2987 (3)

60、 主析取范式的求法主析取范式的求法l主析取范式求法有两种：真值表法和公主析取范式求法有两种：真值表法和公式化归法。定理式化归法。定理1.7.1的证明已给出了用的证明已给出了用真值表求主析取范式的方法，而公式化真值表求主析取范式的方法，而公式化归法给出如下：归法给出如下：l(a)把给定公式化成析取范式；把给定公式化成析取范式；l(b) 删除析取范式中所有为永假的简单删除析取范式中所有为永假的简单合取式；合取式；2022-3-2988l(c) 用等幂律化简简单合取式中同一命用等幂律化简简单合取式中同一命题变元的重复出现为一次出现，如题变元的重复出现为一次出现，如PPP。l(d) 用同一律补进简单合