信息安全原理与数学基础(二)

基本信息

授课教师：zbs

 

Lecture 03

周日补课, 达咩

逻辑学

探索, 阐述和确立有效推理原则的科学

三段论学说

$大前提+小前提=结论$

仍然以自然语言描述, 自然语言具有模糊性

 

数理逻辑

利用计算的方法开替代人们思维中的逻辑推理过程

四大分支

• 公理化集合论
• 证明论
• 递归论
• 模型论

本课程介绍的是四大分支的共同部分

 

命题 (proposition)

定义 对确定的对象作出判断的陈述句

• 如果判断正确, 称为真(true)命题
• 否则称命题为假(false)命题
• 真与假是命题的属性, 称为真值

要点 陈述句; 判断; 确定的对象

• 真值是命题的固有属性, 但是否知道真值和真值是否存在没有关系
• 悖论不能作为命题
• 命题非真即假 – 排中律 (基本假设)

反证法利用了排中律

 

原子命题和复合命题

• 逻辑联结词 logical connectives
• 原子命题 atom proposition
• 复合命题 compound proposition

 

逻辑符号

真值

真为 1, 假为 0

逻辑联结词用真值表定义

否定词 negation

非(not) $\lnot$

合取词 conjunction

并且(and) $\land$

析取词 disjunction

或(or) $\lor$

自然语言中的 “或”, 可能被解释为逻辑上的 “异或”(xor)

真值表中, 有 n 个原子命题, 就会有 $2^n$ 行代表等数量的可能性

蕴涵词 implication

如果…那么…(if…then…) $\to$

$p\to q$ 中, $p$ 为蕴涵前件, $q$ 为蕴涵后件

$当且仅当, p=1,q=0时, p\to q=0$

当前件为假时, 无法判断后件, 因此蕴涵词取 1

双向蕴涵词 two-way implication

当且仅当(if and only if) $\lrarr$

$p\lrarr q中, p和q同真同假$

 

命题公式 proposition formula

命题常元 proposition constants

• 表示具体命题以及常命题的 $p,q,r,s$
• 真值 $\mathrm{T},\mathrm{F}$

命题变元 proposition variables

• 表示命题的 $p,q,r,s$ 

命题公式的定义

• 命题常元和命题变元是命题公式
• 如果 $A,B$ 是命题公式，那么其逻辑组合也是命题公式
• 只有有限步应用上述两条组成的符号串是命题公式

我们约定逻辑连接词的 优先级顺序

1. $\lnot$
2. $\land,\lor$
3. $\to$
4. $\lrarr$

优先级相同，从左到右的次序结合

蔚来员工：我不敢买蔚来的车了，因为我写的代码都上线了

 

真值函数

变元和函数值的取值范围都是 $\lbrace 0,1\rbrace$

对于每一个赋值，公式均有一个确定的函数真值

真值表

当 $A(p_1,p_2,…,p_n)$ 包含 $k$ 个联结词时，$A$ 的真值表应为 $(2^n)\times(n+k)$

成真赋值和成假赋值

 

自然语言的形式化

1. 善于确定原子命题
2. 善于辨别联结词
3. 对于涉及多个对象的否定词，位置要精准
4. 不要省略必要的括号
5. 有时候形式化结果不是唯一的，可能具有不同的形式，但是逻辑上是等价的

 

命题公式的分类

1. 永真式 tautology
2. 永假式
3. 可满足式

重言式的例子和证明

1. $\forall A,A\lor\lnot A=1$
2. $\forall A,A\land\lnot A=0$

证明：真值表大法好

 

Lecture 04

逻辑等价式

$A\equiv B$

E1～E17

1. $\lnot\lnot A\equiv A$
2. $A\land A\equiv A;A\lor A\equiv A$
3. 交换律
4. 结合律
5. $A\land(B\lor C)\equiv(A\land B)\lor(A\land C);A\lor(B\land C)\equiv(A\lor B)\land(A\lor C)$
6. 德摩根定律 $\lnot(A\land B)\equiv \lnot A \lor\lnot B$
7. 吸收率 $A\lor(A\land B)\equiv A;A\land(A\lor B)\equiv A$
8. 蕴涵等值式 $A\to B\equiv\lnot A\lor B$
9. $A\lrarr B\equiv (A\to B)\land (B\to A)$
10. 零律 $A\lor T\equiv T;A\land F\equiv F$
11. 同一律
12. 排中矛盾律
13. $\lnot T\equiv F;\lnot F\equiv T$
14. $A\land B\to C\equiv A\to(B\to C)$
15. 假言易位 $A\to B\equiv \lnot B\to\lnot A$
16. 归谬论 $(A\to B)\land(A\to\lnot B)\equiv\lnot A$
17. $A\lrarr B\equiv (A\land B)\lor(\lnot A\land\lnot B)$

tip 推演的时候要写出运用的公式

 

逻辑蕴涵式

如果 $A$ 的所有成真赋值都是 $B$ 的成真赋值，那么记作 $A\models B$

L1～L8

1. $A\models A\lor B$
2. $A\land B\models A$
3. $A\land(A\to B)\models B$
4. $(A\to B)\land\lnot B\models \lnot A$
5. $\lnot A\land(A\lor B)\models B$
6. $(A\to B)\land(B\to C)\models A\to C$
7. $(A\to B)\land(C\to D)\models (A\land C)\to(B\land D)$
8. $(A\lrarr B)\land(B\lrarr C)\models A\lrarr C$

逻辑结果

逻辑蕴涵常被推广为 $\Gamma\models B$

• $\Gamma$ 是一系列的公式
• 若$\Gamma\equiv\empty$，记作$\models B$，B永真

重要性质

自反，对称，传递

 

重言式的代入原理

将重言式 $A$ 中每个命题变元 $p$ 的所有出现都代换为 $B$，记作 $A(B/p)$，也是重言式

命题公式的替换原理

将命题公式 $A$ 中的子公式 $C$ 部分的替换为等价的 $D$，得到的新公式为$B$，则 $A\equiv B$

 

范式

在多个逻辑等价的公式中，较为符合规范或标准的形式

• 文字：命题常元，变元及其否定
• 析取子句：文字或若干文字的析取
• 合取字句：文字或若干文字的合取
• 互补文字对：一对正文字和负文字

析取范式DNF

若 $A^\prime$ 等价于 $A$，且 $A^\prime$ 为合取子句或若干合取子句的析取，称为析取范式

$A_1\lor A_2\lor A_3\lor…\lor A_n$

 

合取范式CNF

若 $A^\prime$ 等价于 $A$，且 $A^\prime$ 为析取子句或若干析取子句的合取，称为合取范式

$A_1\land A_2\land A_3\land…\land A_n$

 

重言式与矛盾式的判断

识别重言式

• 若合取范式的每个析取字句都至少包含了一个互补文字对

识别矛盾式

• 若析取范式的每个合取子句都至少包含了一个互补文字对

利用德摩根律让 $\lnot$ 向内深入，最后只作用于文字

 

主范式

一个公式的析取范式和合取范式都不是唯一的
一个公式的析取范式本身又可能是合取范式

主析取/合取范式

若 $A^\prime$ 是主析取/合取范式，则在其每个子句里，所有变元 $p_1,p_2,…,p_n$ 均恰巧出现一次

以主析取范式为例，约定：

1. 对合取子句按照其变元下标从小到大排列，记作 $m_i$
2. $i$ 对应的 n-bit 二进制数表示描述了对应下标的变元在该合取子句中的否定状态（0表示负文字，否则是正文字）
3. 定义主范式为下标从小到大的极小项的排列

则

• 极小项只有唯一的成真赋值，等于其下标的二进制形式中各 bit 的值
• 极小项的成真赋值与主析取范式的成真赋值的关系

之前还在讲数学危机

对于主合取范式，讨论对应的极大项，成假赋值即可

 

存在性

若某个合取子句 $A$ 既不包含 $p_j$ ，也不包含 $\lnot p_j$ ，则：

$$A\equiv A\land 1\equiv A\land(p_j\lor\lnot p_j)\equiv (A\land p_j)\lor (A\land\lnot p_j)$$

若出现重复的 $p$ ，则可以消去

唯一性

反证法：假设 $B$ 和 $C$ 是不同的主析取范式

则存在某个极小项是 $B$ 的成真却不是 $C$ 的成真

矛盾

 

公式的等值分类

等值的数量等于主析取范式的数量

• 极小项的数量为 $N = 2^n$
• 主析取范式的数量为 $2^N$

 

Lecture 05

真值函数

真值函数 $F(p_1,p_2,…,p_n)$ 与等值类相对应

若任意真值函数都可以用仅包含某个联结词集中的联结词的命题公式表示，则这个联结词集被称为功能完备集

 

功能完备集

$\lbrace\lnot,\land(,\lor)\rbrace$

冗余联结词

可以被集合中其他联结词定义的联结词

• $\to$
• $\lrarr$
• $\land/\lor!!$

称不包含冗余联结词的功能完备集为极小完备集

 

仅包含一个联结词的功能完备集

定义 Peirce 记号 $\darr:p\darr q\equiv\lnot(p\lor q)$

$\lbrace\darr\rbrace$ 是功能完备集

 

形式系统（仅做了解）

• 是一个符号体系
• 以若干基本的重言式为基础，称为公理
• 确保重言式导出重言式

证明

称公式序列 $A_1,A_2,…,A_m$ 为 $A_m$ 的证明，若 $A_i$

• 是公理
• 由前者用推理规则推得

则 $A_m$ 是定理

 

演绎

设公式序列 $A_1,A_2,…,A_m$ 是以 $\Gamma$ 为前提的推理，若 $A_i$

• 是 $\Gamma$ 的公式
• 是公理
• 由前者用推理规则推得

则 $A_m$ 是 $\Gamma$ 的演绎结果

 

命题演算形式系统 PC

定义

1. 是 PC 的符号系统
2. 命题变元和命题常元
3. 联结词 $\lnot,\to$
4. 括号
5. 命题公式

PC 的公理

• $A\to(B\to A)$
• $(A\to(B\to C))\to((A\to B)\to(A\to C))$
• $(\lnot A\to\lnot B)\to(B\to A)$

PC 的推理规则

• $A,A\to B/B$

PC 的性质

1. 合理性

   不出错

2. 一致性

   不矛盾

3. 完备性

   全知全能

 

元定理

演绎定理

• $\Gamma\vdash_{PC} A\to B\iff\Gamma\cup\lbrace A\rbrace\vdash_{PC} B$
• $\mathrm{If}\ \Gamma=\empty,\mathrm{then}\ \vdash_{PC} A\to B\iff \lbrace A\rbrace\vdash_{PC} B\ \mathrm{or}\ A\vdash_{PC} B$

 

归谬定理

$\forall\ \Gamma,A,B,\mathrm{if}\ \Gamma\cup\lbrace\neg A\rbrace\vdash_{PC}B,\Gamma\cup\lbrace\neg A\rbrace\vdash_{PC}\lnot B,\mathrm{then}\ \Gamma\vdash_{PC}A$

• 若同一组前提能推导出相互矛盾的结果， 说明这组前提之间相互不一致
• 总有一些前提的其余前提的对立面

 

穷举定理

$\forall\ \Gamma,A,B,\mathrm{if}\ \Gamma\cup\lbrace A\rbrace\vdash_{PC}B,\Gamma\cup\lbrace\neg A\rbrace\vdash_{PC}B,\mathrm{then}\ \Gamma\vdash_{PC}A$

 

Lecture 06

谓词逻辑

结构分析

• 命题
• 被判断的对象：个体
• 判断：谓词
• 个体的数量：量词

 

个体

一切被讨论的对象

• 确定的个体常用 $a,b,c$ 表示，称作个体常元
• 不确定的个体常用 $x,y,z,u,v,w$ 表示，称作个体变元
• 被讨论的对象的全体用 $D$ 表示，称作个体域
• 包含所有对象的全体叫做全体域，记作 $U$

 

谓词

表示个体性质和关系的语言成分

谓词命名式

如 $P(x),Q(x,y)$
命名式中的变元字母没有独立含义，仅是占位符

谓词填式

 

量词

1. 全称量词 $\forall$
2. 存在量词 $\exists$

量词作用于谓词时，需要引入指导变元

指导变元是不可取值代入的，称作约束变元
可以取值代入的被称为自由变元

量词作用的谓词或复合谓词表达式，称作量词的辖域

 

谓词公式

定义

谓词填式是公式，命题常元是公式
公式与公式的逻辑运算结果也是公式

$\forall xP(x)$ 中，后者可以不出现 $x$

 

成为命题

给定个体域，公式中的所有谓词都有明确意义，公式中的所有自由变元取定个体

数学公式可以代替公式