1.1命题与联结词

1请问：东东是否误解了爷爷原话的意思，为什么？2爷爷没有住上这样的高楼，所以爷爷没有好好学习。你只有现在好好学习，将来才能住上这样的高楼。指用数学的方法(符号、公式及演算)来研究逻辑的学科。317世纪的威廉·莱布尼兹(G.W.Leibniz,)，试图建立一种符号语言，并寻求一种推理演算的方法，以解决推理的问题。1879年，戈特洛布·弗雷格(F.L.G.Frege,)的《概念语言：一种按算术的公式语言构成的纯思维公式语言》的出版标志着数理逻辑的基础部分正式建立4E.W.Dijkstra（1930-2002）是著名的荷兰计算机科学教授、软件大师、现代数值计算的奠基人，他于1959年提出Dijkstra算法，1972年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多错误了。不少东西逻辑学家早就说了，可我不知道。要是我能年轻20岁的话，就回去好好学逻辑。5•程序设计语言•程序设计方法学程序设计•机器思维和推理•专家系统、定理的机器证明•逻辑型程序设计语言PROLOG人工智能•数字逻辑电路•网络协议工程、知识工程、•模糊数学、形式语言与自动机其他6命题逻辑一阶逻辑§1.1命题与联结词（1）3不是偶数。（2）三角形两边长度之和大于第三边长度。（3）四个角为直角的四边形为正方形。真命题真命题假命题什么是命题？能判断真假的陈述句称为命题（proposition）。9说明：（1）命题是具有唯一真值的陈述句。（2）以下类型的句子，如疑问句、祈使句、感叹句、不能唯一确定真值的陈述句，都不是命题。作为命题所表达的判断结果称为命题的真值(truthvalue)，只两个取值：真或假。•真命题•假命题（1）4是素数。（2）π是无理数。（3）2012年2月21日是晴天。（4）存在外星人。（5）x大于y。（6）3大于2吗？（7）请不要吸烟！（8）这朵花真美丽啊！（9）我正在说谎。悖论假命题真命题命题(真值唯一)命题(真值唯一)非命题（无确定真值）非命题（疑问句）非命题（祈使句）非命题（感叹句）非命题（无确定真值）悖论（paradox）字面意思为“荒谬的理论或自相矛盾的话”。◦从逻辑上看，悖论语句具有这样的特征：如果假定这个语句为真，那么会推出这个语句为假；反之，如果假定这个语句为假，又会推出这个语句为真。◦悖论古已有之，一般认为，最早的悖论是古希腊的“说谎者悖论”。11《圣经·新约·提多书》是这样记述的：克里特人中的一个本地先知说：“克里特人总是撒谎，乃是恶兽，又馋又懒。”这个克里特岛的“先知”是伊壁孟尼德（Epimenides）。12欧布里德（Eubulides）后来将这句话改进为：我正在说谎。（1）本命题是假的。（2）本理发师只给那些不给自己理发的人理发。……13补充阅读材料：《数学悖论奇景》1.唐·吉诃德悖论小说《唐·吉诃德》里描写过一个国家，它有一条奇怪的法律，每个旅游者都要回答一个问题：“你来这里做什么？”回答对了，一切都好办；回答错了，就要被绞死。一天，有个旅游者回答：“我来这里是要被绞死。”旅游者被送到国王那里。国王苦苦想了好久：他回答得是对还是错？究竟要不要把他绞死。如果说他回答得对，那就不要绞死他——可这样一来，他的回答又成了错的了！如果说他回答错了，那就要绞死他——但这恰恰又证明他回答对了。实在是左右为难！142.一块钱哪儿去了？一个唱片商店里，卖30张老式硬唱片，一块钱两张；另外30张软唱片是一块钱三张。那天，这60张唱片卖光了。30张硬唱片收入15元，30张软唱片收入10元，总共是25元。第二天，老板又拿出60张唱片。他想：“如果30张唱片是一块钱卖两张，30张是一块钱卖三张，何不放在一起，两块钱卖5张呢？”这一天，60张唱片全按两块钱5张卖出去了。老板点钱时才发现，只卖得24元，而不是25元。这一块钱到哪儿去了呢？15存在真值可以发生变化的命题吗？答案：存在。1617根据命题陈述句的复杂度，命题可以分为两类：（1）简单命题（2）复合命题18不能被分解成更简单的陈述句的肯定陈述句称为简单命题或原子命题（atomicproposition）。19例如，例2中命题（1）~（4）都是简单命题。（1）4是素数。（2）π是无理数。（3）2012年2月21日是晴天。（4）存在外星人。简单命题是命题逻辑最小、最基本的研究单位。能够被分解出更简单的肯定陈述句（简单命题）的命题称为复合命题（compoundproposition）。20例3复合命题的例子（1）3不是偶数。（2）2是偶素数。（3）2或4是素数。（4）如果2是素数，则3也是素数。（5）2是素数当且仅当3也是素数。在命题逻辑中有五个基本联结词：非、并且、或、如果….，则….、当且仅当（1）3不是偶数。非3是偶数。简单命题：3是偶数。联结词：非（2）2是偶素数。2是偶数并且2是素数。简单命题：2是偶数。2是素数。联结词：并且（3）2或4是素数。2是素数或4是素数。简单命题：2是素数。4是素数。联结词：或21（4）如果2是素数，则3也是素数。简单命题：2是素数。3是素数。联结词：如果，则（5）2是素数当且仅当3也是素数。简单命题：2是素数。3是素数。联结词：当且仅当22简单命题的符号化教材采用小写英文字母p、q、r、…、pi、qi、ri、…来表示简单命题，在论述中来代替命题，这些字母称为命题标识符。用命题标识符来代替命题的过程称为命题的符号化；用“1”表示真，用“0”表示假，于是命题的真值取值为1或0。23简单命题符号化的格式命题标识符：符号化的对象（简单命题）设p：4是素数q：π是无理数r：2012年2月21日是晴天s：存在外星人于是p,q,r,s成为这四个简单命题的标识符。24例4符号化下列简单命题。（1）4是素数。（2）π是无理数。（3）2012年2月21日是晴天。（4）存在外星人。复合命题的符号化是基于简单命题的符号化来实现的，分为三个步骤：（1）分析出简单命题和联结词（2）将简单命题符号化（3）用联结词联结命题标识符25（1）3不是偶数。（2）2是偶素数。（3）2或4是素数。（4）如果2是素数，则3也是素数。（5）2是素数当且仅当3也是素数。（1）3不是偶数。非3是偶数。简单命题：3是偶数。联结词：非（2）2是偶素数。2是偶数并且2是素数。简单命题：2是偶数。2是素数。联结词：并且（3）2或4是素数。2是素数或4是素数。简单命题：2是素数。4是素数。联结词：或（4）如果2是素数，则3也是素数。简单命题：2是素数。3是素数。联结词：如果，则（5）2是素数当且仅当3也是素数。简单命题：2是素数。3是素数。联结词：当且仅当3不是偶数。2是偶素数。2或4是素数。如果2是素数，则3也是素数。2是素数当且仅当3也是素数。为了得到复合命题的符号化形式，我们还必须对五个联结词进行符号化！解：设p：3是偶数；q：2是偶数；r：2是素数；s：4是素数；t：3是素数。符号化为：非p符号化为：q并且r符号化为：r或s符号化为：如果r，则t符号化为：r当且仅当t在命题逻辑中有五个基本联结词：29非并且或如果….，则….当且仅当否定┐合取∧析取∨蕴涵→等价定义1.1设p为任意的命题，则复合命题“p的否定”称为p的否定式，记作┐p，符号“┐”称为否定联结词。由定义可知：当p为真时，┐p为假；反之当p为假时，┐p为真。30例5符号化复合命题“3不是偶数。”解：设p：3是偶数则命题符号化为┐p。p的真值为0，所以┐p的真值为1。定义1.2设p、q为任意两个命题，复合命题“p与q”（或“p并且q”）称为p与q的合取式，记作p∧q，符号∧称为合取联结词。由定义可知：p∧q的逻辑关系为p与q同时成立，所以p∧q为真当且仅当p与q同时为真。31例5符号化复合命题“2是偶素数”。解：设q：2是偶数，r：2是素数则命题符号化为q∧r由于q与r的真值都为1，所以q∧r的真值为1说明：既…，又…、不但…，而且…、虽然…，但是…、一面…，一面…、…，而是…等都符号化为合取式。解：令p:李平用功、q:李平聪明（1）符号化为p∧q（2）符号化为q∧┐p（3）符号化为┐(┐q)∧┐p令r:王丽用功（4）符号化为p∧r32练习1将下列命题符号化。（1）李平不仅用功而且聪明。（2）李平虽然聪明，但不用功。（3）李平不是不聪明，而是不用功。（4）李平和王丽都用功。（5）李平和王丽是同学。解：令s:李平是同学、t:王丽是同学（5）符号化s∧t33练习1将下列命题符号化。（1）李平不仅用功而且聪明。（2）李平虽然聪明，但不用功。（3）李平不是不聪明，而是不用功。（4）李平和王丽都用功。（5）李平和王丽是同学。解：令s:李平和王丽是同学（5）符号化为s“李平和王丽是同学”是简单命题！！注意：并非所有的“与”或“和”都可以使用联结词∧。定义1.3设p、q为任意的两个命题，复合命题“p或q”称为p与q的析取式，记作p∨q，符号∨称为析取联结词。规定：p∨q为假当且仅当p与q同时为假。34例5符号化复合命题“2或4是素数”。解：令r：2是素数，s：4是素数则命题符号化为r∨s。由于r为真，所以r∨s为真。命题的析取有“相容或”和“排斥或”之分。相容或：析取的两命题可以同时为真。排斥或：析取的两命题不能同时为真。35定义（exclusiveor）设p、q为两个命题，复合命题“p，q之中恰有一个成立”称为p与q的异或式或排斥或式，记作pq，称作异或联结词。易见：1、pq可写成(p∧┐q)∨(┐p∧q)2、pq为真当且仅当p、q中恰有一个为真（1）张晓静爱唱歌或爱听音乐。（2）张晓静是江苏人或安徽人。（3）张晓静只能挑选202或203房间。（1）张晓静爱唱歌或爱听音乐。解：令p:张晓静爱唱歌，q:张晓静爱听音乐。符号化为:p∨q（2）张晓静是江苏人或安徽人。解：令r:张晓静是江苏人，s:张晓静是安徽人。符号化为:（r∧┐s）∨（┐r∧s）（3）张晓静只能挑选202或203房间。解：令t:张晓静挑选202房间，u:张晓静挑选203房间。符号化为:（t∧┐u）∨（┐t∧u）r∨s思考题：符号化命题“派小王、小张、小李中一人去开会。”定义1.4设p、q为任意命题，复合命题“如果p，则q”称作p与q的蕴涵式，记作p→q，并称p是蕴涵式的前件（hypothesisorpremise），q为蕴涵式的后件（conclusionorconsequence）。→称为蕴涵联结词。◦规定：p→q为假当且仅当p为真q为假。即当p为真q为假时，p→q为假；其它情况都为真。◦p→q的逻辑关系：p是q的充分条件，q是p的必要条件。说明：（1）p→q的其它叙述方式：“只要p，就q”、“因为p，所以q”、“p仅当q”、“只有q才p”、“除非q才p”，“除非q，否则非p”等等。这些叙述方式都使用p→q来符号化。（2）在自然语言中，p与q往往具有某种内在的联系；在数理逻辑中，p与q可以无任何内在联系。如：因为天下乌鸦一般黑，所以太阳东升西落。（3）在数学或其它自然科学中，“如果p，则q”往往表达的是前件为真，后件也为真的推理关系。但在数理逻辑中，作为一种规定只有p为真q为假这一种情况使得p→q为假。而当p为假时，无论q是真是假，p→q都为真。解：令p:3+3=6，p的真值为1q:雪是白色的，q的真值为1则（1）p→q，命题的真值分别为1（2）┐p→q，命题的真值分别为1（3）p→┐q，命题的真值分别为0（4）┐p→┐q，命题的真值分别为141（1）如果3+3=6，则雪是白色的。（2）如果3+3≠6，则雪是白色的。（3）如果3+3=6，则雪不是白色的。（4）如果3+3≠6，则雪不是白色的。（5）只要a能被4整除，则a就一定能被2整除。（6）a能被4整除仅当a能被2整除。（7）除非a能被2整除，a才能被4整除。（8）除非a能被2整除，否则a不能被4整除。（9）只有a能被2整除，a才能被4整除。其中a