下载文档原格式
谓词基本推理公式
谓词逻辑是逻辑学中的一种形式系统，它使用谓词来表达命题的性质和关系。
基本推理公式是谓词逻辑中的一些基本规则，用于推导命题的真假。
以下是几个常用的谓词逻辑基本推理公式：
1. 交换律：A→B ↔ B→A
2. 结合律：(A→B)→C ↔ A→(B→C)
3. 吸收律：A→(B∧C) ↔ (A→B)∧(A→C)
4. 分配律：(A∧B)→C ↔ A→(B→C)
5. 重写律：A→B ↔ ¬B→¬A
6. 否定引入律：¬(A∧B) ↔ (¬A∧¬B)
7. 否定消去律：¬¬A ↔ A
8. 双条件引入律：A↔B ↔ (A→B)∧(B→A)
9. 双条件消去律：A↔B ↔ (A∧B)∨(¬A∧¬B)
10. 全称量词引入律：∀x(P(x)) ↔ P(y)/y (y属于某个集合)
11. 存在量词引入律：∃x(P(x)) ↔ P(y)/y (y属于某个集合)
这些基本推理公式是谓词逻辑的基础，可以用于推导其他命题的真假。
在具体使用时，需要根据命题的具体情况进行选择和应用。
谓词逻辑基本推理公式
谓词逻辑的基本推理公式包括：
1. 全称量词规则：如果个体域中每一个个体具有性质A，则存在一个个体具有性质A。
即，能找出一个就表示存在。
公式为A ( c ) ⇒∃ x A
( x )A(c)\Rightarrow\exists xA(x)A(c)⇒∃xA(x)。
规则成立的条件是c是个体域中某个确定的个体，代替c的x不在A©中出现过。
2. 存在量词规则：如果个体域中存在个体具有性质A，则至少存在一个个体具有性质A。
公式为∃ x A ( x ) ∀ y A ( y )\exists xA(x)\forall yA(y)∃x A(x)∀yA(y)。
3. 归结推理：将公式中的量词的指导变元及其辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变。
4. 代入规则：把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的这个符号。
5. 解释（赋值）：谓词公式A的个体域D是非空集合，则每一个常项指定D中一个元素；每一个n元函数指定Dn到D的一个函数；每一个n元谓词指定Dn到{0,1}的一个谓词。
按这个规则做的一组指派，称为A的一个解释或赋值。
以上是谓词逻辑的基本推理公式，通过这些公式可以推导出更复杂的逻辑推理结果。
数理逻辑中的谓词函数与谓词公式数理逻辑（mathematical logic）是研究形式逻辑（formal logic）的一个分支，它运用数学方法来研究逻辑的基本原理与推理规则。
在数理逻辑中，谓词函数和谓词公式是非常重要的概念。
本文将介绍谓词函数与谓词公式的概念、性质及其在数理逻辑中的应用。
一、谓词函数的定义与性质在数理逻辑中，谓词函数（Predicate Function）是一种将一组变量映射到真值的函数。
它通过变量的赋值将谓词的真值确定下来。
谓词函数的定义可以用集合和映射来描述。
1.1 谓词函数的定义设P是一个谓词，n是一个正整数，X1, X2, ..., Xn是n个变量，则称(P, n)为一个n元谓词，也称为谓词函数。
通常用P(x1, x2, ..., xn)来表示一个具体的n元谓词函数。
1.2 谓词函数的性质（1）真值集合：对于给定的变量赋值，谓词函数的结果是一个命题（proposition），即取值要么为真，要么为假。
谓词函数的真值集合可以用集合来表示。
（2）变元：谓词函数中的变量称为变元（arguments）。
变元的个数决定了谓词函数的元数（arity）。
（3）布尔函数：谓词函数可以看作是一种特殊的布尔函数，即输入是布尔值，输出也是布尔值的函数。
（4）值域：谓词函数的取值范围称为值域（range）。
值域通常是真值集合{真, 假}。
二、谓词公式的定义与性质谓词公式（Predicate Formula）是由谓词函数和逻辑连接词（如否定、合取、析取、蕴含、等价等）通过逻辑运算得到的复合命题。
谓词公式可以描述系统中的关系、属性和规则等。
2.1 谓词公式的定义谓词公式由谓词及其变元，逻辑连接词和量词（如全称量词∀、存在量词∃等）组成。
谓词公式可以使用自由变量或约束变量形式来表示。
2.2 谓词公式的性质（1）合法公式：符合数理逻辑规则的谓词公式称为合法公式，也称为良构公式。
（2）可满足性：对于合法公式，如果存在一种变量赋值使该谓词公式成为真命题，则称该谓词公式是可满足的。
离散数学常考题型梳理第7章谓词逻辑一、题型分析本章主要介绍谓词逻辑的基本概念、基本定理与方法等．经常涉及到的题型有：7-1谓词公式的翻译7-2求辖域、约束变元、自由变元、变元换名7-3在有限个体域下消去量词7-4谓词推理演算因此，在本章学习过程中希望大家要清楚地知道：1．谓词用以描述个体的性质或个体间关系的语法模式称为谓词．谓词命名式是谓词与个体和个体变元结合的表示形式．谓词命名式也简称为谓词．谓词一般用大写字母P、Q、R等表示，个体一般用小写字母a、b、c等表示，个体变元就一般用小写字母x、y、z等表示．谓词可以写成P(x，y)、H(x，y，z)、F(x)等形式．2．量词将表明个体取值量上的词“任意”、“所有的”、“全部”、“凡是”、“一切”等称为全称量词．全称量词用∀表示．将表明个体取值量上的词“存在”、“有的”、“有些”、“至少有”等称为存在量词．存在量词用∃表示．在书写谓词时，通常将个体变元的个体域定义为全总个体域，然后根据需要对各个不同的个体应用描述个体特性的谓词（称为特性谓词）来加以约束限制．在谓词形式中，特性谓词的加入有两条规则：(1) 对全称量词，特性谓词作为蕴含式（条件式）的前件加入．(2) 对存在量词，特性谓词作为合取项加入．即在命题符号化时要注意：使用全称量词∀，特性谓词后用→；使用存在量词∃，特性谓词后用∧．设G(x)是一元谓词，个体域为D．则命题∀xG(x)的真值：∀xG(x)取1值当且仅当对任意x∈D，G(x)都取1值．∀xG(x)取0值当且仅当有一个x0∈D，使得G(x0)取0值．命题∃xG(x)的真值：∃xG(x)取1值当且仅当有一个x0∈D，使得G(x0)取1值．∃xG(x)取0值当且仅当对任意x∈D，G(x)都取0值．3．谓词公式谓词公式可由下述各条规则组成：(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)至(4)构成的公式为合式公式．由上定义知，命题演算公式也是谓词合式公式．4．变元的约束对于(∃x)P(x) 或(∀x)P(x) 形式的公式，∃或∀后面所跟的个体变元x称为相应量词的指导变元．紧接于量词之后最小的子公式称为量词的辖域．在量词的辖域内指导变元的一切出现均称为变元的约束出现．约束出现的变元称为约束变元．在公式中，变元的非约束出现称为变元的自由出现．自由出现的变元称为自由变元．约束变元的换名规则：对约束变元进行换名，即将量词辖域中出现的某个约束变元和相应的指导变元，换成另一个辖域中未曾出现过的变元符号，公式中的其余部分不变．自由变元的代入规则：对自由变元进行代入，即对自由变元用与原公式中所有变元不同的符号去代替，并且处处代替．5．在有限个体域下消去量词当个体域为有限集合{a1，a2，…，a n}时，消去量词的规则为：(∀x)P(x)⇔P(a1)∧P(a2)∧…∧P(a n)(∃x)P(x)⇔P(a1)∨P(a2)∨…∨P(a n)6．推理理论谓词演算的推理是命题演算推理的推广和扩充，命题演算中的基本等价式，重言蕴含式以及P规则、T规则、CP规则在谓词演算中仍然适用．谓词逻辑中几个常用的等价式：⌝(∀x)P(x)⇔(∃x)⌝P(x)⌝(∃x)P(x)⇔(∀x)⌝P(x)(∀x)(A(x)∨B)⇔(∀x)A(x)∨B(∀x)(A(x)∧B)⇔(∀x)A(x)∧B(∃x)(A(x)∨B)⇔(∃x)A(x)∨B(∃x)(A(x)∧B)⇔(∃x)A(x)∧B（注：子公式B中不出现约束变元x）(∀x)(A(x)∧B(x))⇔(∀x)A(x)∧(∀x)B(x)(∃x)(A(x)∨B(x))⇔(∃x)A(x)∨(∃x)B(x)谓词逻辑的推理演算新增加了添加与消去量词的四条规则：(1) 全称指定规则（全称量词消去规则），表示为US，即：(∀x)P(x)P(c)此规则是对量词约束的变元任意指定一个个体，其逻辑含义是，如果(∀x)P(x)成立，则可以任取个体域中某个任意的个体c，而P(c)也是成立的．(2) 全称推广规则（全称量词附加规则），表示为UG，即：P(c)(∀x)P(x)此规则是对使得谓词P成立的个体c进行推广，其逻辑含义是，如果对于个体域中任意的个体c，有P(c)成立，则(∀x)P(x)也成立．(3) 存在指定规则（存在量词消去规则），表示为ES，即：(∃x)P(x)P(c)此规则是对量词约束的变元指定一个个体，其逻辑含义是，如果(∃x)P(x)成立，则个体域中有某个个体c使得P(c)成立．(4) 存在推广规则（存在量词附加规则），表示为EG，即：P(c)(∃x)P(x)此规则是对使得谓词P成立的个体c进行推广，其逻辑含义是，如果对于个体域中存在某个个体c，使P(c)成立，则(∃x)P(x)也成立．二、常考知识点分析常考知识点1：命题公式的翻译（历年考核次数：5次，本课程共考过6次；重要程度：★★★★★）（2008年7月试卷第13题）将语句“有人去上课．”翻译成谓词公式．[解题过程]设P(x)：x是人，Q(x)：x去上课．则语句“有人去上课．”翻译成谓词公式为x P x Q x∃∧．()(()())易错点：有同学会误表示为(∃x)(P(x)→Q(x))．提示：用存在量词“∃”来表明个体的取值量，对各个不同的个体应用描述个体特性的特性谓词P(x)来加以约束限制时，特性谓词作为合取项加入．（2009年1月试卷第13题）将语句“所有的人都学习努力．”翻译成谓词公式．[解题过程]设P(x)：x是人，Q(x)：x学习努力．则语句“所有的人都学习努力．”翻译成谓词公式为(∀x)(P(x)→Q(x))．易错点：有同学会误表示为(∀x)(P(x)∧Q(x))．提示：用全你量词“∀”来表明个体的取值量，对各个不同的个体应用描述个体特性的特性谓词P(x)来加以约束限制时，特性谓词作为条件式的前件加入．常考知识点2：量词辖域、约束变元、自由变元（历年考核次数：3次，本课程共考过6次；重要程度：★★★）（2008年9月试卷第16题）设谓词公式)yxzQyzxPx↔→∃，试∀∧∀yRy,,))(),()Fz(y(,(（1）写出量词的辖域；（2）指出该公式的自由变元和约束变元．[解题过程] （1）量词∃的辖域为)),,(),((z x y zQ y x P ∀→，第1个量词∀的辖域为),,(z x y Q ，第2个量词∀的辖域为),(z y R ．（2）)),,(),((z x y zQ y x P ∀→与)(y F 中的y ，以及),(z y R 中的z 为自由变元． )),,(),((z x y zQ y x P ∀→中的x ，),,(z x y Q 中的z ，以及),(z y R 中的y 为约束变元．易错点：求辖域容易出错，要注意式中括号的配对．提示：紧跟量词后面的个体变元为该量词的指导变元，在该量词的辖域中与指导变元相同的变元为约束变元，与指导变元不同的或不在任何量词的辖域中的变元为自由变元。
第二章谓词逻辑在命题逻辑中，我们把原子命题看作命题演算和推理的基本单位，是不可再分的整体。
因而命题逻辑无法研究命题的内部结构及命题之间的内在联系，甚至无法有效地研究一些简单的推理。
例如，著名的“苏格拉底三段论”：凡是人都是要死的；苏格拉底是人；所以苏格拉底是要死的。
我们知道，这个推理是正确的，但用命题逻辑无法说明这一点。
设p:凡人都是要死的；q：苏格拉底是人；r：苏格拉底是要死的。
则“苏格拉底三段论”可符号化为（p∧q）→r。
显然（p∧q）→r不是重言式。
因此，为了能够进一步深入地研究推理，需要对原子命题做进一步的分析。
2.1 谓词逻辑的基本概念2.1.1 个体与谓词我们可以将原子命题的结构分解为个体和谓词。
定义2.1-1 个体(Individual)：个体是我们思维的对象，它是具有独立意义、可以独立存在的客体。
谓词(Predicate)：谓词是表示一个个体的性质或若干个个体之间的关系的词。
个体和谓词一起构成了原子命题中的主谓结构。
例2.1-1⑪海水是咸的。
⑫张强与张亮是兄弟。
⑬无锡位于上海与南京之间。
⑪、⑫、⑬都是原子命题，其中海水、张强、张亮、无锡、上海和南京都是个体，“…是咸的”、“…与…是兄弟”和“…位于…与…之间”都是谓词。
⑪中的谓词描述了一个个体的性质，称为一元谓词，⑫中的谓词表示两个个体之间的关系，称为二元谓词，⑬中的谓词表示三个个体之间的关系，称为三元谓词。
依次类推，我们将描述n个个体之间关系的谓词称为n元谓词，通常用大写英文字母来表示谓词。
为方便起见，将命题称为零元谓词。
例如，例2.1-1中的三个谓词可符号化为：P(x)：x是咸的；Q(x，y)：x与y是兄弟；R(x，y，z)：x位于y和z之间。
这里P 、Q 和R表示的都是具体的谓词，称为谓词常元；否则称为谓词变元。
P(x)、Q(x，y)和R(x，y，z)等都是谓词表示的函数形式，通常称为谓词函数，简称为谓词。
然而，仅仅一个谓词，即使是谓词常元，也不能构成一个命题。
第2章 谓词逻辑本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明.一、重点内容1. 谓词与量词谓词，在谓词逻辑中，原子命题分解成个体词和谓词. 个体词是可以独立存在的客体，它可以是具体事物或抽象的概念。
谓词是用来刻划个体词的性质或事物之间关系的词. 个体词分个体常项(用a ,b ,c ,…表示)和个体变项(用x ,y ,z ,…表示)；谓词分谓词常项(表示具体性质和关系)和谓词变项(表示抽象的或泛指的谓词)，用F ,G ,P ,…表示.注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题.量词，是在命题中表示数量的词，量词有两类：全称量词∀，表示“所有的”或“每一个”；存在量词∃，表示“存在某个”或“至少有一个”.在谓词逻辑中，使用量词应注意以下几点：(1) 在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变.(2) 在考虑命题符号化时，如果对个体域未作说明，一律使用全总个体域.(3) 多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的含义.谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题. 所谓解释就是使公式中的每一个变项都有个体域中的元素相对应.在谓词逻辑中，命题符号化必须明确个体域，无特别说明认为是全总个体域。
一般地，使用全称量词∀，特性谓词后用→；使用存在量词∃，特性谓词后用∧.2. 公式与解释谓词公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材). 命题的符号化结果都是谓词公式.例如∀x (F (x )→G (x ))，∃x (F (x )∧G (x ))，∀x ∀y (F (x )∧F (y )∧L (x ,y )→H (x ,y ))等都是谓词公式. 变元与辖域，在谓词公式∀xA 和∃xA 中，x 是指导变元，A 是相应量词的辖域. 在∀x 和∃x 的辖域A 中，x 的所有出现都是约束出现，即x 是约束变元，不是约束出现的变元，就是自由变元. 也就是说，量词后面的式子是辖域. 量词只对辖域内的同一变元有效.换名规则，就是把公式中量词的指导变元及其辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变.代入规则，就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的这个符号.解释(赋值)，谓词公式A 的个体域D 是非空集合，则 (1) 每一个常项指定D 中一个元素； (2) 每一个n 元函数指定D n 到D 的一个函数；(3) 每一个n 元谓词指定D n 到{0,1}的一个谓词；按这个规则做的一组指派，称为A 的一个解释或赋值.在有限个体域下，消除量词的规则为：如D ＝{a 1,a 2,…,a n }，则)(...)()()()(...)()()(2121n n a A a A a A x xA a A a A a A x xA ∨∨∨⇔∃∧∧∧⇔∀谓词公式分类，在任何解释下，谓词公式A 取真值1，公式A 为逻辑有效式(永真式)；在任何解释下谓词公式A 取真值0，公式A 为永假式；至少有一个解释使公式A 取真值1，公式A 称为可满足式.3. 前束范式 一个谓词公式的前束范式仍是谓词公式. 若谓词公式F 等值地转化成B x Q x Q x Q k k ...2211那么B x Q x Q x Q k k ...2211就是F 的前束范式，其中Q 1，Q 2，…，Q k 只能是∀或∃，x 1,x 2,…,x k 是个体变元，B 是不含量词的谓词公式.每个谓词公式F 都可以变换成与它等值的前束范式. 其步骤如下：① 消去联结词→，↔，⎺∨；② 将联结词⌝移至原子谓词公式之前；③ 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同；④将∀x ,∃x 移至整个公式最左边；⑤ 得到公式的前束范式.4.谓词逻辑的推理理论 谓词演算的推理是命题演算推理的推广和扩充，命题演算中的基本等值公式，重言蕴含式以及P ，T ，CP 规则在谓词演算中仍然使用. 在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，引入消去和附加量词的规则，有US 规则(全称量词消去规则)，UG 规则(全称量词附加规则)，ES 规则(存在量词消去规则)，EG 规则(存在量词附加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行.二、实例例2.1 将下列命题符号化：(1) 有某些实数是有理数；(2) 所有的人都呼吸；(3)每个母亲都爱自己的孩子.注意：一般地，全称量词“∀”后，跟蕴含联结词“→”；存在量词“∃”后，跟合取联结词“∧”.解 (1) 设R (x )：x 是实数，Q (x )：x 是有理数。
谓词逻辑知识点总结一、语言和推理的形式化语言和推理的形式化是数理逻辑的基础，它主要研究如何用严格的符号化方法来表示和分析自然语言中的语言和推理。
在谓词逻辑中，我们通常将自然语言中的命题分解成基本的谓词和常量，然后用谓词逻辑公式来表示这些命题。
例如，对于命题“人类都是有智慧的”，我们可以用P(x)来表示“x是人类”，用Q(x)表示“x有智慧”，那么这个命题可以表示为∀x(P(x)→Q(x))。
而推理的形式化则主要是研究如何用逻辑规则和演绎推理方法来推导出符合逻辑规律的结论。
二、谓词演算及其语义谓词逻辑的核心内容就是谓词演算，它是一种用来分析和推导谓词逻辑公式的形式系统。
谓词演算主要包括语法、语义和推导三个方面。
在语法方面，我们主要研究谓词逻辑公式的形式和结构，包括原子公式、复合公式和量词公式等。
在语义方面，我们主要研究谓词逻辑公式的意义和解释，包括谓词的扩展、量词的解释、模型的概念等。
在推导方面，我们主要研究如何用逻辑规则和推导方法来推导谓词逻辑公式的推导系统。
三、逻辑推导逻辑推导是谓词逻辑的核心内容之一，它主要研究如何用逻辑规则和演绎推理方法来推导出新的谓词逻辑公式。
在逻辑推导中，我们主要研究形式系统中的推理规则和推导方法，包括假言推理、析取推理、量词引入和消去等基本推理规则。
通过逻辑推导，我们可以推导出符合逻辑规律的结论，从而解决一些具体的逻辑问题。
四、完全正式系统完全正式系统是谓词逻辑的一个重要概念，它主要指的是一个完全形式化的逻辑系统，包括语法、语义和推导等方面。
在完全正式系统中，我们可以用严格的形式化方法来表示和分析逻辑语言和推理，从而解决一些具体的数理逻辑问题。
完全正式系统的建立对于谓词逻辑的发展具有重要意义，它不仅为逻辑学理论的研究提供了统一的规范框架，同时也为数理逻辑在实际应用中的推广提供了重要的理论基础。
五、争议在谓词逻辑的发展过程中，一些争议性问题也是不可避免的。
比如，有关谓词逻辑的语言和推理的形式化方法，不同的学者有着不同的观点和理论，针对谓词逻辑公式的语法和语义，也存在一些争议性问题。
