一阶逻辑典型习题

1、第二章 一阶逻辑1. 用谓词表达式写出下列命题:(1) 王文不是学生;(2) 2是素数且是偶数;(3) 若m是奇数,则2m不是奇数;(4) 河北省南接河南省;(5) 若2大于3.则2大于4.解 (1) P(x)：x是学生 a：王文于是（1）为：. (2 ) H(x)：x是素数 M（x）：x是偶数 a：2于是（2）为：H（a）(3) R(x) ：x是奇数于是（3）为：R（m）. (4) L(x,y) ：x 南接y c：河北省 d：河南省于是（4）为L（c,d）. (5) S(x,y)：x大于y a：2 b：3 c ：4于是（5）为：S（a,b）.说明 从语法上看，每个被视为命题的语句，是由主语和

2、谓语两部分组成的。其中，主语是语句中的主动者，称为个体。谓语是用来表明主语的性质或用来说明几个主语之间的关系，称为谓词。 例如前例（1）中的“王文”，（4）中的“河北省”、“河南省”都是个体；而其中的“”都是谓词。 在一阶逻辑中，表示具体的、特指的个体的词是个体常量；表示抽象的或泛指的或在一定范围内变化的词是个体变量。个体变量的取值范围是定义域。例如前例（2）中的“2”是个体常量；（3）中的“m ”是个体变量，它的定义域是整数集。表示个体性质的谓词，一般形如G（x）,是一元谓词或一元命题函数。表示n个个体之间关系的谓词，一般形如P（x1，n）,是n元谓词或n元命题函数。谓词函数不是命题，实际上

3、是一种不确定的命题形式，但是当其中的变量x被某个常量替换时，谓词函数便转化为命题。例如，“x是有理数”是一元谓词，记作G（x），其中G表示谓词“”，D：实数集，G（x）：x是有理数，是一元谓词（不是命题，没有真值）。3，G（3）：3是有理数，是命题，真值为1。由于命题逻辑是一阶逻辑的特例（命题可看作是无变量的谓词或0元谓词），因此，命题逻辑中的联结词在一阶逻辑中均可使用。注意，n元谓词中，与谓词想联系着的几个个体名称的次序是不能随意变动的，如前例中的（4）。 2.用谓词表达式写出下列命题：（1） 凡是有理数都可以写成分数；（2） 存在着会说话的机器人；（3） 并非每个实数都是有理数；（4） 如

4、果有限个数的乘积为零，那么至少有一个因子等于零；（5） 没有不犯错误的人。 解 （1）G（x）：x有理数 H（x）： x可以写成分数 于是（1）为： （2）F（x）：x会说话 Q（x）：x是机器人 于是（2）为：。（3）R（x）：x是实数 Q（x）：x是有理数于是 （3）为：R（x） (或为：). (4) N(x)：x是有限个数的乘积 Z(y)：y为0 P（x）：x的乘积为0 F（y）：y为乘积中的一个因子于是 （4）为：。 （5）M(x)：x为人 F（x）：x犯错误于是 （5）为： ( 或为：. 说明 引进了谓词，还要引进量词，这样才能建立起一阶逻辑。 全称量词和存在量词统称为量词。 全称量

5、词表示“对任意x”、“对每一个x”、“对于所以的x”等语句；存在量词表示“存在一个x”、“对于一些x”、“至少有一个x”等语句。 设G（x）是一元谓词，任取x0,则G（x0）是一个命题。于是， G（x）是命题：“对任意x,，都有G（x）。命题 G（x）的真值规定如下：G（x）G（x） x,G（x）都取1值；G（x）取0值 x0，使得G（x0）取0值；G（x）是命题：“存在一个x0，使得G（x0）成立”。命题G（x）的真值规定如下：G（x）G（x） x0，使得G（x0）取1；G（x）取0值 x,G（x）都取0值。在使用量词时，由于定义域的不同，命题符号化的形式可能不一样。 如 命题“凡是有理数都

6、可以写成分数”。 当定义域D：有理数集H（x）：x可以写成分数，则有 H（x）。 当定义域D：实数集G（x）：x是有理数 H（x）：x可以写成分数，则有 G（x）。 当定义域D：非空个体名称集（即一切事物的集合）时，则同。一般来说，谓词的定义域D可以是有限集，如1，2，3，4、a,b,c、狗，5，计算机等；也可以是无限集，如有理数集、实数集等。不过，这种约定的定义域并不常见。这时，我们认为个体x的定义域是一切事物。3设谓词的定义域都是a,b,c,试将下面的表达式中的量词消除，写成与之等价的命题公式。 P(x)； R（x）S(x)； R（x）S(x)； （P(x)； P(x) P(x)； F(x

7、) yG(y); .解 P(x)=P（a）P(b) P(c). R（x）S(x)=R(a) R(b) R(c)S(a) S(b) S(c). R（x）S(x)=( R(a) R(b) R(c) ( S(a) S(b) S(c). （P(x)=( P（a）Q(a) ( P（b）) Q(b) ) ( P（c） Q(c ). P(x) P(x)=( P（a） P（b） P（c）) ( P（a）P(b) P(c). F(x) yG(y)=(F(a) F(b) F(c) (G(a) G(b) G(c). =(H(a,a) H(a,b) H(a,c) (H(b,a) H(b,b) H(b,c) (H(c,

8、a) (H(c,b) H（c,c）)4. 指出下列命题的真值：（P(x)Q(x)）其中，P(x)：x3 H(x):x=4 定义域：D=2； （P(x)，其中，P(x)：x=1 Q(x):x=2 定义域：D=1,2; (PQ(x) R(e) 其中，P：32 Q(x):x3 R（x）:x5 e:5定义域：D=-2,3,6. 解 （P(x)Q(x)）=（P(2)Q(2)）=（00）=1。 （P(x)= （P(1) Q(1)）（P(2) Q(2)）=（1 0）（0 1）=11 (PQ(x) R(e)= (PQ(-2) (PQ(3) (PQ(6) R(5)。因为在上式中，P真，Q(-2)真，Q(3)真，

9、Q(6)假，R(5)假，所以，原式= (11) (11) (10) 0=00。说明 当定义域为有限集时，如D=a1,n,由量词的定义可以看出，对任意的谓词G（x）,都有： G(x)= G(a1) G(an); G(x)= G(a1) G(an).这实际上是将一阶逻辑中的命题公式转化为等价的命题落雷中的命题公式。若在表达式中有多个量词，则可以按其层次，逐层将量词消除。例如D=a,b,=(P(x,，a) P(x,，b)= (P(a,a) ) P(a,b) (P(b,a) P(b,b)5 将下列表达式中的变量适当改名，是的约束变量不是自由的，自由变量不是约束的 F（x）G(x,y); （P(x) R

10、(x,y)）Q(x,y); (P(x,z) Q(y) ; (P(x) (R(x) Q(x) R(x) ; . 解 (1) 的改名为：；的改名为：；的改名为： ；的改名为： ；的改名为：。说明 在符号G（x）或G(x)中的G(x)是量词或的作用范围，称谓辖域。当量词后面有括号时，则括号内的公式为此量词的辖域，此时在辖域内出现的个体变量x是约束的，或者说x的出现是约束的；当辖域内不含有时，在辖域内出现的个体变量是自由的，或者说y是自由的（可视为参数）。如（P（x,y）x的辖域是P（x,y）. 从左向右算起，变量x的第一、第二次出现是约束的，第三次的出现是自由的；变量y的第一次出现是自由的，第二次出

11、现是约束的；变量z在全式中的出现都是自由的。为避免出现这样一个变量在同一个公式中具有的双重身份，在一阶逻辑中，合理的引出了约束变量的改名规则。从而可以做到，在一阶逻辑中的表达式里，每个变量都可以只以一种面目出现，即约束都不是自由的；由变量也都不是约束的。6设I是如下一个解释：D：实数集Ra f(x,y) F(x,y)2 x-y x试确定下列公式在I下的真值 F（a,x）,a）; (3) (4) 解 （1） 因为在I下，对任意的x及a, 有f(a,x)=a-x,F(f(a,x):a-xa,将2代入，得2-x2,即-x0,显然为假，所以F（a,x）,a）=（-x0）,真值为0。（2） 因为在I下，

12、对任意的x,y,F(f(x,y),x):x-yx,为假，所以，真值为0。(3) 因为在I下，F（x,y）:xy,f(x,z):x-z,f(y,z):y-z,F(f(x,z),f(y,z):x-zy-z,即 xy.显然，对任意的x,y,z,(x-y)为真。所以，真值为1。(4) 因为在I下， f(x,y)=x-y,f(f(x,y),y)=(x-y)-y=x-2y,F(x,f(f(x,y),y):xx-2y.对任意的x，令y=-1,均有x x-2y。所以真值为1。7 设I是如下一个解释： D：自然数集N a f(x,y) g(x,y) F(x,y) 3 x+y xy x=y试确定下列公式在I下的真

13、值。（1）；（2） ； （3） ；（4） F（f(x,y),g(x,y)）.解 （1）因为在I下，对任意的x, 有g(x,a)=xa,F(g(x,a),x): xa=x,将a代入，x3=x,显然为假。所以=（x3=x）真值为0。（2）因为在I下，对任意的x，y,及a,f(x,a)=x+a,f(y,a)=y+a,F(f(x,a),y):x+a=y,F(f(y,a),x):y+a=x,将a=3代入，F（f(x,a),y为假。所以，=真值为0。(3) 公式可化为：，真值为1。(4) 公式可转化为：，真值为0。8 设I是如下一个解释：D：3，2a b f(3) f(2) P(3,3) P(3,2) p

14、(2,3) P(2,2)3 2 2 3 1 1 0 0试求出下列公式在I下的真值。（1） p( a,f(a)p(b,f(b);（2） ;（3） .解 （1） p( a,f(a)p(b,f(b) = p( 3，f(3)p(2，f(2)= p(3,2)p(2,3)= 10（2） =P(3,x)P(2,x)=(P(3,3) P(2,3) )P(3,2) P(2,2)=(10) (10)=11=1.(3) =(P(x,3)P(f(x),f(3) (P(x,2) P(f(x),f(2)= P(3,3) P(f(3),f(3)(P(3,2)P(f(3),f(2) P(2,3) P(f(2),f(3) )(

15、P(2,2)P(f(2),f(2)= P(3,3) P(2,2)(P(3,2)P(2,3) P(2,3) P(3,2) )(P(2,2)P(3,3)=(10)(10) (01 )(01)=0011=0. 9 设G=（1） 若解释I的非空区域D包含仅仅一个元素，G在I下取1值；（2） 设D=a,b,试找出一个D上的解释I，使G在I取0值。 解 （1） 因为在解释I下，D=a,所以P（x）=P(a), P(x)=P(a),故G= P(a) P(a),取1值。（2）设D=a,b,于是在解释I下，P（x）=P(a) P(b), P(x)= P(a) P(b).故 G=（P(a) P(b)）（P(a)

16、P(b)）。于是，当解释I是如下一个解释：D=a,bP(a) p(b)1 0 时，G=取0值。 说明 由递规定义给出的公式是抽象的符号串，没有什么意义。但是，当我们对这个符号串中的符号做出具体的解释，即给出一个集合D，将公式中的常量符号赋以D中某个元素，变量符号的变化范围指定为D，函数符号赋以D上的一个具体函数，为此符号赋以D上一个具体谓词时，公式就有了确定的真值。我们已经知道，命题逻辑的公式恒真性是可解的，然而一阶逻辑的公式恒真性却是不可解的。这是因为，在一阶逻辑中，为判定公式是否恒真，需要考虑公式的所有解释，但是，这是人类所无法实现的，也就是说采用判定命题逻辑的公式恒真性的真值表，对一阶逻

17、辑的公式是不存在的。当然，对某些特殊的公式还是可以判定的。10 设G1=（P（x）Q(x)）,G2=Q(a).证明：P（a）是G1和G2的逻辑结果。分析 欲证P（a）是G1和G2的逻辑结果，当且仅当（G1 G2）P（a）。证 设I是G1，G2的任一个解释，并且I满足G1 G2，即I满足（P（x）Q(x)）Q(a)，以下证明I满足P（a）。否则，令P（a）在I下为假，即P（a）为真，于是，因为Q(a)为真，所以，I下（P（a）Q(a)）为假。故（P（x）Q(x)）在I下为假，矛盾。故P（a）在I下亦为真，由蕴涵定义知（G1 G2）P（a），即P（a）是G1和G2的逻辑结果。 证毕。11 证明一阶

18、逻辑蕴涵公式：（1） （A（x）B(x)） A（x） B(x); (2) ( A（x）B(x) A（x） B(x); (3) P(x) Q(x) ( P(x) Q(x); (4) A（x） B(x) ( A（x）B(x). 证 （1）设I是 A（x），B(x)的任一解释，并且I满足（A（x）B(x)）。 于是，在解释I下所指定的区域D中，存在x0D,使A（x0）B(x0)取1值，从而A（x0）取1值，B(x0)取1值。因此在解释I下， B(x) 取1值。故解释I使 A（x） B(x) 取1值。故（A（x）B(x)） A（x） B(x)。 (2)设I是 A（x），B(x)的任一解释，并且I满足(

19、 A（x）B(x) A（x）。 于是I满足( A（x）B(x)，并同时满足 A（x），即对所有xD, A（x）B(x) 取1值, 同时A（x）取1值,，即I满足 B(x)。因为I的任意性，所以，( A（x）B(x) A（x） B(x)，亦即( A（x）B(x) A（x） B(x)。 （3）设I是 P（x）,Q(x)的任一解释，并且I满足P(x) Q(x)。于是I满足P(x)，并同时满足Q(x)，亦即在解释I下所指定的区域D中，存在x0D,使P（x0）取1值,并同时使Q（x0）取1值。 因此，在I下，P（x0） Q（x0）取1值,亦即在I下，使( P(x) Q(x) 取1值。故( A（x）B(x

20、) A（x） B(x)。 （4）设I是 P（x）,Q(x)的任一解释，并且I满足 A（x） B(x)。而在I下， A（x） B(x)= A（x） B(x)= （ A（x） B(x)。 由基本蕴涵式，有（ A（x） B(x) （ A（x） B(x)），在I下，（ A（x） B(x)= ( A（x）B(x)。于是，由蕴涵关系的传递性，对任意解释I，有 A（x） B(x) ( A（x）B(x)。12 证明（1） （A（x） B(x)）=(A（x） B(x)；（2） A（x） B=(A（x） B)；（3） （P(x)Q(y)）= P(x) Q(y).证 （1） （A（x） B(x)）=（ A（x） B

21、(x)）=（ A（x）B(x)= (A（x）B(x)= (A（x） B(x)； （2） A（x） B=A（x） B= A（x） B=（ A（x） B）=(A（x） B)； （3） （P(x)Q(y)）=（ P(x) Q(y)）= P(x) Q(y)= P(x) Q(y)= P(x) Q(y)。 说明 在一阶逻辑中，要证明来年感个公式的等价或蕴涵，是一件十分复杂的事情。但是，对于比较简单公式等价、蕴涵的证明，采用教材中关于三段论的证明方法，即用解释的方法进行证明，和是应该掌握的。当然，也可以引用命题逻辑和一阶逻辑中的有关基本等价式和蕴涵式。 另外，也还要注意准确划定量词的辖域以及逻辑联结词的等价

22、转换。13 将下面命题符号化：（1） “尽管有人聪明，但未必一切人都聪明”；（2） “每个人都有一些缺点”；（3） “如果每一个在银行存钱的人都能得到利息，则如果没有利息，就没有人在银行存钱”；（4） 设f1(x), fn(x),函数序列,f(x)是一个函数, “对任何x0,都存在N,使当n,有| f( x0) fn(x)|,则称函数序列 fn(x),在(a,b)区间内敛于f(x)”. 解 (1) 令F (x): x 聪明 M(x):x是人 于是,命题可表示为: (M(x) F (x) )( M(x) F (x).(2) 令R(x,y): x都有y P(x):x是人 Q(y):y是缺点于是,命题可表示为: ( P(x) Q(y) R(x,y)(3) 令S(x,y):x存在y M(y):y是钱 H(x):x是人 R(x,z): x得到zP(z):z是利息 于是,命题可表示为:( H(x) ( S(x,y) M(y) ( R(x,z) P(z