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

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

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