《离散数学》命题逻辑省名师优质课赛课获奖课件市赛课一等奖课件.ppt

第第1 1章章 命题逻辑命题逻辑 命题逻辑第1页 逻辑是研究推理科学。数理逻辑是用数学方法研究推理形式结构和推理规律数学学科。因为它使用一套符号来表示各种推理逻辑关系，所以数理逻辑又称为符号逻辑。从广义上讲，数理逻辑包含集合论、模型论、递归论、证实论和命题演算、谓词演算，但本书只研究两个演算：命题演算和谓词演算两个演算。数理逻辑研究中心问题是推理，而推理前提与结论都是表示判断陈说句，因而表示判断陈说句组成了推理基本单位。数理逻辑称之为命题。第第1 1章章命命题题逻逻辑辑第2页一、命题一、命题定义定义1.1 能判断真假陈说句叫做能判断真假陈说句叫做命题命题。该定义有两层含义：该定义有两层含义：(1)命题是陈说句。其它语句，如疑问句、祈命题是陈说句。其它语句，如疑问句、祈使句、感叹句均不是命题；使句、感叹句均不是命题；(2)这个陈说句对事物判断是否符合客观事实这个陈说句对事物判断是否符合客观事实是能够给出结论：不是是能够给出结论：不是真真（符合客观事实）就（符合客观事实）就是是假假（不符合客观事实），不能不真也不假，（不符合客观事实），不能不真也不假，也不能既真又假，所以又称二值逻辑。也不能既真又假，所以又称二值逻辑。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第3页二、命题真值二、命题真值 命题所表示判断结果称为命题所表示判断结果称为命题真值命题真值。真值只取两个值：真（判断真值只取两个值：真（判断与事实相符）与事实相符）或假（判断或假（判断与事实不符）与事实不符）。通惯用通惯用1（或字母（或字母T）表示真，用）表示真，用0（或字母（或字母F）表示假。）表示假。真命题真命题：真值为真命题。：真值为真命题。假命题假命题：真值为假命题。：真值为假命题。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第4页例例6.1.16.1.1 判断以下语句是否为命题，并指出其真值。判断以下语句是否为命题，并指出其真值。（1 1）北京是中国首都。）北京是中国首都。（2 2）5 5能够被能够被2 2整除。整除。（3 3）2+2=52+2=5。（4 4）请勿吸烟。）请勿吸烟。祈使句祈使句（5 5）乌鸦是黑色吗？乌鸦是黑色吗？疑问句疑问句（6 6）这个小男孩多勇敢啊！这个小男孩多勇敢啊！感叹句感叹句（7 7）地球外星球上存在生物地球外星球上存在生物。（8 8）我正在说谎。）我正在说谎。悖论悖论注意：注意：注意：注意：一个语句本身是否能分辨真假与我们是否知道它一个语句本身是否能分辨真假与我们是否知道它真假是两回事。也就是说，对于一个句子，有时我们可真假是两回事。也就是说，对于一个句子，有时我们可能无法判定它真假，但它本身却是有真假，那么这个语能无法判定它真假，但它本身却是有真假，那么这个语句是命题，不然就不是命题。句是命题，不然就不是命题。悖论不是命题。悖论不是命题。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第5页判断一个句子是否为命题1、是否为陈说句2、真值是否唯一-X+y5-1+101=110-真值是否唯一与我们是否知道它真值是两回事第6页三、命题分类三、命题分类原子命题原子命题（Automic Proposition）：不能再不能再分解为更简单陈说句命题；也称简单命题。分解为更简单陈说句命题；也称简单命题。复合命题复合命题（Compound Proposition）：由若由若干简单命题用联结词联结成命题。干简单命题用联结词联结成命题。比如：比如：“雪是白雪是白”是原子命题；是原子命题；“昨天下雨，而且打雷昨天下雨，而且打雷”，“假如明天假如明天天晴我就去打球或者游泳天晴我就去打球或者游泳”都是复合命题。都是复合命题。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第7页四、命题表示四、命题表示 引进数学符号来表示命题。引进数学符号来表示命题。惯惯用用大大写写英英文文字字母母A,B,P,Q或或带带下下标标字字母母P1,P2,P3,或或数数字字(1),2,等等表表示示命命题题，称称之之为为命题标识符命题标识符。比如：比如：P：罗纳尔多是球星。：罗纳尔多是球星。Q：5是负数。是负数。P3：明天天气晴。明天天气晴。(2)：太阳从西方升起。：太阳从西方升起。皆皆为为符符号号化化命命题题，其其真真值值依依次次为为1、0、1或或0、0。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第8页v 命命题题标标识识符符有有命命题题常常量量、命命题题变变元元和和原原子子变变元之分。元之分。命题常元命题常元：真值确定命题标识符。：真值确定命题标识符。命命题题变变元元：真真值值不不确确定定，仅仅表表示示任任意意命命题题位置标志。位置标志。原原子子变变元元：当当命命题题变变元元表表示示原原子子命命题题时时，该变元称为原子变元该变元称为原子变元v 假假如如命命题题符符号号P P代代表表命命题题常常元元则则意意味味它它是是某某个个详详细细命命题题符符号号化化，假假如如P P代代表表命命题题变变元元则则意意味味着着它可指代任何详细命题。它可指代任何详细命题。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第9页一、否定联结词“”（或“”）否定联结词是一元联结词。相当于日惯用语中“非”，“不”，“无”，“没有”等。设P为一命题，P否定是一个新复合命题,称为P否定式，记作“P”，读作“非P”。P为真当且仅当P为假。P P 0 1 1 01.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第10页例例6.1.2.P:天津是一个城市天津是一个城市.Q:3是偶数是偶数.于是于是:P:天津不是一个城市天津不是一个城市.Q:3不是偶数不是偶数.例例6.1.3.P:苏州处处清洁苏州处处清洁.Q:这些都是男同学这些都是男同学.P:苏苏州州不不处处处处清清洁洁 (注注意意,不不是是处处处处不不清清洁洁).Q:这些不都是男同学这些不都是男同学.1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第11页二、合取二、合取联结联结词词“”合取词是二元联结词。相当于自然语言中合取词是二元联结词。相当于自然语言中“与与”、“而且而且”、“而且而且”、“也也”等。等。设设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命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第12页例例6.1.4.将以下命题符号化将以下命题符号化.(1)李平既聪明又用功李平既聪明又用功.(2)李平即使聪明李平即使聪明,但不用功但不用功.(3)李平不但聪明李平不但聪明,而且用功而且用功.(4)李平不是不聪明李平不是不聪明,而是不用功而是不用功.解解:设设 P:李平聪明李平聪明.Q:李平用功李平用功.则则 (1)PQ (2)PQ (3)PQ (4)(P)Q 注注意意：不不要要见见到到“与与”或或“和和”就就使使用用联联结结词词！比如比如:(1)李敏和李华是姐妹。李敏和李华是姐妹。(2)李敏和张华是朋友。李敏和张华是朋友。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第13页1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词例例6.1.5.试生成以下命题合取试生成以下命题合取.(1)P:我们在我们在6-503.Q:今天是星期二今天是星期二.(2)S：李平在吃饭：李平在吃饭.R：张明在吃饭：张明在吃饭.解解:(1)PQ:我们在我们在6-503且今天是星期二且今天是星期二.(2)SR:李平与张明在吃饭李平与张明在吃饭.第14页三、析取联结词三、析取联结词“”析取词是二元联结词。相当于析取词是二元联结词。相当于自然语言中自然语言中“或或”、“要么要么要么要么”等。等。设设P,Q为为二二命命题题，复复合合命命题题“P或或Q”，记记作作PQ。PQ为为真真当当且且仅当仅当 P与与Q中最少有一个为真。中最少有一个为真。P Q P Q 0 0 0 0 1 1 1 0 1 1 1 1 在在当当代代汉汉语语中中，“或或”有有“可可可可兼兼兼兼或或或或”和和“排排排排斥或斥或斥或斥或”之分。这里只是之分。这里只是“可兼或可兼或可兼或可兼或”。例例6.1.6（1）小王爱打球或爱跑步。）小王爱打球或爱跑步。（可兼或）可兼或）可兼或）可兼或）设设P：小王爱打球。：小王爱打球。Q：小王爱跑步。：小王爱跑步。则上述命题可符号化为：则上述命题可符号化为：P Q1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第15页1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词（2）林芳学过英语或法语。）林芳学过英语或法语。（可兼或）可兼或）可兼或）可兼或）设设P：林芳学过英语。：林芳学过英语。Q：林芳学过法语。：林芳学过法语。则上述命题可符号化为：则上述命题可符号化为：P Q（3）派小王或小李中一人去开会。（）派小王或小李中一人去开会。（排斥或排斥或排斥或排斥或）设设P：派小王去开会。：派小王去开会。Q：派小李去开会。：派小李去开会。则上述命题可符号化为：则上述命题可符号化为：(PQ)(PQ)第16页四、蕴含联结词四、蕴含联结词“”蕴含词是二元联结词。相当于自然语言中蕴含词是二元联结词。相当于自然语言中“若若则则”、“假如假如就就”、“只有只有才才”。设设P,Q为为二二命命题题,复复合合命命题题“若若P则则Q”记记作作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命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第17页例例6.1.76.1.7 将以下命题符号化。将以下命题符号化。1 1）天不下雨，则草木枯黄。）天不下雨，则草木枯黄。P P：天下雨。：天下雨。Q Q：草木枯黄。：草木枯黄。则原命题可表示为：则原命题可表示为：PQPQ。2 2）假如小明学日语，小华学英语，则小芳）假如小明学日语，小华学英语，则小芳学德语。学德语。P P：小明学日语：小明学日语.Q.Q：小华学英语：小华学英语.R.R：小芳学：小芳学德语德语.则原命题可表示为：则原命题可表示为：(PQ)R(PQ)R3 3）只要不下雨，我就骑自行车上班。）只要不下雨，我就骑自行车上班。P P：天下雨。：天下雨。Q Q：我骑自行车上班。：我骑自行车上班。则原命题可表示为：则原命题可表示为：PQPQ。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第18页4 4）只有不下雨，我才骑自行车上班。）只有不下雨，我才骑自行车上班。P P：天下雨。：天下雨。Q Q：我骑自行车上班。：我骑自行车上班。则原命题可表示为：则原命题可表示为：Q Q P P。注意注意:(1)与与自自然然语语言言不不一一样样：前前件件与与后后件件能能够够没没有有任任何内在联络！何内在联络！(2)在数学中，在数学中，“若若P则则Q”往往表示前件往往表示前件P为真，为真，则后件则后件Q为真推理关系为真推理关系.但数理逻辑中，当前但数理逻辑中，当前件件P为假时，为假时，PQ真值为真。真值为真。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第19页“假如假如 p p，则，则 q”q”不一样表述法很多：不一样表述法很多：若若 p p，就，就 q q 只要只要 p p，就，就 q q p p 仅当仅当 q q 只有只有 q q 才才 p p 除非除非 q,q,才才 p p 除非除非 q,q,不然非不然非 p p，1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第20页 例：设 p:天冷，q:小王穿羽绒服，将以下命题符号化 (1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，不然天不冷.(7)假如天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当日冷时候.注意：注意：pq 与与 pq 等值（真值相同）等值（真值相同）pqpqpqpqqp qpqpqp1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第21页五、等价联结词五、等价联结词“”等价联结词等价联结词是二元联结词。是二元联结词。相当于自然语言中相当于自然语言中“等价等价”、“当且仅当当且仅当”、“充要条件充要条件”等，等，真值表如右图。真值表如右图。设设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命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第22页注：注：（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是奇数是奇数.(PQ)(4)2+24 当且仅当当且仅当3不是奇数不是奇数.(PQ)1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第23页5种联结词类似5种运算符，称之为逻辑运算符，有运算优先级次序：-联结词优先次序为：,;-假如出现联结词同级，又无括号时，则按从左到右次序运算;-若遇有括号时，应该先进行括号中运算。1.11.11.11.1命命命命题题题题符符符符号号号号化化化化及及及及联联联联结结结结词词词词第24页一、概念一、概念定义定义1.3 1.3 命题公式命题公式按以下规则生成按以下规则生成：（1 1）单个命题常项或变项）单个命题常项或变项p,q,r,.,0,1p,q,r,.,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命命命命题题题题公公公公式式式式及及及及分分分分类类类类第25页注注:(1)(1)命命题题公公式式也也称称为为合合式式公公式式，由由命命题题常常项项、命命题题变变项、联结词和括弧组成项、联结词和括弧组成。(2)(2)假如把公式中命题变元代以原子命题或复合命题，则该公式便是一个复合命题。所以，对复合命题研究可化为对命题公式研究。命题公式命题公式普通不是命题普通不是命题,仅当公式中命题变元用确仅当公式中命题变元用确定命题代入时，才得到一个命题。其真值依赖于代换变定命题代入时，才得到一个命题。其真值依赖于代换变元那些命题真值。元那些命题真值。日常生活中推理问题是用自然语言描述，所以要进日常生活中推理问题是用自然语言描述，所以要进行推理演算必须先把自然语言行推理演算必须先把自然语言符号化符号化（或形式化）成逻（或形式化）成逻辑语言，即命题公式。然后再依据逻辑演算规律进行推辑语言，即命题公式。然后再依据逻辑演算规律进行推理演算。理演算。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类第26页二、命题符号化(1)分析出各简单命题分析出各简单命题,将它们符号化将它们符号化;(2)使用适当联结词使用适当联结词,把简单命题逐一联结起来把简单命题逐一联结起来,组组成复合命题符号化表示成复合命题符号化表示.例例6.3.26.3.2 将以下用自然语言描述命题符号化。将以下用自然语言描述命题符号化。（1 1）我和他既是弟兄又是同学。）我和他既是弟兄又是同学。解 令P：我和他是弟兄；Q：我和他是同学，则该语句可符号化为PQ。（2 2）我和你之间最少有一个要去海南岛。）我和你之间最少有一个要去海南岛。解 令P：我去海南岛；Q：你去海南岛，则该语句可符号化为PQ。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类第27页（3 3）假如他没来见你，那么他或者是生病了，）假如他没来见你，那么他或者是生病了，或者是不在当地。或者是不在当地。解 令P：他来见你；Q：他生病；R：他在当地，则该语句可符号化为P(QR)。（4 4）n n是偶数当且仅当它能被是偶数当且仅当它能被2 2整除。整除。解 令P：n 是偶数；Q：n 能被2 整除，则该语句可符号化为PQ。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类第28页三、公式解释或赋值三、公式解释或赋值 设设P1,P2,Pn是是出出现现在在公公式式G中中全全部部命命题题变变元元,指指定定P1,P2,Pn一一组组真真值值，则则称称这这组组真真值值为为G一个一个赋值赋值或或解释，记作解释，记作I。公式公式G在在I下真值记作下真值记作TI(G)。若若指指定定一一组组值值使使A真真值值为为真真(假假),称称这这组组值值为为A成真成真(假假)赋值。赋值。比比如如:对对公公式式(PQ)R，赋赋值值011(即即令令P=0，Q=1，R=1)为为(PQ)R成真赋值。成真赋值。赋值赋值011也可记作也可记作P,Q,R。含有含有n个命题变元公式共有个命题变元公式共有2n组不一样赋值。组不一样赋值。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类第29页四、真值表四、真值表 将将命命题题公公式式G在在其其全全部部解解释释下下所所取取真真值值列列成一个表成一个表,称做命题公式称做命题公式G 真值表真值表。为方便结构真值表，特约定以下：为方便结构真值表，特约定以下：命题变元按字典序排列。命题变元按字典序排列。对对每每个个指指派派，以以二二进进制制数数从从小小到到大大或或从从大到小次序列出。大到小次序列出。若若公公式式较较复复杂杂，可可先先列列出出各各子子公公式式真真值值(若若有有括括号号，则则应应从从里里层层向向外外层层展展开开)，最最终终列列出所求公式真值。出所求公式真值。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类第30页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 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命命命命题题题题公公公公式式式式及及及及分分分分类类类类第31页五、命题公式分类五、命题公式分类重言式重言式/永真式永真式：若若G G在在全部解释下都是真，则全部解释下都是真，则称称G G为为重言式或永真式。重言式或永真式。矛盾式矛盾式/永假式永假式：G G在在全部解释下都是假，则称全部解释下都是假，则称G G为为称为矛盾式或永假式。称为矛盾式或永假式。可满足式可满足式：若若G G不是恒假。不是恒假。几点说明几点说明 1 1）G G是是可可满满足足式式等等价价定定义义是是：G G最最少少存存在在一一个个成真指派。成真指派。2 2）重言式一定是可满足式，但反之不真。）重言式一定是可满足式，但反之不真。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类第32页 3 3）怎样利用好真值表来判断公式类型：）怎样利用好真值表来判断公式类型：若若真真值值表表最最终终一一列列全全为为1 1，则则公公式式为为重言式；重言式；若若真真值值表表最最终终一一列列全全为为0 0，则则公公式式为为矛盾式；矛盾式；若若真真值值表表最最终终一一列列中中最最少少有有一一个个1 1，则公式为可满足式。则公式为可满足式。1.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类第33页例例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命命命命题题题题公公公公式式式式及及及及分分分分类类类类第34页(2)(Q(2)(QP)P)(P PQ)Q)解解 令令=(Q=(QP)P)(P(P Q)Q)P QP QQPPP Q Q 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命命命命题题题题公公公公式式式式及及及及分分分分类类类类第35页(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 00 00 00 01 11 10 00 00 00 01.21.21.21.2命命命命题题题题公公公公式式式式及及及及分分分分类类类类第36页一、公式等值（等价）一、公式等值（等价）问题：问题：是否存在两个命题公式是否存在两个命题公式G G和和H H，在任意，在任意解释下它们真值都相同？解释下它们真值都相同？若存在，怎样用已经有概念描述上述现象若存在，怎样用已经有概念描述上述现象？解答：存在，比如解答：存在，比如n=2n=2命题公式命题公式,P,PQ与(PQ)在任意解释下都有系统真值。描述：GH是重言式 给这种现象引入一个概念：数学上用相等，等价，这里用等价、等值。1.31.3等等值值演演算算第37页定义定义1.101.10 设设G G，H H是两个命题公式，若是两个命题公式，若G GH H是重言式，是重言式，则称则称G G与与H H等价（等值），记作等价（等值），记作G GH H。-G GH H当且仅当当且仅当G GH H为重言式。为重言式。-与与是两个完全不一样符号。是两个完全不一样符号。不是命题联结词，而是公式间关系符号，不是命题联结词，而是公式间关系符号，不表示一个公式，即不代表命题，它不表示一个公式，即不代表命题，它表示公式表示公式与公式与公式有等价关系，有等价关系，是命题联结词，是命题联结词，是一个公式，表示是一个公式，表示某个命题。某个命题。公式之间等价关系特点：-自反-对称-传递1.31.3等等值值演演算算第38页二、公式等价（等值）判定方法（二、公式等价（等值）判定方法（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等等值值演演算算第39页三、公式等价判定方法（三、公式等价判定方法（2)2)依据已知等价公式依据已知等价公式,推演出另外一些等价公推演出另外一些等价公式过程称为式过程称为等值演算等值演算.惯用等价公式：惯用等价公式：（1 1）双重否定律：）双重否定律：()（2-32-3）等幂律：）等幂律：，（4-54-5）交换律：）交换律：，（6-76-7）结合律）结合律 ()()，()()1.31.3等等值值演演算算第40页（8-98-9）分配律）分配律 ()()()（对对 分配律）分配律）()()()（对对 分配律）分配律）（10-1110-11）德摩根律）德摩根律 ()，()（12-1312-13）吸收律）吸收律 ()，()（14-1514-15）零律：）零律：1 11 1，0 00 0（16-1716-17）同一律：）同一律：0 0，1 1（1818）排中律：）排中律：1 1（1919）矛盾律：）矛盾律：0 01.31.3等等值值演演算算第41页（2020）蕴含等值式）蕴含等值式 (21)(21)等价（双条件）等值式等价（双条件）等值式 ()()，()()（2222）假言易位）假言易位 （2323）等价否定等值式）等价否定等值式 （2424）归谬论）归谬论 ()()1.31.3等等值值演演算算第42页等值演算中置换规则等值演算中置换规则 置换：置换：用一个命题公式代换另一个命题公式中一个子公式。定理1.1（置换定理）设(A)是含命题公式A命题公式，(B)是用命题公式B置换了(A)中A之后得到命题公式，假如AB，则(A)(B)。1.31.3等等值值演演算算第43页例例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等等值值演演算算第44页例例6.4.26.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等等值值演演算算第45页（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)Q)R R 0 0 R R 0 0所以该公式是矛盾式。所以该公式是矛盾式。1.31.3等等值值演演算算第46页（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等等值值演演算算第47页 例例6.4.36.4.3 设有设有A A，B B，C C，D D四人做百米竞赛，四人做百米竞赛，观众甲，乙，丙分别对比赛名次进行了预测：观众甲，乙，丙分别对比赛名次进行了预测：甲说甲说C C第一，第一，B B第二；第二；乙说乙说C C第二，第二，D D第三；第三；丙说丙说A A第二，第二，D D第四；第四；比赛结束后发觉甲，乙，丙每人汇报情比赛结束后发觉甲，乙，丙每人汇报情况都是各对二分之一，试问实际名次怎样（无况都是各对二分之一，试问实际名次怎样（无并列者）？并列者）？1.31.3等等值值演演算算第48页 解解 设设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,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(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等等值值演演算算第49页因为因为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 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等等值值演演算算第50页因为因为A A，B B不能同时第二，不能同时第二，D D不能第三又第四，所以不能第三又第四，所以 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等等值值演演算算第51页四、联结词全功效集 前面已经引入了五中联结词，逻辑设计中还惯用到其它一些联结词：-异或（排斥或）联结词-与非联结词-或非联结词在一个形式系统中引入多少联结词好？-自然系统中越多越好，应用方便-公理系统中越少越好，研究方便一个联结词集合应该满足什么条件？1.41.4联联结结词词全全功功效效集集第52页对于命题公式，我们关注是它真值情况。N个命题变元命题公式，每个变元有两种赋值情况，共有2N中赋值情况。而每种赋值，又有两种结果，共有 种不一样赋值、取值情况。一个好方法是，每种赋值、取值情况用一个联结词表示。能够用函数观点来研究命题公式变元赋值与最终命题公式取值之间关系1.41.4联联结结词词全全功功效效集集第53页定义定义 称定义域为称定义域为000,001,111，值域，值域为为0,1函函数数是是n元元真真值值函函数数，定定义义域域中中元元素素是是长长为为n0,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联联结结词词全全功功效效集集第54页对于任何一个含对于任何一个含n个命题变项命题公式个命题变项命题公式A，都存在，都存在惟一一个惟一一个n元真值函数元真值函数F为为A真值表真值表.等值公式对应真值函数相同等值公式对应真值函数相同.下表给出全部下表给出全部2元真值函数对应真值表元真值函数对应真值表,每一个含每一个含2 2个命题变项公式真值表都能够在下表中找到个命题变项公式真值表都能够在下表中找到.比如：比如：pq,p q,(p q)(pq)q)等等都对应都对应表中表中1.41.4联联结结词词全全功功效效集集第55页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 1 0 1 0 1 0 1 1.41.4联联结结词词全全功功效效集集第56页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 qp p pq 1第57页联结词全功效集联结词全功效集 定义定义 在一个联结词集合中，假如一个联结词可在一个联结词集合中，假如一个联结词可由集合中其它联结词定义，则称此联结词为由集合中其它联结词定义，则称此联结词为冗余冗余联结词联结词，不然称为，不然称为独立联结词独立联结词.比如比如,在联结词集在联结词集 ,中，因为中，因为 p pq qp p q q,所以，所以，为冗余联结词为冗余联结词;类似地，类似地，也是冗余也是冗余联结词联结词.又在又在 ,中，因为中，因为 p p q q(p pq q)，所以，所以，是冗余联结词是冗余联结词.类似地，类似地，也是冗余联也是冗余联结词结词.1.41.4联联结结词词全全功功效效集集第58页联结词全功效集联结词全功效集(续续)定定义义 设设S S是是一一个个联联结结词词集集合合，假假如如任任何何n n(n n 1)1)元元真真