习题(第二章一阶逻辑)080923演示教学

§2.1
一阶逻辑的基本概念
原因：命题逻辑不考虑命题之间的内在联系
和数量关系。
要反映这种内在联系，就要对命题逻 辑进行分析,分析出其中的个体词、谓词和 量词，再研究它们之间的逻辑关系，总结出 正确的推理形式和规则，这就是一阶(谓词) 逻辑的研究内容。 办法：将命题再次细分。
§2.1 一阶逻辑的基本概念
不带任何个体变项的谓词称为0元谓词
§2.1 一阶逻辑的基本概念
特别提醒：n元谓词不是命题，只有其中的个 体变元用特定个体或个体常元替代时，才能成 为一个命题。但个体变元在哪些论域取特定的 值，对命题的真值极有影响。
例如：令S(x)：x是大学生。若x的论域为中医 药大学信息技术学院的全体同学，则S(x)是真 的；若x的论域是某中学的全体学生，则S(x)是 假的；若x的论域是某剧场中的观众，且观众 中有大学生也有非大学生的其它观众，则S(x) 是真值是不确定的。
例211指出下列公式的辖域和变元约束的情况换名规则设a是一公式将a中某个辖域中约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现的某个个体变项符号公式中其它部分不变设所得公式为a则代替规则设a是一公式将a中某个自由出现的个体变项所有出现用a中未曾出现的个体变项符号代替a中其它部分不变设所得公式为a注意
§2.1 一阶逻辑的基本概念
量词 用来表示个体常项或变项之间数量关系的词。 量词分为两种： 全称量词：“一切”、“所有”、“凡”、 “每一个”、“任意”等意，符号记作。如： x 表示个体域内所有的x。x称为全称量词， 称x为指导变元。 存在量词：“有一个”、“有的”、“存在”、 “至少有一个”等，符号记作。如:y表示 个体域内有的y。x称为存在量词，x称为指
§2.1 一阶逻辑的基本概念

1． 个体 （个体词） ——所研究对象中可以独立存在的具体或抽
2. 谓词——表示个体词性质或相互之间关系的词 （1） 谓词常项：F: …是人，F(a)：a 是人 （2） 谓词变项：F: …具有性质 F，F(x)：x 具有性质 F （3） n（n1）元谓词：含有 n 个个体词的谓词，记作 P(x1, 是以个体变项的个体域为定义域，以{0，1}为值域的 n 元函数 ① n=1，一元谓词——表示性质 ② n2，多元谓词——表示事物之间的关系 L(x,y)：x 与 y 有关系 L，L(x,y)：xy（谓词常项） ，… （4）0 元谓词——不含个体变项的谓词——命题常项或变项； ab:a 取为 2,b 取为 3 命题看成谓词的特殊情况，命 A0 是含命题变项 p1, p2, …,pn 的命题公式， 1, A A2, …,An 是 n 个谓词公式，用 Ai (1in) 处处代替 A0 中的 pi，所得公式 A 称为 A0 的代换实例. 例如， F(x)G(x), xF(x)yG(y)等都是 pq 的代 换实例，而x(F(x)G(x))等不是 pq 的代换实例. 定理 2 重言式的代换实例都是永真式，矛盾式的代换实例 都是矛盾式.
三、一阶逻辑中的解释 定义 7 一阶逻辑公式 A 的解释 I 由下面 4 部分组成： (a) 非空个体域 D (b) D 中一些特定元素的集合 (c) D 上一些特定函数集合 (d) D 上特定谓词的集合
下面对解释Ⅰ做几点说明： D为解释Ⅰ的个体域，即：Ⅰ为D上的解释 A中出现的个体常项指定D中的一个元素，A中的函数和 谓词，指定D上的函数和谓词； 有些公式在解释Ⅰ下变成一个命题，该命题的真值称为A 在解释Ⅰ下的真值； 被解释的公式不一定全部包含解释中的4部分.
3．闭式的性质. 定理 1 闭式在任何解释下都是命题 4．公式的类型 定义 8 （1）永真式（逻辑有效式） ：任何解释下为真 （2）矛盾式（永假式） ：任何解释下为假 （3）可满足式：至少在一个解释下为真 几点说明： 永真式为可满足式，但反之不真 判断公式是否为永真式（矛盾式）不是易事 某些代换实例可判公式类型

公式
指
导
变
项
xA , xA
相 应 量 词 的 域 辖
例2.6 指出下列各合式公式中的指 导变项、量词的辖域、个体变项的自 由出现和约束出现
1、 x(F( x ) yH ( x, y )); 2、 xF ( x ) G ( x, y ); 3、 xy( R( x, y ) L( y , z )) xH ( x, y ).



2.2 一阶逻辑合式公 式及解释
定义2.1 字母表



1、个体常项：a,b,c,…,ai,bi,ci,…,i≥1 2、个体变项：x,y,z,…,xi,yi,zi,…, i≥1 3、函数符号：f,g,h,…,fi,gi,hi,…, i≥1 4、谓词符号：F,G,H,…Fi,Gi,Hi,…, i≥1 5、量词符号：, 6、联结词符：﹁, ∧, ∨, →, 7、括号和逗号: ( , ) , ，
1)x(F( x ) G ( x, a ))
例2.7 给定解释I如下 : 1)Di=｛2,3｝; 2) Di中特定元素a=2 3)函数f(x)为f(2)=3,f(3)=2; 4)谓词F(x)为F(2)=0,F(3)=1 G(x,y)为G(i,j)=1, i,j=2,3; L(x,y)为L(2,2)=L(3,3)=1; L(2,3)=L(3,2)=0.求下列各式的值:

表示具体的或特 个体常项 定的个体的词 a,b,c, · · ·
个体变项
表示抽象的或泛 指的个体的词 x,y,z, · · ·
个体变项的 取值范围 全总个 体域
个体域 （或论域）
宇宙间一切 事物组成的 个体域
表示具体性质或 谓词常项 关系的谓词 F,G,H,· · · 谓词变项

3是实数。"正确。 解 设N（x）：x是自然数，R（x）：x是实数，则推理形式化为：
x（N（x）→R（x）），N（3） R（3）
下面进行证明。 （1） x（N（x）→R（x）） 前提引入
（2）N（3）→R（3）
（3）N（3） （4）R（3）
（1）UI
前提引入 （2）（3）假言推理
第2章 一阶逻辑
论并非蕴涵式（x的辖域是其后整个公式），附加
证明法也不适用，此时我们应考虑归缪法。
第2章 一阶逻辑
证明
（1） x（y（F（y）∧H（x，y）） →z（G（z）∧H（x，z））） 否定结论引入 （2）x （y（F（y）∧H（x，y））
→z（G（z）∧H（x，z）））
第2章 一阶逻辑
EG规则(existential generalization)
存在量词引入规则（简称EG规则）
A(c) xA(x)
成立条件： (1)c是个体常项。 (2)x不出现在A(c)中。
A(c) xA( x )
第2章 一阶逻辑
【例2.4.1】 证明推理"所有的自然数均是实数，3是自然数，因此，
(2)EI
（1）UI
（8）H（c）
（9）P（c）∧H（c）
（6）化简
（7）（8）合取引入
（10）x（P（x）∧H（x）） （9）EG
第2章 一阶逻辑
【例2.4.4】 设前提为
下面推理是否正确？

xyF（x，y）， 前提引入
（1）UI
（1） xyF（x，y）
（2）yF（t，y）
（3）F（t，c）
（4） xF（x，c） （5）y xF（x，y）
（2）EI