离散数学习题与参考答案

2023年12月27日发(作者：鹿城区中考数学试卷)

习题二 谓词逻辑

一、 选择题

1、 下列哪个式子不是谓词演算的合式公式( )

A. (x)(A(x,2)∧B(y)) B. (x)(A(x)∧B(x,y))

C. ((x)∧(y))→(A(x,y)∧B(x,y)) D. (x)(A(x)→B(y))

2、设个体域是整数集，则下列命题的真值为真的是（ ）

A.xy (xy=1) B. xy(x+y=y)

C.xy(x+y=x) D. xy(y=2x)

3、设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于( )

A.(x)A(x)→B B. (x)A(x)→B C. A(x)→B D.(x)A(x)→(x)B

4、谓词公式(x)(P(x)∨(y)R(y))→Q(x)中的x( ).

A.只是约束变元

B.只是自由变元

C.既非约束变元又非自由变元

D.既是约束变元又是自由变元

5、谓词公式(x)P(x,y)∧(x)(Q(x,z)→(x)(y)R(x,y,z))中量词x的辖域是（ ）.

A．(x)Q(x,z)→(x)(y)R(x,y,z))

B．Q(x,z)→(y)R(x,y,z)

C．Q(x,z)→(x)(y)R(x,y,z)

D．Q(x,z)

6、在论域D={a,b}中与公式（A.C.

）A（x）等价的不含存在量词的公式是（ ）

B.

D.

7、设M（x）：x是人；F（x）：x要吃饭.用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表达式是（ ）.

A．C．A．P(x)∧S(x)

C．P(a)∧S(b)

A．mP(m)  yR(x,y)

C．xP(x)  xR(x,x)

B．D．

8、设个体域A={a,b}，公式xP(x)∧xS(x)在A中消去量词后应为（ ）.

B．P(a)∧P(b)∧(S(a)∨S(b))

D．P(a)∧P(b)∧S(a)∨S(b)

B．xP(x)  zR(x,z)

D．xP(x)  nR(x,n)

9、按照约束变元的改名规则，xP(x)  yR(x,y)不可改写成（ ）.

10、 xy(P(x,y)∧Q(y,z))∧ (x)p(x,y),下面的描述中错误的是（ ）

A.( x)的辖域是（  y）（P（x,y）∧Q(y,z)）

B．z是该谓词公式的约束变元

C.( x）的辖域是P（x,y）

D. x是该谓词公式的约束变元

二、填空题

1、设P(x)：x非常聪明；Q(x):x非常能干；a：小李；则命题“小李非常聪明和能干”的为谓词表达式为_______.

2、使公式(x)( y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的条件是______不含有y，______不含有x.

3、公式(x)A(x)→B(y)的前束范式为______.

4、公式x(P(x)→Q(x,y)∨zR(y, z))→S(x)中的自由变元为________________，约束变元为________________.

5、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为________________。

6、设个体域为整数集，则公式xy(x+y=0)的意义是________________。

三、计算题

1、给定个体域D={a,b},F(a,a)=T,F(a,b)=F,F(b,a)=F,F(b,b)=T,试求(x)( y)F(x,y)的真值.

2、给定个体域D={a,b},F(a,b)=T,F(a,b)=F,F(b,a)=F,F(b,b)=T,试求(y)(

x)F(x,y)的真值.

四、证明题

1.前提：结论:

2、将下列推理符号化并给出形式证明:

每一个大学生不是文科生就是理科生；有的大学生是优等生；小张不是文科生但他是优等生。因此，如果小张是大学生，他就是理科生。

设P(x)：x是大学生，Q(x)：x是文科生，S(x)：x是理科生，T(x)：x是优等生，c：小张，