《逻辑和证明》PPT课件.ppt

第二章 逻辑和证明,数理逻辑：用数学的方法研究逻辑推理数理逻辑的目标：逻辑推理机械（演算）化数理逻辑的基本方法：符号化德国数学家、哲学家莱布尼兹是公认的数理逻辑的创始人数理逻辑在计算机科学中发挥着重要的作用，计算机科学的发展也推动了数理逻辑的发展,2.1 命题,辑推理的前提和结论都是关于某些事物的判断（陈述）命题：有确定的（能判定）真、假性的陈述句 真命题：是真的命题 假命题：是假的命题 数理逻辑的基本成分,例 判断下列句子是否是命题以及真假性1.2+4=8 假命题2.北京是中国的首都。真命题3.华盛顿是美国的首都。真命题4.x+1=4 不是命题 5.公园里的人真多啊！不是命题6.请勿吸烟！不是命题7.小红今天去学校吗？不是命题8.明年二月五日下雨。不是命题9.火星上存在生命。假命题10.本句子是假的。不是命题,命题符号化：用字母来表示命题，常用小写字母表示原子命题（p、q、r、s）比较：代数中用字母表示变量例p：2+4=8q：水是液体命题的真值：命题的真假性 真命题的真值为真，表示为T 假命题的真值为假，表示为F 比较：命题变量的真值与代数变量的值原子命题：不能再进一步分解的命题 复合命题：由（用联结词）其他（多个）命题组合而成的命题,例 判断原子命题或复合命题小王既学英语又学日语。复合命题4不是奇数。复合命题如果天不下雨那么我骑车上班。复合命题小女孩七岁或八岁了。复合命题3是偶数当且仅当3能被2整除。复合命题,五种联结词的符号化(1)定义1 否定联结词，p：非p，p的否定(2)定义2 合取联结词，pq：p而且q，p和q的合取(3)定义3 析取联结词，pq：p或者q，p和q的析取(4)定义5 蕴涵联结词，pq：p 蕴涵q，p假设（前项，前提），q结论注意与日常叙述中的“如果那么”的区别蕴含与合同和义务：条件不成立，也就没有义务(5)定义6 双蕴涵（等价）联结词，p q：p与q的等价,真值表：给出命题真值之间的关系含有n(n0)个命题变量的命题公式的真值表有2n行在数理逻辑中，组成一个复合命题的原子命题在语义可以没有任何联系 数理逻辑关心复合命题的结构，其真值由组成它的原子命题的真值唯一确定,例 太阳从西方升起，则2+2=4。联结词（运算符）的优先级：，减少所需的括号数目 例 命题符号化是命题演算的基础，符号化过程：找出命题中的原子命题，分别用小写英文字母表示它们 将原子命题用适当的联结词联结起来,例8 怎样把下面的句子翻译成逻辑表达式？“只有你主修计算机科学或不是新生，才可以从校园内访问因特网。”解：有许多方法翻译这个句子为逻辑表达式。尽管可以用一个命题变量，如q来表示这一句子，但在分析其含义或用其作推理时，这种表示不会有什么作用。我们的办法是用命题变量表示其中的每一个句子成分，并找出期间合适的逻辑联结词。具体的说，令a，c和f分别表示“你可以从校园内访问因特网”、“你主修计算机科学”和“你是个新生”。注意到“只有才”是表达蕴含的一种方式，上述句子可以译为：,习题 下列哪些是命题，这些命题的真值是什么？别过来。几点了？在纽约没有黑苍蝇。4+x=5。若x=1，则x+1=5。若x=z，则x+y=y+z。2.令p，q，r为如下命题，p：你得流感了。q：你错过了最后的考试。r：这门课你通过了。将命题用汉语表示。（接下页）,3.令p，q，r为如下命题，p:你的期末考试得了A。q:你做了本书每一道练习。r:这门课你得了个A。用p，q，r和逻辑连接符写出这个命题：期末考试得A并且做本书的每道练习，足以使你这门课得A。4.构造的真值表。,