第二章 谓词逻辑
学习指导
2 .1 谓词逻辑的基本概念
谓词 在原子命题中，所描述的对象称为个体，用以描述一个个体的性质或多个个体间关系的部分，称为谓词。一般用大写字母P ，Q ，R ，… 等来表示它们。另外这些大写字母还可以用来表示一个谓词所在的位置，而不表示具体的谓词，此时称之为谓词符号。如果一个谓词描述n 个个体的性质或关系，那么称此谓词为n 元谓词。表示一个n 元谓词所在位置的字母称为n 元谓词符号。约定0元谓词符号为命题变元。
个体常元和个体变元 表示具体的，特指的个体词，称为个体常元，常用小写字母 , … 或带下标的小写字母, … 来表示。同样这些小写字母也可以用来表示一个个体常元所在的位置，而不表示具体的个体常元，此时称之为个体常元符号。表示抽象的，泛指的或在一定范围内变化的个体词，称为个体变元，常用小写字母c b a ,,i i i c b a ,,z y x ,,, … 或
带下标的小写字母, … 来表示。
个体变元的取值范围称为个体域，常用大写字母表示。个体常元符号与个体变元是两个不同的概念，例如对个体变元可以加量词，但对个体常元符号却不能加。
i i i z y x ,,D n 元谓词函数 设P 为一个元谓词符号，为个个体变元，由它们组成的称为n 元谓词函数。本身不是一个命题， 但在用具体的谓词代替P ，用n 个个体常元分别代替个个体变元n n x x x ",,21n ),,(21n x x x P "),,(21n x x x P "n 12,,,n x x "x 之后，它就是一个命题了。
量词 （1） 符号“”称为全称量词符，用来表达个体域中所有个体，对应于自然语言中“对所有的”，“每一个”，“对任何一个”和“一切”等词语。?x ?称为全称量词，x 称为其指导变元。
（2）符号“”称为存在量词符，用来表达个体域中某个或某些个体，对应于自然语言中“存在一些”，“至少有一个”，“对于一些”和“有的”等词语。?x ?称为存在量词，x 称为其指导变元。
全总个体域 由宇宙间一切事物组成的个体域称为全总个体域。
一般地，命题中个体变元的个体域是被明确给出的，如果没有明确给出个体域，那么我们就认为个体域是全总个体域。
特性谓词 我们把为了确定个体变元的取值范围而引进的谓词称为特性谓词。一般地对全称量词的指导变元限制取值范围用特性谓词和条件式，对存在量词的指导变元限制取值范围用特性谓词和合取式。
2 .2. 谓词公式
项 项由下列规则形成：
(1) 个体常元符号和个体变元是项。
(2) 若是元函数符号，且… 是项，那么(… ）是项。
f n ,,21t t n t f ,,21t t n t (3) 所有项都由有限次经过(1)和(2)生成。
原子公式 若… ,是元谓词函数，… , 是项，则称… ,
）为原子谓词公式，简称原子公式。约定当,,(21x x P )n x n ,,21t t n t (P ,,21t t n t 0n =时，原子公式为0、1或命题变元。
谓词公式 合式谓词公式当且仅当为由下列原则形成的符号串：
(1) 原子公式是合式谓词公式。
(2) 如果是合式谓词公式，那么A )(A ?是合式谓词公式。
(3) 如果，A B 是合式谓词公式，那么)(),(),(B A B A B A →∨∧和都是合式谓词公式。
)(B A ?(4) 如果是合式谓词公式，A x 是个体变元，那么A x )(?和A x )(?都是合式谓词公式。
(5) 仅有限次使用(1),(2),(3)和(4)规则所形成的符号串才是合式谓词公式。
由定义可知，合式谓词公式是按上述规则由原子公式，连结词，量词，圆括号和逗号所组成的符号串。为使用方便，称合式谓词公式为谓词公式。在不引起混淆时可以将合式谓词公式的一些括号省略，其省略规则与命题公式的括号省略规则相同，但是量词后面的括号是不能省略的，除非量词后面的括号内的谓词公式是原子公式。
谓词逻辑的翻译或符号化 把一个自然语言叙述的命题，用谓词公式表示出来，称为谓词逻辑的翻译或符号化。
2. 3 约束变元与自由变元
子公式 设为谓词公式A 中的一个连续的部分， 且本身也是一个谓词公式， 那么称为A 的一个子公式。
1A 1A 1A 量词作用域与约束变元 给定一个谓词公式，一个A 中量词的作用域或辖域是邻接此量词后的最短的子公式。设A 中有一部分形如A B x )(?（或B x )(?），其中B 为量词x ?（或x ?）的辖域，则称B x )(?（或）为的B x )(?A x 约束部分，x 在B 中的所有出现称为约束出现，B 中x 称为约束变元。B 中不是约束出现的其它个体变元称为在B 中的自由变元，
其在B 中的出现称为在B 中自由出现。
A 中不在任一子公式中约束出现的个体变元称为自由变元，自由变元在A 中的出现称为自由出现。常用元语言符号表示()x A x 是在A 中自由出现的任意的公式（为方便和清楚起见，有时还要求x 在A 中是处处自由出现的，尽管这一点不是本质需要的）。
闭式 设为任一公式，
如果中无自由出现的个体变元，那么称是封闭的合式公式，简称闭式。
A A A 在一个合式公式中，有的个体变元既可以约束出现，又可以自由出现，这就容易产生混淆，为了避免混淆，采用下面两条规则：
换名规则 将量词辖域中某个约束出现的个体变元及对应的指导变元，在此辖域中出现的每一处，改成此辖域中未曾出现过的个体变元字母符号，公式中其余部分不变。
代入规则 对某自由出现的个体变元用与原公式中所有个体变元字母符号都不同的个体变元字母符号去代替，且在其自由出现的每一处都代替。
2.4 解释和逻辑有效式
解释 谓词逻辑的一个解释I 由下面四部分组成：
（1） 非空个体域,
I D （2）
中部分特定元素 …. I D ,','b a （3）定义（指自变量的各分量）和取值都在上的一些特定函数….
I D ,','g f （4）
上的特定谓词：，…. I D ','Q P 解释I 是利用以上四部分逐条解释谓词逻辑中的对应符号，其对应关系如下：
（1） 个体变元,,y x …在
内取值。 I D （2） 个体常元符号, … 被解释成', … 。
b a ,,'b a （3） 函数符号 … 被解释成 … 。
,,g f ,','g f （4） 谓词符号, … 被解释成, … 。
Q P ,','Q P 在一个具体解释I 下，任一个谓词公式除自由变元可以在个体域内变化外，其余的都已经完全确定了。所以对一个闭式来说，此时它就有确定的意义和真假值了，是命题。 I D 真 设为谓词公式，A I 为一个解释，在解释I 下，将中所有的自由变元任意分别
A
用中的个体常元代替。如果由此得到的所有命题都是真命题， 那么称在解释I D A I 下为真。如果由此得到的所有命题都是假命题， 那么称在解释A I 下为假。
逻辑有效式与矛盾式 设为谓词公式，如果A A 在任何解释下都为真，那么称A 为逻辑
有效式（或称永真式）。如果A 在任何解释下都为假，那么称A 为矛盾式（或称永假式）
。如果至少存在一个解释使A 为真，那么称A 为可满足式。显然逻辑有效式是可满足式。
代换实例 设是含命题变元的命题公式，
是个谓词公式，用）n P P P A A ,,,(21"=n P P P ,,,21"n A A A ,,,21"n )1(n i A i ≤≤处处代换 ，所得谓词公式称为的一个代换实例。
i P A ′A 定理（谓词逻辑代人规则） 命题公式中的重言式的代换实例是谓词公式中的逻辑有效式，称之为重言式。命题公式中的矛盾式的代换实例也是谓词逻辑中的矛盾式。
2.5 等价关系，蕴涵关系和前束范式
等价关系 设是谓词逻辑中任意的两公式，如果B A ,B A ?为逻辑有效式，那么称与A B 是等价的，记作。
B A ?蕴涵关系 设是谓词逻辑中任意的两公式，
如果为逻辑有效式，那么称蕴涵B A ,B A →A B ，记作。
B A ?定理（谓词逻辑置换规则） 设为谓词公式A 的一个子公式，为一个与等价的谓词公式。在A 中将置换成得到的新的谓词公式记为B ， 那么。
1A 1B 1A 1A 1B B A ?常见的等价关系：
表2.1 等价关系
量词转换律
() 13E )()()()(x A x x A x ?????
() 14E )()()
()(x A x x A x ????? 量词辖域的扩张与收缩律
() 15E ))()((B x A x ∧?B x A x ∧??)()(
() 16E B x A x B x A x ∨??∨
?)()())()(( () 17E B x A x B x A x ∧??∧
?)()())()(( () 18E B x A x B x A x ∨??∨
?)()())()(( 量词分配律
() 19E )()()()())()()((x B x x A x x B x A x ?∧??∧
? () 20E )()()()())()()((x B x x A x x B x A x ?∨??∨?
含联结词“”的等价关系
→() 21E B x A x B x A x →??→?)()())
()(( () 22E B x A x B x A x →??→?)()())
()(( () 23E )()())()((x B x A x B A x ?→?→?
() 24E )()())()((x B x A x B A x ?→?→?
() 25E )()()()())()
()((x B x x A x x B x A x ?→??→? 双量词等价关系
)(26E ),())((),())((y x A x y y x A y x ?????
)(27E ),())((),())((y x A x y y x A y x ?????
常见的蕴涵关系：
表2.2 蕴涵关系
量词分配蕴涵律
() 12I )()()()())()()((x B x x A x x B x A x ?∧??∧?
() 13I )()()(()
()()()(x B x A x x B x x A x ∨???∨?
含联结词“”的蕴涵关系
→() 14I )()()()())()
()((x B x x A x x B x A x ?→??→? () 15I )()()()())()
()((x B x x A x x B x A x ?→??→? () 16I ))()()(()()()
()(x B x A x x B x x A x →???→?
双量词蕴涵关系 )(17I ),())((),())((y x A x y y x A y x ?????
)(18I ),())((),())((y x A y x y x A y x ?????
)(19I ),())((),())((y x A y x y x A y x ?????
)(20I ),())((),())((y x A y x y x A x y ?????
)(21I ),())((),())((y x A x y y x A y x ?????
)(22I ),())((),())((y x A y x y x A x y ?????
前束范式 一个谓词公式称为前束范式，如果它有如下形式：
1122()()()k k Q x Q x Q x B "其中为?或?，)1(k i Q i ≤≤B 为不含有量词的公式，称 为公式的首标。
1122()()(k k Q x Q x Q x ")定理 任一谓词公式都存在与之等价的前束范式。
求前束范式的步骤：
(1) 消除给定谓词公式中的联结词和→?，使之等价于仅含量词和联结词，∧与的谓词公式。
?∨(2) 将联结词?向内深入到原子命题前面。
(3) 利用换名规则使所有变元（约束变元和自由变元）的符号都不相同。
(4) 利用量词辖域的扩展和收缩律，将所有量词按在公式中出现的次序移到公式最前面，扩大量词的辖域为整个公式。
由于在等价演算时顺序可以不同，所以与给定公式等价的前束范式是不唯一的。
2. 6. 谓词逻辑的推理理论
推理的形式结构 在谓词逻辑中，推理的形式结构为一个谓词公式的有限序列A 1, A 2 , ... , A n ；B ，其中A 1, A 2 , ... , A n 称为前提，B 称为结论。如果B A A A k →∧∧∧"21 是逻辑有效式，即，那么称推理正确，此时称B A A A k ?∧∧∧"21B 是的有效结论，并且记为：
k A A A ,,,21" ├ k A A A ,,,21"B
全称量词消去规则（简称 规则）
， US 这条规则有以下两种形式：
├
)()(x A x ?)(y A ├
)()(x A x ?)(c A 规则成立的条件是：
US （1）x 是中自由出现的个体变元(本条件也隐含在元语言符号的定义里)。
)(x A )(x A （2）为任意的不在中约束出现的个体变元。
y )(x A （3）为任意的个体常元。
c 全称量词引人规则（简称 规则）
UG ├
)(y A )()(x A x ?UG 规则成立的条件是：
（1）在中自由出现，且上面有效推理的前提是取任何值时所有的。
y )(y A y )(y A （2）取代的y x 不能在中约束出现过。
)(y A 存在量词消去规则（简称规则）
ES )()(x A x ?├
)(c A ES 规则成立的条件：
（1）是使为真的特定的个体常元。
c )(c A
（2）不曾在中出现过。在形式证明中还要求c 不在以前步骤中出现过。
c )(x A （3）中除)(x A x 外还有其他自由出现的个体变元时，不能用此规则。
存在量词引入规则（简称 规则）
EG ├
)(c A )()(x A x ?EG 规则成立的条件是：
（1）是特定的个体常元。
c （2）取代的c x 不在中出现。 )(c A
逻辑学复习知识点 前言：逻辑学：传统逻辑、现代逻辑；它是基础性，工具性的学科（更直接，更系统） 第一章（绪论）： 第一节什么是逻辑学 1.“逻辑”的含义：源于古希腊，原意：思想，言辞，理性，规律。 逻辑是一门学科，即逻辑学（思维科学）。 2.逻辑学的研究对象：研究思维的形式结构及其规律的科学。 逻辑学的研究目的：总结出人们正确运用各种思维形式的逻辑规律。 思维：感性认识（感觉，知觉，表象）和理性认识（概念，命题（判断），推理） 思维的形式结构（思维的逻辑形式）：包括逻辑常项和变项 逻辑常项：不随思维具体内容变化而变化，是判定一种逻辑形式具体类型的唯一依据。 传统逻辑：自然语言（日常用语）现代逻辑：人工语言（符号语言：表意符号，公式，公式序列） 思维形式结构的规律：逻辑规则：仅适用于某种思维形式。逻辑思维的基本规律：普遍适用于各种类型的思维形式。（传统逻辑定义） 逻辑思维的基本规律包括：同一律，矛盾律，排中律，充足理由律。表现方式： 现代逻辑的基础部分：经典命题逻辑,经典谓词逻辑（表现方式：重言式（重言蕴涵式，重言等值式））第二节逻辑学的性质和作用 1.逻辑学的性质：工具性，全人类性（没有民族性，阶级性） 2.逻辑学的作用： 联合国教科文组织1974年规定的七大基础学科：逻辑学、数学、天文学和天体物理学、地球科学和空间科学、物理学、化学、生命科学
三方面作用：促成逻辑思维由自发向自觉转变；培养和提高人们认识事物、从事科学研究的能力；帮助识别、驳斥谬误和诡辩。 3.第三节逻辑简史 逻辑学的历史：两千多年逻辑学的三大源头：古中国、古印度、古希腊。 西方逻辑：以古希腊逻辑为先河，在发展的历程中完整地经历了传统和现代两个形态。（以此为例） 传统逻辑的诞生与发展： 传统逻辑：由亚里士多德开始直至莱布尼兹之前的整个逻辑类型。特点：借助自然语言，主要范围是常见日常思维类型。 亚里士多德：（公元前384-公元前322）:古希腊著名学者，第一次全面、系统研究逻辑学主要问题，首创逻辑学这门科学。被称作“西方逻辑之父”，主要逻辑著作《范畴篇》、《解释篇》、《前分析篇》、《后分析篇》、《论辩篇》、《辩谬篇》，分别论述概念、命题（判断）、推理、论证、论辩的方法和如何驳斥诡辩的问题。哲学著作《形而上学》系统论述了矛盾律、排中律，涉及同一律。奠定了西方逻辑学发展的坚实基础。古希腊斯多葛学派及欧洲中世纪的逻辑学家：研究了假言命题、选言命题、联言命题和推理形式，提出相应推理规则。 弗兰西斯.培根（1561-1626）：英国哲学家、逻辑学家。17世纪，实验自然科学兴起和发展，研究了科学归纳法问题。《新工具》一书中提出科学归纳的“三表法”：“存在和具有表”、“差异表”、“程度表”，奠定归纳逻辑的基础。 穆勒（1806-1873）：19世纪英国哲学家、逻辑学家。在《逻辑体系》（我国近代学者严复译为《逻辑名学》）把科学归纳法发展为五种：求同法、求异法、求同求异并用法、共变法、剩余法。至此，传统逻辑的基本框架大致形成。 现代逻辑的兴起与发展： 现代逻辑（“数理逻辑”或“符号逻辑”）:由莱布尼兹奠定基本思想,目前仍在不断发展中的逻辑类型。特点：借助人工语言（符号语言），建立形式系统，对研究对象整体把握。 莱布尼兹（1646-1716）：德国著名数学家、哲学家。17世纪末期，提出用数学演算的方法处理演绎逻辑；
谓词逻辑习题 1. 将下列命题用谓词符号化。 （1）小王学过英语和法语。 （2）2大于3仅当2大于4。 （3）3不是偶数。 （4）2或3是质数。 （5）除非李键是东北人，否则他一定怕冷。 解： (1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ? (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨ (5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ，， =，消去下列各式的量词。 （1）))()((y Q x P y x ∧?? （2）))()((y Q x P y x ∨?? （3）)()(y yQ x xP ?→? （4）))()((y yQ y x P x ?→?， 解： (1) 中))()(()(y Q x P y x A ∧?=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧?=，因此))()(())()((y Q y P y y Q x P y x ∧?∧?? ，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧? ，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧?? （2）中))()(()(y Q x P y x A ∨?=，它对y 不是自由的，故不能用UI 规则，然而，对 )(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨?，这时用UI 规则，可得： ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨? （3）略 （4）略 3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321 {，，=D 。求下列各式的真值。 （1）)3(，x xP ? （2）)1(y yP ，? （3）)(y x yP x ，?? （4）)(y x yP x ，?? （5）)(y x yP x ， ?? （6）)(y x xP y ， ?? 解：
谓词演算的 推理理论
在谓词逻辑中，除了命题逻辑中的推理规则继续有效外，还有以下四条规则。设前提Г= {A 1,A 2,…,A k }. 1. 全称指定规则（全称量词消去规则）US ： 例1 取个体域为实数域，F(x, y): x>y, P(x)=(?y) F(x,y), 则(?x)P(x) ?P(z)=(?y) F(z,y). 而不能(?x) P(x) ?P(y)=(?y) F(y,y). 其中x,y 是个体变项符号，c 为任意的个体常量. 或 (?x ) P (x ) ∴ P (y ) (?x) P (x ) ∴ P (c )
2 . 全称推广规则（全称量词引入规则） UG： P(x) ∴ (?x)P(x) 其中x是个体变项符号，且不在前提的任何公式中 自由出现. 3. 存在指定规则（存在量词消去规则） ES： (?x)P(x) ∴ P(c) 1)c是使P(x)为真的特定的个体常量，不是任意的. 2)c不在前提中或者先前推导公式中出现或自由出现， 换句话说，此c是在该推导之前从未使用过的.
4. 存在推广规则（存在量词引入规则) EG： P(c) ∴ ( x)P(x) 其中x是个体变项符号, c是个体常项符号.
谓词逻辑的推理理论由下列要素构成. 1. 等价公式 2. 蕴含式 3. 推理规则： (1) 前提引入规则 (2) 结论引入规则 (3) CP推理规则 (4)归谬论 (5) US规则 (6) UG规则 (7) ES规则 (8) EG规则
1)在推导的过程中，可以引用命题演算中的规则P、规则T、 规则CP . 2)为了在推导过程中消去量词，可以引用规则US和规则ES来 消去量词. 3)当所要求的结论可能被定量时，此时可引用规则UG和规则 EG将其量词加入. 4)证明时可采用如命题演算中的直接证明方法和间接证明方法. 5)在推导过程中，对消去量词的公式或公式中没含量词的子公 式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式. 6)在推导过程中，对含有量词的公式可以引用谓词中的基本等 价公式和基本蕴涵公式.
从命题逻辑到谓词逻辑 命题逻辑研究的基本元素是命题。命题是有真假意义的一句话，而对这句话的结构和成分是不考虑的。因此，用这样简单的手段，很多思维过程不能在命题逻辑中表达出来。 例如，逻辑学中著名的三段论： 凡人必死 张三是人 张三必死 在命题逻辑中就无法表示这种推理过程。 因为，如果用P代表“凡人必死”这个命题，Q代表“张三是人”这个命题，R代表“张三必死”这个命题，则按照三段论，R应该是P和Q的逻辑结果。但是，在命题逻辑中，R 却不是P和Q的逻辑结果，因为公式 P∧Q→R 显然不是恒真的，解释{P，Q，?R}就能弄假上面的公式。 发生这种情况的原因是：命题逻辑中描述出来的三段论，即PùQ?R，使R成为一个与P，Q 无关的独立命题。因此，取解释时，可将P，Q取真，R取假，从而弄假公式P∧Q→R。但是，实际上命题R是和命题P，Q有关系的，只是这种关系在命题逻辑中无法表示。因此，对命题的成分、结构和命题间的共同特性等需要做进一步的分析，这正是谓词逻辑所要研究的问题。为了表示出这三个命题的内在关系，我们需要引进谓词的概念。在谓词演算中，可将命题分解为谓词与个体两部分。例如，在前面的例子“张三是人”中的“是人”是谓语，称为谓词，“张三”是主语，称为个体。 定义3.1.1 可以独立存在的物体称为个体。（它可以是抽象的，也可以是具体的。） 如人、学生、桌子、自然数等都可以做个体。在谓词演算中，个体通常在一个命题里表示思维对象。 定义3.1.2 设D是非空个体名称集合，定义在Dn上取值于{1，0}上的n元函数，称为n 元命题函数或n元谓词。其中Dn表示集合D的n次笛卡尔乘积。 一般地，一元谓词描述个体的性质，二元或多元谓词描述两个或多个个体间的关系。0元谓词中无个体，理解为就是命题，这样，谓词逻辑包括命题逻辑。 下面我们举一个谓词的例子：
2.5 谓词演算的推理理论 1．推理定律 谓词演算中也存在一些基本的等价与蕴含关系，参见表2-2。我们以此作为推理的基础，即推理定律。 表2-2 序号 等价或蕴含关系 含义 E27 E28 ┐?xA(x)??x┐A(x) ┐?xA(x)??x┐A(x) 量词否定等值式 E29 E30?x(A(x)∧B(x))??xA(x)∧?xB(x) ?x(A(x)∨B(x))??xA(x)∨?xB(x) 量词分配等值式（量词分配律） E31 E32 E33 E34 E35 E36 E37 E38 E39 E40 E41 E42 E43?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 ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(A(x)→B(x))??xA(x)→?xB(x) ?x(A(x)→B)??xA(x)→B ?xA(x)→B??x(A(x)→B) A→?xB(x)??x(A→B(x)) A→?xB(x)??x(A→B(x)) 量词作用域的扩张与收缩 I21 I22?xA(x)∨?xB(x)??x(A(x)∨B(x)) ?x(A(x)∧B(x))??xA(x)∧?xB(x) I23 ?xA(x)→?xB(x)??x(A(x)→B(x)) 表2-2中的I、E序号是接着表1-5和1-8排列的，表明它们都是谓词逻辑的推理定律。E31~E34与E35~E38只是A和B的顺序不同。 2．量词的消除与产生规则 谓词推理可以看作是对命题推理的扩充。除了原来的P规则（前提引入）、T规则（命题等价和蕴含）及反证法、CP规则外，为什么还需引入新的推理规则呢？ 命题逻辑中只有一种命题，但谓词逻辑中有2种，即量词量化的命题和谓词填式命题。如果仅由表2-2的推理定律就可推证，并不需要引入新的规则，但这种情况十分罕见，也失去了谓词逻辑本身的意义。为此，要引入如下4个规则完成量词量化命题与谓词填式之间的转换，其中的A(x)表示任意的谓词。 (1) 全称指定（消去）规则US（Ubiquity Specification，或记为?-）
§2.2 谓词公式及其解释 习题2.2 1. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。 （1）))()((y x Q x P x ，→? （2）)()(y x yQ y x xP ，，?→? （3）)())()((z y x xR z y Q y x P y x ，，，，?∨∧?? 解 （1）x ?中的x 是指导变元；量词x ?的辖域是),()(y x Q x P →；x 是约束变元，y 是自由变元。 （2）x ?中的x ，y ?中的y 都是指导变元；x ?的辖域是)(y x P ，，y ?的辖域是)(y x Q ，；)(y x P ，中的x 是x ?的约束变元，y 是自由变元； )(y x Q ，中的x 是自由变元，y 是y ?的约束变元。 （3）x ?中的x ，y ?中的y 以及x ?中的x 都是指导变元；x ?的辖域是))()((z y Q y x P y ，，∧?，y ?的辖域是)()(z y Q y x P ，，∧，x ?的辖域是)(z y x R ，，；)(y x P ，中的x ，y 都是约束变元；)(z y Q ，中的y 是约束变元；z 是自由变元， )(z y x R ，，中的x 为约束变元，y ，z 是自由变元。 2. 设个体域}21 {，=D ，请给出两种不同的解释1I 和2I ，使得下面谓词公式在1I 下都是真命题，而在2I 下都是假命题。 （1）))()((x Q x P x →? （2）))()((x Q x P x ∧? 解（1）解释1I ：个体域}21 {，=D ，0:)(,0:)(>>x x Q x x P 。 （2）解释2I ：个体域}21 {，=D ，2:)(,0:)(>>x x Q x x P 。 3. 对下面的谓词公式，分别给出一个使其为真和为假的解释。 （1）)))()(()((y x R y Q y x P x ，∧?→? （2）)),()()((y x R y Q x P y x →∧?? 解 （1）成真解释：个体域D ＝{1,2,3},0:)(
第五章谓词逻辑 习题5.1 1. a)每个自然数都有唯一的后继； 解：“每个”是全称的概念；“自然数”需引进一个特性谓词；“有”表示存在；“唯一”表示所有具有该性质的元素均相等（即若x具有该性质，y也具有该性质，则x等于y）；“后继”用谓词表示。于是，可令： N(x)：x是自然数； Q(x, y)：y是x的后继； E(x, y)：x等于y； 则上述命题可以符号化为： (? x) ( N ( x ) → (? y) (Q ( x, y ) ∧ (? z) (Q ( x, z ) → E ( y, z ) ) b) 没有以0为后继的自然数； 解：“没有”表示不存在；“自然数”用特性谓词表示；“后继”用谓词表示。于是，可令：N(x)：x是自然数； Q(x, y)：y是x的后继； 则上述命题可以符号化为： ? (? x)( N ( x ) ∧ Q ( x, 0 ) ) 注意：①对于引进的特性谓词，在全称量词约束下要用逻辑联结词“→”，在存在量词约束下要用逻辑联结词“∧”。 ②“唯一”概念的符号化。 2. a)存在唯一的偶素数； 解：“存在”是存在量词的概念；“唯一”可参照上题；“偶数”、“素数”用谓词表示。于是，可令： E(x)：x是偶数； S(x)：x是素数； R(x, y)：x等于y； 则上述命题可以符号化为： (? x) ( E ( x ) ∧ S ( x ) ∧ (? y) ( E ( y ) ∧ S ( y ) → R ( x, y ) ) b)没有既是奇数又是偶数的数； 解：“没有”表示不存在；“奇数”、“偶数”、“数”用谓词表示。于是，可令： O(x)：x是奇数； E(x)：x是偶数； Q(x)：x是数；
对现代逻辑中量词的逻辑哲学省察 量词是现代逻辑的关键性概念，对量词的解释既是现代逻辑、也是现代哲学的重要问题。首先，现代逻辑中的量词在本质上是一个二阶函数，量词的这种特点克服了传统逻辑量词的局限性，并使得现代逻辑的语言处理能力大为增强，但同时也使得对量词的语义解释涉及了很多概念和理论。其次，两种对量词的解释方案——指称量化和替换量化，它们的不同特点造成了不同的逻辑后果和哲学后果。最后，量词成为分析诸如真、指称以及本体论这些哲学概念的核心概念，逻辑也为哲学问题的解决提供了深刻的视角。 标签：量词—变元；对象量化；替换量化；本体论承诺 量词是逻辑学的一个基本概念，传统逻辑围绕着量词做了很多的工作并形成了一系列的理论，但直到现代逻辑产生后，量词在逻辑学中的核心地位和价值才得到彰显和重视。现代逻辑的两个基本研究路径——句法学和语义学都是围绕着量词概念而展开的，对量词的语义解释也与现代哲学中的真、指称、意义、同一、本体论等理论密切相关，量词由此成为现代逻辑的核心概念，对量词理论的关注也成为现代哲学的基本问题。 一、现代逻辑中量词的句法特点 量词是用来表示数量的概念。自然语言中的量词很多，如“所有的”“很多”“大多数”“一些”等，但逻辑作为一种追求真的普遍规律的科学，只选取了表示全部数量的全称量词（“所有的”）和表示部分数量的特称量词（“有些”）作为研究对象，后者也经常被称为存在量词，传统逻辑和现代逻辑的量词理论都是围绕着这两个量词而展开。一个有意思的现象是，虽然全称量词和特称量词也是传统逻辑的基本量词，但围绕着这两个量词，传统逻辑并没有形成对应于现代逻辑的量化理论，也没有围绕着量词形成太多的其他相关理论；而量词却成为现代逻辑的核心概念，现代谓词逻辑甚至被称为量词逻辑，现代逻辑的很多理论，如真、指称等理论都和量词密切相关，而这种现象的出现是和传统逻辑与现代逻辑中量词的不同特点密切相关的。 在传统逻辑中，量词是与句子中的主语密切相关的，量词被用在主语的前面，用来表达主项所断定的对象的范围和数量。传统逻辑中量词的这个特点是与日常语言表达方式密切相关的。从古希腊逻辑发轫之初，人们主要关注的是形如“所有人都是会死的”，即“S是P”这样的主谓式句子的推理，在这样的推理中，推理形式和日常语言的形式是紧密相关的甚至是一致的。“所有人都是会死的（Everyone is mortal）”在传统逻辑看来就是这样一个主谓式句子：“人”是这个句子的主语，“会死的”是这个句子的谓语，“所有人”这样的量词加诸句子的主语的前面，表达了主项的数量。亚里士多德的三段论理论也建立在对这样的主谓式的性质命题的关注之上。虽然三段论推理代表了传统逻辑的最高成就，但是推理形式过分依赖于日常语言形式还是使得传统逻辑的处理句子和推理的能力受到很大的局限。首先，三段论不能处理包含单称词的语句的推理问题，虽然亚里士多
谓词逻辑表示法是把一些知识表示为经典逻辑中的谓词表示式。它只能表示出精确的知识，而对不确定的知识无法有效表示，同时这种表示方式也不能很好地体现知识的内在联系。在进行教学时，首先需要通过实例让学生了解什么是命题和命题公式，什么是谓词和谓词公式，然后用实例来分析讲解将知识表示为谓词公式的过程： 1）定义谓词和个体 例：王先生是李文的老师。首先定义谓词：TEACHER(X,Y):X 是Y 的老师，而后定义个体：王先生(Wang)，李文（LiWen ）； 2）为每个谓词中的变元赋以特定的值：TEACHER(Wang,LiWen)； 3）根据所要表达的知识语义，以适当的连接词和量词符号将各个谓词连接起来，得到知识的谓词公式：TEACHER(Wang,LiWen)。 在理解连接词∧(逻辑与)、∨（逻辑或）、┐（逻辑非）时可以参考我们平时的语言 中的“并且”、“或者”、“不”，对P →Q 的理解可以参考┐P ∨Q 。在此节只要求学生对谓词表示法有了解，命题的证明等内容不做要求，可以将相关内容放在辅助教学网站的拓展篇，以满足不同学生的需求。 在教学中除了书本中介绍的例子之外，还可以使用以下例子。 例1：用谓词逻辑和公式表达意境。 分析如下命题和谓词逻辑，并尽可能正确表达它的含义： （1） 蓝的（天）∧飘（白云）∧奔跑（马儿）∧飞翔歌唱（鸟儿）； 答：这是一个由“与”关系连接起来的谓词逻辑公式，它表达了一种大自然的景观：蓝色的天上白云飘飘，马儿在奔跑，鸟儿在飞翔歌唱。 （2） )(x {好姑娘（x ）∧居住的地方(z,x) ∧遥远的(z) ∧(y)[人(y) ∧行走 经过(y,z) →回头留恋地张望(y)]} 答：这是一个既有谓词表示，又有命题逻辑表达，既有连接词，又有全称量词和存在量词的较复杂的谓词公式，它表达的意思是：在那遥远的地方，有位好姑娘，人们经过她的身旁，都要回头留恋地张望。这就是青海民歌《在那遥远的地方》（王洛宾词曲）中的意境。 例2:用谓词逻辑表示知识单元。 设有下述记录：①小李给小王送礼物；②小李是工程师；③小王是程序员；④小李的地址是南京路115号；⑤小王的地址是黄山路458号。 请用谓词逻辑（中或英文）表示上述记录，并分成必要的知识单元。 答：1）定义谓词，GIVE(x,y,p),x 给Y 送礼物p ； OCCUPATION(x,y)，X 是Y 职业； ADDRESS （x,y ）,x 的地址是Y ； 2）定义个体 小李(xiaoli)，小王(xiaowang)，工程师（engineer ），程序员(programmer)、 南京路115号（115-nianjing-road ），黄山路458号（458-huangshan-road)。 3）知识谓词公式： ① GIVE(xiaoli,xiaowang,presents)； ② OCCUPATION(xiaoli,engineer)； ③ OCCUPATION （xiaowang,programmer ）； ④ ADDRESS （xiaoli,115-nianjing-road ）； ⑤ ADDRESS(xiaowang,458-huangshan-road)；
例1 证明下面诸命题推得的结论是有效的: 如果今天是星期三, 那么我有一次离散数学或数字逻辑测验; 如果离散数学课老师有事, 那么没有离散数学测验; 今天是星期三且离散数学老师有事, 所以, 我有一次数字逻辑测验。 证明先将各命题形式化。 设A: 今天是星期三。B: 我有一次离散数学测验。 C: 我有一次数字逻辑测验。D: 离散数学课老师有事。 则本题要求证: A→B∨C , D→┐B , A∧D C。 (1) A∧D（前提） (2) A ((1),Ｉ1） (3) A→B∨C（前提） (4) B∨C ((2), (3), Ｉ11） (5) D ((1), Ｉ2） (6) D→┐B（前提） (7) ┐B（(5), (6), Ｉ11） (8) C（(4), (7),Ｉ10） 例2 证明三段论方法的正确性： 凡人要死。 苏格拉底是人。 苏格拉底要死。 令H(x): x是人。 M(x): x要死。 a: 苏格拉底。 则本题要证明：x(H (x)→M (x )) , H (a ) M (a ) 证明 (1) H (a ) （前提） (2) x (H (x )→M (x ))（前提） (3) H (a )→M (a ) （(2),US） (4) M ( a ) （(1), (3), Ｉ11 例3 用形式证明的方法证明“任何人如果他喜欢步行, 他就不喜欢乘汽车,每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱跨自行车, 所以
有的人不爱步行。 ” 证明设个体域为全体人的集合。 P (x): x喜欢步行。 Q (x): x喜欢搭车。 R (x): x喜欢骑自行车。 则本题要证明: x (P (x)→┐Q (x )), x (Q (x )∨R (x )) , x┐R (x ) x┐P (x )本题证明树如图2―2。其证明过程如下: (1) x ┐R (x)（前提） (2) ┐R (c ) （(1), ES） (3) x (Q (x )∨R (x)) （前提） (4) Q (c )∨R (c ) （(3), US）
弗雷格的逻辑和数学思想的哲学基础 张庆熊复旦大学现代哲学研究所 【提要】弗雷格在《算术基础》中阐述了三条基本原理，这三条原理一方面说明他为什么要构造他的人工语言系统，另一方面说明算术何以能够建立在逻辑的基础之上，这是从哲学的高度出发论证他的逻辑和数学思想的基础。 弗雷格（Gottlob Friedrich Ludwig Frege，1848－1925）于1897年发表《概念文字：一种模仿算术语言构造的纯思维的形式语言》（Begriffsschrift，eine der arithmetischen nachgebildete Formelsprache des reinen Denkens）。这本薄薄的书可谓现代逻辑的开山之作。它奠定了数理逻辑中的命题逻辑和一阶谓词逻辑的基础。然而，对于这本逻辑史上划时代的专著，在当时却少有人问津。弗雷格反思其原因，认为除人们对那陌生的符号系统望而生畏外，还不理解他为什么要构造这一系统的理由。他在1884年发表了专著《算术基础》（Grundlagen der Arithmetik）。在这本书中，他没有使用数理逻辑的符号，而是哲学理论上论证他所构造的人工语言系统的基本原理，指出严格区分心理的东西和逻辑的东西、主观的东西和客观的东西的必要性；强调决不要忘记概念和客体之间的区别；对当时所流行的逻辑学和数学中的心理主义展开批判。他认为逻辑是数学的基础，数的概念可以被定义为逻辑的类的概念，而类则被看成概念的外延。可以说，《算术基础》一书是弗雷格在哲学的方面为他的数学基础研究中的逻辑主义的方案奠定基础。 弗雷格在《算术基础》中所提出的原理一共只有三条，下面我们就结合考察这三条原理来评述弗雷格的逻辑和数学思想的哲学基础。 一、逻辑规律的客观性 在弗雷格所处的时代，逻辑研究中的心理主义占支配地位。按照这种心理主义的观点，逻辑推理是一种思维的活动，思维的活动是一种心理的活动，所以逻辑的规律可以还原为心理的规律，逻辑的真理是一种主观的真理。弗雷格认为，这种心理的观点就如压在逻辑和数学成长之树上的巨石一样，为使逻辑和数学研究得以顺利展开，必须搬开这块巨石。为此，他在《算术哲学》导言中所列出的第一条原理就是： “严格区分心理的东西和逻辑的东西、主观的东西和客观的东西。”1 弗雷格认为，这种心理主义的观点混淆了逻辑本身和从事逻辑推理的心理活动。一个人在从事逻辑推理的时候，确实发生心理的活动。这种心理的活动是主 1G. Frege，Die Grundlage der Arithmetik. Eine Logisch-mathematische Untersuchung über den Begriff der
? 离散数学基础 2017-11-19 ?定义：个体和谓词 ?在原子命题中，描述的对象称为个体，用于描述个体的性质或个体之间的关系部分称为谓词。 ?例：张三是个大学生。 ?个体：张三；谓词：是个大学生 ?例：张三和李四是表兄弟。 ?个体：张三、李四；谓词：是表兄弟（关系） ?习惯上，用小写字母 a, b, c, … 表示个体，大写字母 P, Q, R, … 表示谓词。 ?例：a：张三；b：李四； P(x)：x 是个大学生；Q(x, y)：x 和 y 是表兄弟。 则：P(a)：张三是个大学生； P(b)：李四是个大学生； Q(a, b)：张三和李四是表兄弟。 ?定义：原子命题的谓词形式 ?一个原子命题用一个谓词常项（如 P）和 n 个有次序的个体常量（如 a1, a2, …, a n）表示成 P(a1, a2, …, a n)，称为该原子命题的谓词形式。 ?例：Q(a, b)：张三和李四是表兄弟。 ?当讨论的个体处于一个论述范围时，个体常量被个体变量取代。如 Q(x, y)。?定义：n 元原子谓词 ?由一个谓词（如 P）和 n 个个体变量（如 x1, x2, …, x n）组成的 P(x1, x2, …, x n)，称为 n 元原子谓词，或简称 n 元谓词，或 n 元命题函数。 ?一个 n 元谓词 P(x1, …, x n) 只有 P 取谓词常项，且其中所有个体变量均取得个体常项时，该谓词才成为命题。 ?特别地将命题看成是0元谓词。 ?定义：个体论域 ?个体变量 x i 的论述范围（取值范围）称为 x i 的论域或变程。 ?全总论域：将一个 n 元谓词的各个个体论域综合在一起，称为该谓词的全总
命题逻辑和谓词逻辑习题课的题目及参考 答案 说明：红色标注题目可以暂且不做 命题逻辑和谓词逻辑习题课的题目 一、填空 1、若P，Q，为二命题，Q P→真值为0 当且仅当。2、命题“对于任意给定的正实数，都存 在比它大的实数”令F(x)：x为实数，:) , (则命题的逻辑谓词公式y L> x x y 为 。
3、谓词合式公式)( xP? ?的前束式 x → ) (x xQ 为。 4、将量词辖域中出现的 和指导变元交换为另一变元符号，公式 其余的部分不变，这种方法称为换名规 则。 5、设x是谓词合式公式A的一个客体变 元，A的论域为D，A(x)关于y是自由的，则 被称为存在量词消去规则，记为ES。 6．设P，Q 的真值为0，R，S的真值为1，则 → ∨ Q P? ∨ ?的真值 → ∧ ? (S ))) ( R ( ) P R ( = 。 7．公式P ∧) ( ) (的主合取式为 ∨ R S R P? ∨ ∧
。 8．若解释I的论域D仅包含一个元素，则)( xP? → ?在I下真值为 xP ) (x x 。 9. P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 10. 论域D={1，2}，指定谓词P 则公式),(x y ?真值 x? yP 为。 11.P，Q真值为0 ；R，S真值为1。则
∧ wff∧ R ∨ → )) ∧的真值∨ S P )) P ) ( ( (( Q R (S 为 。 12. R ?) ) ((的主合取式 ∧ R Q ∨ P wff→ 为 。 13.设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词))) x y O P y ?的自然语言是 → ? wff∧ x ( ) ( N ( , y ( (x ) 。 14.谓词)),,( x y z P x z ?的前束 ? P ? ∧ → wff? y ) , ( , )) y ( z ( uQ x (u 式为 。
一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y)))
第二节 谓词公式的分类与解释 为了给出谓词公式的定义，先给出项和原子公式的定义。 定义2.1 项： （1） 个体常项和个体变项是项； （2） 设),...,,(21n x x x ?是任意的n 元函数，n t t t ,...,,21是项，则),...,,(21n t t t ?是项； （3） 有限地使用（1），（2）形成的符号串是项。 定义2.2 设),...,,(21n x x x R 是任意的n 元谓词，n t t t ,...,,21是项，则称),...,,(21n t t t R 是原子公式。 定义2.3合式公式： （1） 原子公式是合式公式； （2） 若A 是合式公式，则)(A ?也是合式公式； （3） 若B A ,是合式公式，则)(),(),(),(B A B A B A B A ?→∨∧也是合式公式； （4） 若A 是合式公式，则(),()xA xA ??也是合式公式。其中x 为任意的个体变项； （5） 有限次地应用（1）～（4）形成的字符串是合式公式。 这样定义的合式公式又称作谓词公式，简称公式。合式公式的最外层括号可以省去。 定义2.4 （1） 在公式xA ?和xA ?中，A 是相应量词的辖域，x 称为指导变量。 （2） 在公式xA ?和xA ?中，x 的所有出现都是约束出现的，不是约束出现的变项称 为自由出现的。 例如：在公式))),,()((),((z y x L y G y y x F x ∧?→?中，?的辖域为 ))),,()((),((z y x L y G y y x F ∧?→ ?的辖域为 )),,()((z y x L y G ∧ x ?中的x 和y ?中的y 都是指导变量。x 的出现都是约束的，),(y x F 中的y 是自由出现的，)(y G 与),,(z y x L 中的y 是约束出现的，z 的出现是自由的。 一般情况下，在一个谓词公式A 中，除了可能含若干个个体常项，函数常项，谓词常 项外，还可能含个体变项，函数变项，谓词变项等。用下面定义对公式进行解释。 定义2.5 一个解释I 由下面4个部分构成： （1） 非空的个体域D ； （2） D 上一部分特定的元素； （3） D 上一些特定的函数；
第二章谓词逻辑 练习一 1、指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并回答它们是否是命题： （1）?x(P(x)∨Q(x))∧R （R为命题常元） （2）?x(P(x)∧Q(x))∧?xS(x)→T(x) （3）?x(P(x)→?y(B(x,y)∧Q(y))∨T(y)) （4）P(x)→(?y?x(P(x)∧B(x,y))→P(x)) 解（1）全称量词?，辖域P(x)∨Q(x)，其中x为约束变元，?x(P(x)∨Q(x))∧R是命题。 （2）全称量词?，辖域P(x)∨Q(x)，其中x为约束变元。 存在量词?，辖域S(x) ，其中x为约束变元。 T(x)中x为自由变元。?x(P(x)∧Q(x))∧?xS(x)→T(x)不是命题。 （3）全称量词?，辖域P(x)→?y(B(x,y)∧Q(y))∨T(y)，其中x为约束变元，T(y)中y为自由变元。存在量词?，辖域B(x,y)∧Q(y)，其中y为约束变元。?x(P(x)→?y(B(x,y)∧Q(y))∨T(y))是命题。 （4）全称量词?，辖域?x(P(x)∧B(x,y))，其中y为约束变元。 存在量词?，辖域P(x)∧B(x,y)，其中x为约束变元。 不在量词辖域中的P(x)中的x为自由变元。P(x)→(?y?x(P(x)∧B(x,y))→P(x)) 不是命题。 2、对个体域{0，1}判定下列公式的真值, E(x)表示“x是偶数”： （1）?x(E(x)→┐x=1) （2）?x(E(x)∧┐x=1) （3）?x(E(x)∧x=1) （4）?x(E(x)→x=1) 再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。
1、设)()()(),,(323221321x x x x x x x x x E ∧∨∧∨∧=是布尔代数],,},1,0[{-∧∨上的一个布尔表达式，试写出),,(321x x x E 的析取范式和合取范式。 答： 析取范式：)()() ()()(),,(321321321321321321x x x x x x x x x x x x x x x x x x E ∧∧∨∧∧∨∧∧∨∧∧∨∧∧= 合取范式：)()()(),,(321321321321x x x x x x x x x x x x E ∨∨∧∨∨∧∨∨∨= 2．设P(x)：x 是大象，Q(x)：x 是老鼠，R(x,y)：x 比y 重，则命题“大象比老鼠重”的符号化为 答： ?x ?y ( (P(x) ∧ Q(x)) → R(x,y)) 3．设L(x)：x 是演员，J(x)：x 是老师，A(x , y)：x 钦佩y ，命题“所有演员都钦佩某些老 师”符号化为（ B ）。 A 、)),()((y x A x L x →?； B 、))),()(()((y x A y J y x L x ∧?→? ； C 、)),()()((y x A y J x L y x ∧∧??； D 、)),()()((y x A y J x L y x →∧?? 。 4．下列各式中哪个不成立（ A ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 5．用推理规则证明)()(a G a P ∧?是 ))()((,)(,))()((, )))()(()((x G x S x a S a R a Q x R x Q x P x ??∧?∧→?的有效 结论。 证明：（1） ))()(()(x P x Q x xP ∧→? P （2） ))()(()(a P a Q a P ∧→ US(1) (3) ))()((a R a Q ∧? P
排列组合公式/排列组合计算公式 2008-07-08 13:30 公式P是指排列，从N个元素取R个进行排列。 公式C是指组合，从N个元素取R个，不进行排列。 N-元素的总个数 R参与选择的元素个数 ！-阶乘，如9！＝9*8*7*6*5*4*3*2*1 从N倒数r个，表达式应该为n*（n-1)*(n-2)..(n-r+1); 因为从n到（n-r+1)个数为n－（n-r+1)＝r 举例： Q1:有从1到9共计9个号码球，请问，可以组成多少个三位数？ A1: 123和213是两个不同的排列数。即对排列顺序有要求的，既属于“排列P”计算范畴。 上问题中，任何一个号码只能用一次，显然不会出现988,997之类的组合，我们可以这么看，百位数有9种可能，十位数则应该有9-1种可能，个位数则应该只有9-1-1种可能，最终共有9*8*7个三位数。计算公式＝P（3，9)＝9*8*7,(从9倒数3个的乘积） Q2: 有从1到9共计9个号码球，请问，如果三个一组，代表“三国联盟”，可以组合成多少个“三国联盟”？ A2: 213组合和312组合，代表同一个组合，只要有三个号码球在一起即可。即不要求顺序的，属于“组合C”计算范畴。 上问题中，将所有的包括排列数的个数去除掉属于重复的个数即为最终组合数C(3,9)=9*8*7/3*2*1 排列、组合的概念和公式典型例题分析 例1设有3名学生和4个课外小组．（1）每名学生都只参加一个课外小组；（2）每
名学生都只参加一个课外小组，而且每个小组至多有一名学生参加．各有多少种不同方法？ 解（1）由于每名学生都可以参加4个课外小组中的任何一个，而不限制每个课外小组的人数，因此共有种不同方法． （2）由于每名学生都只参加一个课外小组，而且每个小组至多有一名学生参加，因此共有种不同方法． 点评由于要让3名学生逐个选择课外小组，故两问都用乘法原理进行计算． 例2 排成一行，其中不排第一，不排第二，不排第三，不排第四的不同排法共有多少种？ 解依题意，符合要求的排法可分为第一个排、、中的某一个，共3类，每一类中不同排法可采用画“树图”的方式逐一排出： ∴ 符合题意的不同排法共有9种． 点评按照分“类”的思路，本题应用了加法原理．为把握不同排法的规律，“树图”是一种具有直观形象的有效做法，也是解决计数问题的一种数学模型． 例３判断下列问题是排列问题还是组合问题？并计算出结果． （1）高三年级学生会有11人：①每两人互通一封信，共通了多少封信？②每两人互握了一次手，共握了多少次手？ （2）高二年级数学课外小组共10人：①从中选一名正组长和一名副组长，共有多少种不同的选法？②从中选2名参加省数学竞赛，有多少种不同的选法？ （3）有2，3，5，7，11，13，17，19八个质数：①从中任取两个数求它们的商可以有多少种不同的商？②从中任取两个求它的积，可以得到多少个不同的积？ （4）有8盆花：①从中选出2盆分别给甲乙两人每人一盆，有多少种不同的选法？②从中选出2盆放在教室有多少种不同的选法？ 分析（1）①由于每人互通一封信，甲给乙的信与乙给甲的信是不同的两封信，所以与顺序有关是排列；②由于每两人互握一次手，甲与乙握手，乙与甲握手是同一次握手，与顺序无关，所以是组合问题．其他类似分析． （1）①是排列问题，共用了封信；②是组合问题，共需握手（次）． （2）①是排列问题，共有（种）不同的选法；②是组合问题，共有种不同的选法． （3）①是排列问题，共有种不同的商；②是组合问题，共有种不同的积． （4）①是排列问题，共有种不同的选法；②是组合问题，共有种不同的选法． 例４证明． 证明左式