离散数学习题与参考答案 VIP专享VIP免费

习题二谓词逻辑一、选择题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)→BB.(x)A(x)→BC.A(x)→BD.(x)A(x)→(x)B4、谓词公式(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（x）等价的不含存在量词的公式是（）A.B.C.D.7、设M（x）：x是人；F（x）：x要吃饭.用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表达式是（）.A．B．C．D．8、设个体域A={a,b}，公式xP(x)∧xS(x)在A中消去量词后应为（）.A．P(x)∧S(x)B．P(a)∧P(b)∧(S(a)∨S(b))C．P(a)∧S(b)D．P(a)∧P(b)∧S(a)∨S(b)9、按照约束变元的改名规则，xP(x)yR(x,y)不可改写成（）.A．mP(m)yR(x,y)B．xP(x)zR(x,z)C．xP(x)xR(x,x)D．xP(x)nR(x,n)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：小张，