對對稱布爾函數(shù)的定義

對對稱布爾函數(shù)的定義

1值二值計量邏輯現(xiàn)實世界中有許多不同的匯率，其中許多具體的語句不能簡單地用“真”和“假”來評估二值，但必須量化二值。基于這個考慮，本文的第二位作者將等式思想引入了數(shù)理邏輯，并建立了基于概率邏輯的計量邏輯理論[1.6]。在此基礎(chǔ)上，它與概率邏輯相結(jié)合，并將隨機性思維引入經(jīng)典的推理模式?，F(xiàn)在，它已經(jīng)在各種命題邏輯系統(tǒng)中建立了相應(yīng)的邏輯計量空間，并將類似的推理引入到各種命題邏輯系統(tǒng)中，如拉卡西翁、福、神、，等。邏輯方程的性質(zhì)是：將類似的推理引入數(shù)學(xué)邏輯方程的不同性質(zhì)的系統(tǒng)。此外，除了個人單位的結(jié)果之外，我們還可以說，在邏輯計量空間本身的研究還沒有開始。邏輯方程的真性由其誘導(dǎo)的矩陣函數(shù)決定。然而，在密碼學(xué)中，由于對矩陣函數(shù)的深入研究，相關(guān)矩陣函數(shù)的性質(zhì)將不可避免地引入數(shù)學(xué)邏輯。因此，如果我們想將矩陣函數(shù)的不同性質(zhì)引入數(shù)學(xué)邏輯，就會有效地促進計量邏輯的發(fā)展?；诖?，作為第一步，本文將對稱矩陣的概念引入數(shù)學(xué)邏輯理論，并定義了對稱邏輯方程和準(zhǔn)對稱邏輯方程的邏輯方程。同時，請注意，二值邏輯方程與矩陣函數(shù)密切相關(guān)，但存在重要差異。對稱公式的兩個完全對立的性質(zhì)狀態(tài)表明，它是n元的一部分。為了證明對稱邏輯方程的兩個完全對立的性質(zhì)，它僅代表所有n元邏輯方程的一部分，其比例隨著n的增加而增加。然而，從另一個角度來看，n元的另一個方程是，因為它可以證明對稱邏輯方程的真性集與所有邏輯方程集中在一起，而且是緊密的。最后，從交叉角度的角度，我們證實，經(jīng)典邏輯計量空間中的所有對稱公式集中在密集分布，而不是到處都密集。2關(guān)于多原子公式的模型定義1稱映射f:{0,1}n※{0,1}為n元布爾函數(shù).設(shè)α=(x1,x2,…,xn)∈{0,1}n,若f(α)=1,則稱α為f的特征向量;稱α中1的個數(shù)為α的重量.若一旦{0,1}n中某重量為k的向量是f的特征向量,那么{0,1}n中全部重量為k的向量都是f的特征向量(0≤k≤n),則稱f為對稱的布爾函數(shù).以下用N(f)記f的特征向量的個數(shù),顯然注1上面關(guān)于f對稱性的表述并非文獻中的原始定義,但易證本文的定義和文獻中的定義是等價的.定義2稱為n元對稱布爾函數(shù)f的基本表示形式,其中注2定義2中采用的是f的多項式表示,由于不影響本文的推導(dǎo),為節(jié)省篇幅起見,我們對什么是多項式表示不作介紹.定義3設(shè)S=｛p1,p2,p3,…｝,F(S)是由S生成的(?,∨,→)型自由代數(shù),稱S中的元為原子公式,稱F(S)中的元為合式公式,簡稱公式.設(shè){0,1}是最簡單的布爾代數(shù),其中則{0,1}也是(?,∨,→)型代數(shù).定義4設(shè)A(p1,p2,…pn)是含有原子公式p1,p2,…pn的邏輯公式,用xi取代pi(i=1,2,…,n),并按式(3)理解邏輯連接詞?,∨,→,則得一布爾函數(shù)fA:{0,1}n→{0,1},稱為A所誘導(dǎo)的布爾函數(shù).稱N(fA)/2n為公式A的真度,記為τ(A).設(shè)A,B為F(S)中的兩個公式,稱為A與B之間的相似度.再令是F(S)上的偽距離,稱(F(S),ρ)為邏輯度量空間.已知兩個邏輯公式邏輯等價當(dāng)且僅當(dāng)它們之間的相似度為1,或等價地,它們之間的偽距離為0.(2)公式A中的原子公式的標(biāo)號未必是從1到n的連續(xù)編號,但設(shè)其中最大編號為n,令B=A∨(p1∧?p1)∨…∨(pn∧?pn),則B與A邏輯等價,B中原子公式的標(biāo)號就是從1到n的連續(xù)編號了,所誘導(dǎo)的布爾函數(shù)也就可寫為f(x1,…,xn)的形式了.以下凡提到含有n個原子公式的邏輯公式A,恒假定A中的原子公式的標(biāo)號是從1到n的連續(xù)編號.(3)當(dāng)A與B相似(即ξ(A,B)=1)時ρ(A,B)=0,這時A和B可以是不同的公式,可見(F(S),ρ)不是度量空間,只是偽度量空間.但由于邏輯等價關(guān)系≈是F(S)上的(?,∨,→)型同余關(guān)系,這里A≈B當(dāng)且僅當(dāng)ρ(A,B)=0,所以ρ自然地在Lindenbaum商代數(shù)[F(S)]=F(S)/≈上誘導(dǎo)一個真正的度量,仍記為ρ.這時([F(S)],ρ)就是一個度量空間.3以a與b為對稱邏輯公式的準(zhǔn)對稱邏輯公式定義5設(shè)A是含有n個原子公式的邏輯公式.如果A所誘導(dǎo)的布爾函數(shù)是對稱布爾函數(shù),則稱A為n元對稱邏輯公式.容易看出,如果兩個邏輯公式誘導(dǎo)的布爾函數(shù)相同,則此二公式邏輯等價,但反過來,邏輯等價的公式未必誘導(dǎo)出相同的布爾函數(shù).例1設(shè)A=p1∧p2,B=(p1∧p2)∨(p3∧?p3),則A與B邏輯等價,但它們所誘導(dǎo)的布爾函數(shù)分別是2元布爾函數(shù)和3元布爾函數(shù),顯然是不同的.值得注意的是,前者的特征向量只有一個,即,(1,1),后者的特征向量有兩個,即,(1,1,1)和(1,1,0).所以由定義1看出,前者是對稱函數(shù),而后者不是對稱函數(shù).因此我們得出結(jié)論:命題1如果一個邏輯公式是對稱公式,則和它邏輯等價的公式未必是對稱公式.命題1反映出了二值邏輯公式與布爾函數(shù)既密切相關(guān),又有明顯區(qū)別.命題2設(shè)A與B含有同樣的n個原子公式,則A與B邏輯等價當(dāng)且僅當(dāng)A與B誘導(dǎo)同樣的布爾函數(shù).證明設(shè)A與B含有同樣的n個原子公式,且A與B邏輯等價.這時二者之間的相似度等于1,那么由式(4)得τ((A→B)∧(B→A))=1,即,(A→B)∧(B→A)是重言式.分別用f和g表示A和B所誘導(dǎo)的布爾函數(shù),則(A→B)∧(B→A)所誘導(dǎo)的布爾函數(shù)可寫為(f→g)∧(g→f),這里的運算由式(3)確定.由(A→B)∧(B→A)是重言式知每個n維0-1向量都是(f→g)∧(g→f)的特征向量,所以f和g的特征向量必相同.那么f與g也就是相同的布爾函數(shù).可見A與B誘導(dǎo)同樣的布爾函數(shù).反過來,當(dāng)A與B誘導(dǎo)同樣的布爾函數(shù)時,由定義4知A與B邏輯等價.注4當(dāng)含有同樣的n個原子公式的公式A與B誘導(dǎo)同樣的布爾函數(shù)時,除了可能有的原子公式的排序而外,A與B是沒有區(qū)別的,如,A=(p4∧p1)∨(p2∧p3),B=(p2∧p3)∨(p1∧p4).以下認(rèn)為這兩種邏輯公式是同一個邏輯公式.定義6設(shè)邏輯公式B(p1,…,pn)與對稱邏輯公式A(p1,…,pm)邏輯等價,則稱B為準(zhǔn)對稱邏輯公式.例2在例1中,B是準(zhǔn)對稱邏輯公式.又,對稱邏輯公式自然也是準(zhǔn)對稱邏輯公式.所以準(zhǔn)對稱邏輯公式之集包含了對稱邏輯公式之集.命題3設(shè)B(p1,…,pn)與對稱邏輯公式A(p1,…,pm)邏輯等價,且B(p1,…,pn)不是對稱邏輯公式,則m<n.證明由命題2知m≠n.設(shè)m>n,令C=B∨(pn+1∧?pn+1)∨…∨(pm∧?pm),則C與B邏輯等價,從而C也與A邏輯等價.所以由命題2知C誘導(dǎo)的布爾函數(shù)h是對稱布爾函數(shù).用g表示B誘導(dǎo)的布爾函數(shù).由g不是對稱布爾函數(shù)知存在重量為k的兩個n維0-1向量α和β使g(α)≠g(β).分別令α和β的第n+1到第m個坐標(biāo)全為0,就得到布爾函數(shù)h的兩個重量為k的向量α*和β*使h(α*)≠h(β*).這與h是對稱布爾函數(shù)相矛盾!所以m<n.命題4設(shè)二對稱邏輯公式A(p1,…,pm)與B(p1,…,pn)邏輯等價,且A與B不是重言式,也不是矛盾式,則m=n.證明分別用f(x1,…,xm)與g(x1,…,xn)表示A與B所誘導(dǎo)的布爾函數(shù),設(shè)m≠n,不放假定m<n.這時重言式(A→B)∧(B→A)誘導(dǎo)的布爾函數(shù)(f→g)∧(g→f)恒等于1,這里的運算由式(3)確定.那么f(x1,…,xm)與g(x1,…,xn)恒相等.因為A不是重言式,也不是矛盾式,所以{0,1}m中存在重量為k的向量α和重量為k+1的向量β使f(α)和f(β)不相等(0≤k<m).不妨設(shè)f(α)=0,f(β)=1.則g也有重量為k+1的n維特征向量β*,因為只需在β后補充n-m個0就得到這種向量β*.但在α后補充1個1和m-n-1個0又得到一個重量為k+1的n維向量α*.這時g在兩個重量為k+1的向量上取不同的值,與g是對稱布爾函數(shù)相矛盾!所以m=n.命題5設(shè)B(p1,…,pn)是準(zhǔn)對稱邏輯公式,且B不是重言式,也不是矛盾式,則存在唯一的對稱邏輯公式與B邏輯等價.證明如果有兩個對稱邏輯公式A和C都與B邏輯等價,則A和C是邏輯等價的對稱公式,所以由命題4知A和C含有同樣多的原子公式.再由命題2和注4知A和C是相同的邏輯公式.4準(zhǔn)對稱邏輯公式的真度之集定理1n元對稱邏輯公式占全體n元邏輯公式的比例隨n的增大而趨向于零.證明設(shè)A是n元對稱邏輯公式,則fA是n元對稱布爾函數(shù).由式(2)知隨著αk在{0,1}中各種可能的選取,不同的n元對稱布爾函數(shù)共有2n+1個,n元對稱邏輯公式也就共有2n+1個.但全體n元布爾函數(shù)共有22n個,全體n元邏輯公式也就共有22n個.顯然2n+1與22n之比隨n的增大而趨向于0.所以n元對稱邏輯公式占全體n元邏輯公式的比例隨n的增大而趨向于零.由定理1看出,n元對稱邏輯公式只是全體n元邏輯公式中的極少一部分.但有趣的是,從另一個角度看n元對稱公式卻又表現(xiàn)出截然相反的性質(zhì).事實上,我們有下面的定理2對稱邏輯公式的真度之集像全體邏輯公式的真度之集一樣,是在中稠密的.為了證明定理2,我們需要一個引理.引理1二項展開式的系數(shù)具有如下性質(zhì):(1)C02n,C12n,…,Cn2n是遞增數(shù)列,C2nn+1,C2nn+2,…,C2n2n是遞減數(shù)列,Cn2n是最大值.證明(1)設(shè)k<n,則所以(1)中的前一個結(jié)論成立.其它類似可證.(2)由斯特林公式得由此可得這就證明了(2).現(xiàn)在證明定理2.證明設(shè)Q?.如果對任意給定的正數(shù)ε,Q有有限子集,其成員由小到大依次為:τ(0),τ(1),…,τ(m),滿足條件τ(0)=1/2m,τ(m)=1和τ(k+1)-τ(k)<ε(k=0,1,…,m-1),則Q在中稠密.現(xiàn)在用Q記全體對稱邏輯公式的真度之集,以下只需證明Q滿足上述條件即可.事實上,設(shè)ε是任意給定的正數(shù),由引理1知可取2n充分大,使Cn2n/22n<ε.取2n元對稱布爾函數(shù)fk,使其特征向量之集為ki=∪0D(i),這里D(i)是全體重量為i的2n維0-1向量之集,則由D(i)=Ci2n知誘導(dǎo)出對稱布爾函數(shù)fk的邏輯公式Ak的真度等于ki=∑0(Ci2n/22n).這時令且由引理1知所以滿足所需要的條件,定理2證畢.推論1準(zhǔn)對稱邏輯公式的真度之集像全體邏輯公式的真度之集一樣,是在中稠密的.證明因為準(zhǔn)對稱邏輯公式之集包含了對稱邏輯公式之集,所以由定理2即得本推論.以下我們從拓?fù)涞挠^點討論對稱邏輯公式之集在邏輯度量空間中的分布.定義7設(shè)(X,∪)是拓?fù)淇臻g,E是X的子集.如果E在(X,∪)中的閉包不含內(nèi)點,則稱E是無處稠密集.引理2設(shè)(X,ρ)是(偽)度量空間,E是X的子集.如果(1)E自身不含內(nèi)點;(2)E的補集中每個點都和E有正距離.則E是X中的無處稠密集.證明設(shè)E不是無處稠密集,則E的閉包clE有內(nèi)點a,即,存在正數(shù)ε使以a為中心以ε為半徑的實心球B(a,ε)包含于clE之中.但由(1)知E不含內(nèi)點,所以B(a,ε)中有點b不屬于E.那么由(2)知ρ(b,E)=δ>0.從而b不是E的聚點,即,b不屬于clE,這與b∈B(a,ε)?clE相矛盾!所以E是無處稠密集.定理3全體對稱邏輯公式之集是邏輯度量空間中的無處稠密集.證明只需證明全體準(zhǔn)對稱邏輯公式之集E是邏輯度量空間中的無處稠密集,因為E包含了全體對稱邏輯公式之集,且無處稠密集的子集是無處稠密集.設(shè)A是準(zhǔn)對稱邏輯公式,我們證明在A的任一小的鄰域中都存在非準(zhǔn)對稱邏輯公式,從而E不含內(nèi)點.因為準(zhǔn)對稱公式與某對稱邏輯公式邏輯等價,從而二者之間的距離為0,所以不妨設(shè)A是對稱公式,A所誘導(dǎo)的布爾函數(shù)為f(x1,…,xn).設(shè)ε是任意給定的正數(shù),將A誘導(dǎo)的布爾函數(shù)等價擴充為則誘導(dǎo)出式(6)的邏輯公式B與A邏輯等價.取k充分大,使.(1)如果A是矛盾式,任取僅有1個重量為n的特征向量的n+k元布爾函數(shù)g,則由定義4知誘導(dǎo)出g的邏輯公式C與A之間的距離為1/2n+k<ε,且可證C不是準(zhǔn)對稱公式.事實上,n+k元對稱布爾函數(shù)一旦有重量為n的特征向量,就有Cnn+k>1個這種向量,不會僅有1個,所以C不是對稱公式.又,由非對稱的準(zhǔn)對稱公式誘導(dǎo)的布爾函數(shù)的構(gòu)造知:改變n+k維0-1向量的最后一個坐標(biāo)不會影響該布爾函數(shù)的值,它一旦有重量為n的特征向量,就至少有兩個這種向量,所以C也不是準(zhǔn)對稱公式.(2)如果A是重言式,則取僅有1個重量為n的n+k維0-1向量不是特征向量的n+k元布爾函數(shù)h,則由定義4知誘導(dǎo)出h的邏輯公式D與A之間的距離為1/2n+k<ε,且用和(1)中類似的分析可證D不是準(zhǔn)對稱邏輯公式.(3)現(xiàn)在設(shè)A既不是矛盾式也不是重言式,則布爾函數(shù)f既可取值0又可取值1.由命題4和n+k>n知B不是對稱邏輯公式.現(xiàn)在任選一個n+k維0-1向量α,則由式(6)知對每個前n個坐標(biāo)和α的前n個坐標(biāo)相同的向量β而言,恒有f*(α)=f*(β).取n+k維0-1向量γ,改變它的最后一個坐標(biāo)得另一個n+k維0-1向量λ.作n+k元布爾函數(shù)g*使g*(λ)≠f*(λ),而在其余n+k維0-1向量處g*與f*的值都相等.以H記誘導(dǎo)出布爾函數(shù)g*的邏輯公式,則可證H不是準(zhǔn)對稱邏輯公式.由g*的作法和定義4知ρ(A,H)=1/2n+k<ε.綜上所述知準(zhǔn)對稱公式集E不含內(nèi)點,所以引理2中的條件(1)成立.以下只需證明引理2中條件(2)也成立.事實上,設(shè)C不是準(zhǔn)對稱邏輯公式,C所誘導(dǎo)的布爾函數(shù)為h(x1,…,xn).任取n元對稱邏輯公式A,設(shè)A誘導(dǎo)的布爾函數(shù)為f(x1,…,xn).則由A和C不等價和定義4知ρ(C,A)≥1/2n=δ>0.再設(shè)G是任一對稱邏輯公式,G所誘導(dǎo)的布爾函數(shù)為η(x1,…,xm).如果m≤n,把η等價擴充為n元布爾函數(shù),并設(shè)Q為相應(yīng)的邏輯公式,則Q是準(zhǔn)對稱公式而C不是準(zhǔn)對稱公式,所以ρ(C,G)=ρ(C,Q)≥1/2n=δ>0.最后設(shè)m>n,m=n+k.將h等價擴充為由C不是準(zhǔn)對稱公式知存在重量為r的不同的n維0-1向量α和β使h(α)=0且h(β)=1或h(α)=1且h(β)=0.不妨設(shè)h(α)=0且h(β)=1.因為重量為n或0的n維向量只有一個,所以由α與β不相等知1<r<n.在向量α的后面任意添加k維0-1向量,共可得出2k個n+k維0-1向量,布爾函數(shù)h*在這些向量處的值都等于0.我們稱這些向量為0值向量.同樣地,在向量β的后面任意添加k維0-1向量,共可得出2k個n+k維0-1向量,布爾函數(shù)h*在這些向量處的值都等于1.我們稱這些向量為1值向量.這些向量(包括0值向量和1值向量)的重量等于從r到r+k的各個值.其中重量等于r+i的向量有Cki個(i=0,1,…,k).對稱布爾函數(shù)η在上述重量等于r+