信息安全数学基础

信息安全数学基础第一页，共四十二页，2022年，8月28日一阶语言L一阶语言L是经典谓词（一阶）逻辑的形式语言一阶语言L是符号的集合个体符号：abc…关系符号：FGH…特别的，≡函数符号：fgh…自由变元符号：uvw…约束变元符号：xyz…联结符号：¬

∧∨→↔量词符号：标点符号：（，）注意：在一阶语言中没有命题符号。一阶语言L的含义本质上不涉及语义，而只有语法。第二页，共四十二页，2022年，8月28日表达式表达式：L中有限个符号组成的字符串表达式的长度：表达式中的符号数目空表达式：长度为0的表达式，记为表达式相等：U=Viff表达式U和V中符号依次相同表达式U和V依次并列形成新的表达式UV，且若表达式U=W1VW2，则V是U的段。若V是U的段且V和U不相等，则V是U的真段。初始段、结尾段、真初始段、真结尾段第三页，共四十二页，2022年，8月28日Term(L)的归纳定义Term(L)的定义

i）a，u∈Term(L)ii）若t1，t2，…

，tn∈Term(L)，且f为n元函数符号，则f(t1，t2，…

，tn)∈Term(L)iii）t是能由有限次应用i）—ii）形成的表达式ifft∈Term(L)不含自由变元的项被称为闭项。t表示项。Term(L)的归纳证明原理。第四页，共四十二页，2022年，8月28日项的结构定理：Term(L)中的项具有以下三种形式之一：个体符号，自由变元符号，f(t1，t2，…

，tn)，其中f为n元函数符号；且项具有的形式是唯一的。定理：若t是f(t1，t2，…

，tn)的段，则t=f(t1，t2，…

，tn)或t为ti（i=1，2，…，n）的段。第五页，共四十二页，2022年，8月28日Atom(L)的定义Atom(L)的定义

L的表达式是Atom(L)的元素，当且仅当它为下列情况之一：

i）F(t1，t2，…

，tn)，其中F为n元关系符号，t1，t2，…

，tn∈Term(L)。ii）≡(t1，t2)，其中≡为相等关系符号，t1，t2∈Term(L)。第六页，共四十二页，2022年，8月28日Form(L)的归纳定义（一）合式公式集Form(L)i）Atom(L)⊆Form(L)ii）若A∈Form(L)，则(﹁A)∈Form(L)iii）若A，B∈Form(L)，则(A*B)∈Form(L)。其中*表示∧，∨，→，↔中的任何一个iv）若A(u)∈Form(L)，且x不在A(u)中出现，则∀xA(x)，∃xA(x)

∈Form(L)v）A是能由有限次应用i）—iv）形成的表达式iffA∈Form(L)第七页，共四十二页，2022年，8月28日Form(L)的归纳定义（二）不含自由变元的公式被称为闭公式或语句，Sent(L)表示所有语句构成的集合。含有某个约束变元而不含它的量词的表达式被称为拟公式。拟公式不是公式。

A，B，C表示公式、拟公式。第八页，共四十二页，2022年，8月28日Form(L)的归纳证明原理定理：设R是一个性质，若

i）对于任何p∈Atom(L)，R(p)；

ii）对于任何A∈Form(L)，若R(A)，则R((﹁A))；

iii）对于任何A，B∈Form(L)，若R(A)且R(B)，则R((A*B))。其中*表示∧，∨，→，↔中的任何一个；

iv）对于任何A(u)∈Form(L)，若R(A(u))，且x不在A(u)中出现，则R(∀xA(x))，R(∃xA(x))。则对于任何A∈Form(L)，R(A)。第九页，共四十二页，2022年，8月28日公式结构定理：L的每一公式恰好具有以下8种形式之一：原子公式，(﹁A)，(A∧B)，(A∨B)，(A→B)，(A↔B)，∀xA(x)，∃xA(x)

；并且在各种情形，公式所具有的那种形式是唯一的。第十页，共四十二页，2022年，8月28日公式的语法分类原子公式复合公式否定式合取式析取式蕴含式等值式全称式存在式第十一页，共四十二页，2022年，8月28日辖域若(﹁A)是C的段，则称A为它左方的﹁在C中的辖域若(A*B)是C的段，则称A和B分别为它们之间的*在C中的左辖域和右辖域。其中*表示∧，∨，→，↔中的任何一个若∀xA(x)或∃xA(x)是B的段，则称A(x)为∀x或∃x在B中的辖域

定理：任何A中的任何﹁（如果有）有唯一的辖域；任何A中的任何*（如果有）有唯一的左辖域和右辖域；任何A中的任何∀x或∃x（如果有）有唯一的辖域定理：若A是(﹁B)的段，则A=(﹁B)或A是B的段；若A是(B*C)的段，则A=(B*C)或A是B的段或A是C的段；若A是∀xB(x)或∃xB(x)的段，则A=∀xB(x)或∃xB(x)，或A是B(x)的段。第十二页，共四十二页，2022年，8月28日形式可推演用∑表示任何公式集，即∑⊆Form(L)。∑∪{A}可以记为∑，A。∑∪∑’可以记为∑，∑’。若∑={A1,A2,A3,…}，则∑可以记为A1,A2,A3,…。∑├A表示A由∑形式可推演（形式可证明）的。其中，∑为前提，A为结论。├不是L中符号。∑├A不是公式。A├┤B表示“A├B并且B├A”，并称A和B是语法等值的。第十三页，共四十二页，2022年，8月28日一阶逻辑的推演规则（一）共11+6条，A，B，C为公式(Ref)A├A(+)若∑├A， 则∑，∑’├A(﹁-)若∑，﹁A

├B，

∑，﹁A

├﹁B，则∑├A(→-)若∑├A→B，

∑├A，则∑├B(→+)若∑，A├B，

则∑├A→B(∧-)若∑├A∧B，则∑├A，∑├B

(∧+)若∑├A

，

∑├B

，则∑├A∧B

(∨-)若∑，A├C，∑，B├C，则∑，A∨B├C(∨+)若∑├A

，则∑├A∨B，

∑├B∨A(↔-)若∑├A↔B，∑├A，则∑├B

若∑├A↔B，∑├B，则∑├A(↔+)若∑，A├B，∑，B├A，则∑├A↔B

第十四页，共四十二页，2022年，8月28日一阶逻辑的推演规则（二）(∀-)若∑├∀xA(x)，则∑├A(t)(∨+)若∑├A(u)，u不在∑中出现，则∑├∀xA(x)(∃-)若∑，A(u)├B，u不在∑，B中出现，则∑，∃xA(x)├B(∃+)若∑├A(t)，则∑├∃xA(x)，其中A(x)是在A(t)中把t的某些（不一定全部）出现替换成x而得。(≡-)若∑├A(t1)，∑├t1≡t2，则∑├A(t2)，其中A(t2)是在A(t1)中把t1的某些（不一定全部）出现替换成t2而得。(≡+)Ф├u≡u第十五页，共四十二页，2022年，8月28日形式推演的定义A是在一阶逻辑中由∑形式可推演（形式可证明）的，记为∑├A，当且仅当∑├A能有限次使用一阶逻辑中形式推演规则生成。这是一个归纳定义。关于归纳证明。一个有限序列∑1├A1，∑2├A2，…，∑n├An被称为∑n├An的形式证明。其中，∑k├Ak（1≤k≤n）由使用某一推演规则而生成。第十六页，共四十二页，2022年，8月28日证明：¬∀xA(x)├┤∃x(¬A(x))证：先证¬∀xA(x)├∃x(¬A(x))。

(1)¬A(u)├¬A(u)u不在A(x)中出现(Ref)(2)¬A(u)├∃x(¬A(x))(∃+)(1)(3)¬∃x(¬A(x))，¬A(u)├∃x(¬A(x))(+)(2)(4)¬∃x(¬A(x))，¬A(u)├¬∃x(¬A(x))(∈)(5)¬∃x(¬A(x))├A(u)(¬-)(3)(4)(6)¬∃x(¬A(x))├

∀xA(x)(∀+)(5)(7)¬∀xA(x)，¬∃x(¬A(x))├

∀xA(x)(+)(6)(8)¬∀xA(x)，¬∃x(¬A(x))├

¬∀xA(x)(∈)(9)¬∀xA(x)├∃x(¬A(x))(¬-)(7)(8)第十七页，共四十二页，2022年，8月28日再证∃x(¬A(x))

├¬∀xA(x)。(1)∀xA(x)

├∀xA(x)(Ref)(2)∀xA(x)

├A(u)u不在A(x)中出现(∀-)(1)(3)﹁A(u)，∀xA(x)

├A(u)(+)(2)(4)﹁A(u)，∀xA(x)

├﹁A(u)(∈)(5)﹁A(u)├

﹁∀xA(x)

(﹁+)(3)(4)(6)∃x(¬A(x))

├¬∀xA(x)

(∃-)(5)第十八页，共四十二页，2022年，8月28日证明：∀x(A(x)→B(x))├∀xA(x)→∀xB(x)证：(1)∀x(A(x)→B(x))├∀x(A(x)→B(x))(Ref)(2)∀x(A(x)→B(x))├A(u)→B(u)(∀-)(1)u不在A(x)和B(x)中出现(3)∀x(A(x)→B(x))，∀xA(x)├A(u)→B(u)(+)(2)(4)∀x(A(x)→B(x))，∀xA(x)├∀xA(x)(∈)(5)∀x(A(x)→B(x))，∀xA(x)├A(u)(∀-)(4)(6)∀x(A(x)→B(x))，∀xA(x)├B(u)(→-)(3)(5)(7)∀x(A(x)→B(x))，∀xA(x)├∀xB(x)(∀+)(6)(8)∀x(A(x)→B(x))├

∀xA(x)→∀xB(x)(→+)(7)第十九页，共四十二页，2022年，8月28日证明：∀x(A(x)→B(x))├∃xA(x)→∃xB(x)证：(1)∀x(A(x)→B(x))├∀x(A(x)→B(x))(Ref)(2)∀x(A(x)→B(x))├A(u)→B(u)(∀-)(1)u不在A(x)和B(x)中出现(3)∀x(A(x)→B(x))，A(u)├A(u)→B(u)(+)(2)(4)∀x(A(x)→B(x))，A(u)├A(u)(∈)(5)∀x(A(x)→B(x))，A(u)├B(u)(→-)(3)(4)(6)∀x(A(x)→B(x))，A(u)├∃xB(x)(∃+)(5)(7)∀x(A(x)→B(x))，∃xA(x)├∃xB(x)(∃-)(6)(8)∀x(A(x)→B(x))├

∃xA(x)→∃xB(x)(→+)(7)第二十页，共四十二页，2022年，8月28日证明：∀x(A(x)→B(x))，∀x(B(x)→C(x))├∀x(A(x)→C(x))证：(1)∀x(A(x)→B(x))├∀x(A(x)→B(x))(Ref)(2)∀x(A(x)→B(x))├A(u)→B(u)(∀-)(1)u不在A(x)、B(x)和C(x)中出现(3)∀x(A(x)→B(x))，∀x(B(x)→C(x))，A(u)├A(u)→B(u)(+)(2)(4)∀x(A(x)→B(x))，∀x(B(x)→C(x))，A(u)├A(u)(∈)(5)∀x(A(x)→B(x))，∀x(B(x)→C(x))，A(u)├B(u)(→-)(3)(4)(6)∀x(A(x)→B(x))，∀x(B(x)→C(x))，A(u)├∀x(B(x)→C(x))(∈)(7)∀x(A(x)→B(x))，∀x(B(x)→C(x))，A(u)├B(u)→C(u)(∀-)(6)(8)∀x(A(x)→B(x))，∀x(B(x)→C(x))，A(u)├C(u)(→-)(5)(7)(9)∀x(A(x)→B(x))，∀x(B(x)→C(x))├A(u)→C(u)(→+)(8)(10)∀x(A(x)→B(x))，∀x(B(x)→C(x))├

∀x(A(x)→C(x))(∀+)(9)第二十一页，共四十二页，2022年，8月28日证明：A→∀xB(x)

├┤∀x(A→B(x))。x不在A中出现。证：先证A→∀xB(x)

├

∀x(A→B(x))。

(1)A→∀xB(x)，A├

A→∀xB(x)(∈)(2)A→∀xB(x)，A├

A

(∈)(3)A→∀xB(x)，A├∀xB(x)(→-)(1)(2)(4)A→∀xB(x)，A├B(u)(∀-)(3) u不在A和B(x)中出现

(5)A→∀xB(x)├A→B(u)(→+)(4)(6)A→∀xB(x)

├

∀x(A→B(x))(∀+)(5)第二十二页，共四十二页，2022年，8月28日再证∀x(A→B(x))├

A→∀xB(x)

。(1)∀x(A→B(x))，A├

∀x(A→B(x))(∈)(2)∀x(A→B(x))，A├A→B(u)(∀-)(1)u不在A和B(x)中出现(3)∀x(A→B(x))，A├A(∈)(4)∀x(A→B(x))，A├B(u)(→-)(2)(3)(5)∀x(A→B(x))，A├∀xB(x)(∀+)(4)(6)∀x(A→B(x))├A→∀xB(x)(→+)(5)第二十三页，共四十二页，2022年，8月28日证明：A(t1)，t1≡

t2├A(t2)证：

(1)A(t1)，t1≡

t2

├A(t1)(∈)(2)A(t1)，t1≡

t2

├t1≡

t2

(∈)(3)A(t1)，t1≡

t2

├A(t2)(≡-)(1)(2)第二十四页，共四十二页，2022年，8月28日证明：Ф├t

≡

t证：

(1)Ф├u

≡

u(≡+)(2)Ф├∀x(x

≡

x)(∀+)(1)(3)Ф├t≡

t(∀-)(2)第二十五页，共四十二页，2022年，8月28日证明：t1≡

t2├t2≡

t1证：

(1)Ф├t1≡

t1

(已证)(2)t1≡

t2├t1≡

t1

(+)(1)(3)t1≡

t2├t1≡

t2

(Ref)(4)t1≡

t2

├t2≡

t1(≡-)(2)(3)第二十六页，共四十二页，2022年，8月28日证明：A(t)├┤∀x(x≡

t→A(x))证：先证A(t)├

∀x(x≡

t→A(x))(1)A(t)，u

≡

t├A(t)(∈)u不在A(t)中出现。

(2)A(t)，u

≡

t├u

≡

t(∈)(3)u

≡

t├t

≡

u(已证)(4)A(t)，u

≡

t├t

≡

u(Tr)(2)(3)(5)A(t)，u

≡

t├A(u)(≡-)(1)(4)(6)A(t)├u

≡

t→A(u)(→+)(5)

(7)A(t)├

∀x(x

≡

t→A(x))(∀+)(6)第二十七页，共四十二页，2022年，8月28日再证∀x(x≡

t→A(x))├A(t)(1)∀x(x≡

t→A(x))├∀x(x≡

t→A(x))(Ref)(2)∀x(x≡

t→A(x))├t

≡

t→A(t)(∀-)(1)(3)Ф├t

≡

t(≡+)(4)∀x(x≡

t→A(x))├t

≡

t(+)(3)(5)∀x(x≡

t→A(x))├A(t)(→-)(2)(4)第二十八页，共四十二页，2022年，8月28日语义（一）论域（个体域）问题所讨论的对象集称为论域，记为D。论域中的对象称为个体。全总个体域：包含一切对象的集合，它是特殊的个体域。个体符号论域D中的个体常元n元函数符号ff：Dn→D第二十九页，共四十二页，2022年，8月28日语义（二）n元关系符号F F⊆Dn自由变元符号取值范围为论域D的个体变元量词

∀xF(x)：对于所有x∈D，F(x)。∃xF(x)：存在x∈D，使得F(x)。约束变元被量词量化的变元。受限制量词量词的范围由原来的论域被限制为论域的某个子集。第三十页，共四十二页，2022年，8月28日语义（三）闭项代表论域D中的个体常元；非闭项代表个体变元。含n个不同自由变元符号的公式称为论域D上的n元命题函数：Dn→{1，0}闭公式是0元命题函数，是命题。第三十一页，共四十二页，2022年，8月28日语义（四）对于一阶语言L的赋值包括一个论域D和一个函数v。v以所有的个体符号、关系符号、函数符号、自由变元符号构成的集合为定义域，且将v(a)，v(F)，v(≡)，v(f)，v(u)记为av，Fv，≡v

，fv，uv，其中a为个体符号，F为n元关系符号，f为m元函数符号，u为自由变元符号则i）av，uv∈Dii）Fv⊆Dn

iii）≡v={<x,x>|x∈D}iv）fv：Dm→D第三十二页，共四十二页，2022年，8月28日语义（五）项t在赋值v下的值，记为tv。其定义为：

i）av，uv∈Dii）(f(t1，t2，…

，tn))v=fv(t1v，t2v，…

，tnv)，其中t1，t2，…

，tn∈Term(L)定理：设v是论域D上的一个赋值，且t∈Term(L)，则tv∈D。第三十三页，共四十二页，2022年，8月28日语义（六）公式A在赋值v下的值，记为Av。其定义为：(i)若<t1v，t2v，…，tnv>∈Fv，(F(t1，t2，…，tn))v=1；否则，(F(t1，t2，…，tn))v=0。(ii)若Av=0，则(﹁A)v=1；否则，(﹁A)v=0。(iii)若Av=Bv=1，则(A∧B)v=1；否则，(A∧B)v=0。(iv)若Av=Bv=0，则(A∨B)v=0；否则，(A∨B)v=1。(v)若Av=1并且Bv=0，则(A→B)v=0；否则，(A→B)v=1。(vi)若Av=Bv，则(A↔B)v=1；否则，(A↔B)v=0。(vii)u代入x，由A(x)得到A(u)，且u不在A(x)中出现。若对于任何α∈D，A(u)v(u/α)=1，则(∀xA(x))v=1；否则，(∀xA(x))v=0。(viii)u代入x，由A(x)得到A(u)，且u不在A(x)中出现。若存在α∈D，使得A(u)v(u/α)=1，则(∃xA(x))v=1，否则，(∃xA(x))v=0。定理：设v是论域D上的一个赋值，且A∈Form(L)，则Av∈{1，0}。第三十四页，共四十二页，2022年，8月28日公式的语义分类若对于所有B∈∑，Bv=1，则∑v=1；否则，∑v=0。∑是可满足的，当且仅当存在赋值v，使得∑v=1。特别的，若{A}是可满足的，则称A为可满足式。A是有效的，当且仅当对于任何的赋值v，Av=1。第三十五页，共四十二页，2022年，8月28日逻辑推论设∑⊆Form(L)，A∈Form(L)。A是∑的逻辑推论，记作∑╞A，当且仅当对于任何赋值v，∑v=1蕴涵Av=1（Av=0蕴涵∑v=0）。Φ╞A表示A为有效公式。╞不是L中符号。∑╞A不是公式。A╞╡B表示“A╞B并且B╞A”，并称A和B是逻辑等值的。第三十六页，共四十二页，2022年，8月28日证明：