1.1逻辑

本页由讲义拆分版 TeX 初步转换生成；答案默认收起。

讲义正文

逻辑

命题逻辑初步

在数学里,逻辑是指研究某个形式语言的有效推论. 逻辑使得我们描述问题时可以严谨、无歧义,引导我们通过推理获得事物的本质.

然而,数学推理无法建立在浮沙之上,如果我们希望构建一个严密的推理体系,我们必须从自然语言中识别出那一类“意义确定、不随人的主观意愿而改变”的语句.这类语句最核心的特征在于：它们所陈述的内容,要么是事实,要么与事实相悖,二者必居其一.

于是我们称一个能判断真假的陈述句为命题

命题表述的陈述或真或假,但不可兼具,这时也称命题取真或取假,一般用“T”表示真,用“F”表示假.称真值可以变化的命题为命题变元,用小写字母\(\displaystyle p,q,r\)等表示.

问题

判断下列句子是否为命题.

（1）今天是星期五.

（2）你会说英语吗？

（3）\(\displaystyle 3-x=5.\)

（4）任一大于2的偶数一定可以表示为两个素数之和.

（5）“我现在说的是假话.”

为保持逻辑的清晰,对于较为复杂的表述,需要将简单的命题复合成复杂命题,这需要用到下述命题连结词.

定义 1.1.1（命题连结词）

命题连结词共五种,依次为：

（1）否定，若$\displaystyle p$为命题,则$\displaystyle p$的否定“非$\displaystyle p$”也为命题,记为$\displaystyle \neg p$,$\displaystyle p$与$\displaystyle \neg p$的真值相反.

（2）合取，若$\displaystyle p,q$为命题,则“$\displaystyle p$且$\displaystyle q$”也为命题,记为$\displaystyle p\wedge q$.$\displaystyle p\wedge q$为真当且仅当$\displaystyle p,q$全为真.

（3）析取，若$\displaystyle p,q$为命题,则“$\displaystyle p$或$\displaystyle q$”也为命题,记为$\displaystyle p\vee q$.“$\displaystyle p\vee q$为假”当且仅当“$\displaystyle p,q$全为假”.

（4）蕴涵，若$\displaystyle p,q$为命题,则$\displaystyle p$与$\displaystyle q$的蕴涵式“若$\displaystyle p$则$\displaystyle q$”（“$\displaystyle p$蕴涵$\displaystyle q$”）也为命题,记为$\displaystyle p\rightarrow q$,“$\displaystyle p\rightarrow q$为假”当且仅当“$\displaystyle p$为真,$\displaystyle q$为假”.

（5）双蕴涵，若$\displaystyle p,q$为命题,则$\displaystyle p$与$\displaystyle q$的蕴涵式“$\displaystyle p$等价于$\displaystyle q$”（“$\displaystyle p$双蕴涵$\displaystyle q$”）也为命题,记为$\displaystyle p\leftrightarrow q$,“$\displaystyle p\leftrightarrow q$为真”当且仅当“$\displaystyle p,q$同时为真或同时为假”.

为描述复杂的事物关系,有时需要将多个命题变元组合起来.

定义 1.1.2（命题表达式）

由命题变元、逻辑联结词以及用于确定运算优先顺序的括号,按照一定的逻辑规则组合而成的符号串,称为命题表达式,进行逻辑运算时,命题连结词的优先级自高到低分别为：\(\displaystyle \neg,\wedge,\vee,\rightarrow,\leftrightarrow\).

\iffalse \footnote{将自然语言中的陈述性成分提取为命题变元,并选取恰当的逻辑联结词以构建还原原句语义的逻辑表达式——这一过程被称为语义形式化.它是传统基于规则的自然语言处理（NLP）中最具挑战性的核心难题之一.例如：

“每个男孩都喜欢一个女孩.”这句话在逻辑上可以有两种完全不同的表达式：

（1）\(\displaystyle \forall x (\text{Boy}(x) \to \exists y (\text{Girl}(y) \land \text{Like}(x, y)))\) （“每个男孩都有自己喜欢的女孩.”）

（2）\(\displaystyle \exists y (\text{Girl}(y) \land \forall x (\text{Boy}(x) \to \text{Like}(x, y)))\) （“存在一个特定的女孩,全城的男孩都喜欢她.”） } \fi 对于一个命题表达式,若无论其中出现的命题变元如何取值,表达式总取真,则称此表达式为永真式；若无论其中出现的命题变元如何取值,表达式总取假,则称此表达式为永假式；上述情况以外的称为可能式.

问题

解答下述问题

（1）记命题：

\(\displaystyle p:\)你可以从校园网访问因特网

\(\displaystyle q:\)你主修计算机科学

\(\displaystyle r:\)你是新生

将“如果你主修计算机科学或不是新生,你就可以从校园网访问因特网.”翻译为命题表达式.

（2）

儿子：“爸爸,我要玩游戏.”

父亲：“你不做完作业就不能玩游戏.”

记命题：

\(\displaystyle p:\)你做完了作业,\(\displaystyle q:\)你可以玩游戏.

将“你不做完作业就不能玩游戏”翻译为命题表达式.并思考：按照父亲的逻辑,儿子做完作业后是不是就可以玩游戏了？

从上述思考题可以发现,命题的表示方法不唯一.若在所有情况下命题\(\displaystyle p,q\)均具有相同的真值,则称\(\displaystyle p\)与\(\displaystyle q\)逻辑等价,记为\(\displaystyle p\Leftrightarrow q\),此处仅列举三个常用的等值式：

**德摩根律：**$\displaystyle (\neg A\wedge\neg B)\equiv \neg (A\vee B),(\neg A\vee\neg B)\equiv \neg (A\wedge B)$

**蕴涵等值：**$\displaystyle A\rightarrow B\equiv \neg A\vee B$

**假言易位：**$\displaystyle A\rightarrow B\equiv \neg B\rightarrow \neg A$

谓词

在语法上,句子被划分成两部分：主语以及剩下的谓语.谓语告诉我们主语的部分信息.

问题

请指出下方两个句子的主语与谓语.

（1）月球是地球的卫星.

（2）为了抵抗海浪,克努特大帝把脚弄湿了.

习惯了用\(\displaystyle x\)这样的符号来表示为质量的数学家可能会说上述两个句子的谓语分别是

（1）\(\displaystyle x\)是地球的卫星.

（2）为了抵抗海浪,$\displaystyle x$把脚弄湿了.

这种描述方法的好处在于,它写出了主语在句子中的位置,我们只需要把\(\displaystyle x\)替换为合适的主语,就能得到原话.由此产生了如下的数学定义

定义 1.1.3（谓词）

一个谓词是一句有关符号\(\displaystyle x\)的话.当我们把\(\displaystyle x\)替换为元素\(\displaystyle a\in Y\)时,如果得到的陈述非真即假,我们就说该谓词“对于集合\(\displaystyle Y\)是有效的”,记得到的陈述的真值为\(\displaystyle P(a)\).

如果句子中的变量多于一个,如“实数\(\displaystyle x>y\)”,那么它是一个二元谓词,记作\(\displaystyle Q(x,y)\),同理可扩展到多元情况.

已知对集合\(\displaystyle S\)有效的谓词\(\displaystyle P(x)\),想知道它是否对\(\displaystyle S\)中的所有元素均为真,或是\(\displaystyle S\)中是否存在部分元素使得\(\displaystyle P(x)\)为真,可以写出下述命题：

“对所有\(\displaystyle x\in S\),\(\displaystyle P(x)\)为真.”

“对某些$\displaystyle x\in S$,$\displaystyle P(x)$为真.”

可以使用全称量词\(\displaystyle \forall\)和存在量词\(\displaystyle \exists\)来简化这两个命题的表述,分别对应为\footnote{在日常生活中,“某些官员是廉洁的”这种命题是有弦外之音的,但在数学中并非如此,\(\displaystyle \exists x\in S:P(x)\)这句陈述并未暗示确实存在一个\(\displaystyle x\in S\),使得\(\displaystyle P(x)\)为假.}

\(\displaystyle \forall x\in S:P(x)\)

$\displaystyle \exists x\in S:P(x)$

如果同时出现多个量词,一定要注意它们的顺序.

问题

记\(\displaystyle P(x,y)\)是谓词“\(\displaystyle x+y=0\)”,判断下述命题的真值： $\(\displaystyle (a). \forall x\in\mathbb{R},\exists y\in\mathbb{R}:P(x,y)\quad (b). \exists y\in\mathbb{R},\forall x\in\mathbb{R}:P(x,y)\)$

涉及量词的等价式

在前面的几节中，我们发现考察不同公式之间的等价式很有用，本小节将研究一部分涉及量词的等价式。

我们用公式 \(\displaystyle \neg\exists x\,P(x)\) 来陈述“人无完人”，其中 \(\displaystyle P(x)\) 表示“\(\displaystyle x\) 是完美的”，论域是所有人类。但表达相同思想的另一种方式是：每个人都算不上完美，用公式写出是 \(\displaystyle \forall x\,\neg P(x)\)。这两个公式是等价的。类似的推理表明，\(\displaystyle \neg\forall x\,P(x)\) 等价于 \(\displaystyle \exists x\,\neg P(x)\)。说 \(\displaystyle \neg\forall x\,P(x)\) 意味着并非对所有 \(\displaystyle x\) 值 \(\displaystyle P(x)\) 都为真。这等价于说至少有一个 \(\displaystyle x\) 值使 \(\displaystyle P(x)\) 为假，而这正是 \(\displaystyle \exists x\,\neg P(x)\) 的意思。

于是，我们得到下面两条涉及否定和量词的律：

定理

\[\displaystyle \neg\exists x\,P(x)\ \text{等价于}\ \forall x\,\neg P(x).\quad \neg\forall x\,P(x)\ \text{等价于}\ \exists x\,\neg P(x).\]

原命题,逆命题,否命题与逆否命题

我们把形式为“若\(\displaystyle p\),则\(\displaystyle q\)”的命题称为原命题,并且可以通过交换条件与结论,或对他们进行否定来构造出另外三个相关命题.

定义 1.1.5（否命题、逆命题、逆否命题）

设原命题为“若\(\displaystyle p\),则\(\displaystyle q\)”,则

（1）**否命题**为“若$\displaystyle \neg p$,则$\displaystyle \neg q$”；

（2）**逆命题**为“若$\displaystyle q$,则$\displaystyle p$”；

（3）**逆否命题**为“若$\displaystyle \neg q$,则$\displaystyle \neg p$”.

问题

证明：原命题与逆否命题等价,逆命题与否命题等价.

常用的数学证明方法

\paragraph{直接证明法}此处不谈,这是常用的证明方法.

\paragraph{构造证明法}一般用于存在性问题证明,有时需要相当的洞察力,要求对问题结构有着深刻的理解.

\paragraph{反证法}看下面一个情景：母亲和小孩一起玩游戏.

母亲（充满爱意地）：“你是我最喜欢的小兔子.”

孩子（反驳）：“我不是一只兔子！”

母亲\footnote{现实中,很多大人都喜欢和小孩子进行这种毫无意义的,傻乎乎的,却很可爱的对话.}：“你当然是一只小兔子！”

孩子（抗议）：“但是我没有毛茸茸的小尾巴！”

它们所做的事情就是反证的一个简单例子.

假如我是一只小兔子

那么我就会有一个毛茸茸的小尾巴

但是我没有一个毛茸茸的小尾巴

所以我不是一只小兔子

反证法的核心逻辑基于排中律（一个命题要么为真,要么为假,不存在中间状态）.参考上述例子,我们可确定其基本流程：

（1）假设要证明的结论不成立（原命题的否定为真）；

（2）从假设出发经过正确的逻辑推导,得到一个与已知条件,公理,定义或基本事实相矛盾的结果；

（3）既然推导无误,只可能“初始假设”错误,从而证明了原命题为真.

如果

直接证明时感觉待证命题过于宽泛，而其否命题是具体的；

结论中含有“不”、“至少（多）、“唯一”、“无限”、“不存在”等词语

时,可以优先考虑反证法.

\paragraph{数学归纳法}将在第二章详细介绍.

A 组习题

习题

A组

1. 【2010 湖南适应性训练2】 下列命题中,\(\displaystyle (\triangle)\)是真命题.

   • \(\displaystyle \forall x \in \mathbb{R}, x^3 \geqslant x^2\)
   • \(\displaystyle \forall x \in \mathbb{R}, x^3 < x^2\)
   • \(\displaystyle \forall x \in \mathbb{R}, \exists y \in \mathbb{R}, y^2 < x\)
   • \(\displaystyle \exists x \in \mathbb{R}, \forall y \in \mathbb{R}, y \cdot x = y\)
   答案

   D.

   1. 【2013 山东文 8理 7】 给定两个命题 \(\displaystyle p, q\)．若 \(\displaystyle \neg p\) 是 \(\displaystyle q\) 的必要而不充分条件,则 \(\displaystyle p\) 是 \(\displaystyle \neg q\) 的

   2. 充分不必要条件

   3. 必要而不充分条件
   4. 充要条件
   5. 既不充分也不必要条件