23个人,为什么生日相同的机会已过半?
在一年365天、生日等可能且彼此独立的简化模型中,23人里至少两人同生日的概率约为50.7%。直觉常把问题误读成“有人和我同生日”,实际上这里允许任何一对人相同。
23个人形成253对关系。更容易的算法是先计算所有生日互不相同的概率,再用1减去它:1 − (365×364×…×343)/365²³。真实生日分布并不均匀,但这个模型已经足够展示:关系数量增长,可能远快于人数本身。
华盛顿大学:生日问题讲义 ↗一个余数能排除无穷多个解,一次坐标变换却消不掉潮汐。从可以推演的例子出发,走近数学、物理、计算与语言中的问题。每篇附参考资料,适合带着纸笔慢慢读。
选择感兴趣的方向,点标题展开正文。公式与例子保留了必要条件,可以顺着参考资料继续读。
在普通实数里,2x=2可以两边除以2,得到x=1。把计算放到十二小时制的钟面上,情况变了:2×1和2×7都与2相差12的整数倍,所以x=1与x=7都是解。钟面上的加法、乘法仍有规则,熟悉的消去步骤却失效了。
原因可以直接算出来:在模12的运算中,2×6=0,但2和6都不等于0。若把2x=2误写成x=1,就抹掉了乘以2时丢失的信息。只有与12互素的数才有乘法逆元,例如5×5=1,因此除以5可以严格定义。
代数学研究运算所服从的结构。一个推理能否从实数搬到另一个系统,取决于证明到底用了哪些性质。遇到陌生对象,先检查消去律、逆元和零因子,常比照搬计算习惯更可靠。
参考:Etingof等《Introduction to Representation Theory》,代数与商结构 ↗本篇链接 ↗设一个操作把三个数循环移动:(x,y,z)变成(z,x,y)。连续做三次就回到原处,这个关系可以用矩阵的三次方等于单位矩阵表达。表示论把抽象的操作关系放进线性空间,让矩阵运算替我们检查结构。
三个坐标的共同变化与彼此差异可以分开。向量(1,1,1)在循环移动下不变,张成一个一维子空间;满足x+y+z=0的向量组成另一个保持不变的平面。任意向量都能唯一分成平均值部分与总和为0的部分,三维问题于是被拆成一维与二维问题。
这里有用的是找到在操作下保持封闭的子空间。对称性往往迫使某些变量只能一起变化,另一些则始终保持不变。分解是否总能完成,还要看所用的域和代数结构;本例在实数空间中的分解可以直接验证。
参考:Etingof等《Introduction to Representation Theory》,表示与不变子空间 ↗本篇链接 ↗整数平方除以3,余数只能是0或1。这个小事实已经能排除x²+y²=3的整数解:若两平方和的余数为0,两项就都必须为0,说明x、y都被3整除;但这会让左边被9整除,右边却不能。
再看x²+y²=3z²。如果存在非零整数解,先把三个数的公因子约尽。同样的模3检查迫使x、y都被3整除;代回后又得到z²被3整除,因而z也被3整除。这与已经约尽公因子矛盾。
推理的关键是将一个假定的最简解逼成更不简的解。余数提供局部限制,最简性把限制升级成全局矛盾。数论里很多难题都依靠这种配合:先在较小的算术世界检查,再研究这些检查能约束原问题到什么程度。
参考:MIT 18.781:数论,同余与整除 ↗本篇链接 ↗直线y=0与直线y=x交于原点;它与抛物线y=x²也交于原点。如果只列出交点坐标,两种情况看起来完全相同。把y=0代回方程,却分别得到x=0与x²=0:后一个方程在原点有二重根,对应相切。
交点的重数使这种差别可以进入计算。轻轻把横线移到y=ε,在实数范围,抛物线可能出现两个交点,也可能没有;在复数范围并按重数计算,二次方程的两个根仍有统一的计数方式。特定位置上重合的根,保存着扰动后怎样分开的线索。
代数几何把多项式关系与几何对象放在一起研究。它提醒我们,单独的解集有时不足以表达一个方程系统:重数、局部变化和所选数域也属于问题的一部分。讨论“两个模型给出同一结果”时,要先说明保留了哪些结构。
参考:Vakil《The Rising Sea: Foundations of Algebraic Geometry》 ↗本篇链接 ↗把纸卷成圆筒,纸面上相邻两点之间的长度可以保持不变。沿接缝剪开,圆筒还能铺回平面。球面却做不到:若坚持保持纸上的所有局部长度,就无法将一张平纸完整贴上球面而不拉伸、剪裁或起皱。
区分它们的是高斯曲率。平面和圆柱面的高斯曲率都为0,半径R的球面则为1/R²。高斯的绝妙定理说明,这种曲率可以从曲面自身的长度测量中确定,在保持长度的局部变形下不会改变。
沿球面测地线围成的小三角形,内角和超过180度;多出的弧度等于面积除以R²。生活在曲面上的观察者,单靠测长与测角就能发现几何差异,无须先从外面观看它。这是“内在性质”一个可以实际计算的例子。
参考:Katz:Differential Geometry and Topology,高斯曲率 ↗本篇链接 ↗在一张实心圆盘上画一个闭合圈,可以让它连续缩小,最后收成一点,全程留在圆盘里。若纸的中央挖掉一个洞,一个绕洞一周的圈就无法用同样方式缩掉:要么穿过缺口,要么剪断曲线,都会违反允许的操作。
这里检查的是连续变形期间什么始终不变。围绕缺口的绕行次数,可以为圆环区域上的闭合路径提供整数标记;连续移动路径而不跨过洞,无法把绕行一次变成零次。基本群把路径的连接与变形进一步组织成代数结构。
“存在某种变形”和“已经画出几张相似的图”之间有很大距离。拓扑不变量的作用,是证明无论怎样尝试,都不会越过某个结构障碍。找到在全部允许操作下保持不变的量,常能一次排除无穷多条失败路线。
参考:MIT 18.901:拓扑学讲义,基本群与路径变形 ↗本篇链接 ↗在0到1的闭区间上看函数fₙ(x)=xⁿ。固定任何x<1,随着n增大,函数值趋近0;但x=1处始终等于1。每个fₙ都连续,极限函数却在1处发生跳跃。逐点收敛本身无法保证连续性留到极限。
原因在“多大的n才够用”。逐点收敛允许不同位置各自等到不同时间;一致收敛要求找到同一个N,使之后所有函数在整个区间上都足够接近极限。在靠近1而又不到1的位置,xⁿ总能保持很大,统一的误差界因而失败。
这一区别可以写成量词的交换:对每个x存在N,与存在N适用于每个x,强弱不同。把无限过程交换次序前,需要检查足够的条件。实分析用精确误差控制回答的,正是哪些看似自然的交换可以成立。
参考:MIT 18.100C:逐点收敛与一致收敛 ↗本篇链接 ↗想象一个无限长的数列,第n个数列只在第n个位置等于1,其余位置全为0。盯住任何一个固定位置,最终看到的都是0;但每个数列的平方和始终为1,整体长度没有减小。变化只是不断向更远的位置移动。
在平方可求和的数列空间ℓ²中,把这些数列记成eₙ。对任意固定的ℓ²向量a,内积⟨eₙ,a⟩=aₙ趋近0,所以eₙ弱收敛到0;它与0的范数距离却始终为1,因而不按范数收敛。弱收敛检查所有固定的连续线性观察,要求仍比统一控制整体距离弱。
这个例子说明,局部或固定探针看见的稳定,不一定意味着全局误差已经消失。处理函数、信号或无限多个自由度时,必须先指定使用哪一种距离与哪一类观察,再讨论“越来越接近”。
参考:Christopher Heil:Weak and Weak* Convergence ↗本篇链接 ↗一根均匀细杆的温度起伏,可以分成不同波长的波。在简化热方程里,频率为k的起伏随时间乘上exp(−κk²t),κ是正的扩散系数。波纹越密,衰减越快,所以温度图像会逐渐变得平滑。
如果想从今天的温度倒推过去,就要把这些分量乘回exp(κk²t)。测量里极小的高频噪声会被猛烈放大;提高一点测量精度,仍可能不足以稳定恢复细节。某种理想条件下能够唯一确定过去,并不保证实际数据允许可靠重建。
这就是逆问题为何常需要正则化:接受某种平滑先验或约束,以换取对误差的控制。约束带来的偏差必须说明。偏微分方程不仅描述物理变化,也让我们看清信息怎样流失,以及哪些反向推断会对微小噪声过于敏感。
参考:Gilbert Strang:Heat Equation ↗本篇链接 ↗考虑区间上的倍增映射:每一步把x乘以2,再去掉整数部分。写成二进制,它恰好把小数点后的第一位移走。只要初值有无限精度,每一步都被确定;若只知道前二十位,那么大约二十步后,结果就开始取决于尚未测到的位。
在尚未跨越取模边界的局部,两条相近轨道的差距每步约放大一倍。有限精度于是对应有限的预测窗口。增加测量精度能延长窗口,但需要的精度会随预测步数迅速增长。确定性与实际可预测性可以同时存在很大距离。
混沌研究寻找这种敏感依赖的条件,也研究长期统计规律。单条轨道很难远期预测,不妨碍某些平均量可以稳定描述。不过,不能看到任何一次预测失败就宣布发生了混沌;还需要检查模型和动力学证据。
参考:Sethna与Myers:Chaos and Lyapunov Exponents ↗本篇链接 ↗一个聚会里,有些人彼此握手。把每个人握手的次数相加,每次握手都会被算两次,因此总和必为偶数。这立刻推出:握手次数为奇数的人,人数一定是偶数。无须知道每个人究竟与谁握过手。
更一般地,设n个人里要选k人并指定一位负责人。先选团队再选负责人,有k·C(n,k)种;先选负责人,再从其余n−1人里选k−1位成员,有n·C(n−1,k−1)种。两边计算同一批带负责人团队,因此必然相等。
双重计数的力量来自对象之间的明确对应。写出两个看似相关的表达式还不够,必须说明每个对象被计了几次、有没有遗漏。许多漂亮恒等式背后,藏着一个比代数展开更容易理解的选择过程。
参考:Alexander Hulpke:Combinatorics,双重计数 ↗本篇链接 ↗一个电子受散射后,实验可能看到额外的光子。在足够高能量的相互作用里,还可能产生新的粒子与反粒子。若理论只允许固定数目的小球移动,就必须不断临时扩大原来的描述空间。量子场论从一开始便容纳这些不同粒子数的状态。
对自由场做量子化时,不同动量模式类似一组量子谐振子。某个模式激发一次,可以对应一个该模式的粒子;激发次数决定占据数。相互作用则允许不同模式交换能量,并在满足守恒条件下改变粒子数。这里的解释以适当的自由或渐近粒子描述为前提。
这使许多表面不同的过程获得共同语言:电子场、光子场及其耦合决定哪些散射和衰变可以发生。费曼图帮助组织相关计算,但它们通常表示振幅展开中的项,不能不加条件地当作微观过程的逐帧照片。
参考:David Tong:Quantum Field Theory,Free Fields ↗本篇链接 ↗把一支理想铅笔竖在桌上,水平方向没有预先偏好的倒下方位;一旦倒下,它却选中了某个方向。描述规律的对称,与某个状态表现出的对称,并不必然相同。这个例子只能说明区分方式,不能代替真实量子场论中的动力学。
在粒子物理里,希格斯场的真空结构与电弱相互作用的组织方式紧密相关。希格斯机制使W、Z玻色子具有质量,同时保留理论所需的一致性结构。把它简单讲成“所有粒子撞上某种介质所以变重”,会丢掉规范理论与真空选择的关键。
一个模型不仅要列出粒子,还要说明允许哪些相互作用、如何生成质量,以及怎样给出可检验的散射与衰变预测。粒子物理的深处,经常是用少量结构原则同时约束许多实验现象。
参考:J. Iliopoulos:Introduction to the Standard Model of the Electro-Weak Interactions ↗本篇链接 ↗一个足够小的自由下落实验室里,悬浮物体在短时间内看起来近似不受重力。这是等效原理的出发点之一。但把实验室做大,就会发现不同位置的物体并非完全平行地坠落:靠近地球中心的方向略有不同,引力强度也随位置变化。
这些相对加速度构成潮汐效应。广义相对论用时空曲率描述相邻自由落体轨迹怎样会聚或分离。选取一个局部自由落体系,可以在一点消去某些坐标描述中的引力项,却无法把真实曲率一并抹掉。
这一区分为判断“效应能否通过换坐标消失”提供了标准。某个物理量在特定坐标下为零,未必代表所有可测的相对效应都为零;要寻找能通过邻近轨迹比较确定的结构。
参考:David Tong:General Relativity,曲率与测地偏离 ↗本篇链接 ↗假设地球与另一颗恒星在同一惯性系里相距4光年。一位旅行者以0.8倍光速前往再返回,忽略转向耗时。地球系中每程5年,总共10年;旅行者每程积累的固有时乘上√(1−0.8²)=0.6,总共6年。重逢时可以直接比较钟面。
关键在两条世界线不同:留在地球的一方在这个理想化模型中保持惯性,旅行者必须改变运动方向,无法用一个贯穿全程的惯性系与其对称交换。加速改变了路径;实际积累多少时间,需要沿整条路径计算。
时间膨胀公式中的“谁在运动”不能脱离具体比较程序。对远方事件怎样定义同时,与两只钟最终重逢后的读数差,是不同层次的问题。把事件、参考系和比较方式写清,所谓悖论通常就会变成可计算的几何关系。
参考:David Tong:Dynamics and Relativity,狭义相对论 ↗本篇链接 ↗在均匀膨胀的模型里,两点的物理距离可以写成D(t)=a(t)χ,其中χ是保持不变的共动距离,a是尺度因子。对时间求导得到Ḋ=HD,H=ȧ/a。换到另一位共动观察者的位置,任意两点之间仍服从同样的关系,因此看见远处整体退行不够用来挑出一个特殊中心。
把模型倒推时,a变小表示共动点之间的距离整体缩小。大爆炸模型描述的是可观测宇宙早期的热、密和膨胀历史;将它画成原有空房间里某一点爆炸,再向外飞散,容易偷偷加入模型并未要求的外部空间。
距离还要区分测量定义:光行距离、光度距离、角直径距离在宇宙学中并不总是同一个数。几何模型、光的传播和实际观测必须接起来,才能把一个红移可靠地解释成有关宇宙历史的信息。
参考:David Tong:Cosmology,The Expanding Universe ↗本篇链接 ↗在整数数量子霍尔效应的理想描述中,霍尔电导以e²/h的整数倍出现。材料的微观细节可以改变很多,测得的平台却能保持高度稳定。这促使我们寻找比某一条具体电子轨道更稳固的描述。
对适当的非相互作用能带模型,填满能带的几何结构可由陈数这样的整数刻画。在保持相关能隙等条件、又不跨越相变的连续变形中,整数不能一点点变成另一个整数;要改变它,就得出现使原来描述失效的关键变化。
保护条件必须一同讲清。实际样品的无序、温度与相互作用都需要处理,更不是所有固体性质都由拓扑决定。这里有启发性的是:稳定的宏观行为,有时可以由结构约束解释,而无需要求每个微观细节都被精确复制。
参考:David Tong:The Quantum Hall Effect ↗本篇链接 ↗设一盒气体最初只占据左半边,打开隔板后,通常会扩散到整个盒子。把全部粒子的速度精确反向,在适用的理想可逆动力学下可以构造回去的轨道。这个可能性与日常几乎看不到自发复原并不矛盾。
“遍布两边”的宏观描述,通常对应远多于“全部在左边”的微观安排。玻尔兹曼熵S=k log Ω把相应状态数或相空间体积引入解释。需要同时注意初态、宏观划分与统计假设;单凭微观运动方程的时间反演性质,推不出完整的宏观时间箭头。
低熵起点非常关键。若一开始已经处于平衡附近,所谓“熵必然马上明显增加”就不成立,有限系统还会有涨落。统计物理把常见趋势解释为大量自由度中的典型行为,同时保留少见事件的概率地位。
参考:David Tong:Statistical Physics,熵与统计系综 ↗本篇链接 ↗对理想弹簧振子,运动方程是mẍ+kx=0。定义E=mẋ²/2+kx²/2,求导得到Ė=ẋ(mẍ+kx)=0,所以E守恒。这里没有追踪所有可能的运动轨迹,只利用方程的结构就获得对全部解的约束。
诺特定理把这一思路推广:在满足适用条件的变分理论中,作用量的连续对称性对应守恒关系。时间平移关联能量,空间平移关联动量,旋转关联角动量。要检查的是作用量和边界条件的相应性质,不能见到任何外观相似就宣布存在守恒量。
加上摩擦后,原来机械系统的能量会降低;把耗散的环境自由度重新纳入,才可能恢复更完整的能量账目。选择系统边界、说明对称性以及推导守恒关系,是数学物理让直觉变得可检查的一条路线。
参考:David Tong:Classical Field Theory,Noether定理 ↗本篇链接 ↗在每条边代价都为1的图里,从起点先访问一步能到的点,再访问两步能到的点,依次展开。这就是广度优先搜索的分层结构。第一次发现某个点时,记录的层数已经是它的最短距离。
理由可以反证:若某点第一次在第k层被发现,却存在少于k步的路径,那么该路径上它之前的点应在更早的层被处理,并提前发现它。这与“第一次在第k层发现”矛盾。正确性来自处理顺序与路径结构的配合。
把边改成不同权重,按步数分层就可能失效:两条便宜的边可以比一条昂贵的边更短。算法的适用前提属于证明的一部分。真正掌握一个方法,意味着知道它维护什么不变量,也知道改动哪些条件会使证明断裂。
参考:MIT 6.006:Breadth-First Search ↗本篇链接 ↗给出一个已经填好的数独,检查行、列和宫里的数字是否重复很直接;但从空格较多的题面寻找填法,要面对大量可能组合。复杂性理论将这类区别表达为问题规模增长时所需资源的变化,而不是某一道题让人感觉多难。
P与NP讨论的是一整类随输入规模扩展的判定问题。NP要求“是”的实例有长度受多项式约束、且能被快速核验的证书,并不意为“没有快速算法”。P是否等于NP仍未解决。现实中的固定9×9数独,也不能直接等同于规模无界的复杂性问题。
归约提供了连接问题的方式:若A能高效变成B,且B有高效算法,就能高效解A。证明B难时,方向必须是把已知难的A送入B。把箭头写反,会让一段看似有力的论证失去结论。
参考:Boaz Barak:Polynomial-Time Reductions ↗本篇链接 ↗一台只有简单读写规则的图灵机,和可以使用变量、数组与循环的程序语言,看起来差距巨大。可在适当编码下,一方可以逐步模拟另一方。这种模拟说明,它们能处理的可计算任务具有相同范围,尽管运行时间可能相差很多。
通用机器还可以把另一个程序的描述当作输入,解释并执行它。程序于是既能充当规则,也能充当数据;编译器、解释器和很多自我指涉论证都依赖这个转变。编码的细节需要有限、有效,不能把一个无限答案表偷偷当成免费部件。
因此,比较两种计算工具至少要分两层:能否完成同一任务,以及消耗多少时间、空间或其他资源。前一层相同,后一层仍可能有巨大的差异。把表达能力与效率拆开,能让“某种新机器突破限制”的说法接受更精确的检查。
参考:Boaz Barak:Equivalent Models of Computation ↗本篇链接 ↗对固定长度的消息m,用同样长、独立均匀随机的密钥k做逐位异或,得到c=m⊕k。给定任何明文m与密文c,恰好有一个密钥把它们连接起来;所有候选明文于是都能解释这份密文。这是一次一密达到完美保密的基本原因。
条件一变,结论就会变。若两条消息复用同一个密钥,c₁⊕c₂=m₁⊕m₂,明文之间的关系便泄露出来。密文仍可能长得杂乱,但“看上去乱”没有挡住这个精确推导。密钥必须随机、足够长且不复用。
现代密码学常转而要求资源受限的攻击者难以区分两种消息的密文,并明确允许哪些查询与辅助信息。安全证明总是相对某个威胁模型成立。先把对手、目标和假设写清,才能判断一句“无法破解”究竟保护了什么。
参考:Boneh与Shoup:A Graduate Course in Applied Cryptography ↗本篇链接 ↗“每个人都喜欢某一本书”允许不同人选不同的书;“有一本书,每个人都喜欢”要求找到同一本。用量词写出来,分别是∀x∃y L(x,y)与∃y∀x L(x,y)。第二句能推出第一句,反向推理一般不成立。
举一个两人的模型就够:甲只喜欢A书,乙只喜欢B书,且A、B不同。第一句为真,第二句为假。反例只需满足前提又破坏结论,无须展示现实中所有人的阅读偏好。这也是模型在逻辑中很有力的原因。
在实际论证里,“每次测试都有一个解释”也未必意味着“存在一个解释,能同时说明所有测试”。谁可以依赖谁、同一个对象要不要贯穿全程,常被自然语言隐藏。把量词顺序写出,能让这种依赖关系无处含糊。
参考:斯坦福哲学百科:Classical Logic,量词与模型 ↗本篇链接 ↗一个程序从0开始,把1加到n。若循环变量i表示已经处理到的位置,可以维护不变量s=i(i+1)/2。开始时i=0、s=0,性质成立;每一步把i增加1,再把新i加入s,代数计算说明性质继续成立。退出时i=n,于是得到目标和式。
证明还要说明循环为何会结束,例如n−i在循环条件下是非负整数并逐步减少。只证明“如果结束就给出正确结果”,属于部分正确性;加入终止论证,才得到相应的总正确性。机器整数溢出等真实语义也不能被自动忽略。
测试展示选定输入上的行为,形式验证尝试覆盖规格规定的全部输入。证明的可信范围仍由规格和模型决定:若把错误要求写进规格,再严格的证明也只会保证程序满足那份要求。找对要证明的命题,同样重要。
参考:Software Foundations:Hoare Logic ↗本篇链接 ↗假设一台机器只有N个状态,却要判断任意长字符串的括号是否正确配对。让它分别读完0个、1个,直到N个左括号,共有N+1种前缀。根据抽屉原理,至少两种不同长度的前缀会把它带到同一个状态。
设撞在一起的前缀分别有i个与j个左括号,且i<j。接着给两者都添上i个右括号。前一种字符串恰好配平,后一种还留下j−i个左括号。机器从相同状态读同样的后缀,只能做出同样判断,于是至少错一个。
若允许一个可任意增长的栈,情况就不同了:每遇左括号压栈,每遇右括号弹栈。机器模型的记忆结构决定能区分哪些历史。对有界长度的输入可以预留足够状态;上面的不可能结论针对无界深度。
参考:Scott Aaronson:非正则语言与有限自动机 ↗本篇链接 ↗假设存在总能终止的程序H,准确判断任意程序P在输入x上会不会停机。现在构造D:收到一个程序描述p后,先问H(p,p);若回答会停机,D就无限循环;若回答不会,D就立刻停止。
再把D自身的描述交给D。若H判断D会停机,D按照定义就不停;若H判断D不停,D就停止。两种回答都与其必须准确的要求矛盾。因此,这种适用于所有程序和输入、且自己总会结束的判断器不存在。
限制中的每个词都重要。某一类程序可能有可行的终止性检查,某个具体程序也可能容易判断。遇到无法完成的通用任务时,缩小输入范围、允许不确定答案或改变目标,常比继续许诺一个万能工具更有建设性。
参考:Boaz Barak:Universality and Uncomputability ↗本篇链接 ↗在一个简单的带类型语言里,加法要求数字,条件分支要求布尔值。表达式“如果3,那么真,否则5”会在运行前被拒绝。类型规则通过限制表达式的组合方式,提前排除一些没有定义的执行情形。
类型安全的经典证明常分为两步:保持性说明执行一步后类型不变;进展性说明合适的闭合、类型正确表达式要么已经是值,要么还能继续执行。把两项结合,便能证明它不会突然卡在模型规定的类型错误上。
这份保证不会自动让一个排序程序排得正确,也不必然保证程序终止。要证明更多性质,需要更强的规格、类型或其他验证工具。程序语言理论的一个重要习惯,是将每一种保证写成明确命题,逐项检查它依赖的语义与条件。
参考:Software Foundations:Type Systems,进展性与保持性 ↗本篇链接 ↗英语句子“I saw the man with a telescope”可以理解为那个人拿着望远镜,也可以理解为我借助望远镜看见了那个人。词序不变,改变的是“with a telescope”与哪一部分组合。句法分析需要表达这种层次关系。
把句子表示成树,可以把修饰语接在名词短语内部,或让相应成分作用于看见这一事件。不同的分组随后约束语义如何组合。不能仅凭出现位置相邻,就认定两个词属于同一个结构单位;替换、协调等测试可以为结构假设提供证据。
形式句法尝试用明确规则描述哪些结构能够生成,并让规则面对真实语言材料。一个模型若什么词串都能任意画出一棵树,就失去了约束力。结构分析的价值,体现在它同时解释了什么,又排除了什么。
参考:MIT 24.900:Syntax 1,短语结构 ↗本篇链接 ↗这句话既可以表示每位学生各自读过某本书,也可以表示有某一本书,所有学生都读过。第一种读法容许甲读A、乙读B;第二种要求共同的书。自然语言的表面形式没有把这种区别完整写出来。
形式语义会明确对象、谓词和量词的组合。例如先让“每位学生”取宽辖域,书的选择就可以依赖学生;若“一本书”取宽辖域,就先固定书,再检查全部学生。模型给出可检验的真值条件:哪些情境使句子在某种读法下成立。
组合原则约束整句意义如何来自词的意义和组合结构。真正的分析需要从部件推到句子,而不只是给整句话贴两个标签。语义学因此可以追问,歧义来自词本身、结构,还是另外的解释机制。
参考:Barbara Partee:Logical Structure in Natural Language,量词辖域 ↗本篇链接 ↗在经典一阶逻辑的一种常用形式化中,这句话写成:对每个x,如果x是独角兽,那么x有角。只要找不到一个“是独角兽却没有角”的反例,整个全称命题就为真。若论域里根本没有独角兽,它仍然成立。
由此不能推出“至少有一只独角兽有角”。后一命题需要某个对象同时满足两个条件,额外承担了存在承诺。将全称陈述直接换成存在陈述,会跨过一个没有获得支持的推理步骤。
自然语言里,人们有时会从说话行为推测相关对象确实存在,这需要另行分析。逻辑语义先规定表达式在模型中怎样解释,再区分哪些推论由真值条件保证、哪些依赖语境。一个条件没有反例,与确实找到了满足条件的对象,必须分别记录。
参考:斯坦福哲学百科:Quantifiers and Quantification ↗本篇链接 ↗从逻辑上说,“有些人到了”与“所有人都到了”可以同时成立。但在合适语境中,听者通常会推测:既然对方没说信息更强的“所有人”,可能就是还没到齐。这个额外推断叫作标量含义之一。
推断依赖说话者掌握多少信息。若他只看见门口两个人进来,根本不知道其余人在哪,“有些人到了”就未必暗示未到齐。形式语用模型可以把说话者的知识状态与表达选择纳入,再让听者反推可能情形。
研究发现,这类含义的强度会随语言环境变化,不能简单给“有些”添加一个永远固定的“并非全部”。语用推理可以有系统,却仍然可撤销。检查一句话引出的判断时,值得追问它来自字面内容,还是来自对说话者的假设。
参考:Judith Degen(2015):Some含义的语境依赖研究 ↗本篇链接 ↗用规则S→aSb或S→空串,可以生成ab、aabb、aaabbb等无限多个字符串。有限规则能够描述无限集合,这使形式语法有机会处理超出记忆清单的结构。但生成了无限多个串,本身没有说明它们怎样获得意义,也没有说明人脑如何处理它们。
自然语言模型还需要解释不同结构的分布、歧义与理解难度。一个语法如果生成过多本不应允许的句子,就是过度生成;只漏掉少数常见结构,也可能说明它缺了一项重要机制。用几个漂亮例子展示模型远远不够。
无限串模型与真实人类有限的记忆、时间和经验之间,还隔着能力与实际表现的区分。形式化的价值在于把假设写到可以暴露错误的程度:哪些规则产生哪些预测,什么数据会要求我们改动它。
参考:Boaz Barak:Automata and Regular Expressions,形式语言 ↗本篇链接 ↗“现任法国国王是秃头”看起来像是在谈论某个人,但法国没有现任国王。罗素提出一种分析:这句话同时要求有一个现任法国国王、这样的人至多一个,而且那个人是秃头。把隐含承诺拆开后,就无须为了理解句子而额外承认一个不存在的人。
否定放在哪里也会改变意思。“并非存在唯一的法国国王且他是秃头”,与“存在唯一的法国国王而他不是秃头”,并不相同。前一句在相关存在条件失败时可以成立,后一句仍承担国王存在的承诺。
罗素的处理是影响深远的理论方案,后续语义学还提出了预设等不同分析。这里值得保留的方法,是让争论中的隐含结构显形:哪一部分是假设存在,哪一部分要求唯一,哪一部分才是真正要判断的性质。
参考:斯坦福哲学百科:Descriptions,罗素摹状词理论 ↗本篇链接 ↗在一年365天、生日等可能且彼此独立的简化模型中,23人里至少两人同生日的概率约为50.7%。直觉常把问题误读成“有人和我同生日”,实际上这里允许任何一对人相同。
23个人形成253对关系。更容易的算法是先计算所有生日互不相同的概率,再用1减去它:1 − (365×364×…×343)/365²³。真实生日分布并不均匀,但这个模型已经足够展示:关系数量增长,可能远快于人数本身。
华盛顿大学:生日问题讲义 ↗“所有行星都是立方体;地球是行星;所以地球是立方体。”推理形式有效:如果前提都真,结论就不能是假。问题在于第一条前提并不真实。
逻辑有效性检查前提到结论的关系;健全论证还要求前提为真。讨论中既要检查推导,也要检查事实根据。一个人在形式上无懈可击,仍可能从错误的出发点走得很远。
斯坦福哲学百科:逻辑后承 ↗对于满足适用条件、足以表达基本算术且一致的有效公理化形式系统,不完备性结果表明:系统不能解决其中所有算术命题。这里的限制属于特定形式系统与证明能力。
它不是“任何事情都无法证明”,也不是人类直觉必然胜过所有机器的快捷证明。真正令人着迷的是,数学可以用严格的论证研究严格论证自身的边界。边界很深刻,仍需要把条件写全。
斯坦福哲学百科:不完备性定理 ↗探测器记录粒子与材料相互作用留下的信号。科学家利用磁场中的弯曲轨迹、能量沉积和不同探测器的响应,重建可能发生的过程。常见的彩色碰撞图是数据的可视化表达。
短寿命粒子可能在抵达探测器前已经衰变。研究者检查衰变产物的能量和动量等信息,与不同模型的预测比较。看见一条线不是结论的终点;从信号到解释,才是科学推断最精彩的部分。
CERN:探测器如何工作 ↗处理括号嵌套时,最晚打开的括号应该最先关闭。一个“栈”保存尚未配对的开括号:遇到开括号压入,遇到闭括号检查栈顶并移出。顺序本身就携带了结构。
这与程序调用、表达式解析和形式语言有关。一个很小的例子说明:选择合适的表示,可以把原本容易混乱的问题变成稳定的操作步骤。聪明有时表现为更少的蛮力,以及更合适的结构。
IIT Bombay:形式语言与自动机课程讲义 ↗