（1）逻辑和证明

2019-10-20 本文已影响0人古剑诛仙

本系列是离散数学及其应用第七版与北京交通大学的离散数学课程的个人笔记，章节顺序以书为准

本章内容完全从数学定义上学习，建议看之前读一下王路的逻辑基础做铺垫，深入可以看数理逻辑

1.命题逻辑

命题是一个陈述语句，它或真或假，但不能同时成立，使用一个字母代表命题变元，其值为true或false

image.png

命题联结词

image.png

事实上，有多种记法：

image.png

合取：命题p和q，当两者同真时才为真，即p且q，记作 $p∧q$ （当初记忆时为了和∨区别合字上面的的人正好和∧相似这样就很容易记住了）

image.png
析取：命题p和q，有一者为真即为真，即p或q，记作 $p∨q$
image.png
非：命题p的否命题记作 $¬p$ ，或~p
image.png
异或：命题p和q，两者相反即为真，相同为假，即p异或q，记作 $p\oplus q$ ，也称为不可兼或

条件语句

命题p和q，条件语句 $p\to q$ 或 $p\Rightarrow q$ 表示命题“如果p，则q”。当p为真而q为假时，条件语句 $p\to q$ 为假，其余情况都为真。在条件语句中，p称为假设或前提，q称为结论。其真值表如下

image.png

条件语句 $p\to q$ 可以理解为如下等价的语句

image.png

等价形式中，值得注意的是以下两种：

p仅当q可以理解为当q不为真时，p一定为假，也就是说当q为假，p为真时，q仅当p这条语句为假。p为假时，q可以为真也可以为假。
q除非 $¬p$ 可以理解为如果 $¬p$ 是假的，即p是真的，则q必然是真的

自然语言与符号的对照

image.png

几种特殊情况

image.png

符号化的通用原则

image.png

下面是一些例子

image.png

条件语句的逆命题，否命题，逆否命题
对 $p\to q$ 来说，其逆命题为 $q\to p$ ，否命题为 $¬p\to ¬q$ ，逆否命题为 $¬q\to ¬p$
对于任意命题，其原命题和逆否命题是等价的，否命题与逆命题也是等价的，但上述两种情况却不是等价的

双条件语句
对命题p和q， $p\leftrightarrow q$ 或 $p\Leftrightarrow q$ 表示p当且仅当q。也就是说p和q具有相同的真值时，双条件语句为真，否则为假。可以理解为如下等价的语句：

p是q的充分必要条件
如果p那么q，反之亦然

即 $p\leftrightarrow q$ 等价于 $(p\to q)∧(q\to p)$

双条件与条件语句的区别：
如果下雨，主队就能获胜；（除了下雨之外可能还有别的办法也可以获胜）
主队能获胜当且仅当下雨；（除了下雨，没有其他办法获胜了）

综合 $A\to B,B\to A,A\leftrightarrow B$ 三种情况

image.png
也就能够理解对应A仅当B，对应A当B，对应A当且仅当B的含义了

逻辑运算符的优先级

image.png
由上向下递减

2. 命题逻辑的应用

语句翻译
大体遵循以下原则

image.png

命题的符号化遵循以下规则

image.png

复杂命题的示例：

image.png

命题公式
格式要求：对命题公式形如p,q,r...来说， $¬p,¬(p),(p∧q),(p∨q),(p\to q),(p\leftrightarrow q)$ 的组合嵌套使用都是命题，其中使用了n个命题变元，就属于n元命题公式
在括号的书写上，只有满足以下要求

image.png
的情况，可以省略括号（同优先级的情况括号不能省略）

对于n元命题公式A，其含有 $p_1,p_2...p_n$ 命题变元，则这组命题变元的一组确定真值称为该命题公式的一个真值指派（表示为一串长度为n的01序列），若这组真值指派使得A为真，则称为成真指派，若这组真值指派使得A为假，则称为成假指派。可以通过真值表直观的理解复杂命题。

对于n元命题公式A，若其所有 $2^n$ 个真值指派都是成真指派，则称A为永真式或重言式，若其所有 $2^n$ 个真值指派都是成假指派，则称A为永假式或矛盾式，若其至少存在一个成真指派，则称A为可满足式，若A至少存在一个成真指派与成假指派，则称A为非重言的可满足式

任意两个重言式的析取或合取仍然是重言式，任意两个矛盾式的析取或合取依然是矛盾式

真值表的使用规则

image.png

命题等价式

如果对于命题公式A与B，有 $A\leftrightarrow B$ 是永真式，则命题A与B是逻辑等价的，记作 $A\equiv B$

注意这并不是一个命题，恒等也不是一个逻辑联结词
如果 $p_1,p_2,...,p_n$ 是A,B中出现的全部命题变项，则A与B是逻辑等价的当且仅当任意一组命题变项的真值指派，对A，B的产生的结果是相同的

等值演算是指由已知的等值式推演出新的等值式的过程

判断两个命题公式等值的办法

image.png

下面是真值表法的示例

image.png

显然当命题变项过多时，列写真值表是很麻烦的一件事，此时使用等值演算，基于一些基本的逻辑等价式，对复杂的逻辑式应用代入规则和替换规则化简后比较

image.png

在此之上还有一些常用的

$p∨q≡\sim p\to q$
$p∧q≡\sim (p\to \sim q)$
$(p\to q)∧(p\to r)≡p\to(q∧r)$
$(p\to r)∧(q\to r)≡(p∨q)\to r$
$(p\to q)∨(p\to r)≡p\to(q∨r)$
$(p\to r)∨(q\to r)≡(p∧q)\to r≡p\to(q\to r)≡q\to(p\to r)$
$p\leftrightarrow q≡(p∧q)∨(\sim p\ ∧\sim q)$
$\sim(p\leftrightarrow q)≡p\leftrightarrow \sim q$
$p \oplus q ≡\sim(p\leftrightarrow q)≡(p\leftrightarrow \sim q)≡(\sim p\leftrightarrow - q)$

代入规则

image.png

替换规则

image.png

几个例子

image.png

image.png

即可知，p,r为假，q,s为真

对偶

定义：在仅含有连接词~，∧，∨的命题公式A中，将∧∨相互取代，T和F也这么做，所得命题称为A的对偶式，记作 $A^*$ ，显然 $(A^*)^*=A$

性质1：在仅含有连接词~，∧，∨的命题公式A中， $p_1,p_2...p_n$ 是其命题变项，则有
$\sim A(p_1,p_2...p_n)\equiv A^*(\sim p_1,\sim p_2...\sim p_n)$
推论：在仅含有连接词~，∧，∨的命题公式A中，若A为重言式，则 $A^*$ 为矛盾式

性质2：在仅含有连接词~，∧，∨的命题公式A与B中，若 $A\equiv B$ ，则 $A^*\equiv B^*$

范式

image.png

显然，析取式是重言式当且仅当其中出现互补对，合取式是矛盾式当且仅当其中出现互补对

image.png

性质：

image.png

求范式的步骤：

image.png

示例：

image.png

极小项与极大项

极小项

image.png

极大项

image.png

比较

image.png

主范式

提出主范式的原因

image.png

主析取范式

image.png

而实际上，将2,4,5,6,7转化为二进制数，再化为命题变元的表示，也就是所有原命题的成真指派

主合取范式

image.png

而实际上，将0,1,3转化为二进制数，再化为命题变元的表示（跟析取相反），也就是所有原命题的成真指派

两种范式的转换

image.png

主范式的意义

image.png

联结词的完备集
我们已经知道了很多联结词，有一元的比如取反，剩下的都是二元的，但对任意一个有n个命题变项的命题公式A，我们使用多少个联结词就能通过与命题变项的组合把A完整的表述出来呢？

定义：设C是一个联结词的集合，如果任何由n个命题变项组成的命题公式都存在仅使用C中的联结词构成的等值公式，则称C是完备的联结词集合，或联结词的完备集。同时当 C是一个联结词的完备集时，C中某个联结词可以通过其他联结词表达出来，这个联结词叫冗余联结词。不含有冗余联结词的联结词的完备集叫极小完备集。

定理1：如果对联结词完备集A来说，其中所有联结词都可以通过联结词集合B中的联结词表达出来，那么B也是联结词的完备集

定理2：以下常见联结词集合都是完备集

{~,∧,∨} 显然这不是一个极小完备集，∧,∨都是冗余联结词（两者只有一个即可）
{~,∧}
{~,∨}
{~, $\to$ }

其证明如下

有上节内容，根据命题公式的主析取范式的唯一性，而主析取范式由这三种联结词构成，所以是完备集
$p∨q\equiv \sim\sim(p∨q)\equiv\sim(\sim p\ ∧\sim q)$ ，且1是完备集，故2也是完备集
$p∧q\equiv \sim\sim(p∧q)\equiv\sim(\sim p\ ∨\sim q)$ ，且1是完备集，故3也是完备集
$p∨q\equiv \sim(\sim p)∨q\equiv\sim p\to q$ ，且3是完备集，故4也是完备集

再给出两个二元联结词

与非：对命题p,q，p与非q，记作 $p\uparrow q$ ，表示仅当p,q均为真时，p与非q为假，等值表示为 $p\uparrow q\equiv\sim (p∧q)$

或非：对命题p,q，p或非q，记作 $p\downarrow q$ ，表示仅当p,q均为假时，p或非q为真，等值表示为 $p\downarrow q\equiv\sim (p∨q)$

下面证明这两个联结词是完备集
与非： $\sim p\equiv\sim(p∧p)\equiv p\uparrow p,p∧q\equiv \sim\sim(p∧q)\equiv \sim( p\uparrow q)$

上面的完备集中，至少需要两个联结词，而与非，或非本身已经是完备集，这也解答了为什么逻辑电路中，选用或非门或者与非门的一种，就可以构造出全部的逻辑电路（而现实中也的确是这么做的）

命题的逻辑推理

基于国内外教材顺序的不同，本小节内容建议先阅读离散数学及其应用1.6节至1.8节内容后再来学习

image.png

这里补充一下，之前我们用 $p\to q$ 表示p蕴含q，在推理证明部分我们用 $p\Rightarrow q$ 式表示蕴含式 $p\to q$ 为永真式，即

image.png

也就是说我们只关注p为真时，q也为真，而不在意p为假时，q的真假（而p蕴含q则包括这一情况）

image.png

其实使用演绎法会发现最后是~p与~q间的关系，这是无论如何也无法用符号联结的

image.png

演绎法

image.png

前后件附加
$(A\Rightarrow B)\Rightarrow ((A∨C)\Rightarrow(B∨C))$
$(A\Rightarrow B)\Rightarrow ((A∧C)\Rightarrow(B∧C))$
$(A\Rightarrow B)\Rightarrow ((C\Rightarrow A)\Rightarrow(C\Rightarrow B))$
对偶 $(A\Rightarrow B)\Rightarrow(B^*\Rightarrow A^*)$

image.png

名词初看比较唬人，下面写一些自己的理解：

image.png

（1）逻辑和证明

1.命题逻辑

2. 命题逻辑的应用

猜你喜欢

热点阅读