大学离散数学《谓词逻辑》课程讲义课件

离散数学系列离散数学谓词逻辑个体·谓词·量词·符号化·等价式·推理DATE2026年课程导览01从命题到谓词命题逻辑的局限与谓词逻辑的引入02个体词、谓词与量词基本符号体系的建立03谓词公式与符号化命题符号化的方法与技巧04谓词等价式与范式公式变换与规范形式05谓词推理理论形式化推理与证明能力06易错辨析与综合应用常见误区梳理与综合运用SECTION01从命题到谓词命题逻辑无法刻画内部结构从整体命题走向个体与谓词的分析命题逻辑的困境所在命题逻辑把命题当作不可分割的整体，只研究命题之间的真值联结关系p、q、r

是三个独立命题，彼此无结构关联结论

r

无法由

p

和

q

的有效形式推出，推理链条在符号层面断裂1所有人都会死符号化为p作为整体处理，内部结构不可见2苏格拉底是人符号化为q作为整体处理，内部结构不可见3苏格拉底会死符号化为r作为整体处理，内部结构不可见命题逻辑「看不见」命题内部的个体与性质剖析命题的内部结构谓词逻辑将命题拆解为个体词、谓词、量词三部分，使三段论的有效性得以形式化证明。示例命题拆解苏格拉底是人个体（苏格拉底）+谓词（是人）所有人都会死个体+谓词+量词（所有）层逻辑研究的两个层次命题命题逻辑：以命题为最小单位，研究命题间的联结谓词谓词逻辑：以个体、谓词为最小单位，研究命题内部结构谓词逻辑的地位与意义学习路径预告01概念构建：建立个体词、谓词、量词的基本概念02符号化与等价变换：掌握谓词公式的符号化方法与等价变换03推理理论：构建谓词推理理论，形成完整证明能力谓词逻辑是命题逻辑的扩展与深化，表达能力强于命题逻辑谓词逻辑的价值结构刻画命题内部结构，可分析全称、存在等量化表述基础是数学证明、程序验证、人工智能知识表示的重要基础关键从「整体判断」走向「精细分析」的关键一步SECTION02个体词、谓词与量词符号是逻辑的语言个体、谓词与量词构成基本表达单元个体词：论域与个体“个体变项取何值依赖于论域的约定；论域不同，同一公式的含义可能完全不同。”个体词与论域：从核心概念到个体词的分类核心概念个体词：表示所研究对象中独立存在的客体。论域（个体域）：个体变项的取值范围，即讨论对象的全体。全总个体域：宇宙间一切事物组成的集合。个体词的分类个体常项具体的、确定的个体，如

a、b、c。个体变项抽象的、不确定的个体，如

x、y、z。谓词：刻画个体的性质与关系谓词的元数=该谓词所跟个体词的个数n元谓词填式需n个个体词才能成为命题谓词：表示个体性质或个体之间关系的词一元谓词与多元谓词一元谓词刻画单个个体的性质，如

F(x)

表示「x是学生」多元谓词刻画多个个体间的关系，如

L(x,y)

表示「x小于y」两种书写形式谓词填式将个体词代入谓词变项，如

F(a)谓词命名式为谓词指定确定的含义，如

F(x)：x是学生量词：全称与存在量词后的变项x是指导变项，其作用范围称为量词的辖域量词是区分谓词逻辑与命题逻辑的核心标志量词是表示个体数量的词，是谓词逻辑的独有特征全称量词∀3项含义表示“所有”“任意”“一切”符号化∀x读法∀xF(x)读作——对任意个体x，都有性质F存在量词∃3项含义表示“存在”“有的”“至少有一个”符号化∃x读法∃xF(x)读作——存在个体x，具有性质F论域限定与真值判定明确论域思路一第一步先声明个体域第二步再直接量化全总个体域思路二核心用特性谓词限定个体范围全称例“所有人都会死”→∀x(人(x)→会死(x))存在例“有的人爱数学”→∃x(人(x)∧爱数学(x))特性谓词与量词的搭配方式（∀配→，∃配∧）是易错点量化命题的真值依赖于论域的选取VSSECTION03谓词公式与符号化把自然语言翻译成逻辑语言掌握符号化的方法与常见技巧谓词公式的构成原子公式由谓词填式构成，合式公式按规则递归生成原子公式示例：F(x)、L(x,y)合式公式的定义原子公式是合式公式若

A

是合式公式，则

¬A

是合式公式若

A、B

是合式公式，则

(A∧B)、(A∨B)、(A→B)、(AB)

都是合式公式若

A

是合式公式，x

是个体变项，则

∀xA、∃xA

是合式公式只有有限次应用上述规则所得的公式才是合式公式增加量词规则是谓词公式区别于命题公式的关键12345量词的辖域与变项含自由变项的公式不表示命题，其真值依赖于自由变项的取值区分约束变项与自由变项，关键在于辖域量词的辖域量词后紧跟的公式部分，即量词的作用范围约束变项在量词辖域内且与该量词指导变项同名的变项自由变项不受任何量词约束的个体变项判断依据：看变项是否落在同名量词的辖域之内换名规则：约束变项可以改名，但须改辖域内所有同名变项代入规则：自由变项可以代入，但须对该变项每一处都代入命题符号化的方法符号化的核心：找准个体词、谓词、量词三要素自然语言句式符号化结果所有S都是P∀x(S(x)→P(x))所有S都不是P∀x(S(x)→¬P(x))有些S是P∃x(S(x)∧P(x))有些S不是P∃x(S(x)∧¬P(x))01论域确定论域，或引入特性谓词限定范围02个体词找出个体词，记为个体常项或变项03谓词提炼谓词，明确其元数与含义04量词判断量词类型，选择

∀或∃符号化实例精讲多元谓词与嵌套量词的符号化，关键在于准确设定谓词含义与量词顺序。例1：多元谓词“张三喜欢李四”→L(a,b)，L(x,y)：x喜欢y“每个人都有一个爱好”→∀x∃yH(x,y)例2：嵌套量词“所有的学生都敬重某些老师”设

S(x)：x是学生，T(y)：y是老师，R(x,y)：x敬重y符号化为

∀x(S(x)→∃y(T(y)∧R(x,y)))例3：量词顺序的影响∀x∃yL(x,y)与∃y∀xL(x,y)含义不同前者：每人各有喜欢的人后者：存在一个人被所有人喜欢SECTION04谓词等价式与范式等价变换是推理的基石掌握等价式与前束范式等规范形式谓词等价式AB恒为真时，称A与B等价，记作

A⇔B量词否定等价式2项¬∀xA(x)⇔∃x¬A(x)¬∃xA(x)⇔∀x¬A(x)量词辖域扩展等价式4项∀x(A(x)∧B)⇔∀xA(x)∧B∃x(A(x)∨B)⇔∃xA(x)∨B∀x(A(x)∨B)⇔∀xA(x)∨B∃x(A(x)∧B)⇔∃xA(x)∧B前提：B为不含变项x的公式量词分配与换名成立式∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)不成立∀对∨

不满足分配律∃对∧

不满足分配律量词换名与顺序01换名换名规则：∀xA(x)⇔∀yA(y)，∃xA(x)⇔∃yA(y)（y为新变项）02易位量词易位：∃y∀xA(x,y)⇒∀x∃yA(x,y)，反之不成立03作用换名是为消除同名变项冲突，是变换前束范式的必备操作前束范式第1步消去消去→与用等价式替换。第2步内移内移否定词用量词否定等价式将

¬

移到原子公式前。第3步换名换名避免同名变项冲突。第4步前移前移量词用量词辖域扩展等价式将所有量词移到最前端。前束范式：所有量词都移到公式最前面，且辖域延伸到整个公式末尾；标准形式：Q₁x₁Q₂x₂…QₙxₙM，其中M为不含量词的母式。任何谓词公式都存在与之等价的前束范式；前束范式通常不唯一，但母式可化为合取范式的称前束合取范式。范式变换实例例题求公式

∃xF(x)→∀yG(y)

的前束范式结果∀x∀z(¬F(x)∨G(z))前束范式为

∀x∀z(¬F(x)∨G(z))第1步消去→消去→¬∃xF(x)∨∀yG(y)第2步否定内移否定内移∀x¬F(x)∨∀yG(y)第3步换名换名∀x¬F(x)∨∀zG(z)第4步量词前移量词前移∀x∀z(¬F(x)∨G(z))关键在于先消去联结词，再内移否定，最后前移量词母式¬F(x)∨G(z)已是合取范式形式SECTION05谓词推理理论从已知推出未知掌握推理规则与形式化证明方法谓词推理的基本规则四条规则的使用限制是推理正确性的关键，尤其US与ES的顺序谓词推理在命题推理规则基础上，增加量词消去与引入规则全全称量词规则US全称例示：∀xA(x)⇒A(c)，c为任意个体常项UG全称推广：A(c)⇒∀xA(x)，c须为任意选取的个体存存在量词规则ES存在例示：∃xA(x)⇒A(c)，c须为新引入的特定个体EG存在推广：A(c)⇒∃xA(x)，c为特定个体即可推理规则的使用限制关键限制US

的个体常项必须任意：不能对含自由变项的公式随意全称推广ES

的个体常项必须全新：不能与已有常项重名，且须在

UG

之前使用UG

之前不能有以该个体为自由变项的假设ES与US顺序：通常先做

ES

再做

US，避免个体依赖冲突使用次序建议消去量词：先

ES

后

US引入量词：先

EG

后

UG警示违反限制会导致推出错误结论，务须谨慎推理证明实例精讲证明过程1∀x(M(x)→D(x))前提引入2M(s)前提引入3M(s)→D(s)(1)US4D(s)(2)(3)假言推理苏格拉底三段论得到形式化证明，D(s)

成立延伸练习证明∀x(P(x)→Q(x))，∃xP(x)⇒∃xQ(x)提示：先用

ES

引入新个体，再用

US

与假言推理，最后

EG

推广SECTION06易错辨析与综合应用避开陷阱，融会贯通梳理易错点，提升综合解题能力常见易错点辨析量词与联结词搭配错误∀x(S(x)∧P(x))表示「所有S都是P」应为

∀x(S(x)→P(x))，全称量词配

蕴含错误∃x(S(x)→P(x))应为

∃x(S(x)∧P(x))，存在量词配

合取错误∀x∃y与∃y∀x不等价，顺序改变含义随之改变需明确

量词顺序

对应关系规则使用ES

引入的常项不可重复使用，且须在

UG

之前约束变项换名须改辖域内

全部

同名变项综合应用与能力提升“谓词逻辑是通向数理逻辑与