没有合适的资源?快使用搜索试试~ 我知道了~
→ ∞理论计算机科学电子笔记140(2005)81-91www.elsevier.com/locate/entcs等价的渐近密度Grzegorz Matecki1计算机科学系Jagiellonian大学Krako'w,Poland摘要本文研究了k个命题变量上的真公式之分数对所有公式的渐近性态,其中等价是语言中唯一的连接词。我们考虑两种方法来衡量的渐近行为。在第一种情况下,我们研究长度为n的重言式分数的大小与长度为n的所有公式的数量的关系。 第二种情况是非常相似的,我们调查的重言式分数的长度最多n对所有公式的长度最多n的数量。 在这两种情况下,我们感兴趣的是找到每个分数的极限(通常分别称为“密度”和“累积密度”), n→ ∞。已经证明了k= 1的渐近密度对于除等价之外的所有二元联结都存在。本文证明了对任意k,恰有两个累加用于计算的平均值为:0,1 / 2 k− 1(对于ympti c density)和1/2k−1(4k+1),4k/2k−1(4k+1)(对于ympti c density)。保留字:概率密度,命题演算,渐近评价1介绍本文是在下述意义下寻找某些命题逻辑的渐近密度的继续我们研究了给定长度为n的真公式的分数相对于所有长度为n的公式的个数的大小。一般来说,我们打算找到该分数的极限,当n. 如果 极限存在时,它代表一个数字,我们可以称之为所研究逻辑的真值1电子邮件:matecki@ii.uj.edu.pl1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.06.02282G. Matecki/Electronic Notes in Theoretical Computer Science 140(2005)81→ ∞为了更正式,我们研究的语言Fk组成的一些公式,mulas在k命题变量。对于每个子类T <$Fk,我们可以将密度μ(T)关联为:(一)μ(T)=lim#{t∈ T:|不|= n}n→∞ #{t∈Fk:|不|= n}哪里|·|表示公式的长度。很明显,可能有一个子类,其数μ(T)不存在。然而,如果它存在,我们也可以称之为在Fk的所有公式中找到来自类T的公式的渐近概率。最有趣的情况是当T是Fk中所有重言式的一个类时,因为这样我们就可以问找到一个真公式的概率还有另一种研究渐近密度的方法。在这种情况下,我们研究长度至多为n的真公式的分数相对于长度至多为n的所有公式的数量的大小。和以前一样,我们感兴趣的是找到当n时该分数的极限。类似于前面的定义,如果这个极限存在,我们可以称之为累积密度真理的逻辑研究。对于每个子类T <$Fk,我们定义累积密度cμ(T)如下:(二)cμ(T)=lim#{t ∈ T:|不|≤ n}。n→∞ #{t ∈ Fk:|不|≤ n}在[4]中可以找到一些有趣的结果作者研究了用一个变量上的蕴涵算子构建的所有公式的语言它提供了一个限制,该限制适用于所有互变逻辑的clas变量存在,等于1/ 2+ 5/ 10 72, 36%。如果有k个变量目前还没有证据表明这一限制存在。然而,它表明,分数所有重言式中的一个重言式总是正的,并且位于(4k + 1)/(2k + 1)2和(3k + 1)/(k+1)2之间。另一个有趣的结果在[9]中给出。前一种语言是通过增加否定来扩展的。事实证明,极限仍然存在,但否定将真理的密度降低到42的水平。百分之三十二此外,在[8]中,作者提出了一个简单而快速的(log(n))概率算法,用于检查给定的公式是否是重言式。更一般的结果可以在[1]中找到,其中作者考虑用两个连接词(AND,OR)和文字构建语言他们证明了当变量的数量固定时,用这种语言定义的任何布尔函数都存在渐近密度。此外,他们改进了已知的所选布尔函数的渐近密度的上界。另一个结果可以在硕士论文[3]中找到。它是研究一个固定二元G. Matecki/Electronic Notes in Theoretical Computer Science 140(2005)8183不nnK一个命题变量上的布尔运算符。对于大多数的渐近密度等于0(X,AND,OR,X 1,X 2- pr o j e c t i o n s , N O T X 1 , N O T X 2 , N O T → ,N O T ← , N O T 惠 ) 。 哪里有一个明显的连接(真)密度等于1,只有一个(惠)密度不存在. 其余的结果如下:72。两者均为36%影响,5. 37%,33。82%的NAND。等价性是唯一的联结性,它的渐近密度不存在。相反,对于等价的否定,渐近密度等于0。为此,本文给出了一个等价算子的详细结果。定理4.1证明的主要结果表明,基于等价的语言密度不存在。相反,有两个累加点:0和1/ 2k−1。存在两个极限的唯一原因是不存在奇长重言式没有对这些连接的累积密度进行研究本文证明了基于等价算子的重言式类不存在数cμ()和前面一样,我们证明了存在两个聚点:1/ 2k−1(4k +1)和4k/ 2k−1(4k + 1)。其原因也是没有奇长重言式。2计数公式和重言式k个命题变元上的语言Fk{惠}由命题变元变量{v1,.,vk},并且它由等价符号惠封闭。vi ∈Fk{惠}i≤kφ惠∈Fk{惠}i φ惠∈Fk{惠}和φ惠∈Fk{惠}公式φ ∈ Fk{惠}的长度表示为:|φ|并且定义为公式中所有变量的总数,因此对于所有1 ≤i≤k|vi| = 1和|=的|φ|+的|ψ|.|.定义2.1Fk表示F{惠}中公式的总数,长度n,所以:(3)nkFk=#{φ ∈ F {惠}:|φ|= n}引理2.2数Fk=knCn,其中Cn是第n个(4)C0= 0,C1 = 1,乌斯季-1(五)Cn=i=1CiCn−i84G. Matecki/Electronic Notes in Theoretical Computer Science 140(2005)81⇔nnnnnn| |K证据很容易看出,每个公式都可以用二叉树t1 <$t2来识别,其中t1和t2分别代表φ和φ当然,任何叶子都被适当的变量标记,公式的长度为等于树中所有叶子的数量已知所有具有单标号叶子的二叉树的个数最后,每个叶子都可以用k个变量中的一个来标记,所以Fk=knCn。Q更多关于Catalan数的信息可以在[7]和[2]中找到。定义2.3Tk表示F{惠}中所有重言式的总数nk长度为n,所以:(6)Tk= #{φ∈ F {惠}:|φ|=n且φ是重言式}。我们现在所需要做的就是确定Tk。下面的简单观察将为我们提供足够的信息来写出Tk的闭合形式(引理2.5)。定理2.6给出了Tk的有用形式。注2.4任何来自Fk{惠}语言的公式都是重言式,即每个变量出现偶数次。证据只要注意到等价算子是交换的和分配的就足够了。它允许我们写公式没有任何括号和任何顺序。Q引理2.5如下成立:Σ(七)ΣTk=Cnn2 i,.,2i2 i1 +. +2ik =n1k我的律师。设tτ∈Fk{惠}是重言式。通过Remark2.4,不存在具有奇数长度的拓扑(至少一个变量出现奇数次)K2n+1 = 0,这是正确的,因为当n是奇数时,(7)中的和为空现在我们可以假设τ= 2n。我们已经知道(见证据)引理2.2),每个公式都可以被识别为一棵二叉树,其中每个叶子都被一个适当的变量标记因此,我们需要的是评估一些具有2n个叶子的二叉树,其中每个标签出现偶数次。然后,通过注2.4,我们得到了所有偶数长度重言式的个数。在我们的例子中,C2n二叉树只有一个标号.这些树中的每一个都必须被标记以保持每个变量的偶数的条件令2 ij(j = 1,.,k)代表标签v j的出现次数。所以TG. Matecki/Electronic Notes in Theoretical Computer Science 140(2005)8185n−2你好!(2n)!.−−2 i1+… + 2 ik= 2 n。 现在很容易看出,对于一棵固定树,正确标号的个数等于n-集分成k个块的所有划分的个数,其中每个块分别有2 i j个成员(j =1,. ,k)。最后,适当的树的数量,从而重言式的数量等于C2n·n=22 i,.,2iΣΣ=C2n·(2n)!(2i)!...(2i)!2 i1 +. +2 ik =2 n1k2 i1 +. +2ik =2n1k什么结束了证明。Q定理2.6Tk=12kCn克i=0时. ΣK (k 2 i)n.我证据 请注意,这足以表明,(八)Σ2i1 +.. . + 2ik= n你好!=(2i1)! ...(2 ik)!1克朗2克朗i=0时.Σk(k2i)n. 我然后通过引理2.5证明该命题考虑r个函数f(cosh(z))k,其中recos h(z) =ez+e−z. 我们会把它拔出来的![zn]{(co sh(z))k}bytoways. 首先,请注意(ez+e−z)k=克i=0时.Σke(k−2i)z=我Σ∞n=0例znkn!i=0时.ΣK (k 2i)n我由于ez扩展为Σ∞n=0例zn. 所以,这是一个很好的机会![zn]{(co sh(z))k}等于0(8)的正楷和正楷。N∈t,其中h(z)∈n扩张到n∞n=0例z2n. 发现在(cosh(z))k中,我们使用柯西乘积规则,它给出了美国.克∞z2n=z2nn(2n)!.n=0例 (2n)!n=0例(2n)!2i1+. +2ik=2n (2i1)! ... (2 ik)!而且,正如我们所看到的,这给出了(8)的左边(如果n是奇数,那么86G. Matecki/Electronic Notes in Theoretical Computer Science 140(2005)81(8)中的和当然是空的QG. Matecki/Electronic Notes in Theoretical Computer Science 140(2005)8187| || |p∈ C[−−|n−n3重言式的累计数量在本节中,我们给出了所有长度不大于n的重言式的渐近行为。下面的定理给出了一个工具,通过只分析它的生成函数来发现给定序列的渐近行为。下面的引理的证明可以在[6][Thm.8.4.见[7]。5.3.2]。定理m3.1(Szegolélemma)Letv(z)在z<1中进行分析,其中具有有限多个单变量eiv(k),k=1, . . . . ,s,其中circiez=1。假设在每一个i(k)的中间边界上,v(z)都有f的展开Σ(九)v(z)=p≥0v(k)(1−ze−i(k))a(k)+pb(k),其中a(k)和b(k)>0是实数,并且对于z = 0,为展开选择的B等于v(0)。 然后(十)伊什[zn]{v(z)}=(q)(k)p.a(k)+pb(k)<$n(−ei<$(k))n+O(n−q),与(十一)k=1p=0n(q)= max(1/b(k))(q(a(k))1)。k =1. S对我们来说,Szegolélemmaweneeto knownowwthebeehaviorof. 1/2(1)n+1。下面的观察表明,(10)中的分量O(nq)并不决定整个序列的行为(q=2)。R emark3.2. 1/2<$(−1)n+1=Θ(n−3/2)。我的律师。 因为我们。1/2Σ(−1)n+1 =1. 2n从斯特林到穆拉估计[5]:n. 恩河2πne4n(2n−1)1e 12 n +1 1唯一奇异性|z|=1是1。为了找到z=1G. Matecki/Electronic Notes in Theoretical Computer Science 140(2005)8191JF−KStSF012K−设us定义函数f^SFsucasf^SF(z)=f<$SF(z),sof^(t)= 2 k·1 − t= v+ v t + v t2+.4k− 1+t2其中v1=^(0)=2k. 功能SF4k−1fSF 这是一个SsumptionsofSzegéo引理,其中a= 0且b= 1/ 2。那么,当q= 2时,我们有[zn]{fSF(z)}=v1.二分之一nΣ(n+O(n-2))什么结束了证明。Q引理3.8.- 是的 ΣSTk/(4k)n=−k1/ 2(−1)n−k1/ 2时间复杂度O(n)2k−1(4k− 1)n2k−1(4k + 1)n我的律师。定义前向函数f∈ST(z)=fST(z/(4k)),[zn]{f<$ST(z)}=[zn]{fST(z)}(4k)nSTk=n(4k)n和fST (z)=K2k−1克s=02s/k=.Σ1−S.1k−2sz.4k−z函数f∈ST具有以下奇性:4k,k/(k−2s)fors=0,1, . . , k和2sf=k。很明显,在圆|z| =1,唯一的奇点是1和-1(对于s = 0和s = k),内部没有奇点|z|1<.一、到在z=1和z=0−1的情况下,找到f个最小值的expansion功能:然后2、3、4、5、6、7、8、10、11、12、13、14、15、16、17、18、19、20、21、22、23、24、25、26、27、28、29、20、29、20、21、1 +z)=f<$ST(z)。Kk1−tk.Σ1−.1−k−2s +k−2st2f^1( t) =2k−1n·92G. Matecki/Electronic Notes in Theoretical Computer Science 140(2005)81·4k−1+t2+ 2k−1Ks=12s/k=K K4k− 1+t2k1 −tkk−1。Σ1− .1+k−2s−k−2st2f^2(t)=2k−1 ·4k+1−t2+ 2k−1Ks=02s/k=K K4k+1 −t2其中ref^J(0)=−k,f^J(0)=−k12k−1(4k−1) 22k−1(4k+1)SSG. Matecki/Electronic Notes in Theoretical Computer Science 140(2005)8193St12F−2N−→∞F→∞FnnnnnK函数F_S_T_a_t是S_zegéo_L_emma的一个ssumptions,其中a=0且db=1/ 2。最后,对于q= 2,我们有.- 是的Σ[zn]{f} (z)}=f^J(0)二分之一n(−1)n+f^J(0)二分之一n时间复杂度O(n)Q4结论最后,我们为主要结果做好了准备下面的定理表明,对于τ-拓扑,既不存在渐近密度,也不存在累积渐近密度定理4.1(十九)Tklim infn =0n→∞kTk1(20)lim supn =n→∞k2k−1证据 注意limn→∞(k2i)2nk2n等于1,如果i= 0或i=k,并且对于任何0
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++标准程序库:权威指南
- Java解惑:奇数判断误区与改进方法
- C++编程必读:20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程:从入门到精通
- Spring3.0权威指南:JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略:从环境配置到索引创建
- 内存虚拟硬盘技术:提升电脑速度的秘密武器
- Java操作数据库:保存与显示图片到数据库及页面
- ISO14001:2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发:触发器与控制器重定向技术详解
- FPGA开发实战指南:创新设计与进阶技巧
- ShopExV4.8二次开发入门:解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功