计算机数学基础(上)第1编数理逻辑本章主要内容：2.1谓词逻辑基本概念二、命题函数1．简单命题函数表示一般谓词的式子如A(x)、P(x,y)，称为简单命题函数。2。复合命题函数有限个简单命题函数和联结词组成的表达式称为复合命题函数。3。命题函数本身不是命题，只有命题函数中的变元取得特定的值后才是命题。三、量词表达个体在个体域中取值情况的词称为量词。量词有全称量词和存在量词两种。1。全称量词表示个体的取值情况为“所有的”、“每一个”等。特性谓词后面用联结。例如，命题：所有的素数都是整数，符号化为：A(x):x是素数，H(x):x是整数，2。存在量词表示个体的取值情况为“存在某个”、“至少有一个”等。特性谓词后面用联结。例如，命题：有的素数是偶数，符号化为：A(x):x是素数，M(x):x是偶数，[2000年1月单项选择题1]设F(x):x是鸟，G(x):x会飞，命题“鸟都会飞”符号化为。A）B）C）D）再如课本P.42(B)1设A(x):x是人，B(x):x犯错误，命题“没有不犯错误的人”可符号化为。解：原命题的意思是：不存在不犯错误的人。符号化为：四、多个量词的使用包含有多个个体的命题，可能会对不同的个体使用不同的量词。对这样的命题符号化时要注意：1。量词的顺序不能改变，否则会改变命题的含义。2。特性谓词后面的联结符通常由括号最前面的量词决定。例如，[2000年7月填空题6]设N(x):x是自然数，H(x,y):y是x的后继数，命题“每个自然数都有后继数”可符号化为。解：[2001年1月单项选择题1]设X(x):x是学生，L(x):x是老师，H(u,t):u爱戴t，命题“所有学生都爱戴某些老师”符号化为。A）B）C）D）2.2谓词公式3。合式公式⑴原子公式是合式公式，⑵若A、B是合式公式，则也是合式公式，⑶若A是合式公式，x是A中出现的变元，则也是合式公式，⑷有限次地使用⑴⑵⑶生成的符号串是合式公式(谓词公式)。二、变元在合式公式化中，x：指导变元，A：量词的辖域。若A中有x，则x称为约束变元，若A中无x，则x称为自由变元。例如在中，x是约束变元，约束出现2次，y是自由变元，的辖域是，即约束变元后面括号内的式子是辖域。量词只对辖域中的指导变元有效。[2001年7月单项选择题2]表达式中的辖域是。A）B）C）D）三、换名规则和代入规则在同一个合式公式中，一个变元既可能约束出现，又可能自由出现。为避免混淆，可采用换名的办法使约束情况更加清楚。1。换名规则——对约束变元换名把公式中量词的指导变元及其辖域中的该变元换成公式中没有出现的新变元，其它部分不变。2。代入规则——对自由变元换名把公式中的自由变元，用公式中没有出现的新变元替代，并且处处替代。公式经换名和代入后，公式的意义不应当改变。2.3谓词的等值演算二、谓词公式的分类在给定的解释下，谓词公式的值称为谓词公式的真值。真值可以为1，也可以为0。如果个体域有限，求谓词公式的真值，可以消去量词，把函数值代入谓词，即可求出。如果一个谓词公式在任何解释下都为真，称为永真式，在任何解释下都为假，称为永假式或矛盾式，若至少有一个解释下为真称为可满足式。要判断一个谓词公式是永真式还是永假式，是较困难的。简单公式当然一眼就可看出，稍复杂一点就只能通过下面所讲的等值演算法化简。如公式等值于1，则为永真式；如公式等值于0，则为永假式。例1，已知解释I如下：解：[2000年7月计算题14]设f是一元运算，P是一元谓词，Q是二元谓词，给定解释I：求在解释I下解：[2000年7月单项选择题2]设个体域为整数，下列公式中真值为1的是A）B）C）D）解：各答案的意义是：任取一个x和任取一个z，都满足x+z=0任取一个x，存在一个t，满足x+t=0存在一个y，对于任取的一个z，满足y+z=0不存在这样的u，v，满足u+v=0正确答案为B三、谓词公式的等值演算谓词公式在等值演算下，可以有不同的表现形式其中特别要记住的有：例如，谓词公式的类型是。A)永真式B)永假式C)非永真的可满足式D)蕴含式解：[2000年1月化简解答题12]通过等值演算说明下列等值式成立：解：2.4前束范式利用等值变换消去联结词2.将联结词移到原子谓词公式之前3.对于公式中变元相同的部分，看能否用等值演算化简合并4.用换名规则或代入规则，使所有约束变元的符号均不相同，约束变元与自由变元也要用不同的符号5.将等移到公式的最左边。例1求谓词公式的前束范式。解：[2000年1月填空题7]谓词命题公式的