计算机科学中的数理逻辑 课件 4.3 FC的语义

4.3FC的语义计算机科学中的数理逻辑2026年4月第4章一阶谓词演算一阶谓词演算形式系统的语义一阶谓词演算形式系统的语义，是指对一阶语言所赋于的意义，即对个体常元、函词、谓词的指称，对变元取值的指派，对量词、联结词意义的规定。更具体地说，一阶谓词演算形式系统的语义是赋予它的一个数学结构，该结构包括：结构与指派01/结构(Structure)一个数学结构U=<U,I>：•个体域U：讨论对象的全体范围。•解释I：将符号映射到具体对象的规则。◦常元→个体域中的特定元素◦n元函词→个体域上的n元函数◦n元谓词→个体域上的n元关系02/指派(Assignment)在一阶谓词演算中，指派是指映射s：{v1,v2,v3,…}→U，即对任一i=1,2,3,…,s(vi)

U，即s对变元指派个体作为其取值。为什么两者缺一不可？只有同时给定结构U（确定“世界”是什么样的）和指派s（确定“谈论对象”是谁），一阶语言中的公式才能最终获得一个确定的“真值”（真或假）。真值规定真值定义的补充规定除了基本的否定、蕴涵和全称量词外，一阶逻辑中还需补充定义合取、析取与存在量词的真值条件，以构建完整的语义解释框架。合取式(Conjunction)B∧C[s]为真，当且仅当析取式(Disjunction)B∨C[s]为真，当且仅当存在量化式(Existential)∃vB[s]为真，当且仅当实例分析：例4.16——在自然数结构下分析公式真值📋给定结构设定•个体域(Domain)U：

自然数集N={0,1,2,...}•解释函数(Interpretation)I：➔二元谓词P₁⁽²⁾对应“小于等于”(≤)关系

➔一元函词f₁⁽¹⁾对应“后继”函数(x+1)

➔常元符号a₁对应自然数01.P₁⁽²⁾(a₁,f₁⁽¹⁾(v₁))：“0≤v₁+1”(对任何指派均为真)2.∀v₁P₁⁽²⁾(a₁,v₁)：“所有自然数v₁，0≤v₁”(结论为真)3.∀v₁∃v₂P₁⁽²⁾(f₁⁽¹⁾(v₁),v₂)：“总有比v₁+1更大的数”(结论为真)4.∃v₂P₁⁽²⁾(f₁⁽¹⁾(v₂),v₂)：“存在v₂使得v₂+1≤v₂”(结论为假)FC公理的永真性证明(I)确保形式系统的逻辑可靠性基础01/第一组公理：重言式公理包含公理模式：AX(1.1),AX(1.2),AX(1.3)。证明思路：这类公理本质上是命题逻辑中的重言式。在一阶逻辑的任何解释下，其中的原子公式无论被赋值为真(1)还是假(0)，根据经典的真值表计算规则，整个复合公式的真值都恒为真，不受具体解释模型的影响。02/第二组公理：全称指定(AX2)∀vA→A_t^v（其中项t对于变元v在A中是可代入的）若“性质A对论域中所有个体v都成立”为真，则性质A必然对论域中任意一个具体的个体t成立。这符合人类的直觉逻辑，因此该公理模式是永真的。为什么要证明公理的永真性？公理是推理系统的基石，若基石不永真（即存在为假的可能），推导出来的定理就不可靠。只有确保公理在所有解释下都为真，才能保证系统具备逻辑可靠性。FC公理的永真性证明(II)确保形式推演系统的逻辑可靠性与完备性基础第三组公理(AX3)·全称分配规则∀v(A→B)→(∀vA→∀vB)直观语义解释：若“对论域中所有对象v，命题A成立能推导出B成立”为真，并且“对所有v，A恒成立”也为真，那么逻辑上必然能推出：“对所有v，B也恒成立”。这是保证全称量词分配律的核心公理。第四组公理(AX4)·概括规则限制A→∀vA(v在A中无自由出现)条件保证了变元v的取值与公式A的真假完全无关，因此可以安全地为A添加全称量词约束。证明核心思路这两组公理构建了一阶逻辑中量