第二章逻辑和证明.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=8 q：水是液体 命题的真值：命题的真假性 真命题的真值为真，表示为T 假命题的真值为假，表示为F 比较：命题变量的真值与代数变量的值 原子命题： 不能再进一步分解的命题 复合命题： 由（用联结词）其他（多个）命题组合而成的 命题 例 判断原子命题或复合命题 小王既学英语又学日语。 复合命题 4不是奇数。 复合命题 如果天不下雨那么我骑车上班。 复合命题 小女孩七岁或八岁了。 复合命题 3是偶数当且仅当3能被2整除。 复合命题 五种联结词的符号化 (1)定义1 否定联结词?，? p：非p，p的否定 (2)定义2 合取联结词∧，p∧q：p而且q，p和q的合取 (3)定义3 析取联结词∨，p∨q：p或者q，p和q的析取 (4)定义5 蕴涵联结词→，p→q：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.构造 的真值表。 * * *