信息安全數(shù)學(xué)基礎(chǔ)第一頁，共四十二頁，2022年，8月28日一階語言L一階語言L是經(jīng)典謂詞（一階）邏輯的形式語言一階語言L是符號的集合個(gè)體符號：abc…關(guān)系符號：FGH…特別的，≡函數(shù)符號：fgh…自由變元符號：uvw…約束變元符號：xyz…聯(lián)結(jié)符號：?

∧∨→?量詞符號：標(biāo)點(diǎn)符號：（，）注意：在一階語言中沒有命題符號。一階語言L的含義本質(zhì)上不涉及語義，而只有語法。第二頁，共四十二頁，2022年，8月28日表達(dá)式表達(dá)式：L中有限個(gè)符號組成的字符串表達(dá)式的長度：表達(dá)式中的符號數(shù)目空表達(dá)式：長度為0的表達(dá)式，記為表達(dá)式相等：U=Viff表達(dá)式U和V中符號依次相同表達(dá)式U和V依次并列形成新的表達(dá)式UV，且若表達(dá)式U=W1VW2，則V是U的段。若V是U的段且V和U不相等，則V是U的真段。初始段、結(jié)尾段、真初始段、真結(jié)尾段第三頁，共四十二頁，2022年，8月28日Term(L)的歸納定義Term(L)的定義

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

，tn∈Term(L)，且f為n元函數(shù)符號，則f(t1，t2，…

，tn)∈Term(L)iii）t是能由有限次應(yīng)用i）—ii）形成的表達(dá)式ifft∈Term(L)不含自由變元的項(xiàng)被稱為閉項(xiàng)。t表示項(xiàng)。Term(L)的歸納證明原理。第四頁，共四十二頁，2022年，8月28日項(xiàng)的結(jié)構(gòu)定理：Term(L)中的項(xiàng)具有以下三種形式之一：個(gè)體符號，自由變元符號，f(t1，t2，…

，tn)，其中f為n元函數(shù)符號；且項(xiàng)具有的形式是唯一的。定理：若t是f(t1，t2，…

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

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

L的表達(dá)式是Atom(L)的元素，當(dāng)且僅當(dāng)它為下列情況之一：

i）F(t1，t2，…

，tn)，其中F為n元關(guān)系符號，t1，t2，…

，tn∈Term(L)。ii）≡(t1，t2)，其中≡為相等關(guān)系符號，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)。其中*表示∧，∨，→，?中的任何一個(gè)iv）若A(u)∈Form(L)，且x不在A(u)中出現(xiàn)，則?xA(x)，?xA(x)

∈Form(L)v）A是能由有限次應(yīng)用i）—iv）形成的表達(dá)式iffA∈Form(L)第七頁，共四十二頁，2022年，8月28日Form(L)的歸納定義（二）不含自由變元的公式被稱為閉公式或語句，Sent(L)表示所有語句構(gòu)成的集合。含有某個(gè)約束變元而不含它的量詞的表達(dá)式被稱為擬公式。擬公式不是公式。

A，B，C表示公式、擬公式。第八頁，共四十二頁，2022年，8月28日Form(L)的歸納證明原理定理：設(shè)R是一個(gè)性質(zhì)，若

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))。其中*表示∧，∨，→，?中的任何一個(gè)；

iv）對于任何A(u)∈Form(L)，若R(A(u))，且x不在A(u)中出現(xiàn)，則R(?xA(x))，R(?xA(x))。則對于任何A∈Form(L)，R(A)。第九頁，共四十二頁，2022年，8月28日公式結(jié)構(gòu)定理：L的每一公式恰好具有以下8種形式之一：原子公式，(﹁A)，(A∧B)，(A∨B)，(A→B)，(A?B)，?xA(x)，?xA(x)

；并且在各種情形，公式所具有的那種形式是唯一的。第十頁，共四十二頁，2022年，8月28日公式的語法分類原子公式復(fù)合公式否定式合取式析取式蘊(yùn)含式等值式全稱式存在式第十一頁，共四十二頁，2022年，8月28日轄域若(﹁A)是C的段，則稱A為它左方的﹁在C中的轄域若(A*B)是C的段，則稱A和B分別為它們之間的*在C中的左轄域和右轄域。其中*表示∧，∨，→，?中的任何一個(gè)若?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為結(jié)論。├不是L中符號。∑├A不是公式。A├┤B表示“A├B并且B├A”，并稱A和B是語法等值的。第十三頁，共四十二頁，2022年，8月28日一階邏輯的推演規(guī)則（一）共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日一階邏輯的推演規(guī)則（二）(?-)若∑├?xA(x)，則∑├A(t)(∨+)若∑├A(u)，u不在∑中出現(xiàn)，則∑├?xA(x)(?-)若∑，A(u)├B，u不在∑，B中出現(xiàn)，則∑，?xA(x)├B(?+)若∑├A(t)，則∑├?xA(x)，其中A(x)是在A(t)中把t的某些（不一定全部）出現(xiàn)替換成x而得。(≡-)若∑├A(t1)，∑├t1≡t2，則∑├A(t2)，其中A(t2)是在A(t1)中把t1的某些（不一定全部）出現(xiàn)替換成t2而得。(≡+)Ф├u≡u第十五頁，共四十二頁，2022年，8月28日形式推演的定義A是在一階邏輯中由∑形式可推演（形式可證明）的，記為∑├A，當(dāng)且僅當(dāng)∑├A能有限次使用一階邏輯中形式推演規(guī)則生成。這是一個(gè)歸納定義。關(guān)于歸納證明。一個(gè)有限序列∑1├A1，∑2├A2，…，∑n├An被稱為∑n├An的形式證明。其中，∑k├Ak（1≤k≤n）由使用某一推演規(guī)則而生成。第十六頁，共四十二頁，2022年，8月28日證明：??xA(x)├┤?x(?A(x))證：先證??xA(x)├?x(?A(x))。

(1)?A(u)├?A(u)u不在A(x)中出現(xiàn)(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)中出現(xiàn)(?-)(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)中出現(xiàn)(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)中出現(xiàn)(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)中出現(xiàn)(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中出現(xiàn)。證：先證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)中出現(xiàn)

(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)中出現(xiàn)(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)中出現(xiàn)。

(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日語義（一）論域（個(gè)體域）問題所討論的對象集稱為論域，記為D。論域中的對象稱為個(gè)體。全總個(gè)體域：包含一切對象的集合，它是特殊的個(gè)體域。個(gè)體符號論域D中的個(gè)體常元n元函數(shù)符號ff：Dn→D第二十九頁，共四十二頁，2022年，8月28日語義（二）n元關(guān)系符號F F?Dn自由變元符號取值范圍為論域D的個(gè)體變元量詞

?xF(x)：對于所有x∈D，F(xiàn)(x)。?xF(x)：存在x∈D，使得F(x)。約束變元被量詞量化的變元。受限制量詞量詞的范圍由原來的論域被限制為論域的某個(gè)子集。第三十頁，共四十二頁，2022年，8月28日語義（三）閉項(xiàng)代表論域D中的個(gè)體常元；非閉項(xiàng)代表個(gè)體變元。含n個(gè)不同自由變元符號的公式稱為論域D上的n元命題函數(shù)：Dn→{1，0}閉公式是0元命題函數(shù)，是命題。第三十一頁，共四十二頁，2022年，8月28日語義（四）對于一階語言L的賦值包括一個(gè)論域D和一個(gè)函數(shù)v。v以所有的個(gè)體符號、關(guān)系符號、函數(shù)符號、自由變元符號構(gòu)成的集合為定義域，且將v(a)，v(F)，v(≡)，v(f)，v(u)記為av，F(xiàn)v，≡v

，fv，uv，其中a為個(gè)體符號，F(xiàn)為n元關(guān)系符號，f為m元函數(shù)符號，u為自由變元符號則i）av，uv∈Dii）Fv?Dn

iii）≡v={<x,x>|x∈D}iv）fv：Dm→D第三十二頁，共四十二頁，2022年，8月28日語義（五）項(xiàng)t在賦值v下的值，記為tv。其定義為：

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

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

，tnv)，其中t1，t2，…

，tn∈Term(L)定理：設(shè)v是論域D上的一個(gè)賦值，且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)中出現(xiàn)。若對于任何α∈D，A(u)v(u/α)=1，則(?xA(x))v=1；否則，(?xA(x))v=0。(viii)u代入x，由A(x)得到A(u)，且u不在A(x)中出現(xiàn)。若存在α∈D，使得A(u)v(u/α)=1，則(?xA(x))v=1，否則，(?xA(x))v=0。定理：設(shè)v是論域D上的一個(gè)賦值，且A∈Form(L)，則Av∈{1，0}。第三十四頁，共四十二頁，2022年，8月28日公式的語義分類若對于所有B∈∑，Bv=1，則∑v=1；否則，∑v=0?！剖强蓾M足的，當(dāng)且僅當(dāng)存在賦值v，使得∑v=1。特別的，若{A}是可滿足的，則稱A為可滿足式。A是有效的，當(dāng)且僅當(dāng)對于任何的賦值v，Av=1。第三十五頁，共四十二頁，2022年，8月28日邏輯推論設(shè)∑?Form(L)，A∈Form(L)。A是∑的邏輯推論，記作∑╞A，當(dāng)且僅當(dāng)對于任何賦值v，∑v=1蘊(yùn)涵Av=1（Av=0蘊(yùn)涵∑v=0）。Φ╞A表示A為有效公式。╞不是L中符號。∑╞A不是公式。A╞╡B表示“A╞B并且B╞A”，并稱A和B是邏輯等值的。第三十六頁，共四十二頁，2022年，8月28日證明：