第一章数理逻辑.ppt

离散数学 数理逻辑 逻辑学 是一门研究思维形式及思维规律的科学 背景知识 起源： 17世纪中叶，莱布尼兹（德国的数学家、物理学家、哲学家）曾经提出“用计算机代替思维完成推理过程”的设想。 发展 英国数学家布尔在1847年创立了布尔代数，奠定了数理逻辑的基础。 数学家布尔 布尔，自学成才的典范。鞋匠的儿子，从小打工帮衬家用，原想做牧师，但生活所迫16岁做了中学教师。教书时自学牛顿的《数学原理》、拉格朗日的《解析函数论》和拉普拉斯的《天体力学》，虽没学位但成了数学教授。主要贡献是创立了布尔代数，在电子工程、计算机、数理逻辑中有很多应用。 布尔的五朵金花 布尔40岁英年早逝，但他的五朵金花女儿很厉害。二女alicia在四维几何方面卓有贡献，四女是英国化学的第一个女教授，小女是《牛虻》的作者伏尼契。小女的孙女中文名字叫寒春，芝加哥大学核物理博士，参加过曼哈顿原子弹计划；后长期定居中国，拿到中国的第一张永久居留证。 完备德国的数学家弗雷格在1879年引入了量词、约束元。为数理逻辑开辟了新的领域。 完善德国著名的数学家哥德尔在1931年 提出了不完全性定理的证明。 近代冯?诺依曼、图灵、克林等人研究了逻辑与计算的关系。逻辑程序设计语言的研制，更促进了数理逻辑的发展。 一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。” ???请问这个人说得对吗？他是怎么推导出来的呢？ 第一章 命题逻辑基本概念 1.1 命题与联结词 命题 表达判断的陈述句。 两个条件：（1）陈述句； （2）能判断真假。 真值 命题的结果。 任何命题的真值都是唯一的。 悖论：由真推出假，又由假推出真从而既不能为真，又不能为假的陈述句。 世界文学名著《唐·吉诃德》中有这样一个故事：唐·吉诃德的仆人桑乔·潘跑到一个小岛上，成了这个岛的国王。他颁布了一条奇怪的法律：每一个到达这个岛的人都必须回答一个问题：“你到这里来做什么？”如果回答对了，就允许他在岛上游玩，而如果答错了，就要把他绞死。对于每一个到岛上来的人，或者是尽兴地玩，或者是被吊上绞架。有多少人敢冒死到这岛上去玩呢？一天，有一个胆大包天的人来了，他照例被问了这个问题，而这个人的回答是：“我到这里来是要被绞死的。”请问桑乔·潘萨是让他在岛上玩，还是把他绞死呢？如果应该让他在岛上游玩，那就与他说“要被绞死”的话不相符合，这就是说，他说“要被绞死”是错话。既然他说错了，就应该被处绞刑。但如果桑乔·潘萨要把他绞死呢？这时他说的“要被绞死”就与事实相符，从而就是对的，既然他答对了，就不该被绞死，而应该让他在岛上玩。小岛的国王发现，他的法律无法执行，因为不管怎么执行，都使法律受到破坏。他思索再三，最后让卫兵把他放了，并且宣布这条法律作废。这又是一条悖论。 1.1 命题与联结词 命题符号化 对自然语言描述的命题及其真值抽象化， 用符号来表示。 用小写字母p,q,r…或pi ,qi ,ri …表示命题； 用“1”表示真，“0”表示假； 如：p:2是素数。q:雪是黑色的。 则 p是真命题，q假命题 如：如果今天下雨，我就乘公交车上班。 用了蓝天六必治，牙好，胃口就好， 吃啥啥香。 自然语言中，常使用的“如果，就”，“因为…，所以…”，“或”，“与”，“但是”等将简单的陈述句组合在一块，构成一个复杂的句子。数理逻辑中也要用到逻辑联结词。但自然语言中的逻辑联结词常具有二义性，且没有符号化。 定义1.1 设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式,记作┐p，符号 ┐称作否定联结词。并规定┐p为真当且仅当p为假。 如：p：3是偶数。 ┐p：3不是偶数 定义1.2 设p , q为二命题，复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q，∧称作合取联结词。并规定p∧q为真当且仅当p与q同时为真。 “既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…” 都可用∧ 如：p：今天下雨。q：今天降温。  p∧q :今天下雨且今天降温。 ┐p∧p其真值永为假。