2.3 谓词公式与翻译

CHAPTER02谓词逻辑2.3谓词公式与翻译目录CONTENTS01谓词公式合式公式的定义

与构成规则02例题解析（一）自然语言语句的

符号化03翻译与解释谓词公式的解释

与个体域的重要性04例题解析（二）在给定解释下

求公式的真值05谓词公式的分类有效公式、矛盾公式

可满足公式2.3.1谓词公式定义2.6：谓词演算的合式公式(Well-FormedFormula)1原子谓词公式是合式公式。2若A是合式公式，则¬A是一个合式公式。3若A和B都是合式公式，则(A∧B),(A∨B),(A→B),和(A↔B)是合式公式。4如果A是合式公式，x是A中出现的任何变元，则(∀x)A和(∃x)A都是合式公式。5封闭性：只有经过有限次地应用规则(1),(2),(3),(4)所得到的公式是合式公式。逻辑符号的形式化表达合式公式示例与说明有效公式Valid1.(∀x)(∃y)(P(x,y)→(Q(x,y)∨R(x)))2.(∀x)(P(x)∨(∃x)R(x,y))符合形成规则的语法结构，量词与联结词使用正确，括号配对完整。无效公式Invalid1.(∀x)(P(x)→R(x)[语法错误：缺右括号]2.(∃y)(∀x)(∨P(x,y))[语法错误：缺运算项]公式构造过程中违反了形成规则，存在语法缺陷，无法构成合法的逻辑表达式。括号省略约定1.省略最外层括号

为书写简洁，公式整体最外层的一对括号通常可以省略。

例:(∃xR(x))➔∃xR(x)2.量词辖域的特殊情况

若量词的辖域中仅包含一个原子公式，辖域的括号可省略。否则，必须保留括号以明确运算优先级。例题2.6：符号化（一）(1)并非每个实数都是有理数设M(x):x是实数|F(x):x是有理数▍符号化结果：¬(∀x)(M(x)→F(x))(2)没有不犯错误的人设M(x):x是人|P(x):x犯错误方法一

（不存在不犯错的人）¬(∃x)(M(x)∧¬P(x))方法二

（所有人都犯错误）(∀x)(M(x)→P(x))例题2.6：符号化（二）(3)这只大红书柜摆满了那些古书。简单刻画：R(a)∧Q(b)∧F(a,b)说明：a代表“大红书柜”，b代表“古书”，F(x,y)表示x摆满y。深度刻画：A(a)∧B(a)∧C(a)∧D(b)∧E(b)∧F(a,b)说明：将“大、红、书柜”与“古、书”的属性逐一拆解符号化。💡关键：对个体的描述粒度与深度不同，翻译结果也不同。(4)任何整数，不是正的就是负的。谓词定义：•I(x)：x是整数；R(x)：x是正数；N(x)：x是负数注：在特定论域下，通常默认排除0或在语境中包含。最终符号化：(∀x)(I(x)→(N(x)∨R(x)))全称量词+蕴含+析取结构例题2.7：LewisCarroll的逻辑谜题（一）自然语言前提陈述：1.所有狮子都是凶猛的；2.有些狮子不喝咖啡；3.有些凶猛的动物不喝咖啡。基本定义与个体域个体域：所有动物的集合(Allanimals)谓词定义：P(x):x是狮子|Q(x):x是凶猛的|R(x):x喝咖啡谓词逻辑符号化表达1.(∀x)(P(x)→Q(x))2.(∃x)(P(x)∧¬R(x))3.(∃x)(Q(x)∧¬R(x))💡逻辑表达技巧：在谓词逻辑符号化中，全称量词(∀)通常与蕴含联结词(→)搭配使用，以描述某一类事物的共性；而存在量词(∃)通常与合取联结词(∧)搭配使用，以描述存在满足多个条件的个体。例题2.7：LewisCarroll的逻辑谜题（二）(2)所有的蜂鸟都五彩斑斓；没有大鸟以蜜为生；不以蜜为生的鸟都色彩单调；蜂鸟都是小鸟。谓词定义P(x):x是蜂鸟|Q(x):x是大鸟

R(x):x是以蜜为生的鸟|S(x):x五彩斑斓个体域(DomainofDiscourse)所有鸟的集合(Thesetofallbirds)符号化：(∀x)(P(x)→S(x))(所有蜂鸟皆五彩斑斓)

2.¬(∃x)(Q(x)∧R(x))(无大鸟以蜜为生)3.(∀x)(¬R(x)→¬S(x))(非蜜食者皆色彩单调)

4.(∀x)(P(x)→¬Q(x))(蜂鸟都是小鸟)2.3.2谓词公式的翻译与解释核心概念：解释（赋值）一个孤立的谓词公式（如(∀x)P(x)）本身没有确切的含义。为了使其具有意义，我们需要对公式中的符号进行解释或赋值，明确其中个体变元、谓词及函数符号的具体所指。个体域的重要性每个由量词确定的表达式，其逻辑真值都与个体域（论域）密切相关。在讨论带有全称量词或存在量词的命题函数时，必须首先明确其个体域，否则无法判断其真假性。例题2.8：对同一公式的不同解释(P(x,y)∧P(y,z))→P(x,z)解释为“小于”关系若x<y且y<z，则x<z。这是一个永真式(有效公式)。解释为“父子”关系若x是y的儿子且y是z的儿子，则x是z的儿子。这是一个永假公式(矛盾公式)。解释为“距离”关系若x距离y10米且y距离z10米，则x距离z10米。这是一个可满足公式。结论：同一个谓词公式在不同的解释下，可以是有效公式、矛盾公式或可满足公式。例题2.9：在给定解释下求公式的真值解释I(Interpretation)▌个体域(Domain)D={a,b}▌函数(Function)f(a)=b,f(b)=a▌谓词(Predicate)P(a)=1,P(b)=0

Q(a,a)=0,Q(a,b)=1,Q(b,a)=1,Q(b,b)=1待求公式(∃x)(P(f(x))∧Q(x,f(a)))这是一个含有存在量词(∃)的一阶谓词公式。我们需要将个体域中的元素代入，验证是否存在至少一个元素使公式成立。分步求解Step1:代入已知常量

∵f(a)=b，代入公式得：

(∃x)(P(f(x))∧Q(x,b))Step2:代入x=a验证

P(f(a))∧Q(a,b)=P(b)∧Q(a,b)=0∧1=0(假)Step3:代入x=b验证

P(f(b))∧Q(b,b)=P(a)∧Q(b,b)=1∧1=1(真)✅最终结论

存在x=b使公式为真，故公式真值为真(T)。例题2.10：求复杂公式的真值（一）解释I(Interpretation)▪个体域(Domain):D={2,3}▪特定元素(SpecificElement):a=2▪函数(Function):f(2)=3,f(3)=2▪谓词(Predicate):F(2)=False,F(3)=TrueG(i,j)=True(对所有i,j∈D)L(x,y)=T当且仅当x=y(即L(2,2)=T,L(3,3)=T)求解(1)(∀x)(F(x)∧G(x,a))1.代入特定元素a=2：

(∀x)(F(x)∧G(x,2))2.全称量词展开(个体域D={2,3})：

⇔(F(2)∧G(2,2))∧(F(3)∧G(3,2))3.代入谓词真值并计算：

⇔(False∧True)∧(True∧True)⇔False∧True⇔False结论：该公式的真值为False(F)例题2.10：求复杂公式的真值（二）(2)求公式(∃x)(F(f(x))∧G(x,f(x)))的真值(∃x)(F(f(x))∧G(x,f(x)))⇔(F(f(2))∧G(2,f(2)))∨(F(f(3))∧G(3,f(3)))⇔(F(3)∧G(2,3))∨(F(2)∧G(3,2))⇔(T∧T)∨(F∧T)⇔T∨F最终结果：公式的真值为T(真)例题2.10：求复杂公式的真值（三）(3)求公式(∀x)(∃y)L(x,y)的真值(∀x)(∃y)L(x,y)⇔((∃y)L(2,y))∧((∃y)L(3,y))⇔(L(2,2)∨L(2,3))∧(L(3,2)∨L(3,3))⇔(T∨F)∧(F∨T)⇔T∧T⇔T结论：该嵌套量词公式的真值为真(T)2.3.3谓词公式的分类有效公式(永真公式)无论对公式中的个体变元赋予什么个体域，无论对公式中的谓词和函数符号作何种具体的解释，公式的真值始终为真。矛盾公式(不可满足)无论对公式中的个体变元赋予什么个体域，无论对公式中的谓词和函数符号作何种具体的解释，公式的真值始终为假。可满足公式至少存在一个解释，使得该公式在这个解释下的真值为真。有效公式是可满足公式的一种特殊形式。💡判断方法提示由于个体域可以是无限的，且解释具有多样性，我们无法使用真值表来判断谓词公式的类型。通常，我们使用等值演算法或寻找具体的解释来分析公式的逻辑性质。例题2.11：判断公式类型（一）(1)(∀x)P(x)∨¬(∀x)P(x)💡分析：令G=(∀x)P(x)，此时原公式的结构就转换为了我们熟悉的命题逻辑范式：G∨¬G。✅结论：“G∨¬G”是经典的逻辑永真式（排中律），无论对谓词和论域做何种解释，其真值恒为真。因此，该公式是有效公式。(2)(∀x)P(x)∧¬(∀x)P(x)💡分析：同样令G=(∀x)P(x)，原公式转化为逻辑范式：G∧¬G。❌结论：“G∧¬G”是经典的逻辑永假式（矛盾律），无论对谓词和论域做何种解释，其真值恒为假。因此，该公式是矛盾公式。例题2.11：判断公式类型（二）(3)F∧(∃x)P(x)▍分析根据逻辑合取（AND）的定义，假值（False）与任何逻辑值进行合取运算，最终结果恒为假。无论公式中的谓词P(x)或个体域的取值如何，都无法改变这一结果。结论：该公式是矛盾公式(Contradiction)(4)(∃x)P(x)→(∀x)Q(x)↔¬(∃x)P(x)∨(∀x)Q(x)▍分析运用蕴含等值式规则：逻辑蕴含式G→H在逻辑上等价于¬G∨H。若令G=(∃x)P(x)，H=(∀x)Q(x)，则原式可化简为逻辑式A↔A的形式，而A↔A在逻辑上恒成立。结论：该公式是有效公式(ValidFormula)例题2.11：判断公式类型（三）(5)(∀x)(P(x)→Q(x))💡分析：公式的真值无法预先确定，而是取决于对谓词P、Q的具体解释，以及个体域的选取。🏁结论：该公式是可满足公式(6)P∨((∀x)R(x)∧(∃x)S(x))💡分析：公式中包含命题变元P。我们可以找到一种解释：只需将P赋值为“真”，无论后面的部分取值如何，整个公式的真值都为真。🏁结论：该公式是可满足公式本节