線性邏輯公式的構造與性質

線性邏輯公式的構造與性質

計量邏輯從概念的擴展到數(shù)值計算，并將數(shù)值計算引入數(shù)學邏輯，使其更具靈活性，并擴大其可能的應用范圍[1、2、3、4、5、6、7、8、9、10和11]。機化思想也被引入經典推理模型，豐富了其研究內容?，F(xiàn)在，盡管密碼學的一些概念已經發(fā)展到邏輯工程中，但它們已經擴展到了邏輯工程中反射變換的性質，文獻研究了古典邏輯工程中對稱邏輯公式的分布，以及對邏輯空間本身結構的研究。布爾函數(shù)既是邏輯學又是密碼學中的重要概念,也是研究數(shù)字電路和密碼技術的重要工具,其中線性布爾函數(shù)是一類重要的布爾函數(shù),因其實現(xiàn)簡單在電路分析中很受重視.本文基于線性布爾函數(shù)概念,在經典邏輯度量空間中定義了線性邏輯公式,給出線性邏輯公式的構造方法,并且在邏輯度量空間中研究線性邏輯公式在反射變換下的性質,證明了所有線性邏輯公式的真度等于1/2.最后,研究了一類代數(shù)次數(shù)等于k的布爾函數(shù)所對應的邏輯公式的性質,證明了該類公式的真度等于1/2k.1值之集記作定義1設S={p1,p2,…},F(S)是由S生成的(ue01e,→)型自由代數(shù),稱F(S)中的元為經典命題邏輯系統(tǒng)中的公式(或命題),稱S中的元為原子公式(或原子命題).定義2設v:F(S)→{0,1}是映射,若v是(ue01e,→)型同態(tài),即ue02fA、B∈F(S),均有則稱v為F(S)的賦值,v(A)也稱為公式A的賦值.F(S)的全體賦值之集記作Ω.設A、B∈F(S),如果對每個v∈Ω,均有v(A)=1,則稱A為重言式,記作ue0d0A;如果對每個v∈Ω,均有v(A)=0,則稱A為矛盾式;如果對每個v∈Ω,均有v(A)=v(B),則稱A與B邏輯等價,記作A≈B.分別稱ξ(A,B)、ρ(A,B)為公式A與B之間的相似度與偽距離,稱(F(S),ρ)為偽距離空間.定義5設S={p1,p2,…},F(S)是由S生成的(ue01e,→)型自由代數(shù),≈是F(S)上的邏輯等價關系,則≈是(ue01e,→)型同余關系,稱商代數(shù)F(S)/≈為Lindenbaum代數(shù),記作[F(S)].公式A所在的同余類記作[A].ue02fA、B∈F(S),令ρ*([A],[B])=ρ(A,B),則ρ*是[F(S)]上的距離,稱([F(S)],ρ*)為經典邏輯度量空間.命題1每個布爾函數(shù)都可由某個邏輯公式導出.例1設3元布爾函數(shù)f:{0,1}3→{0,1}由下表給出:文獻給出了布爾函數(shù)的小項表示法和多項式表示法,而且兩種表示法可以相互轉化.定義6設n元布爾函數(shù)f(x1,…,xn)=b1x1+…+bnxn滿足條件b1,…,bn∈{0,1},且b1,…,bn不全為零,則稱該函數(shù)為線性布爾函數(shù).2線性邏輯公式定義7設A∈F(S),且A中含有n個原子命題p1,…,pn.如果A所導出的布爾函數(shù)是線性布爾函數(shù),則稱A為n元線性邏輯公式.注1這里的線性邏輯公式不是線性邏輯系統(tǒng)中的邏輯公式,而是經典邏輯系統(tǒng)中的邏輯公式,只是它們導出的布爾函數(shù)是線性布爾函數(shù).證明因為A所導出的3元布爾函數(shù)為A(x1,x2,x3)=x10x21x30+x10x21x31+x11x20x30+x11x20x31=(1+x1)x2(1+x3)+(1+x1)x2x3+x1(1+x2)(1+x3)+x1(1+x2)x3=(x2+x1x2+x2x3+x1x2x3)+(x2x3+x1x2x3)+(x1+x1x2+x1x3+x1x2x3)+(x1x3+x1x2x3)=x1+x2,所以A為3元線性邏輯公式.引理1設n是任意的正整數(shù),有下面的結論:(ⅰ)如果n=2k+1為奇數(shù),則(ⅱ)如果n=2k+2為偶數(shù),則引理1中的兩個等式可由二項式系數(shù)的性質得到,證明從略.定理1所有線性邏輯公式的真度均為1/2.證明設公式A是任意的線性邏輯公式,不妨設A中含有n個原子命題p1,…,pn,則A導出的布爾函數(shù)的多項式表示為其中{i1,…,it}是{1,…,n}的任意非空子集.所以,A(x1,…,xn)=1的取法共有2t-1×2n-t=2n-1種.例3構造一個邏輯公式A,使得A所導出的布爾函數(shù)是線性布爾函數(shù)f(x1,x2,x3)=x1+x2+x3.3k/k布爾函數(shù)將k個線性布爾函數(shù)作乘積,可得到一個代數(shù)次數(shù)為k的布爾函數(shù).下面研究這類布爾函數(shù)所對應的邏輯公式在計量邏輯學中的性質.首先討論k=2的情形,即一類代數(shù)次數(shù)等于2的布爾函數(shù)所對應的邏輯公式.4s11+哌+2t2本文借助線性布爾函數(shù)的概念,提出了線性邏輯公式的概念,給出了n元線性邏輯公式的構造方法.并證明了所有線性邏輯公式的真度等于1/2.這從計量學的角度說明了線性布爾函數(shù)的結構相對比較簡單.因為n元布爾函數(shù)的真度共有2n+1種之多,而n元線性布爾函數(shù)所對應的邏輯公式的真度僅僅為其中的一種,這表明n元線性布爾函數(shù)在全體n元布爾函數(shù)之中的分布很稀疏.本文證明可以通過線性布爾函數(shù)去設計一類代數(shù)次數(shù)等于k的布爾函數(shù),這類布爾函數(shù)所對應的邏輯公式的真度等于1/2k,表明這類代數(shù)次數(shù)等于k的布爾函數(shù)在全體n元布爾函數(shù)中的分布也很稀疏.這為文獻中提出的重量分析法提供了參考依據(jù).證明(ⅰ)若{x11,…,x1t1}∩{x21,…,x2t2}=ue07e,即x11,…,x1t1;x21,…,x2t2兩兩互異.定理5設A∈F(S),且A中含有n個原子命題p1,…,pn.如果A所導出的布爾函數(shù)為2個線性布爾函數(shù)的乘積,即(x1,…,xn)=(x11+…+x1t1)(x21+…+x2t2)(x11,…,x1t1兩兩互異;x21,…,x2t2兩兩互異,且{x11,…,x1t1}≠{x21,…,x2t2}.x11,…,x1t1;x21,…,x2t2∈{x1,…,xn}),則τ(A)=1/4.由(x1,…,xn)=(x11+…+x1t1)(x21+…+x2t2)=1可知,x11+…+x1t1=1且x21+…+x2t2=1,而在{x11,…,x1t1}這t1個變量中,使得x11+…+x1t1=1的取法有2t1-1種;在{x21,…,x2t2}這t2個變量中,使得x21+…+x2t2=1的取法有22t2-1種;在{x1,…,xn}-{x11,…,x1t1,x21,…,x2t2}這n-t1-t2個變量處可取值1或0,取法共有2n-t1-t2種,所以(x1,…,xn)=1的取法共有2t1-1×2t2-1×2n-t1-t2=2n-2種,從而可得τ(A)=|(1)|/2n=2n-2/2n=1/4.由(x1,…,xn)=1可知,xi1+…+xit=1且y1+…+yt1-t=z1+…+zt2-t=0;或者xi1+…+xit=0且y1+…+yt1-t=z1+…+zt2-t=1.在{xi1,…,xit}這t個變量中,使得xi1+…+xit=1(或xi1+…+xit=0)的取法有2t-1種;在{y1,…,yt1-t}這t1-t個變量中,使得y1+…+yt1-t=0(或y1+…+yt1-t=1)的取法有2t1-t-1種;在{z1,…,zt2-t}這t2-t個變量中,使得z1+…zt2-t=0(或z1+…+zt2-t=1)的取法有2t2-t-1種.所以使得xi1+…+xit=1且y1+…+yt1-t=z1+…+zt2-t=0的取法共有2t-1×2t1-t-1×2t2-t-1=2t1+t2-t-3種;使得xi1+…+xit=0且y1+…+yt1-t=z1+…zt2-t=1的取法也有2t1+t2-t-3種.而在{x1,…,xn}-{xi1,…,xit}-{y1,…,yt1-t}-{z1,…,zt2-t}這n-t1-t2+t個變量處可取值1或0,取法共有2n-t1-t2+1種.所以(x1,…,xn)=1的取法共有(2t1+t2-t-3+2t1+t2-t-3)×2n-t1-t2+t=2n-2種,從而可得τ(A)=|(1)|/2n=2n-2/2n=1/4.注2特別地,當{x11,…,x1t1}∩{x21,…,x2t2}=時,(x1,…,xn)=(x11+…+x1t1)(x21+…+x2t2)為2次齊次布爾函數(shù).對于一般的代數(shù)次數(shù)等于2的布爾函數(shù)所對應的邏輯公式,其真度不一定為1/4.例4設公式A所導出的布爾函數(shù)為三元布爾函數(shù)(x1,x2,x3)=x1x2+x1x3+x2x3,計算A的真度.解當(x1,x2,x3)=(0,1,1),(1,0,1),(1,1,0),(1,1,1)時,(x1,x2,x3)=1,所以τ(A)=4/23=1/2.定理6設A∈F(S),且A中含有n個原子命題p1,…,pn,φ*是[F(S)]上的反射變換.如果A所導出的布爾函數(shù)為代數(shù)次數(shù)為2的布爾函數(shù)(x1,…,xn)=(x11+…+x1t1)(x21+…+x2t2)(x11,…,x1t1兩兩互異;x21,…,x2t2兩兩互異.x11,…,x1t1;x21,…,x2t2∈{x1,…,xn}),且t1、t2均為偶數(shù),則[A]是反射變換φ*的不動點,即φ*([A])=[A].證明由定理3可知,φ(A)所導出的布爾函數(shù)為(x1,…,xn)=(x1,…,xn),所以φ(A)≈A,即[φ(A)]=[A].因此φ*([A])=[φ(A)]=[A],即[A]是反射變換φ*的不動點.下面研究一類代數(shù)次數(shù)等于k的布爾函數(shù)所對應的邏輯公式.定理7設A∈F(S),且A中含有n個原子命題p1,…,pn.如果A所導出的布爾函數(shù)為k個線性布爾函數(shù)的乘積,即(x1,…,xn)=(x11+…+x1t1)…(xk1+…+xktk)(x11,…,x1t1兩兩互異;…;xk1,…,xktk兩兩互異,且i(1≤i≤k),{xi1,…,xiti}{x11,…,x1t1}∪…∪{xk1,…,xktk}-{xi1,…,xiti}.x11,…,x1t1;…;xk1,…,xktk∈{x1,…,xn}),則τ(A)=1/2k.ue02f證明可采用與定理5類似的證明方法,過程從略.即[A]是反射變換φ*的不動點.特別地,當k=n時,代數(shù)次數(shù)為n的布爾函數(shù)為x1x2…xn.這時,如果公式A中含有n個原子命題p1,…,pn,且A所導出的布爾函數(shù)是(x1,x2,…,xn)=x1x2…xn,則τ(A)=1/2n.注3特別地,當{x11,…,x1t1},…{xk1,…,xktk}兩兩交空時,(x1,…,xn)=(x11+…+x1t1)…(xk1+…+xktk)為k次齊次布爾函數(shù).定理8設A∈F(S),且A中含有n個原子命題p1,…,pn,φ*是[F(S)]上的反射變換.如果A所導出的布爾函數(shù)為代數(shù)次數(shù)為k的布爾函數(shù)(x1,…,xn)=(x11+…+x1t1)…(xk1+…+xktk