18.2 一阶逻辑公式及其解释
本章目录 · 1 节
本章导读
【18.2 一阶语言】先给定带元数的符号表L:常项a、b、c,函数符号f、g、h及各自元数,谓词符号F、G、H及各自元数。再加个体变项、联结词¬、∧、∨、→、↔、量词∀、∃与括号。相同符号在一个语言中不能时而一元时而二元;不同示例可以重新声明不同的符号表。
【定义18.2.1—18.2.4 项与公式】(1)每个常项、变项都是项;若f为n元函数符号且t₁,…,tₙ为项,则f(t₁,…,tₙ)为项;只有有限次按这些规则得到的表达才是项。(2)若F为n元谓词符号,则F(t₁,…,tₙ)为原子公式;带逻辑等号的语言还允许t₁=t₂。(3)若A、B是公式,¬A及(A∧B)、(A∨B)、(A→B)、(A↔B)也是公式;∀xA、∃xA也是公式。公式只由这些规则有限生成。
项指对象,公式表达可判真假的条件:f(x,y)不是公式,F(x,y)不是项。不带等号且没有任何谓词符号的上述语言无法生成原子公式,不能笼统说它就成为命题逻辑;仅保留零元谓词、联结词时才得到相应的命题语言。等号若是逻辑符号,始终解释为对象相同,不任意解释为其他关系。
【定义18.2.5 自由与约束出现】在∀xA、∃xA中,x为指导变元,A为辖域。一个作为项出现的x,若处在相应量词辖域内,受离它最近的同名量词约束;否则自由。同一字母可在一处自由、另一处受约束。量词后用于声明绑定的字母不计作项中的一次出现。内层同名量词会遮蔽外层量词;宜换名避免混淆。
【例18.2.1】(1)∀x(F(x,y)→G(x,z)):辖域为F(x,y)→G(x,z),x约束出现两次,y、z各自由出现一次。原书解答误把G(x,z)写成G(x,y),此处按题式保留z。
(2)(∀x(F(x)→G(y)))→∃y(H(x)∧L(x,y,z)):左侧∀x只管F(x)→G(y),右侧∃y只管H(x)∧L(x,y,z)。x左边约束一次、右边自由两次;y左边自由一次、右边约束一次;z右边自由一次。全式的自由变量集合为{x,y,z}。(例完)
【定义18.2.6 闭式与闭包】没有自由变量的公式叫闭式或句子。对(1)作全称闭包可写∀y∀z∀x(F(x,y)→G(x,z));作混合闭包可写∃z∀y∀x(F(x,y)→G(x,z)),一般含义不同。不能为“闭合”而把G从二元改为三元。保持原式并逐个约束r个不同自由变量时需要r个量词;若允许先代入常项或逻辑化简,则不应把“至少r个量词”误当成对一切改写都成立的断言。
自由变量代入必须防止捕获。如把∀yR(x,y)中的自由x换成y,不能直接得到∀yR(y,y),应先将约束y换新名z,再得到∀zR(y,z)。只有约束变量的一致安全换名保留原意,随意交换量词不保留原意。
【定义18.2.7 解释与赋值】解释I包括非空域D、每个常项a的值aᴵ∈D、每个n元函数f的全函数fᴵ:Dⁿ→D、每个n元谓词F的关系Fᴵ⊆Dⁿ。赋值σ给变项指定D中元素。项按函数递归求值;原子公式按关系判真;联结词按命题逻辑求值。
量词的语义是:I,σ⊨∀xA当且仅当对每个d∈D都有I,σ[x↦d]⊨A;I,σ⊨∃xA当且仅当至少一个d使后式成立。修改绑定x的值不修改同式外部自由变量的值。闭式的真假与σ无关,但仍依赖I;非闭式一般还依赖其自由变量的赋值。函数必须封闭且处处有定义,例如通常减法不是N上的二元全函数。
【例18.2.2】(1)∃xF(f(x),a):在R上解释a=0、f(x)=2x+1、F(u,v):u=v,意为存在实数x使2x+1=0,见证−1/2,真;域改N,同样定义的函数封闭,但方程无解,假。(2)∀xG(x,y):在N上令G(u,v):u≥v;自由y=0时真,y=1时由x=0反驳。没有给y赋值不能断言一个固定真值。(例完)
【例18.2.3】取D=N={0,1,2,…},a=0,f(u,v)=u+v,g(u,v)=uv,F(u,v):u=v;σ(x)=1、σ(y)=2、σ(z)=3。以下量词只覆盖紧随的公式,另外加括号明确范围。
(1)F(f(x,y),g(x,y)),即3=2,假。
(2)F(f(x,a),y)→F(g(x,y),z),即(1=2)→(2=3),真。
(3)¬F(g(x,y),g(y,z)),即2≠6,真。
(4)∀xF(g(x,y),z),即∀x(2x=3),假,x=0即反例。
(5)(∀xF(g(x,a),x))→F(x,y),即(∀x(0=x))→(1=2),前件假,整式真;右边自由x仍取1。
(6)∀xF(g(x,a),x),即∀x(0=x),假,x=1反驳。
(7)∀x∀y(F(f(x,a),y)→F(f(y,a),x)),即∀x∀y(x=y→y=x),真,利用等号对称性。
(8)∀x∀y∃zF(f(x,y),z),即∀x∀y∃z(x+y=z),真,取z=x+y∈N。
(9)∃xF(f(x,x),g(x,x)),即∃x(2x=x²),真,见证0或2。
已指定完整解释及自由变量赋值后,经典一阶公式均有确定真值;“尚不能确定”只适用于这些信息尚未给全的情况。(例完)
【定义18.2.8 公式类型】A在每个非空域的每个解释、每个赋值下都真,称永真式或逻辑有效式,记⊨A;处处假称矛盾式;至少存在一个解释和赋值使其真,称可满足式。既有成真又有成假解释的为非永真的可满足式。一个真模型只能证明可满足,一个反例只能否定永真;检查有限个域不等于判定任意一阶公式。一般一阶有效性、可满足性没有对所有输入都终止的判定算法。
【定义18.2.9、定理18.2.1 代换实例】把命题公式的各命题变元一致换成一阶公式,所得为代换实例。重言式的实例永真,矛盾式的实例处处假,因为在任何给定I、σ下这些子公式仍各取0或1。同一命题变元的每次出现必须换成同一公式;此定理并不是允许任意捕获自由变量。
【例18.2.4】(1)A=∀x(F(x)→G(x,y))。它仍含自由y,原书解答称闭式并把G写成一元,符号不一致。保留题式二元G:取D={0},F={0}、G={(0,0)}、y=0,则真;同域F={0}、G=∅则假。所以A可满足但不永真。
(2)B=∃x(F(x)∧G(x,y))。在R上F为自然数性质、G为相等关系,y=1真、y=−1假,故同样可满足但不永真。
(3)C=(∀xF(x))→((∃x∃yG(x,y))→∀xF(x)),是p→(q→p)的实例,永真。
(4)D=¬((∀xF(x))→∃yG(y))∧∃yG(y),是¬(p→q)∧q的实例,矛盾。第(1)(2)中的G二元,第(4)中的G一元,各式单独声明语言,不在一个共同符号表混用。(例完)
【例18.2.5 五个基本有效式】在非空域中:(1)(∀xF(x))→∃xF(x);(2)(∀xF(x))→F(y);(3)(∀xF(x))→F(c);(4)F(y)→∃xF(x);(5)F(c)→∃xF(x)。证明:全称真时对σ(y)或cᴵ也真;特例真时以该对象为存在见证。第(1)另需非空域选对象,空域会使前真后假。常项c必须在域中有解释。反向F(y)→∀xF(x)一般无效,不能从一个对象推广到所有对象。(例完)
