离散数学左孝陵版第二章答案

《离散数学左孝陵版第二章答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chartertwowelcome第二章谓词逻辑§1谓词的概念与表示法§2命题函数与量词§3谓词公式与翻译§4变元的约束§5谓词演算的等价式与蕴含式§6前束范式§7谓词演算的推理理论§1谓词的概念与表示法在研究命题逻辑中，原子命题是命题演算中最基本的单位，不再对原子命题进行分解，这样会产生二大缺点：（1）不能研究命题的结构，成分和内部逻辑的特征；（2）也不可能表达二个原子命题所具有的共同特征，甚至在命题逻辑中无法处理一些简单又常见的推理过程。例：苏格拉底论证是正确的，但不能用命题逻辑的推理规则推导出来。“所

2、有的人总是要死的。A“苏格拉底是人。B“所以苏格拉底是要死的。”C§1谓词的概念与表示法1.谓词：《定义》：用以刻划客体的性质或关系的即是谓词。我们可把陈述句分解为二部分：主语（名词，代词）和谓语（动词）。例：张华是学生，李明是学生。则可把它表示成：H:表示“是学生”，j:表示“张华”，m:表示“李明”，则可用下列符号表示上述二个命题：H(j)，H(m)。H作为“谓词”（或者谓词字母）用大写英文字母表示，j,m为主语，称为“客体”或称“个体”。§1谓词的概念与表示法（1）谓词填式：谓词字母后填以客体所得的式子。

3、例：H(a,b)（2）若谓词字母联系着一个客体，则称作一元谓词；若谓词字母联系着二个客体，则称作二元谓词；若谓词字母联系着n个客体，则称作n元谓词。（3）客体的次序必须是有规定的。例：河南省北接河北省。nLb写成二元谓词为：L(n,b)，但不能写成L(b,n)。§2命题函数与量词1.命题函数客体在谓词表达式中可以是任意的名词。例：C—“总是要死的。”j：张三；t：老虎；e：桌子。则C(j),C(t),C(e)均表达了命题。在上面的例子中，C：表示“总是要死的”；x：表示变元（客体变元），则C(x)表示“x总是

4、要死的”，则称C(x)为命题函数。《定义》由一个谓词字母和一个非空的客体变元的集合所组成的表达式，称为简单命题函数。§2命题函数与量词讨论定义：（a）当简单命题函数仅有一个客体变元时，称为一元简单命题函数；（b）若用任何客体去取代客体变元之后，则命题函数就变为命题；（c）命题函数中客体变元的取值范围称为个体域（论述域）。例：P(x)表示x是质数。这是一个命题函数。其值取决于个体域。可以将命题函数命题，有两种方法：§2命题函数与量词a)将x取定一个值。如：P(4)，P(5)b)将谓词量化。如：xP(x)，

5、xP(x)个体域的给定形式有二种：①具体给定。如：｛j,e,t｝②全总个体域任意域：所有的个体从该域中取得。§2命题函数与量词2.量词（1）全称量词“”为全称量词符号，读作“对于所有的”，“对任一个”，“对一切”。例：“这里所有的都是苹果”可写成：xA(x)或(x)A(x)几种形式的读法：·xP(x)：“对所有的x，x是…”；·x¬P(x)：“对所有x，x不是…”；·¬xP(x)：“并不是对所有的x，x是…”；·¬x¬P(x)：“并不是所有的x，x不是…”。§2命题函数与量词例：将“对于所有

6、的x和任何的y，如果x高于y，那么y不高于x”写成命题表达形式。解：xy(G(x,y)¬G(y,x))G(x,y)：x高于y（2）存在量词“”为存在量词符号，读作“存在一个”，“对于一些”，“对于某些”，“至少存在一个”，“这里存在着这样的”等等。“”表达式的读法：·xA(x)：存在一个x,使x是…；·x¬A(x)：存在一个x,使x不是…；·¬xA(x)：不存在一个x,使x是…；·¬x¬A(x)：不存在一个x,使x不是…。§2命题函数与量词例：（a）存在一个人；（b）某个人很聪明；（c）某些

7、实数是有理数将（a）,（b）,（c）写成命题。解：规定：M(x)：x是人；C(x)：x是很聪明；R1(x)：x是实数(特性谓词)R2(x)：x是有理数。则（a）xM(x)；（b）x(M(x)C(x))；（c）x(R1(x)R2(x))。（3）量化命题的真值：决定于给定的个体域给定个体域：{a1…an}以{a1…an}中的每一个代入xP(x)P(a1)…P(an)xQ(x)Q(a1)…Q(an)§3谓词公式与翻译1.谓词公式原子谓词公式：不出现命题联结词和量词的谓词命名式称为原子谓词公式

8、，并用P(x1…xn)来表示。（P称为n元谓词，x1…xn称为客体变元），当n=0时称为零元谓词公式。《定义》（谓词公式的归纳法定义）⑴原子谓词公式是谓词公式；⑵若A是谓词公式，则¬A也是谓词公式；⑶若A,B都是谓词公式，则(AB),(AB),(AB),(AB)都是谓词公式；⑷若A是谓词公式，x是任何变元，则xA,xA也都是谓词公式；§3谓词公式与翻译⑸只有按