离散数学 第4章 一阶逻辑基本概念.ppt

* 不能。翻译一下就可以知道这样符号化是不对的。 * * 顺便提一句，由于谓词逻辑中的恒真（恒假）公式，要有所有解释I都可满足（弄假）该公式。而解释I依赖于一个非空集合D，由于集合D可以是无穷集合，而集合D的“数目”也可能是无穷多个，因此，所谓公式的“所有”解释，实际上是无法考虑的，这就使得谓词逻辑中的公式的恒真、恒假性的判断变得异常困难。1936年Church（丘奇）和Turning（图灵）分别独立地证明了对于谓词逻辑，判定问题是不可解的。 幸好，谓词逻辑是半可判定的，亦即，如果谓词逻辑中的公式是恒真的，则有算法在有限步之内检验出这个公式的恒真性。如果该公式不是恒真的（当然也不是恒假的），即是可满足的，则无法在有限步内判定这个事实。从Church和Turning的结果看，这也许是我们所能期望的最好结果了。 * * （4）令个体域为某个元素个数大于等于2的有限整数集，其中a为最小的数。P(x,y)：x大于等于y，Q(x,y)：x小于等于y。 ?x?yP(x,y)?Q(a,y)解释为：存在一个x，对于所有的y，有x大于等于y，并且a小于等于y。命题为真，只要取x为个体域中最大数即可。 ?x?y(P(x,y)?Q(x,y))解释为：存在一个x，对于所有的y，有x大于等于y，并且x小于等于y。命题为假。 * （2）设个体域为{a,b}，令A(a)=1,B(a)=0, A(b)=0,B(b)=1。 例题4.7 (2)?x?y(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y))) 含有两个2元函数变项，两个1元谓词变项，两个2元谓词变项。 指定个体域为全总个体域，F(x)为x是实数， G(x,y)为x≠y，H(x,y)为xy， f(x,y)=x2+y2，g(x,y)=2xy， 则表达的命题为“对于任意的x，y，若x与y都是实数，且x≠y，则x2+y22xy”，这是真命题。 如果H(x,y)改为xy， 则所得命题为假命题。 一阶公式的解释 定义4.7 一阶公式的解释I由下面4部分组成: (a)非空个体域DI。 (b)DI中一些特定元素的集合 。 (c)DI上特定函数集合{ |i, n≥1}。 (d)DI上特定谓词的集合{ |i, n≥1}。 为第i个n元谓词，如i=2，n=3时， 表示第2个3元谓词，它可能以 (x,y,z)的形式出现在解释中，公式A若出现F2(x,y,z)就解释成 (x,y,z)。 为第i个n元函数。例如，i=1，n=2时， 表示第一个二元函数，它出现在解释中，可能是 (x,y)=x2+y2， (x,y)=2xy等，一旦公式中出现f1(x,y)就解释成 (x,y)，出现g1(x,y)就解释成 (x,y)=2xy。 对解释I的几点说明 被解释的公式不一定全部包含解释中的四部分。 在解释的公式A中的个体变项均取值于DI。 若A中含有个体常项，就解释成 。 在解释的定义中引进了几个元语言符号，如 例4.8 给定解释I如下: (a) 个体域D=N(N为自然数集合，即 N={0,1,2,…}) (b) =0 (c) (x,y)=x+y, (x,y)=x?y。 (d) (x,y)为x=y。 在I下，下列哪些公式为真?哪些为假?哪些的真值还不能确定? 例题4.8 例题4.8 (1) F(f(x,y),g(x,y)) (2) F(f(x,a),y)→F(g(x,y),z) (3) ┐F(g(x,y),g(y,z)) (4) ?x F(g(x,y),z) (5) ?x F(g(x,a),x)→F(x,y) (6) ?x F(g(x,a),x) (7) ?x?y(F(f(x,a),y)→F(f(y,a),x)) (8) ?x?y?z F(f(x,y),z) ???? (9) ?x F(f(x,x),g(x,x)) 例题4.8 (1) F(f(x,y),g(x,y)) 公式被解释成“x+y=x·y”，这不是命题。???? (2) F(f(x,a),y)→F(g(x,y),z) 公式被解释成“(x+0=y)→(x·y=z)”，这也不是命题。???? (3) ┐F(g(x,y),g(y,z)) 公式被解释成“x·y≠y·z”，同样不是命题。???? (4) ?x F(g(x,y),z) 公式被解释成“?x(x·y=z)”，不是命题。 例题4.8 (5) ?x F(g(x,a),x)→F(x,y) 公式被解释成“?x(x·0=x)→(x=y)”，由于前件为假，所以被 解释的公式为真。 ? (6) ?x F(g(x,a),x) 公式被