《离散数学》命题逻辑.ppt

《《离散数学》命题逻辑.ppt》由会员分享，可在线阅读，更多相关《《离散数学》命题逻辑.ppt（121页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1 1章章 命题逻辑命题逻辑 命题逻辑 逻辑是研究推理的科学。数理逻辑是用数学方法研究推理的形式结构和推理规律的数学学科。由于它使用一套符号来表达各种推理的逻辑关系，因此数理逻辑又称为符号逻辑。从广义上讲，数理逻辑包括集合论、模型论、递归论、证明论和命题演算、谓词演算，但本书只研究两个演算：命题演算和谓词演算两个演算。数理逻辑研究的中心问题是推理，而推理的前提与结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。数理逻辑称之为命题。第第1 1章章命命题题逻逻辑辑一、命题一、命题定义定义1.1 能判断真假的陈述句叫做能判断真假的陈述句叫做命题命题。该定义有两层含义：该定义有两

2、层含义：(1)命题是陈述句。其他的语句，如疑问句、命题是陈述句。其他的语句，如疑问句、祈使句、感叹句均不是命题；祈使句、感叹句均不是命题；(2)这个陈述句对事物的判断是否符合客观事这个陈述句对事物的判断是否符合客观事实是可以给出结论的：不是实是可以给出结论的：不是真真（符合客观事实）（符合客观事实）就是就是假假（不符合客观事实），不能不真也不假，（不符合客观事实），不能不真也不假，也不能既真又假，所以又称二值逻辑。也不能既真又假，所以又称二值逻辑。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词二、命题的真值二、命题的真值 命题所表示的判断结果称

3、为命题所表示的判断结果称为命题的真值命题的真值。真值只取两个值：真（判断真值只取两个值：真（判断与事实相符）与事实相符）或假（判断或假（判断与事实不符）与事实不符）。通常用通常用1（或字母（或字母T）表示真，用）表示真，用0（或字母（或字母F）表示假。）表示假。真命题真命题：真值为真的命题。：真值为真的命题。假命题假命题：真值为假的命题。：真值为假的命题。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词例例6.1.16.1.1 判断下列语句是否为命题，并指出其真值。判断下列语句是否为命题，并指出其真值。（1 1）北京是中国的首都。）北京是中国的首

4、都。（2 2）5 5可以被可以被2 2整除。整除。（3 3）2+2=52+2=5。（4 4）请勿吸烟。）请勿吸烟。祈使句祈使句（5 5）乌鸦是黑色的吗？乌鸦是黑色的吗？疑问句疑问句（6 6）这个小男孩多勇敢啊！这个小男孩多勇敢啊！感叹句感叹句（7 7）地球外的星球上存在生物地球外的星球上存在生物。（8 8）我正在说谎。）我正在说谎。悖论悖论注意：注意：注意：注意：一个语句本身是否能分辨真假与我们是否知道它一个语句本身是否能分辨真假与我们是否知道它的真假是两回事。也就是说，对于一个句子，有时我们的真假是两回事。也就是说，对于一个句子，有时我们可能无法判定它的真假，但它本身却是有真假的，那么可能无

5、法判定它的真假，但它本身却是有真假的，那么这个语句是命题，否则就不是命题。这个语句是命题，否则就不是命题。悖论不是命题。悖论不是命题。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词判断一个句子是否为命题1、是否为陈述句2、真值是否唯一-X+y5-1+101=110-真值是否唯一与我们是否知道它的真值是两回事三、命题的分类三、命题的分类原子命题原子命题（Automic Proposition）：不能再不能再分解为更简单的陈述句的命题；也称简单命题。分解为更简单的陈述句的命题；也称简单命题。复合命题复合命题（Compound Proposition

6、）：由若由若干简单命题用联结词联结成的命题。干简单命题用联结词联结成的命题。例如：例如：“雪是白的雪是白的”是原子命题；是原子命题；“昨天下雨，而且打雷昨天下雨，而且打雷”，“如果明天如果明天天晴我就去打球或者游泳天晴我就去打球或者游泳”都是复合命题。都是复合命题。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词四、命题的表示四、命题的表示 引进数学符号来表示命题。引进数学符号来表示命题。常常用用大大写写英英文文字字母母A,B,P,Q或或带带下下标标的的字字母母P1,P2,P3,或或数数字字(1),2,等等表表示示命命题题，称称之为之为命题标识符

7、命题标识符。例如：例如：P：罗纳尔多是球星。：罗纳尔多是球星。Q：5是负数。是负数。P3：明天天气晴。明天天气晴。(2)：太阳从西方升起。：太阳从西方升起。皆皆为为符符号号化化的的命命题题，其其真真值值依依次次为为1、0、1或或0、0。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词v 命命题题标标识识符符有有命命题题常常量量、命命题题变变元元和和原原子子变变元之分。元之分。命题常元命题常元：真值确定的命题标识符。：真值确定的命题标识符。命命题题变变元元：真真值值不不确确定定，仅仅表表示示任任意意命命题题的位置标志。的位置标志。原原子子变变元元：

8、当当命命题题变变元元表表示示原原子子命命题题时时，该变元称为原子变元该变元称为原子变元v 如如果果命命题题符符号号P P代代表表命命题题常常元元则则意意味味它它是是某某个个具具体体命命题题的的符符号号化化，如如果果P P代代表表命命题题变变元元则则意意味味着它可指代任何具体命题。着它可指代任何具体命题。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词一、否定联结词“”（或“”）否定联结词是一元联结词。相当于日常用语中的“非”，“不”，“无”，“没有”等。设P为一命题，P的否定是一个新的复合命题,称为P的否定式，记作“P”，读作“非P”。P为真当且

9、仅当P为假。P P 0 1 1 01.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词例例6.1.2.P:天津是一个城市天津是一个城市.Q:3是偶数是偶数.于是于是:P:天津不是一个城市天津不是一个城市.Q:3不是偶数不是偶数.例例6.1.3.P:苏州处处清洁苏州处处清洁.Q:这些都是男同学这些都是男同学.P:苏苏州州不不处处处处清清洁洁 (注注意意,不不是是处处处处不不清清洁洁).Q:这些不都是男同学这些不都是男同学.1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词二、合取二、合取联结联结词词“”合取

10、词是二元联结词。相当于自然语言中的合取词是二元联结词。相当于自然语言中的“与与”、“并且并且”、“而且而且”、“也也”等。等。设设P,Q为二命题，复合命题为二命题，复合命题“P与与Q”记作记作PQ。PQ为真当且仅当为真当且仅当P P和和Q Q同时为真。同时为真。P Q P Q 0 0 0 0 1 0 1 0 0 1 1 11.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词例例6.1.4.将下列命题符号化将下列命题符号化.(1)李平既聪明又用功李平既聪明又用功.(2)李平虽然聪明李平虽然聪明,但不用功但不用功.(3)李平不但聪明李平不但聪明,而且用功

11、而且用功.(4)李平不是不聪明李平不是不聪明,而是不用功而是不用功.解解:设设 P:李平聪明李平聪明.Q:李平用功李平用功.则则 (1)PQ (2)PQ (3)PQ (4)(P)Q 注注意意：不不要要见见到到“与与”或或“和和”就就使使用用联联结结词词！例如例如:(1)李敏和李华是姐妹。李敏和李华是姐妹。(2)李敏和张华是朋友。李敏和张华是朋友。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词例例6.1.5.试生成下列命题的合取试生成下列命题的合取.(

12、1)P:我们在我们在6-503.Q:今天是星期二今天是星期二.(2)S：李平在吃饭李平在吃饭.R：张明在吃饭张明在吃饭.解解:(1)PQ:我们在我们在6-503且且今天是星期二今天是星期二.(2)SR:李平与张明在吃饭李平与张明在吃饭.三、析取联结词三、析取联结词“”析取词是二元联结词。相当于析取词是二元联结词。相当于自然语言中的自然语言中的“或或”、“要么要么要要么么”等。等。设设P,Q为为二二命命题题，复复合合命命题题“P或或Q”，记记作作PQ。PQ为为真真当当且且仅当仅当 P与与Q中至少有一个为真。中至少有一个为真。P Q P Q 0 0 0 0 1 1 1 0 1 1 1 1 在在现现

13、代代汉汉语语中中，“或或”有有“可可可可兼兼兼兼或或或或”和和“排排排排斥或斥或斥或斥或”之分。这里只是之分。这里只是“可兼或可兼或可兼或可兼或”。例例6.1.6（1）小王爱打球或爱跑步。）小王爱打球或爱跑步。（可兼或）可兼或）可兼或）可兼或）设设P：小王爱打球。：小王爱打球。Q：小王爱跑步。：小王爱跑步。则上述命题可符号化为：则上述命题可符号化为：P Q1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词（2）林芳学过英语或法语。）林芳学过英语或法语。（

14、可兼或）可兼或）可兼或）可兼或）设设P：林芳学过英语。：林芳学过英语。Q：林芳学过法语。：林芳学过法语。则上述命题可符号化为：则上述命题可符号化为：P Q（3）派小王或小李中的一人去开会。（）派小王或小李中的一人去开会。（排斥或排斥或排斥或排斥或）设设P：派小王去开会。：派小王去开会。Q：派小李去开会。：派小李去开会。则上述命题可符号化为：则上述命题可符号化为：(PQ)(PQ)四、蕴含联结词四、蕴含联结词“”蕴含词是二元联结词。相当于自然语言中的蕴含词是二元联结词。相当于自然语言中的“若若则则”、“如果如果就就”、“只有只有才才”。设设P,Q为为二二命命题题,复复合合命命题题“若若P则则Q”记

15、记作作PQ。并称。并称P为前件，为前件，Q为后件。为后件。PQ为假当且仅当为假当且仅当P为真且为真且Q为假。为假。P QP Q 0 0 1 0 1 1 1 0 0 1 1 11.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词例例6.1.76.1.7 将下列命题符号化。将下列命题符号化。1 1）天不下雨，则草木枯黄。）天不下雨，则草木枯黄。P P：天下雨。：天下雨。Q Q：草木枯黄。：草木枯黄。则原命题可表示为：则原命题可表示为：PQPQ。2 2）如果小明学日语，小华学英语，则小芳）如果小明学日语，小华学英语，则小芳学德语。学德语。P P：小明学日语

16、：小明学日语.Q.Q：小华学英语：小华学英语.R.R：小芳学：小芳学德语德语.则原命题可表示为：则原命题可表示为：(PQ)R(PQ)R3 3）只要不下雨，我就骑自行车上班。）只要不下雨，我就骑自行车上班。P P：天下雨。：天下雨。Q Q：我骑自行车上班。：我骑自行车上班。则原命题可表示为：则原命题可表示为：PQPQ。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词4 4）只有不下雨，我才骑自行车上班。）只有不下雨，我才骑自行车上班。P P：天下雨。：天下雨。Q Q：我骑自行车上班。：我骑自行车上班。则原命题可表示为：则原命题可表示为：Q Q P

17、P。注意注意:(1)与与自自然然语语言言的的不不同同：前前件件与与后后件件可可以以没没有有任任何内在联系！何内在联系！(2)在数学中，在数学中，“若若P则则Q”往往表示前件往往表示前件P为真，为真，则后件则后件Q为真的推理关系为真的推理关系.但数理逻辑中，当前但数理逻辑中，当前件件P为假时，为假时，PQ的真值为真。的真值为真。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词“如果如果 p p，则，则 q q”的不同表述法很多：的不同表述法很多：若若 p p，就，就 q q 只要只要 p p，就，就 q q p p 仅当仅当 q q 只有只有 q

18、q 才才 p p 除非除非 q,q,才才 p p 除非除非 q,q,否则非否则非 p p，1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词 例：设 p:天冷，q:小王穿羽绒服，将下列命题符号化 (1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.注意：注意：pq 与与 pq 等值（真值相同）等值（真值相同）pqpqpqpqqp qp

19、qpqp1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词五、等价联结词五、等价联结词“”等价联结词等价联结词是二元联结词。是二元联结词。相当于自然语言中的相当于自然语言中的“等价等价”、“当且仅当当且仅当”、“充要条件充要条件”等，等，真值表如右图。真值表如右图。设设P,Q为二命题，复合命题为二命题，复合命题“P当且仅当且仅当当Q”记作记作PQ。PQ为为真真当当且且仅仅当当P，Q真真值相同。值相同。P Q PQ 0 0 1 0 1 0 1 0 0 1 1 11.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词

20、词词词注：注：（1）P仅当仅当Q 可译为可译为PQ P当当Q 可译为可译为QP P当且仅当当且仅当Q 译为译为PQ （2）命题命题PQ所表达的逻辑关系是所表达的逻辑关系是,P与与Q互为互为充分必要条件充分必要条件,相当于相当于(PQ)(QP).双条件联结词连接的两个命题之间可以没有因双条件联结词连接的两个命题之间可以没有因果关系。果关系。例例6.1.8 分析下列命题的真值分析下列命题的真值.(1)2+2=4 当且仅当当且仅当3是奇数是奇数.(PQ)P：2+2=4.Q：3是奇数是奇数.(2)2+2=4 当且仅当当且仅当3不是奇数不是奇数.(PQ)(3)2+24 当且仅当当且仅当3是奇数是奇数.(

21、PQ)(4)2+24 当且仅当当且仅当3不是奇数不是奇数.(PQ)1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词5种联结词类似5种运算符，称之为逻辑运算符，有运算的优先级顺序：-联结词的优先顺序为：,;-如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;-若遇有括号时，应该先进行括号中的运算。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词一、概念一、概念定义定义1.3 1.3 命题公式命题公式按下列规则生成按下列规则生成：（1 1）单单个个命命题题常常项项或或变变项项p,q,rp,q,r

22、,.,0,1,.,0,1是是命命题题的的公公式；式；（2 2）如果）如果是命题公式，则是命题公式，则 也是命题公式；也是命题公式；（3 3）如如果果和和是是命命题题公公式式，则则，均是命题公式；均是命题公式；（4 4）只有有限次地利用（）只有有限次地利用（1 1）（3 3）形成的符号串）形成的符号串才是命题公式。才是命题公式。例如例如：(P(P Q)Q)，P P(P(P Q)Q)等都等都是是命题公式，而命题公式，而CPCPQQ，RPRP等不是等不是命题公式。命题公式。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类注注:(1)(1)命命题题公公式式也也称称为为合

23、合式式公公式式，由由命命题题常常项项、命命题题变变项、联结词和括弧组成项、联结词和括弧组成。(2)(2)如果把公式中的命题变元代以原子命题或复合命题，则该公式便是一个复合命题。因此，对复合命题的研究可化为对命题公式的研究。命题公式命题公式一般不是命题一般不是命题,仅当公式中的命题变元用仅当公式中的命题变元用确定的命题代入时，才得到一个命题。其真值依赖于代确定的命题代入时，才得到一个命题。其真值依赖于代换变元的那些命题的真值。换变元的那些命题的真值。日常生活中的推理问题是用自然语言描述的，因此日常生活中的推理问题是用自然语言描述的，因此要进行推理演算必须先把自然语言要进行推理演算必须先把自然语言

24、符号化符号化（或形式化）（或形式化）成逻辑语言，即命题公式。然后再根据逻辑演算规律进成逻辑语言，即命题公式。然后再根据逻辑演算规律进行推理演算。行推理演算。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类二、命题符号化(1)分析出各简单命题分析出各简单命题,将它们符号化将它们符号化;(2)使用合适的联结词使用合适的联结词,把简单命题逐个的联结起把简单命题逐个的联结起来来,组成复合命题的符号化表示组成复合命题的符号化表示.例例6.3.26.3.2 将下列用自然语言描述的命题符号化。将下列用自然语言描述的命题符号化。（1 1）我和他既是弟兄又是同学。）我和他既是弟兄

25、又是同学。解 令P：我和他是弟兄；Q：我和他是同学，则该语句可符号化为PQ。（2 2）我和你之间至少有一个要去海南岛。）我和你之间至少有一个要去海南岛。解 令P：我去海南岛；Q：你去海南岛，则该语句可符号化为PQ。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类（3 3）如果他没来见你，那么他或者是生病了，如果他没来见你，那么他或者是生病了，或者是不在本地。或者是不在本地。解 令P：他来见你；Q：他生病；R：他在本地，则该语句可符号化为P(QR)。（4 4）n n是偶数当且仅当它能被是偶数当且仅当它能被2 2整除。整除。解 令P：n 是偶数；Q：n 能被2 整除

26、，则该语句可符号化为PQ。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类三、公式的解释或赋值三、公式的解释或赋值 设设P1,P2,Pn是是出出现现在在公公式式G中中的的全全部部的的命命题题变变元元,指指定定P1,P2,Pn的的一一组组真真值值，则则称称这这组组真值为真值为G的一个的一个赋值赋值或或解释，记作解释，记作I。公式公式G在在I下的真值记作下的真值记作TI(G)。若若指指定定的的一一组组值值使使A的的真真值值为为真真(假假),称称这这组组值为值为A的的成真成真(假假)赋值。赋值。例例如如:对对公公式式(PQ)R，赋赋值值011(即即令令P=0，Q=1，

27、R=1)为为(PQ)R的成真赋值。的成真赋值。赋值赋值011也可记作也可记作P,Q,R。含含有有n个个命命题题变变元元的的公公式式共共有有2n组组不不同同的的赋赋值。值。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类四、真值表四、真值表 将将命命题题公公式式G在在其其所所有有解解释释下下所所取取的的真真值值列成一个表列成一个表,称做命题公式称做命题公式G 的的真值表真值表。为方便构造真值表，特约定如下：为方便构造真值表，特约定如下：命题变元按字典序排列。命题变元按字典序排列。对对每每个个指指派派，以以二二进进制制数数从从小小到到大大或或从从大到小顺序列出。大到

28、小顺序列出。若若公公式式较较复复杂杂，可可先先列列出出各各子子公公式式的的真真值值(若若有有括括号号，则则应应从从里里层层向向外外层层展展开开)，最最后后列出所求公式的真值。列出所求公式的真值。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类P Q RP Q RQ Q R RP P(Q(Q R)R)(P(P(Q(Q R R)0 0 00 0 00 0 10 0 10 1 00 1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1 10 01 11 11 10 01 11 11 11 11 11 11 10 01

29、11 11 10 00 00 00 01 10 00 00 0例例6.3.1 利用真值表求命题公式利用真值表求命题公式(P(Q(P(Q R)R)的成真指派和成假指派。的成真指派和成假指派。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类五、命题公式的分类五、命题公式的分类重言式重言式/永真式永真式：若若G G在在所有解释下都是真的，所有解释下都是真的，则称则称G G为为重言式或永真式。重言式或永真式。矛盾式矛盾式/永假式永假式：G G在在所有解释下都是假的，则所有解释下都是假的，则称称G G为为称为矛盾式或永假式。称为矛盾式或永假式。可满足式可满足式：若若G G

30、不是恒假的。不是恒假的。几点说明几点说明 1 1）G G是是可可满满足足式式的的等等价价定定义义是是：G G至至少少存存在在一一个成真指派。个成真指派。2 2）重言式一定是可满足式，但反之不真。）重言式一定是可满足式，但反之不真。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类 3 3）如何利用好真值表来判断公式的类型：）如何利用好真值表来判断公式的类型：若若真真值值表表最最后后一一列列全全为为1 1，则则公公式式为为重言式；重言式；若若真真值值表表最最后后一一列列全全为为0 0，则则公公式式为为矛盾式；矛盾式；若若真真值值表表最最后后一一列列中中至至少少有有一

31、一个个1 1，则公式为可满足式。则公式为可满足式。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类例例6.3.26.3.2 判断下列公式的类型。判断下列公式的类型。(1)(P(1)(PQ)Q)Q Q解解 令令=(P=(P Q)Q)Q Q P QP QP P Q Q 0 00 00 10 11 01 01 11 10 00 00 01 11 11 11 11 11.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类(2)(Q(2)(QP)P)(P PQ)Q)解解 令令=(Q=(QP)P)(P P Q)Q)P QP QQP P P Q Q

32、0 00 00 10 11 01 01 11 11 10 01 11 10 01 10 00 00 00 00 00 01.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类(3)(P(3)(P Q)Q)(P PQ QR)R)解解 令令=(P=(P Q)Q)(P P Q Q R)R)P Q RP Q RP Q P Q R 0 0 00 0 00 0 10 0 10 1 00 1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1 11 11 10 00 01 11 11 11 10 00 00 01 10 00 00 0

33、0 00 00 01 11 10 00 00 00 01.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类一、公式等值（等价）一、公式等值（等价）问题：问题：是否存在两个命题公式是否存在两个命题公式G G和和H H，在任意，在任意解释下它们的真值都相同？解释下它们的真值都相同？若存在，怎样用已有的概念描述上述现象若存在，怎样用已有的概念描述上述现象？解答：存在，比如解答：存在，比如n=2n=2的命题公式的命题公式,P,PQ与(PQ)在任意解释下均有系统的真值。描述：GH是重言式 给这种现象引入一个概念：数学上用相等，等价，这里用等价、等值。1.31.3等等值值演演算

34、算定义定义1.101.10 设设G G，H H是两个命题公式，若是两个命题公式，若G GH H是重言式，是重言式，则称则称G G与与H H等价（等值），记作等价（等值），记作G GH H。-G GH H当且仅当当且仅当G GH H为重言式。为重言式。-与与是两个完全不同的符号。是两个完全不同的符号。不是命题联结词，而是公式间的关系符号，不是命题联结词，而是公式间的关系符号，不表示一个公式，即不代表命题，它不表示一个公式，即不代表命题，它表示公式表示公式与公式与公式有等价关系，有等价关系，是命题联结词，是命题联结词，是一个公式，表示是一个公式，表示某个命题。某个命题。公式之间的等价关系的特点：-

35、自反的-对称的-传递的1.31.3等等值值演演算算二、公式等价（等值）的判定方法（二、公式等价（等值）的判定方法（1)1)判断两个公式判断两个公式与与是否等值，用真值表法判是否等值，用真值表法判断断是否为重言式。是否为重言式。例例1.71.7 判断判断(P(P Q)Q)与与 P PQ Q这两个命题公式这两个命题公式是否等值。是否等值。P QP Q(P(P Q)Q)P PQ Q(P(P Q)Q)(P PQ)Q)0 00 00 10 11 01 01 11 11 10 00 00 01 10 00 00 01 11 11 11 1这一列可不要1.31.3等等值值演演算算三、公式等价的判定方法（三、

36、公式等价的判定方法（2)2)根据已知的等价公式根据已知的等价公式,推演出另外一些等价推演出另外一些等价公式的过程称为公式的过程称为等值演算等值演算.常用的等价公式：常用的等价公式：（1 1）双重否定律：双重否定律：()（2-32-3）等幂律：）等幂律：，（4-54-5）交换律：）交换律：，（6-76-7）结合律）结合律 ()()，()()1.31.3等等值值演演算算（8-98-9）分配律）分配律 ()()()（对对 的分配律）的分配律）()()()（对对 的分配律）的分配律）（10-1110-11）德摩根律）德摩根律 ()，()（12-1312-13）吸收律）吸收律 ()，()（14-1514

37、-15）零律：）零律：1 11 1，0 00 0（16-1716-17）同一律：）同一律：0 0，1 1（1818）排中律：）排中律：1 1（1919）矛盾律：）矛盾律：0 01.31.3等等值值演演算算（2020）蕴含等值式）蕴含等值式 (21)(21)等价（双条件）等值式等价（双条件）等值式 ()()，()()（2222）假言易位）假言易位 （2323）等价否定等值式）等价否定等值式 （2424）归谬论）归谬论 ()()1.31.3等等值值演演算算等值演算中的置换规则等值演算中的置换规则 置换：置换：用一个命题公式代换另一个命题公式中的一个子公式。定理1.1（置换定理）设(A)是含命题公式

38、A的命题公式，(B)是用命题公式B置换了(A)中的A之后的得到的命题公式，如果AB，则(A)(B)。1.31.3等等值值演演算算例例6.4.16.4.1 用等值演算法证明用等值演算法证明 (P(P Q)RQ)R(PR)(PR)(QR)(QR)。证明证明(P(P Q)Q)R R (P(P Q)Q)R R （蕴含等值式）（蕴含等值式）(P PQ)Q)R R （德摩根律）（德摩根律）(P P R)R)(Q Q R)R)（分配律）（分配律）(P(PR)R)(Q Q R)R)（蕴含等值式）（蕴含等值式）(P(PR)R)(Q(QR)R)（蕴含等值式）（蕴含等值式）1.31.3等等值值演演算算例例6.4.2

39、6.4.2 用等值演算法判断下列公式的类型。用等值演算法判断下列公式的类型。（1 1）(PQ)(PQ)P)QP)Q解解 (P(PQ)Q)P)P)Q Q (P P Q)Q)P)P)Q Q(P P Q)Q)P)P)Q Q (P P Q)Q)P)P)Q Q(P(PQ)Q)P)P)Q Q (P(PP)P)(Q QP)P)Q Q(1(1(Q QP)P)Q Q (Q Q Q)Q)P P1 1P P 1 1 因此该公式是重言式。因此该公式是重言式。1.31.3等等值值演演算算（2 2）(P(P(P(P Q)Q)R R 解解 (P(P(P(P Q)Q)R R (P P P P Q)Q)R R (P(PP PQ

40、)Q)R R 0 0 R R 0 0因此该公式是矛盾式。因此该公式是矛盾式。1.31.3等等值值演演算算（3 3）P P(P(P Q)Q)P)Q)P)Q)解解 P P(P(P Q)Q)P)P)Q)Q)P P(P(P Q)Q)P)P)Q)Q)P P(P(PP)P)(Q(QP)P)Q)Q)P P(0(0(Q(QP)P)Q)Q)P P(Q Q P P Q)Q)P P 1 1P P 从最后结果可以看出该公式既不是重言从最后结果可以看出该公式既不是重言式，也不是矛盾式，而是可满足式。式，也不是矛盾式，而是可满足式。1.31.3等等值值演演算算 例例6.4.36.4.3 设有设有A A，B B，C C，D

41、 D四人做百米竞赛，四人做百米竞赛，观众甲，乙，丙分别对比赛的名次进行了预测：观众甲，乙，丙分别对比赛的名次进行了预测：甲说甲说C C第一，第一，B B第二；第二；乙说乙说C C第二，第二，D D第三；第三；丙说丙说A A第二，第二，D D第四；第四；比赛结束后发现甲，乙，丙每人报告的比赛结束后发现甲，乙，丙每人报告的情况都是各对一半，试问实际名次如何（无并情况都是各对一半，试问实际名次如何（无并列者）？列者）？1.31.3等等值值演演算算 解解 设设P Pi i，Q Qi i，R Ri i，S Si i分别表示分别表示A A，B B，C C，D D是第是第i i（i=1,2,3,4i=1,2

42、,3,4）名，由于甲，乙，丙每人报告的情况）名，由于甲，乙，丙每人报告的情况都各对一半，故有下面三个等值式：都各对一半，故有下面三个等值式：(R R1 1Q Q2 2)(R R1 1 Q Q2 2)1 1 (R (R2 2S S3 3)(R R2 2 S S3 3)1 1 (P (P2 2S S4 4)(P P2 2 S S4 4)1 1因为重言式的合取仍为重言式，所以因为重言式的合取仍为重言式，所以 1 1。即即 1 1(R(R1 1Q Q2 2)(R R1 1 Q Q2 2)(R(R2 2S S3 3)(R R2 2 S S3 3)(R(R1 1Q Q2 2 R R2 2S S3 3)(R

43、(R1 1Q Q2 2R R2 2 S S3 3)(R R1 1 Q Q2 2 R R2 2S S3 3)(R R1 1 Q Q2 2R R2 2 S S3 3)1.31.3等等值值演演算算由于由于C C不能既第一又第二，不能既第一又第二，B B和和C C不能并列第二，不能并列第二，所以所以 R R1 1Q Q2 2 R R2 2S S3 30 0 R R1 1 Q Q2 2 R R2 2S S3 30 0于是得于是得 (R(R1 1Q Q2 2R R2 2 S S3 3)(R R1 1 Q Q2 2R R2 2 S S3 3)1 1再将再将与与合取得合取得 1 1，即，即 1 1(P(P2

44、2S S4 4)(P P2 2 S S4 4)(R(R1 1Q Q2 2R R2 2 S S3 3)(R R1 1 Q Q2 2R R2 2 S S3 3)(P(P2 2S S4 4 R R1 1Q Q2 2R R2 2 S S3 3)(P(P2 2S S4 4R R1 1 Q Q2 2 R R2 2 S S3 3)(P P2 2 S S4 4 R R1 1Q Q2 2R R2 2 S S3 3)(P P2 2 S S4 4R R1 1 Q Q2 2R R2 2 S S3 3)1.31.3等等值值演演算算由于由于A A，B B不能同时第二，不能同时第二，D D不能第三又第四，所以不能第三又第四

45、，所以 P P2 2S S4 4R R1 1 Q Q2 2R R2 2 S S3 30 0 P P2 2 S S4 4 R R1 1Q Q2 2R R2 2 S S3 30 0 P P2 2 S S4 4R R1 1 Q Q2 2R R2 2 S S3 30 0于是可得于是可得 P P2 2S S4 4 R R1 1Q Q2 2R R2 2 S S3 31 1因此因此C C第一，第一，A A第二，第二，D D第三，第三，B B第四。第四。1.31.3等等值值演演算算四、联结词全功能集 前面已经引入了五中联结词，逻辑设计中还常用到其它的一些联结词：-异或（排斥或）联结词-与非联结词-或非联结词在

46、一个形式系统中引入多少联结词好？-自然系统中越多越好，应用方便-公理系统中越少越好，研究方便一个联结词的集合应该满足什么条件？1.41.4联联结结词词全全功功能能集集对于命题公式，我们关注的是它的真值情况。N个命题变元的命题公式，每个变元有两种赋值情况，共有2N中赋值情况。而每种赋值，又有两种结果，共有 种不同的赋值、取值情况。一个好的方法是，每种赋值、取值情况用一个联结词表示。可以用函数的观点来研究命题公式的变元赋值与最终命题公式的取值之间的关系1.41.4联联结结词词全全功功能能集集定义定义 称定义域为称定义域为000,001,111，值域，值域为为0,1的的函函数数是是n元元真真值值函函

47、数数，定定义义域域中中的的元元素素是长为是长为n的的0,1串串.常用常用F:0,1n0,1 表示表示F是是n元真值函数元真值函数.共有共有 个个n元真值函数元真值函数.例如例如 F:0,120,1，且，且F(00)=F(01)=F(11)=0，F(01)=1，则，则F为一个确定的为一个确定的2元真值函数元真值函数.1.41.4联联结结词词全全功功能能集集对于任何一个含对于任何一个含n个命题变项的命题公式个命题变项的命题公式A，都存在都存在惟一的一个惟一的一个n元真值函数元真值函数F为为A的真值表的真值表.等值的公式对应的真值函数相同等值的公式对应的真值函数相同.下表给出所有下表给出所有2元真值

48、函数对应的真值表元真值函数对应的真值表,每一个含每一个含2 2个命题变项的公式的真值表都可以在下表中找到个命题变项的公式的真值表都可以在下表中找到.例如：例如：pq,p q,(p q)(pq)q)等等都对应都对应表中的表中的1.41.4联联结结词词全全功功能能集集2元真值函数对应的真值表元真值函数对应的真值表p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 p q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0

49、 1 0 1 0 1 0 1 1.41.4联联结结词词全全功功能能集集p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 p q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1.41.4联联结结词词全全功功能能集集 0 pq的非 p qp的非 q q 异或 q qp p pq 1联结词的全功能集联结词的全功能集 定义定义 在一个联结词的集合中，如果一个联结词可在一个联结词的集合中，

50、如果一个联结词可由集合中的其他联结词定义，则称此联结词为由集合中的其他联结词定义，则称此联结词为冗余冗余的联结词的联结词，否则称为，否则称为独立的联结词独立的联结词.例如例如,在联结词集在联结词集 ,中，由于中，由于 p pq qp p q q,所以，所以，为冗余的联结词为冗余的联结词;类似地，类似地，也是冗余的也是冗余的联结词联结词.又在又在 ,中，由于中，由于 p p q q(p pq q)，所以，所以，是冗余的联结词是冗余的联结词.类似地，类似地，也是冗余的联也是冗余的联结词结词.1.41.4联联结结词词全全功功能能集集联结词的全功能集联结词的全功能集(续续)定定义义 设设S S是是一一