第1章：基础逻辑与证明

逻辑规则给出数学语句的准确含义 为了理解数学，我们必须理解正确的数学论证（即证明）是由什么组成的。只要证明一个数学语句是真的，我们就称之为一个订立。

逻辑规则给出数学语句的准确含义，这些规则用来区分有效和无效的数学论证。

例如，华盛顿是美国的首都 1+1 = 2 2+2=3

我们用字幕来表示命题变元，代表命题的变量。就想用字幕表示数字变量那样。习惯上用字幕p,q,r,s…… 如果一个命题是真命题，它的真值为真，用T表示；如果它是假命题，其真值为假，用F表示。

逆蕴含 倒置蕴含——逆否命题——真值与原命题相同 反蕴含——两个命题顺序不变，只是两个命题都加了否定

当两个复合命题总是具有相同的真值时，我们称之为等价。 一个条件语句与它的倒置等价 一个蕴含的逆蕴含与反蕴含也是等价 可以用真值表进行判断。

在自然语言中，双条件并不总是显示的。“你吃饭完才可以吃餐后甜点”

上一部分介绍了4中重要的逻辑连接词——合取、析取、条件（双条件）、否定。 这个工具非常好用！！

优先级顺序为：否定、合取、析取、条件、双条件

有许多理由需要把语言翻译成由命题变量和逻辑联接词组组成的表达式，特别是因为语言（包括一切人类语言）常有二义性，而把句子译成逻辑表达式可以消除歧义。 例如，只有你主修计算机科学或不是新生，才可以从校园网访问因特网 我们的办法是用命题变元表示其中的每一个句子成分，并找出其间合适的逻辑联结词。具体地说，令a、c和f分别表示“你可以从校园网访问因特网”、“你主修计算机科学”和“你是个学生”。注意到“只有……，才……”

在说明硬件系统和软件系统时，将自然语言语句翻译成逻辑表达式是很重要的一部分。系统和软件工程师从自然语言中提取需求，生成精确、无二义性的规范说明，这些规范说明可作为系统开发的基础。 例如“当文件系统写满时，自动应答不能够发出” p表示“自动应答能够发出”，q表示“文件系统满了”

例如网页检索 NEW AND MEXICO AND UNIVERSITY

可以用逻辑推理解决的难题称为逻辑难题。 例如奥数题中，一直说谎话，一直说真话的人。

位运算只有0、1 逻辑运算充当其中的运算法则

复合命题=用于逻辑运算的命题变元形式的表达式

在所有可能的情况下都有相同真值的两个复合命题称为逻辑等价。

表1-16

1.1和1.2学习的命题逻辑，不能充分地表达数学语言和自然语言中语句的意思。 我们要怎么判断“有一台连接在大学网络的计算机正遭受入侵者的供给”

“x>3”这个语句有两部分，第一部分即变量x是语句的主语，第二部分谓词“大于3”，表明语句的主语会有一个性质。我们可以用P（x）表示语句“x>3”，其实P表示谓词“大于3”，而x是变量。也把语句P(x)说成是命题函数P在x的值。一旦变量x赋一个值，语句P(x)就成为命题，因为有真值。

例子令A(x)表示语句“计算机x正被一个入侵者攻击”。假设在校园的计算机中，只有CS2和MATH1经常被入侵者攻击，那么A(CS1)A(CS2)A(MATH)的真值是什么？

一般涉及n个变量x1，x2,x3,...,xn的语句可以用P(x1,x2,x3,...,xn)表示 形为P(x1,x2,x3,...,xn)的语句是命题函数P在n元组(x1,x2,x3,...,xn)的值，P也称为n元谓词。

当命题函数中所有变量均被赋值时，得到的命题有一个真值。还有另一重要方式，也可以从命题函数产生命题，这就是量化。 量化表示谓词在一定范围的事物上成立的程度。 在语言中，单词“所有”、“一些、“许多”、”没有“以及”没几个“被用于量化。 这两导论两类量化 全称量化 & 存在量化

处理谓词和量词的逻辑领域称为谓词演算。

不同量词没有数量的限制，如“确定有2个”，“有不超过3个”

对论域进行约束

量词比所有命题演算的逻辑运算符有更高的优先级

当量词作用于变量x时，我们说此变量的这一次出现为绑定的。没有被量词绑定或设置为与某一特定值相等的变量出现称为自由的。 出现在命题函数中的所有变量必须是绑定的，才能把此命题函数转变为命题。可以用全称量词、存在量词和赋值来完成转变。

逻辑表达式中应用连词的部分称为这个量词的作用于。因此，一个变量是自由的——如果在指定这个变量的公式中，变量在所有量词的作用于之外。

“班上每个学生都学过一门微积分课。”

例23 使用谓词和量词表达语句“班上的每个学生都学过微积分” 重写“对班上每一个学生，该学生学过微积分课” 引入变量x，语句就变成 “对班上的每一个学生x，x学过微积分课” 引入谓词C(x)，表示语句“x学过微积分课”。因此，如果x的论域是班上的学生，我们可以将将语句进行翻译

然而还有其他正确的翻译方法，并可以使用不同的论域和其他谓词。具体选择什么方法取决于后续要进行的推理。例如，我们可能对更广泛的人群感兴趣，而不仅仅是班上的学生。如果将论域改成所有人，则语句就要变成 “对每个人x，如果是x是班上的学生，那么x学过微积分课。” 如果S(x)便是语句x在这个班上，则我们的语句可表达为~~~~~

例23 用谓词和量词表达系统说明“每封大于1MB的邮件将被压缩”和“如果用户处于活状态，那么至少有一个网络连接有效。”

解：令S(m,y)表示“邮件m大于yMB”，其中变量x的论域是所有邮件，变量y是一个正实数。令C(m)表示“邮件m将被压缩”，那么说明“每封大于1MB的邮件将被压缩。” 对于所有的m,S(m,1)->C(m)

1.3定义了存在量词和全称量词，并展示了如何用它们来表示数学语句。我们也解释了用他们来将汉语语句翻译成逻辑表达式。 嵌套量词 循环量化考虑。对多个变量使用量词时，借助嵌套循环来思考是有益的。

除非所有量词均为全称量词或均为存在量词，否则量词的顺序是重要的。

用汉语表达的数学语句可以被翻译成逻辑表达式 例6：将语句“两个正整数的和是整数”翻译成逻辑表达式 首先重写，以显示隐含的量词和论域：“对每两个整数，如果它们都是正的，那么它们的和是正数。” 然后引入变量x和y就得到“对所有正整数x和y，x+y是正数”

这部分是学习证明。在数学中，证明是建立在数学命题真实性之上的有效论证。对于一个论证，是指表示一连串的命题最终得出结论。对于有效性，是计划得出结论或者论证的最终命题，其过程必须依据前面命题或者论证的前提的真实性。也就是说，一个论证是真实的，当且仅当 它是所有的前提为真而结论为假是不可能的。

“若果你有一个正确的密码，那么你可以登录到网络” 前提：“你有一个正确的密码” 所以：“你可以登录到网络”

我们想知道这是否是一个有效论证。也就是说，想要判断当前提“如果你有一个正确的密码，那么你可以登录到网络”和“你有一个正确的密码”都为真时，结论“你可以登录到网络”是否为真。

p 蕴含q为真，p为真，就可以推出q也为真

除了上述的论证，还有其他的推理规则

当有许多前提时，为了证明一个论证是有效的，常常需要多个推理规则。 证明：前提”今天下午没有出太阳并且今天比昨天冷“，”只有今天下午出太怎样，我们才去游泳“，”若我们不去游泳，则我们将乘独木舟游览“，以及”若我们乘独木舟游览，则我们将在黄昏时回家“，导致结论”我们将在黄昏时回家“。

已经开发出自动执行推理和证明定理任务的计算机程序。许多这类程序利用称为消解的推理规则。 有一个永真式

几种常见的谬误都来源于不正确的论证。这些谬误看上去像是推理规则。但是他们是给予偶然事件而不是永真式。在这里讨论这些谬误，是为了说明正确与不正确的推理之间的区别。

证明是建立在数学语句真实性基础上的有效论证。证明可以用电力，假设为真的公里以及之前已经证明的定力的假设。

一个定理是一个能够表明是真的语句。 引理：在其他结果证明中很有帮助的不大重要的定理成为引理 推论：从定理直接建立被证明的定理。 猜想：是被提出为真的命题，通常是在一些依据的基础上，启发式论证，或者专家的一个直觉。当找到一个猜想的证明，猜想就变成了定理。许多猜想是错误的。

先要理解隐含的论域

1.6.4 证明定理的方法