《信息安全数学基础精选PPT.ppt》由会员分享，可在线阅读，更多相关《信息安全数学基础精选PPT.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息安全数学基础信息安全数学基础第1页，此课件共42页哦一阶语言一阶语言L L n n一阶语言一阶语言L L 是经典谓词（一阶）逻辑的形式语言是经典谓词（一阶）逻辑的形式语言n n一阶语言一阶语言L L 是符号的集合是符号的集合n n个体符号：个体符号：a b c a b c n n关系符号：关系符号：F G H F G H 特别的，特别的，n n函数符号：函数符号：f g h f g h n n自由变元符号：自由变元符号：u v w u v w n n约束变元符号：约束变元符号：x y z x y z n n联结符号：联结符号：n n量词符号：量词符号：n n标点符号：（标点符号：（，）n
2、n注意：在一阶语言中没有命题符号。注意：在一阶语言中没有命题符号。n n一阶语言一阶语言L L 的含义本质上不涉及语义，而只有语法。的含义本质上不涉及语义，而只有语法。第2页，此课件共42页哦表达式表达式n n表达式：L 中有限个符号组成的字符串n n表达式的长度：表达式中的符号数目n n空表达式：长度为0的表达式，记为n n表达式相等：U=V iff 表达式U和V中符号依次相同n n表达式U和V依次并列形成新的表达式UV，且n n若表达式U=W1VW2，则V是U的段。若V是U的段且V和U不相等，则V是U的真段。n n初始段、结尾段、真初始段、真结尾段第3页，此课件共42页哦Term(Term
3、(L L)的归纳定义的归纳定义n nTerm(L)的定义 i i）a，uTerm(L L)ii）若t1，t2，tnTerm(L)，且f为n元函数符号，则f(t1，t2，tn)Term(L)iii）t是能由有限次应用i）ii）形成的表达式 iff tTerm(L)n n不含自由变元的项被称为闭项。n nt表示项。n nTerm(L)的归纳证明原理。第4页，此课件共42页哦项的结构项的结构n n定理：Term(L)中的项具有以下三种形式之一：个体符号，自由变元符号，f(t1，t2，tn)，其中f为n元函数符号；且项具有的形式是唯一的。n n定理：若t是f(t1，t2，tn)的段，则t=f(t1，t
4、2，tn)或t为ti（i=1，2，n）的段。第5页，此课件共42页哦Atom(Atom(L L)的定义的定义n nAtom(L)的定义 L 的表达式是Atom(L)的元素，当且仅当它为下列情况之一：i）F(t1，t2，tn)，其中F为n元关系符号，t1，t2，tn Term(L)。ii）(t1，t2)，其中为相等关系符号，t1，t2Term(L)。第6页，此课件共42页哦Form(Form(L L)的归纳定义（一）的归纳定义（一）n n合式公式集Form(L)i）Atom(L)Form(L)ii）若AForm(L)，则(A)Form(L)iii）若A，BForm(L)，则(A*B)Form(L
5、)。其中*表示，中的任何一个iv）若A(u)Form(L)，且x不在A(u)中出现，则xA(x)，xA(x)Form(L)v）A是能由有限次应用i）iv）形成的表达式 iff AForm(L)第7页，此课件共42页哦Form(Form(L L)的归纳定义（二）的归纳定义（二）n n不含自由变元的公式被称为闭公式或语句，Sent(L)表示所有语句构成的集合。n n含有某个约束变元而不含它的量词的表达式被称为拟公式。n n拟公式不是公式。n n A，B，C表示公式、拟公式。第8页，此课件共42页哦Form(Form(L L)的归纳证明原理的归纳证明原理n n定理：设定理：设R R是一个性质，若i）
6、对于任何）对于任何p pAtom(Atom(L L)，R(p)；ii ii）对于任何A AForm(Form(L L)，若R(A)R(A)，则，则R(A)；iii）对于任何A A，BForm(L)，若，若R(A)R(A)且且R(B)R(B)，则R(A*B)R(A*B)。其中。其中*表示表示，中的任何一个；中的任何一个；iv）对于任何A(u)A(u)Form(Form(L)，若R(A(u)，且x不在不在A(u)A(u)中出现，则R(R(xA(x)xA(x)，R(R(xA(x)xA(x)。则对于任何则对于任何AForm(L)，R(A)。第9页，此课件共42页哦公式结构公式结构定理：L 的每一公式恰
7、好具有以下8种形式之一：原子公式，(A)，(AB)，(AB)，(AB)，(AB)，xA(x)，xA(x)；并且在各种情形，公式所具有的那种形式是唯一的。第10页，此课件共42页哦公式的语法分类公式的语法分类n n原子公式n n复合公式n n否定式n n合取式n n析取式n n蕴含式n n等值式n n全称式n n存在式第11页，此课件共42页哦辖域辖域n n若若(A)A)是是C C的段，则称的段，则称A A为它左方的为它左方的在在C C中的辖域中的辖域n n若若(A*B)(A*B)是是C C的段，则称的段，则称A A和和B B分别为它们之间的分别为它们之间的*在在C C中的左中的左辖域和右辖域。
8、其中辖域和右辖域。其中*表示表示，中的任何一个中的任何一个n n若若xA(x)xA(x)或或xA(x)xA(x)是是B B的段，则称的段，则称A(x)A(x)为为x x或或x x在在B B中的中的辖域辖域 n n定理：任何定理：任何A A中的任何中的任何（如果有）有唯一的辖域；任何（如果有）有唯一的辖域；任何A A中中的任何的任何*（如果有）有唯一的左辖域和右辖域；任何（如果有）有唯一的左辖域和右辖域；任何A A中的任何中的任何x x或或x x（如果有）有唯一的辖域（如果有）有唯一的辖域n n定理：若定理：若A A是是(B)B)的段，则的段，则A=(A=(B)B)或或A A是是B B的段；若的
9、段；若A A是是(B*C)(B*C)的段，则的段，则A=(B*C)A=(B*C)或或A A是是B B的段或的段或A A是是C C的段；若的段；若 A A是是xB(x)xB(x)或或xB(x)xB(x)的段，则的段，则A=A=xB(x)xB(x)或或xB(x)xB(x)，或，或A A是是B(x)B(x)的段。的段。第12页，此课件共42页哦形式可推演形式可推演n n用用 表示任何公式集，即表示任何公式集，即 Form(Form(L)。n n AA可以记为可以记为，A A。n n 可以记为可以记为，。n n若若=A=A1 1,A,A2 2,A,A3 3,，则，则 可以记为可以记为A A1 1,A,
10、A2 2,A,A3 3,。n n A表示A A由由 形式可推演（形式可证明）的。其中，形式可推演（形式可证明）的。其中，为前提，为前提，A A为结论。为结论。n n不是不是L L 中符号。中符号。n n A A不是公式。不是公式。n nA ABB表示表示“A AB B并且并且B BAA”，并称，并称A A和和B B是语法等值的。是语法等值的。第13页，此课件共42页哦一阶逻辑的推演规则（一）一阶逻辑的推演规则（一）n n共共11+611+6条，条，A A，B B，C C为公式为公式n n(Ref)A(Ref)AA An n(+)(+)若若 A A，则则，A An n(-)-)若若，A A BB
11、，A A B B，则则 A An n(-)(-)若若 A AB B，A A，则则 B Bn n(+)(+)若若，A ABB，则则 A AB Bn n(-)-)若若 A AB B，则则 A A，B B n n(+)+)若若 A A ，B B ，则则 A AB Bn n(-)-)若若，A ACC，B BCC，则则，A AB BCCn n(+)+)若若 A A ，则则 A AB B，B BA An n(-)(-)若若 A A B B，A A，则则 B B 若若 A A B B，B B，则则 A An n(+)(+)若若，A ABB，B BAA，则则 A A B B 第14页，此课件共42页哦一阶逻辑
12、的推演规则（二）一阶逻辑的推演规则（二）n n(-)-)若若xA(x)，则A(t)n n(+)+)若若A(u)，u u不在中出现，则xA(x)n n(-)若若，A(u)BA(u)B，u u不在不在，B B中出现，中出现，则，xA(x)Bn n(+)+)若A(t)，则xA(x)，其中A(x)是在A(t)中把t的某些（不一定全部）出现替换成x而得。n n(-)若A(t1 1)，t t1 t2 2，则A(tA(t2 2)，其中，其中A(tA(t2)是在是在A(tA(t1)中把中把t1 1的某些（不一的某些（不一定全部）出现替换成定全部）出现替换成t2而得。n n(+)u u u第15页，此课件共42
13、页哦形式推演的定义形式推演的定义n nA是在一阶逻辑中由形式可推演（形式可证明）的，记为A，当且仅当A能有限次使用一阶逻辑中形式推演规则生成。n n这是一个归纳定义。关于归纳证明。n n一个有限序列1A1，2A2，nAn被称为nAn的形式证明。其中，kAk（1kn）由使用某一推演规则而生成。第16页，此课件共42页哦证明：xA(x)xA(x)x(x(A(x)证：先证先证 xA(x)xA(x)x(x(A(x)。(1)(1)A(u)A(u)uA(u)u不在A(x)中出现 (Ref)(Ref)(2)(2)A(u)A(u)x(x(A(x)(A(x)(+)(1)(3)(3)x(x(A(x)，A(u)x(
14、x(A(x)(A(x)(+)(2)(2)(4)(4)x(A(x)A(x)，A(u)A(u)x(A(x)(A(x)()(5)(5)x(A(x)A(x)A(u)(-)(3)(4)-)(3)(4)(6)(6)x(x(A(x)xA(x)(xA(x)(+)(5)(7)xA(x)xA(x)，x(A(x)A(x)xA(x)(+)(6)xA(x)(+)(6)(8)xA(x)，x(A(x)xA(x)()(9)xA(x)x(x(A(x)(A(x)(-)(7)(8)-)(7)(8)第17页，此课件共42页哦再证再证x(A(x)xA(x)。(1)xA(x)xA(x)xA(x)xA(x)(Ref)(2)xA(x)xA(
15、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(x(A(x)A(x)xA(x)xA(x)(-)(5)第18页，此课件共42页哦证明：证明：x(A(x)B(x)xA(x)xA(x)xB(x)证：(1)x(A(x)B(x)x(A(x)B(x)x(A(x)B(x)(Ref)x(A(x)B(x)(Ref)(2)x(A(x)B(x)A(u)B(u)(A(u)B(u)(-)(1)u u不在不在A(x)A(x)和和B(x)中出现(3)x(A(x)B(x)，xA(x)A(u)B(
16、u)(+)(2)(4)x(A(x)B(x)x(A(x)B(x)，xA(x)xA(x)xA(x)(xA(x)()(5)(5)x(A(x)B(x)x(A(x)B(x)，xA(x)A(u)(A(u)(-)(4)(4)(6)x(A(x)B(x)，xA(x)B(u)(B(u)(-)(3)(5)(3)(5)(7)x(A(x)B(x)x(A(x)B(x)，xA(x)xA(x)xB(x)(xB(x)(+)(6)(8)x(A(x)B(x)xA(x)xA(x)xB(x)(+)(7)(7)第19页，此课件共42页哦证明：证明：证明：证明：x(A(x)B(x)x(A(x)B(x)xA(x)xB(x)xB(x)证：证：
17、(1)x(A(x)B(x)x(A(x)B(x)x(A(x)B(x)(Ref)x(A(x)B(x)(Ref)(2)x(A(x)B(x)A(u)B(u)(A(u)B(u)(-)(1)u不在A(x)A(x)和和B(x)B(x)中出现中出现(3)x(A(x)B(x)x(A(x)B(x)，A(u)A(u)B(u)(+)(2)A(u)B(u)(+)(2)(4)x(A(x)B(x)x(A(x)B(x)，A(u)A(u)A(u)(A(u)()(5)x(A(x)B(x)，A(u)B(u)(-)(3)(4)(6)x(A(x)B(x)x(A(x)B(x)，A(u)xB(x)(B(x)(+)(5)(5)(7)x(A(
18、x)B(x)，xA(x)xB(x)(-)(6)(6)(8)(8)x(A(x)B(x)x(A(x)B(x)xA(x)xB(x)(+)(7)(7)第20页，此课件共42页哦证明：证明：证明：证明：x(A(x)B(x)x(A(x)B(x)，x(B(x)C(x)x(B(x)C(x)x(A(x)C(x)x(A(x)C(x)证：证：(1)(1)x(A(x)B(x)x(A(x)B(x)x(A(x)B(x)(Ref)x(A(x)B(x)(Ref)(2)(2)x(A(x)B(x)x(A(x)B(x)A(u)B(u)(A(u)B(u)(-)(1)(1)u u不在不在A(x)A(x)、B(x)B(x)和和C(x)C
19、(x)中出现中出现(3)(3)x(A(x)B(x)x(A(x)B(x)，x(B(x)C(x)x(B(x)C(x)，A(u)A(u)A(u)B(u)(+)(2)A(u)B(u)(+)(2)(4)(4)x(A(x)B(x)x(A(x)B(x)，x(B(x)C(x)x(B(x)C(x)，A(u)A(u)A(u)(A(u)()(5)(5)x(A(x)B(x)x(A(x)B(x)，x(B(x)C(x)x(B(x)C(x)，A(u)A(u)B(u)(B(u)(-)(3)(4)(3)(4)(6)(6)x(A(x)B(x)x(A(x)B(x)，x(B(x)C(x)x(B(x)C(x)，A(u)A(u)x(B(
20、x)C(x)(x(B(x)C(x)()(7)(7)x(A(x)B(x)x(A(x)B(x)，x(B(x)C(x)x(B(x)C(x)，A(u)A(u)B(u)C(u)(B(u)C(u)(-)(6)(6)(8)(8)x(A(x)B(x)x(A(x)B(x)，x(B(x)C(x)x(B(x)C(x)，A(u)C(u)(A(u)C(u)(-)(5)(7)(5)(7)(9)(9)x(A(x)B(x)x(A(x)B(x)，x(B(x)C(x)x(B(x)C(x)A(u)C(u)(A(u)C(u)(+)(8)(8)(10)(10)x(A(x)B(x)x(A(x)B(x)，x(B(x)C(x)x(B(x)C
21、(x)x(A(x)C(x)(x(A(x)C(x)(+)(9)(9)第21页，此课件共42页哦证明：AxB(x)x(Ax(AB(x)B(x)。x不在不在A A中出现。证：先证AAxB(x)x(Ax(AB(x)。(1)(1)AAxB(x)，A A AxB(x)(xB(x)()(2)AxB(x)，A A A A ()(3)(3)AAxB(x)，A A xB(x)(xB(x)(-)(1)(2)(1)(2)(4)AAxB(x)xB(x)，A B(u)(B(u)(-)(3)u不在A和B(x)B(x)中出现 (5)(5)AxB(x)A AB(u)(+)(4)(4)(6)(6)AxB(x)x(AB(x)(+)
22、(5)(5)第22页，此课件共42页哦再证x(AB(x)AAxB(x)xB(x)。(1)x(AB(x)，A A x(Ax(AB(x)()(2)(2)x(AB(x)B(x)，A A AB(u)(B(u)(-)(1)u不在不在A A和B(x)中出现中出现(3)(3)x(AB(x)B(x)，A A A (A ()(4)x(Ax(AB(x)，A A B(u)(-)(2)(3)(5)(5)x(Ax(AB(x)，A xB(x)(+)(4)(6)(6)x(AB(x)B(x)AxB(x)(+)(5)(5)第23页，此课件共42页哦证明：A(t1)，t1 t2A(t2)证：(1)A(t1)，t1 t2 A(t1
23、)()(2)A(t1)，t1 t2 t1 t2()(3)A(t1)，t1 t2 A(t2)(-)(1)(2)第24页，此课件共42页哦证明：t t证：(1)u u (+)(2)x(x x)(+)(1)(3)t t (-)(2)第25页，此课件共42页哦证明：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)第26页，此课件共42页哦证明：A(t)x(x tA(x)证：先证A(t)x(x tA(x)(1)A(t)，u t A(t)()u不在A(t)中出现。(2)A(
24、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)第27页，此课件共42页哦再证x(x tA(x)A(t)(1)x(x tA(x)x(x tA(x)(Ref)(2)x(x tA(x)t t A(t)(-)(1)(3)t t (+)(4)x(x tA(x)t t (+)(3)(5)x(x tA(x)A(t)(-)(2)(4)第28页，此课件共42页哦语义（一）语义（一）n n论域（个体域）问题所讨论的对
25、象集称为论域，记为问题所讨论的对象集称为论域，记为D。论域中的对象称为个体。n n全总个体域：包含一切对象的集合，它是特殊的个体域。全总个体域：包含一切对象的集合，它是特殊的个体域。n n个体符号个体符号 论域DD中的个体常元n nn元函数符号f f f：Dn nD D第29页，此课件共42页哦语义（二）语义（二）n nn n元关系符号元关系符号F F F FDDn nn n自由变元符号自由变元符号 取值范围为论域取值范围为论域DD的个体变元的个体变元n n量词量词 xF(x)xF(x)：对于所有：对于所有x xDD，F(x)F(x)。xF(x)xF(x)：存在：存在x xDD，使得，使得F(
26、x)F(x)。n n约束变元约束变元 被量词量化的变元。被量词量化的变元。n n受限制量词受限制量词 量词的范围由原来的论域被限制为论域的某个子集。量词的范围由原来的论域被限制为论域的某个子集。第30页，此课件共42页哦语义（三）语义（三）n n闭项代表论域D中的个体常元；非闭项代表个体变元。n n含n个不同自由变元符号的公式称为论域D上的n元命题函数：Dn1，0n n闭公式是0元命题函数，是命题。第31页，此课件共42页哦语义（四）语义（四）n n对于一阶语言L 的赋值包括一个论域D和一个函数v。v以所有的个体符号、关系符号、函数符号、自由变元符号构成的集合为定义域，且将v(a)，v(F)，
27、v()，v(f)，v(u)记为av，Fv，v，fv，uv，其中a为个体符号，F为n元关系符号，f为m元函数符号，u为自由变元符号 则i）av，uvD ii）FvDn iii）v=|x D iv）fv：Dm D第32页，此课件共42页哦语义（五）语义（五）n n项t在赋值v下的值，记为tv。其定义为：i）av，uvD ii）(f(t1，t2，tn)v=fv(t1v，t2v，tnv)，其中t1，t2，tnTerm(L)n n定理：设v是论域D上的一个赋值，且t Term(L)，则tv D。第33页，此课件共42页哦语义（六）语义（六）n n公式公式A A在赋值在赋值v v下的值，记为下的值，记为A
28、 Av v。其定义为：。其定义为：(i)(i)若若t F Fv v，(F(t(F(t1 1，t t2 2，t tn n)v v=1=1；否则，；否则，(F(t(F(t1 1，t t2 2，t tn n)v v=0=0。(ii)(ii)若若A Av v=0=0，则则(A)A)v v=1=1；否则，；否则，(A)A)v v=0=0。(iii)(iii)若若A Av v=B=Bv v=1=1，则则(A(AB)B)v v=1=1；否则，；否则，(A(AB)B)v v=0=0。(iv)(iv)若若A Av v=B=Bv v=0=0，则则(A(AB)B)v v=0=0；否则，；否则，(A(AB)B)v v
29、=1=1。(v)(v)若若A Av v=1=1并且并且B Bv v=0=0，则则(AB)(AB)v v=0=0；否则，；否则，(AB)(AB)v v=1=1。(vi)(vi)若若A Av v=B=Bv v，则则(AB)(AB)v v=1=1；否则，；否则，(AB)(AB)v v=0=0。(vii)u(vii)u代入代入x x，由，由A(x)A(x)得到得到A(u)A(u)，且，且u u不在不在A(x)A(x)中出现。若对于任何中出现。若对于任何 D D，A(u)A(u)v(u/v(u/)=1=1，则，则(xA(x)xA(x)v v=1=1；否则，；否则，(xA(x)xA(x)v v=0=0。(
30、viii)u(viii)u代入代入x x，由，由A(x)A(x)得到得到A(u)A(u)，且，且u u不在不在A(x)A(x)中出现。若存在中出现。若存在 D D，使，使得得A(u)A(u)v(u/v(u/)=1=1，则，则(xA(x)xA(x)v v=1=1，否则，否则，(xA(x)xA(x)v v=0=0。n n定理：设定理：设v v是论域是论域DD上的一个赋值，且上的一个赋值，且A A Form(Form(L L)，则，则A Av v 11，00。第34页，此课件共42页哦公式的语义分类公式的语义分类n n若对于所有B，Bv=1，则v=1；否则，v=0。n n是可满足的，当且仅当存在赋值
31、v，使得v=1。特别的，若A 是可满足的，则称A为可满足式。n nA是有效的，当且仅当对于任何的赋值v，Av=1。第35页，此课件共42页哦逻辑推论逻辑推论n n设Form(L)，AForm(L)。A是的逻辑推论，记作A，当且仅当对于任何赋值v，v=1蕴涵Av=1（Av=0蕴涵 v=0）。n nA表示A为有效公式。n n不是L 中符号。n nA不是公式。n nAB表示“AB并且BA”，并称A和B是逻辑等值的。第36页，此课件共42页哦证明：x(A(x)xA(x)。证：对于任何论域D上的赋值v，若(x(A(x)v=1。即，u代入x，由A(x)得到A(u)，且u不在A(x)中出现。则存在D，使得(
32、A(u)v(u/)=1 可得，A(u)v(u/)=0，(xA(x)v=0，(xA(x)v=1。第37页，此课件共42页哦证明：xA(x)x(A(x)。证：对于任何论域D上的赋值v，若(x(A(x)v=0。即，u代入x，由A(x)得到A(u)，且u不在A(x)中出现。则对于任何D，(A(u)v(u/)=0 可得，A(u)v(u/)=1，(xA(x)v=1，(xA(x)v=0。第38页，此课件共42页哦定理定理n n（等值公式替换）如果BC，且A中将B的某些出现替换为C而得到A，则A A。n n（对偶性）设A为L 的原子公式和联结符号，以及两个量词使用相关规则而形成的公式。若对A中的与，与，原子公
33、式与它的否定式进行交换而得到A（称为A的对偶），则A A。第39页，此课件共42页哦前束范式前束范式n n称L 的公式为前束范式，当且仅当有下面的形式：Q1x1 Q2x2 QnxnB，其中Q1，Q2，Qn是或，且B中不含量词。称Q1x1 Q2x2 Qnxn为前束词，称B为母式。n n定理：任何公式与某个前束范式等值。第40页，此课件共42页哦翻译翻译n n苏格拉底三段论：苏格拉底三段论：n n所有人都是要死的。所有人都是要死的。x(Fx(F(x)G(x)(x)G(x)n n苏格拉底是人。苏格拉底是人。F(a)F(a)n n苏格拉底是要死的。苏格拉底是要死的。G(a)G(a)设论域是全总个体域。设论域是全总个体域。F(u):u是人。G(u):uG(u):u是要死的。是要死的。a：苏格拉底。：苏格拉底。第41页，此课件共42页哦x(Fx(F(x)G(x),F(a)(x)G(x),F(a)G(a)证：(1)x(F(x)G(x),F(a)x(F(x)G(x)()(2)x(F(x)G(x),F(a)F(a)G(a)(-)(1)(3)x(F(x)G(x),F(a)F(a)()(4)x(F(x)G(x),F(a)G(a)(-)(2)(3)第42页，此课件共42页哦